CF2115 总结
感受
做过前两道 ,但是第一道一直卡,想不出怎么维护最小次数使一个数变为 \(gcd\),过了半小时,开始看 \(B\) ,直接会了。看 \(C\) 在想最优策略,被值全部相同但刷出了普通攻击的情况卡了,连 dp 都没列。看 \(D\) 想从高到低位贪心,也发现了最后一个人可以调整,但是因为感觉会对下一位有影响,不好做。剩下的题没看,回去把 A 做了,遗憾离场。
题解
A
首先不难发现结尾状态一定是全变成 gcd 。然后思考最优策略,如果恰好有 \(gcd\) 直接用它与不是 gcd 的做一遍一定是最优的。然后思考没有是 gcd 的情况,先搞出一个 gcd 一定是优的,如果过程在搞出一个 \(gcd\) 之前做了别的事,这个操作的位置没有操作到 gcd 后面还是需要一次操作,同时不可能操作一下别的数会让搞出 \(gcd\) 次数变少,所以问题变为最小的操作次数凑出 \(gcd\) 。因为值域小于 \(5000\) ,所以 \(dp_{i,j}\) 表示用前 \(i\) 个数搞出 \(j\) 的最小操作次数。
数据范围增大有基于反演和卷积的 \(O(V\log V)\)(CF2115A - Gellyfish and Flaming Peony - 洛谷专栏)
B
首先知道结尾状态而不知道初始状态,考虑倒推。不难发现可以对其图论建模 \(z=\min(x,y)\) 反向后有 \(x\ge z,y\ge z\) 对于一个值可能有多个这样的限制,一定要满足最大的那个,那么最优的选择就是压着合法的下界,对于最后推出来的数组做一遍操作判断能否做出 \(b\) 即可。不压下界,一定对任意点都没有贡献,压下界就有可能有贡献。
C
对于值全部相同但刷出了普通攻击,我们有两种选择在 dp 转移时取 \(\max\) 即可。
如果最小值不为 \(1\) 闪耀一定会用,如果有超过最小值的数,不闪耀也一定会用,所以最优决策与最小值和可以操作超过最小值的个数。
设 \(f_{i,j,s}\) 表示还剩 \(i\) 轮,最小值为 \(j\) ,序列总和为 \(nj+s\) 的最大概率,转移比较简单。 不难发现时间复杂度有问题,直接做最后一维是 \(V^2\) 的,但是观察特点,一但 \(s\) 从 \(0\) 消了一次接下来的 \(s\) 最大是 \(n-1\) 。最后一维是 \(n\) 的时间复杂度是可以接受的,所以枚举第一次消 \(0\) 的时候,如果是 \(t\) , 概率显然为 \((1-p)^sp^{t-s}\binom{i-1}{s-1}\) ,这样我们就可以统计答案,且时间复杂度正确。(此题有一点卡精度,所以组合数和概率一起递推,还卡时间,注意常数)。
D
从高到低贪心以及最后一个人控制是正确。
我们先让问题变简单一点,我们钦定全选 \(b_i\) ,同时将 \(a_i=a_i\oplus b_i\) ,问题变为选或不选 \(a_i\) (与原问题等价)。找到最后一个当前位为 \(1\) 就能知道当前位的最优解,但是别的数这一位也有一,就会导致有影响,前面选了奇数个你就必须选 \(1\) 前面选了偶数个就必须不选,为了消除前面的影响,我们对前面为 \(1\) 的位置异或上最后一个,将这一位所有 \(1\) 消掉,同时分情况将答案异或上最后一个的值,这样前面的选择就不影响了,每一位独立,直接暴力做,不难发现这样选择与原问题最优选择等价。
E
完全背包问题,我们有最直接的暴力 \(O((n+m)r)\) 的,但是由于 \(c\le 10^9\) 所以直接做显然不行。
因为值域巨大,我们发现会先填一些性价比很高 \((c_u,w_u)\) 的物品,对于剩下的体积再用其他物品来做,不难证明其他物品最多选 \(c_u\) 个(鸽巢原理),占用的体积最大时 \(c_{max}^2\) 。我们可以先全选性价比最高的,直到选不了,再考虑替换。最后剩下的体积小于 \(c_u\) ,用这个取跑背包,不难发现剩下的体积可能装不满,取出一两个性价比最优的会使答案更大(设答案为 \(C+{V-used\over c_u}*w_u\)),所以我们维护 \(f_i\) 表示最大的 \(i+k\times c_u-{used\over c_u}*w_u\) (相当于取出一些性价比最优的给其他物品选)即可,转移形如同余最短路,转圈算法即可。
将两个做法拼起来 \(r<c^2\) 时,跑完全背包的暴力,否则同余最短路。不能直接同余最短路的原因是取模后没有考虑背包容量,如果小于 \(c^2\) 同余最短路会搞出超过体积的最优解。
F1
首先因为前缀,每次操作会多增加一个连续段(区间是多增加两个)所以考虑序列分块。
对于插入删除操作都可以直接暴力做,时间复杂度是 \(O(n\sqrt n)\) 的。对于删除操作,不好直接做,但是全局删除,所以考虑延迟删除,打个标记,遍历到了再删,每个点只会删一次所以总时间复杂度与插入一样。查询操作,先考虑简单的,在块内,可以暴力遍历一遍每个连续段维护的值,再考虑段间,最大的问题是位置,不知道每个点在上一个集合对应的位置,所以可以记每个块记位置的变化(每个块以上一个块为基础重新1-n 编号,所以要能还回去)。找 \(\sqrt n\) 块中的所有所有位置遍历一遍即可。
总结: 操作分块,每个块内维护连续段(位置连续经历的操作相同),每个连续段维护加入的数(vector),删除的数的个数,还要维护操作完第 \(k\) 个位置是上一块的那个位置。插入操作,就先增加连续段,然后 \(i\) 暴力插入每个连续段的 vector 。反转也是增加连续段然后暴力反转,删除操作打标记。查询操作,找 \(\sqrt n\) 块中的所有所有位置所在的连续段遍历一遍 vector 即可。