znstz的博客

博客

PNR #7 总结

2024-10-20 23:34:31 By znstz

PR #12 验题人题解

2024-02-25 15:02:01 By znstz

Public Round 12

电塔

令操作结束后序列是 y1,y2,,yn,容易发现,把 x,y 分别排序,将 x1 变为 y1,将 x2 变为 y2 ……,是最优的。

于是问题变成了,把 xi 升序排列后,要求对于所有 i(2in),xixi1d,求最少操作次数。

考虑其差分序列,直接套用 UOJ-雪灾与外卖 的模拟费用流算法,能得 70 分。

再次转化,将 xi 减去 (i1)d,问题就变成了让 xi 不降,求最少操作次数,这个能直接做到 O(nlogn)

并查集

先拆一下贡献,对于每条边,将它的经过次数加到答案里,最后答案加上 2(n1),就是真正的答案。

考虑把 u 挂在 v 上的过程,令 S 表示 u 所在连通块的点集,则 find(u)find(v) 这条边的经过次数为:2(|S|1)1+xSdeg(x)。令这一坨式子为一个连通块的权值,显然,我们应该把 u,v 所在连通块中,权值较大的挂在权值较小的上面。

继续观察,假设 u 所在连通块的权值比 v 大,那么把 v 里面的点一个一个挂到 u 上一定是更优的。

枚举起点,将树定根在起点,问题变成了,每个点有一个权值,将 0,1,,n1 放到每个点上,要求父亲的数大于儿子,最大化每个点上权值乘上数的和。这是经典的问题,每次取权值最大的,它上面的数一定是父亲的 1,将它和父亲合并就行,新权值设为连通块内的平均数。

复杂度 O(n2logn)

划分序列

考虑最朴素的 dp:dp(i) 表示前 i 个数的最大价值,转移 dp(i)+mex(i+1,j)sum(i+1,j)dp(j)(jik)

1n 依次计算 dp 值,令当前算到的位置为 i,先维护每个位置到 i 这一段的 mex,直接开珂朵莉树维护其连续段,能分析出总共只有 O(n) 次连续段的变化。

转移考虑根号重构,令 B=n,若 imod,则重构 [i-k+B,i] 这一段的贡献,转移的时候对于散块暴力算,复杂度 O(n \sqrt {n}),实现起来很多细节。

据说存在 polylog 做法,敬请期待官方题解(。

PNR #6 验题人题解

2023-10-15 12:55:25 By znstz

抉择

考虑 dp,dp(i) 表示,考虑前 i 个数,a_i 选了,的最大权值,转移枚举 j(j \gt i)

优化转移,如果 i,j 之间有一个 k(i \lt k \lt j),且 a_i \&a_k 的最高位和 a_i \& a_j 相同,那么选上 a_k 一定更优(2 \cdot 2^{a_i \& a_j 的最高位} \gt a_i \& a_j,枚举 a_i \& a_j 的最高位,找到前面第一个这一位是 1 的数转移就行,复杂度 O(n \log A)

赛时有人挂,原因是没考虑 a_i \& a_j=0 的情况,hack:a=\{4,4,2,2\}

fun fact: pb 认为这个题是一眼题。

重生

最直观的一个结论:除了最后一条命,都只做”深入思考“操作。

考虑二分,二分复活次数 d,计算经过 d 条命的“深入思考”后,最少在下一条命中需要多少时间能完成任务。最后一条命,每个任务需要的时间是:

  • t=0,需要时间为 0
  • t \le d,需要时间为 1
  • t \gt d,需要时间为 t-d+1

考虑这样一个贪心策略,每次选择能减少时间最多的进行“深入思考”,原因是代价关于 t 是凸的。

假设任务 i 被想了 t 次,则需要满足:t \le d, \sum t \le c \cdot d

但是 c,d 可能会特别大,观察到对于 t \ge 2d 的任务,进行一次“深入思考”会产生 d 的时间减少。将所有任务按 d 从大到小排序,尽可能操作直到 t \lt 2d 或操作次数用完。之后每个任务至多被操作两次,把这两次的时间减少量搞出来再贪一遍就行。

复杂度 O(n \log n \log A)

fun fact: 我认为这个题是一眼题。

遍历

考虑点双缩树,x 走到 z 必须经过 y,当且仅当 y 是割点,且 xzy 的不同子树中。

y 是否在 x 子树两种情况讨论,每种情况都分别令 O(1) 个 dfs 序区间内的点不合法。

复杂度 O(n \log n),有一种情况需要求 xdep_y-dep_x-1 级祖先,

fun fact:这个题成为了签到题,前三题通过 18,12,22 位选手。

排序

讲下我的做法,实测 118 次操作,能过原题。

考虑只有 0,1,将连续段放在一起考虑,序列形如 10101010 \cdots,考虑一次操作让 0 连续段个数减半,分段类似 1|0|10|1|0|10\cdots,最后可能会搞出 101 的形式,再来一次操作 1|01,就能排好序了。

考虑分治,将 \le n/2 的看成 0\gt n/2 的看成 1,进行只有 0,1 的算法,然后往两边递归,同一层可以放在一起处理,如果最后顺序不对再整体 reverse 一下就行。操作次数大概是 0.5 \cdot\log^2 n

Public Round #11 验题人题解

2023-07-19 20:55:24 By znstz

作业

先考虑循环节,等概率选取一个长度为 n 循环节为 d 的字符串,考察最小表示在 f 处的概率,若 f \le d,则概率为 d^{-1},否则为 0

先计算循环节为 d 的字符串个数 cnt(d),这个可以用莫反求,cnt(d)=\sum_{c|d} \mu(c)26^{d/c}

然后问题就变成了,每次询问两个数 m,n,求等概率选择一个长度为 n 的字符串和一个长度为 m 的字符串,最小表示位置相同的概率。枚举位置 f,概率是 (\sum_{d|n, f \le d}cnt(d)d^{-1}26^{-n}) \cdot (\sum_{d|m, f \le d}cnt(d)d^{-1}26^{-m})

观察到两部分都可以被分为至多 \sqrt{A} 段相等的连续段,A 是值域,复杂度 O(n \sqrt{A})

交换

部分分在暗示做法。

最关键的一个性质:考虑第 i 个数 h_i 在最后被换到了 p_i 的位置,那么最终状态下,第 p_i 个数是 (-1)^{i-p_i}h_i,且操作次数是 p_i 的逆序对数。

先考虑 |h_i| \neq |h_j| 的部分分,按绝对值从大往小枚举,当前枚举到的数,要么丢到末尾且符号为正,要么丢到开头且符号为负。令 dp(i,0/1) 表示,已经枚举了前 i 个数,开头的数模 2 是什么。转移只需要用 BIT 优化一下计算逆序对。

再考虑 |h_i| \le 1,由于符号翻转很烦,需要一点点的转化去掉它。令初始状态为 a_1,\cdots,a_n,目标状态为 b_1,\cdots,b_n,对于所有奇数(偶数也行)的 i,将 a_i,b_i 取相反数,操作就变成了“交换相邻数,没有符号翻转”(理由:转化前后对于符号的要求均为,若 |i-p_i| 为偶数,需要 a_i,b_{p_i} 符号相同;若 |i-p_i| 为奇数,需要 a_i,b_{p_i} 符号相反)。

在转化后的问题上,需要对于一个 -1,0,1 的序列求出,变成某个序列(中间一段为 0,左右两段 +1,-1 交替排列)所需要的最小交换次数。

先做单组询问:给最终状态用 [1,n] 顺次标号,给初始状态中的标号满足:对于所有 x,y,第 x 个数 y 在两个状态中的标号相同。操作次数就是初始状态标号的逆序对。

对于多组询问需要一点分讨,一个稍微简单的做法是,分 0 左边的数有奇数还是偶数两种情况。对于同种情况,将 0 的区间往右移动两步后,标号序列的变化也仅仅是将两个数的标号移到中间一段 0 的前面,很容易用 BIT 计算逆序对的变化量。

考虑满分做法:dp 状态一样,按绝对值 x 从大到小枚举的时候,将 +x 看成 +1-x 看成 -1,绝对值小于 x 的看成 0。有时候 0 会很多,但是计算逆序对的时候只需要分别计算:(-1,0),(1,0),(-1,1) 之间的贡献,额外用 BIT 维护 0 的位置即可。

复杂度 O(n \log n)

复原

不会,咕

Public Round #10 验题人题解

2023-07-18 20:46:58 By znstz

训练

不能掉到 0 以下,这个限制特别烦。如果某一天掉到 0 以下,那么这一天之前所做的练习都是无效的。也就是说一定存在一个最优方案,在开始练习一个技能之后,一定不会掉到 0 以下。

dp(i,0/1/2,d_1,d_2) 表示,考虑前 i 天,第 i 天练习了什么技能,另外两个技能分别有多少天没有练习。一个非常直观的感觉,d_1,d_2 不会太大,是 O(\sqrt {A}) 级别的,A 是值域。感性理解就是,超出这个级别会导致掉下来太多,而在这一段没有练习的时间的正中间强制练习这个技能,会取得 \ge A 的收益,复杂度 O(nA),注意一下要处理一些技能没开始练习的情况。

打摆

将图看做 100 个点的完全图,每条边染成了黑色或白色。

先取出任意五个节点,解出这个大小为 5 的团。每三个询问一下,得到了 10 个未知数和 10 个方程,把它解出来。由于未知数不多,可以暴力枚举。

每次选一个点 u 加入团,将团中的节点随机打乱,得到排列 p_1,p_2,\cdots,p_k,令 i=1,询问 (u,p_i,p_{i+1}),将其减去边 (p_i,p_{i+1}) 的贡献,有两种情况。

  • (u,p_i)(u,p_{i+1}) 同色,我们可以知道具体的颜色,令 i=i+2,重复此过程。
  • (u,p_i)(u,p_{i+1}) 异色,令 i=i+1,重复此过程直到找到一对同色边,找到之后可以推出前面的一些边。

有一些细节:如果找完了都没有找到同色边,那么可以任意取一个 j,询问 (u,p_j,p_{j+2})(u,p_1,p_j),得到 (u,p_j)(u,p_{j+2}) 的颜色,由于 k \ge 5,一定能找到一个合适的询问。

我们已经将团里面的点随机打乱了,每次问到同色的概率至少是 0.5。即,一次询问在最坏情况下,有 0.5 的概率确定两条边,有 0.5 的概率确定一条边,期望确定 1.5 条边,询问次数期望大约为 \frac{n^2}{2 \times 1.5}=\frac{n^2}{3}

抄袭

考虑 2-sat,有 2n0/1 变量 x_0,x_1,\cdots,x_{2n-1},每个变量表示 x 轴上的一个点所在连线的方向,是向上还是向下的。想到这个,剩下的通过手玩都可以解决。

l_i,r_i 表示颜色 i 靠左,靠右的两个点的位置。

  • l_i \lt l_j \lt r_j \lt r_i,即区间包含,可以得到 x_{l_j}=x_{r_j}
  • l_i \lt l_j \lt r_i \lt r_j,即区间相交,可以得到 x_{l_j} \neq x_{r_i}

手玩 2^4 种情况会发现是必要且充分的,构造方案可以对每个 l_i 上的竖线钦定长度,l_i 越小越长。用 2-sat 或并查集求解,复杂度 O(n^2)。可以主席树优化建图,复杂度 O(n \log n)

znstz Avatar