CF1774

差 5 分上橙。

pw[0] = 1; for(int i = 2; i < 40; i++) pw[i] = pw[i - 1] * 2ll % mod;

A. Add Plus Minus Sign

第奇数个 前面填 ，偶数个前面填 。

B. Coloring

将序列划分成 段，前 段每段 个，最后一段可能为空，每个颜色在每段中最多出现一次。因此，如果某种颜色的出现次数大于 则必定无解。

考虑出现次数等于 的颜色，这些颜色必须在所有段中出现，而最后一段最多只能容纳 个颜色。若这些颜色的出现次数大于 同样无解。

剩下的情况容易构造出合法解。

C. Ice and Fire

结论：令 表示以 位置（下标从 开始）结尾的极长相同子串的长度，则第 位的答案为 。

考虑证明。对于 的情况显然成立。

不妨设 ，，则有

• 必败。连胜 场说明胜者应当比 个数大。
• 必胜。上述前提下有 ，可以构造出一种方案使得 成为上一个阶段的胜者。

同理。

D. Same Count One

对于无法平均分配 的情况无解，其它情况均有解。构造证明。

令 ， ，考虑如下最大流模型：

• 对于 ，源点向 连流量为 的边。
• 对于 ， 向汇点连流量为 的边。
• 对于 且 ， 向 连流量为 的边。

每条边费用均为 ，因此最小费用等于最大流。没流满即无解。

显然有 ，且对于 ，其出度 ， 同理。

考虑逐列贪心构造，即对于第 列能给尽量给。

好像不好证。至少我不会证。

E. Two Chess Pieces

贪心。

先考虑如果没有 的限制怎么做。对于 的子树 ，若子树内部没有棋子 必须经过的点，那么棋子 必然不会进入子树 。棋子 同理。

对于 的限制，继续讨论 的子树 。

• 两颗棋子都需要经过 子树内：直接进，与没有限制相同。
• 只有某一颗棋子需要经过 子树：另一颗棋子最好不进入，除非进入 后距离超过 才向下走 步。

维护两颗棋子所在位置以及当前链即可。注意细节。

F1. Magician and Pigs (Easy Version)

nb 题。sto orz。

发现一次 操作会重复之前的扣血操作，也即扣血量翻倍。于是出现扣血操作后，不超过 次 操作就会使所有的猪猪 。

先统计出每个 操作生成的猪猪到下一个 操作之前的实际血量，以及每次 操作会给已经在场的猪猪扣多少血。

尝试倒序枚举，统计操作 对答案的贡献。

我们维护 表示当前生成一只血量为 的猪猪，到最后会变成多少只。

对于每个操作 ，若其扣血量没有达到上限，则所有血量大于当前总扣血量的猪猪数量乘 。

排除并没有扣血的操作 后， 只会改动 次，大力维护即可。

当前时间复杂度：离线后预处理 ，统计答案时操作 ，操作 总复杂度 。

当前空间复杂度：。

其中 。

F2. Magician and Pigs (Hard Version)

延续 的思路。

影响最大的是值域达到了 ，没法暴力维护 。

但我们没必要维护整个 数组：其中有实际意义的“拐点”只有 个。将拐点存起来大力跳即可。

操作 单次时间复杂度变为 ，操作 单次复杂度 ，空间复杂度 。

赛时 pw[0] = 1; for(int i = 2; i < 40; i++) pw[i] = pw[i - 1] * 2ll % mod; 没调出来，极限没过。