Codeforces 题目选做 II

· · 个人记录

只做了几十道就在模拟赛 / CF 里出现了两次一样的做法，说明随机做 CF 帮助很大！！！

One-Four Overload

这种题出得好多啊。对于 cnt_x=cnt_y 的限制大概就是猜一个钦定方式，钦定 p\ne q（即加强条件），然后跑二分图染色之类的。

钦定出来的只要一眼卡不掉，基本就是对的。

做法我写在 一类问题\二分图染色 里了。

\color{green}*Erase and Extend

注意到最优解一定是不停重复一个前缀。

可以枚举每个前缀二分哈希比较，因为重复的哈希容易计算。复杂度 O(k\log k)。

然而有更高明的做法，

cin >> s;
int p = 1, i = 0, n = s.length();
for (; i < n; ++ i) {
    if (s[i] > s[i % p]) break;
    if (s[i] < s[i % p]) p = i + 1;
}
for (i = 0; i < K; ++ i) putchar(s[i % p]);

对着代码证明正确性很简单，这里就不证了。

感觉在赛场上，二分哈希也不亏。

upd：真的又出了这个做法的题，就是那个叫你所有下标异或上一个数，求最小字典序的 F。

Figure Fixing

和 [NOI Online #1] 的 T1 很像。

如果一张图是非二分图，则可以在和的奇偶性不变的前提下任意改变点权。取一棵生成树然后讨论一下即可。

如果是二分图，两部分的差不能改变。

Colorful Operations

对颜色连续段打懒标记，set 维护连续段，连续段变化的时候在树状数组上处理。

Fair Share

做法我写在 一类问题\二分图染色 里了。

Fibonacci Additions

哈希会被定向卡，有没有什么确定性算法？

考虑作斐波那契差分（瞎说的）。满足：

\sum_{i=1}^t c_iF(t-i+1)=a_t （为什么要这么做？因为要把序列改变形式，使得全为 0 等价于新形式全为 0 而且操作对新形式的改变量为 $O(1)$，试一试就能试出来这个） 考察 $c_i$ 在做了操作之后的变化。应用公式 $F(m+n)=F(m)F(n+1)+F(m-1)F(n)$，可以简单地推知：如果 $[l,r]$ 进行了这个操作，只有 $l,r+1,r+2$ 的 $c$ 会变，变化量就是一个斐波那契数。 维护 $c$ 数列中 0 的个数即可，复杂度线性。 ### Keep the Average High 首先把所有元素都减去 $x$，变为 $s_r\ge s_{l-1}$。 注意到只要每个选择的长度为 $2,3$ 的区间都满足条件，那所有的都满足条件了。根据这个随便设计一个 dp 即可。 ### Lexicographically Small Enough 枚举 LCP 一个一个贪心往前移。 ### $\color{red}*$Tricolor Triangles 非常“数竞”的一题。 核心思想真的很简单，因为三个数互不相同或全相同等价于和同余 0（模 3），做模 3 意义下高斯消元即可。 时间复杂度 $O(m^{3.5})$，$m=256$ 看似不太能过，但写了一下，只要加上各种一直都会加的剪枝（为 0 就不消），跑得真的很快（因为方程涉及到的元都很少）。 题解给出了 bitset 优化的做法。大概就是，对每一行开三个 bitset，分别存储这一行为 0,1,2 的位置，消元时分别枚举这一行和下一行的对应位置的值，通过 bitset & 得到位置，然后把新值 | 到新 bitset 里面去。 利用相同的思想可以做到 $O(\dfrac{mn^2M^2}{w})$ 解线性方程组（$m$ 个方程，模 $M$） upd：模拟赛考了。 ### A Stroll Around the Matrix 由于矩阵是凸的，可以证明最优策略是每次往右边和下边中值大的走。而且，对于一行而言，有一个分界线，前面是往右走，后面是往下走（可能反了）。 于是只需要支持在加等差数列的基础上查询这个分界线，以及区间求和，可以用树状数组维护。 由于做这道题过程中发现自己不会树状数组区间加区间求和，所以补一下： > 我们仅解决后缀加前缀求和的问题。 > > 如果对 $[i,n]$ 加 $x$，$i$ 会加上 $x$，$i+1$ 会加上 $(i+1)x\dots

考虑用两棵树状数组维护 i 这个地方被加了 iK+B，每次修改时，给 i 的 K 后缀加 x，给 i 的 B 后缀减 (i-1)x 即可。

这题要区间加等差数列区间求和，类似地维护 i^2X+iY+Z（其实这样可能出现分数，更好的方法是维护 \binom i2X+iY+Z）。

AmShZ and G.O.A.T.

注意到一个序列 GOAT 充要条件（我也不会证，找找规律就看出来了）是 \forall i,a_{i+1}-a_i\ge a_{i}-a_1。

于是除了最开始相等的项，剩下的只有 O(\log V) 项，lower_bound 找出来。

Squid Game

说实话我个人觉得这题不比 Paint The Middle / Towers 难，然而一个评分 2200/2400 一个评分 3100。

我完全摸不准这种纯贪心题难度，感觉只要知道是纯贪心题，xjb 贪基本上都是对的。

所以难点在于识别出来这是贪心题。。大概想一想 dp 发现没法 dp（或者 dp 就是贪心）基本就是了。

首先，以任意点为根，对于一条 LCA 不是端点的链，只要选根都可以一次满足。

假设所有链都是 LCA 为端点，那肯定在保证合法的基础上，选取的点越浅越好，因此从深到浅依次选。因为浅了可以尽量满足 LCA 不是端点的链，而且对于 LCA 为端点的链，

因此这样是对的，最后特判一下根是不是要选。可以做到线性。

\color{green}*Points Movement

首先可以去掉所有已经被点包含的线段，互相包含的线段仅保留短的。这时，整个图长成：点 - 一些线段 - 点 - 一些线段...

题解做法：注意到一段在 P_i,P_{i+1} 之间的线段，一定是左端点靠前的一些被 P_i 管辖，另一些被 P_{i+1} 管辖，故枚举这个分界点来 dp。然而这时并不知道 P_i 是先左后右地移还是先右后做地移优，因此把它设进状态，这时对于固定的状态其贡献是定值，非常好转移。整个 dp 是线性的。

我的做法：设 f(i,j) 表示点 1\sim i visit j 且 j 是最后一个的最小值。

在 j+1 位置维护 F(j)=\min_i f(i,j)。那么枚举 i visit [j,k] 这些线段，F(k-1)\to f(i,j)

线段树维护 f-2k,f-k,f 的区间最小值即可。

细节：转移应该是怎样的？

所以应该这样：把 $f(x,k)$ 既挂在 $k+1$ 的左端点上，又挂在 $k+1$ 的右端点上。

Good Graph

显然整个图一定总是仙人掌。

首先把改变连通性的边拿出来，这些一定会加。剩下的边需要判断

  1. 是否仍然是仙人掌。
  2. 链上 xor 和是否正确。

第二个问题很简单，线性 dfs 一遍预处理到根 xor 和。

第一个问题，如果仍然是，那就可以暴力覆盖，所以本质上是单点修改链上求和，树状数组即可。总复杂度单 log。

Jumping Around

题目就是求 w(i,j)=||a_i-a_j|-d| 的最小生成树，Boruvka。