AGC026 题解

· · 个人记录

AtCoder Grand Contest 026

A - Colorful Slimes 2

单独考虑每个连续段，在第 2,4,6,\cdots （偶数位置）修改即可，对答案的贡献就是区间长度除以 2 再下取整。

code

B - rng_10s

首先如果 B>A 或者 B>D 那么一定是 No，如果 C\geq B 那么一定是 Yes。

然后不妨把 A 模一下 B。

那么问题就转化为了是否存在一组 x,y 的自然数解，满足：

A-xB+yD\in (B,D)

如果存在，显然就是 No。

先化成 -xB+yD\in (B-A,D-A)，设 g=\gcd(B,D) 显然如果 (B-A,D-A) 有 g 的倍数那么就一定有解。

code

C - String Coloring

不妨先考虑一下某种合法染色方案具备什么性质。

先把 S 分成前 n 个字符（前半部分）和后 n 个字符（后半部分）。

对于前半部分，制造一个长度为 n 的字符串 L：

先从前往后把红色字母依次加到 L 的末尾，然后从后往前把蓝色字母加到 L 的末尾。

同理对于后半部分，制造出一个长度为 n 的字符串 R：

先从后往前把蓝色字母依次加到 R 的末尾，然后从前往后把红色字母加到 R 的末尾。

如果这种染色方案是合法的，显然需要满足以下条件：

然后折半搜索即可。用 map 统计会比较方便。

时间复杂度：\mathcal{O}(2^nn^2)。

code

D - Histogram Coloring

容易想到先建出笛卡尔树然后 dp，不过笛卡尔树在这题并不是很好处理 h_i 相同的情况，所以考虑建出一个多叉树。（相当于笛卡尔树上所有 h_u=h_{f_u} 的 u 向 f_u 进行合并 ）我比较懒所有就写了个 \mathcal{O}(n^2) 的建树。

考虑两步：用新的一层合并儿子、再往下拓展若干行。

假设现在再节点 u，然后它新增了 len_u 列，那么新的一层的这 len_u 个位置可以随便填，也就是 2^{len_u}。

再考虑如果最开始的一行填好了需要往下拓展（没有新的列出现），那么每个新的行必须和它上面一行反色。但是有特殊情况，就是蓝红相间的情况，因为新的一行从它上面一行复制下来同样是合法的。

那么考虑设 dp_{u,0/1} 表示 u 节点代表的区域 （砍掉 h_{f_u} 以下部分后 u 所在的那块区域）的染色方案，满足最后一行不是/是黑白相间。

考虑在第二步（再往下拓展若干行）之前算 dp_{u,0} 的时候算成总方案比较方便，最后再减掉 dp_{u,1} 即可。

先考虑新加的若干个列，那么 dp_{u,0}=2^{len_u},dp_{u,1}=2。

然后合并儿子：（转移方程太好写出来了就不解释了）

dp_{u,0}=dp_{u,0}\times(dp_{v,0}+2\times dp_{v,1}) dp_{u,1}=dp_{u,1}\times dp_{v,1}

最后考虑往下新拓展若干行：

dp_{u,1}=dp_{u,1}\times 2^{h_{f_u}-h_u-1}

时间复杂度：\mathcal{O}(n^2) 或 \mathcal{O}(n\log n)。

code

E - Synchronized Subsequence

把 a 看成 1，把 b 看成 -1 然后求出前缀和，然后以前缀和为 0 的位置以分界点把字符串分成若干段。

显然每一段都独立，并且每一段的所有前缀要么 a 的个数都大于 b 的个数，要么 b 的个数都大于 a 的个数。

考虑把这些区间分成开头是 a 的和开头是 b 的两类。

对于开头是 a 的区间，如有后面有开头是 b 的区间那么这段区间显然可以扔掉。否则，能搞成最优情况就形如 ababab...。

对于开头是 b 的区间，考虑第一个选择的 b 的位置在 x 其对应的 a 的位置在 y （显然 x<y），那么 x+1\sim y-1 这段区间中的 b 一定全部选上最优。然后又会产生些新的区间，最终结果就是把 x 之后的所有 b 选上是最优的。

那么可以枚举第一个选的 b 是在哪个位置，这样总共有 \mathcal{O}(n) 种。然后暴力比较贪心选取字典序最大的方案即可。

注意要从后往前枚举区间进行贪心。

code

F - Manju Game

毒瘤博弈论。

先把奇数位置上的盒子染成黑色，然后把偶数位置上的格子染成白色。

考虑一下选的流程：先手先选一个盒子，然后后手选择一个方向，两人交替把这个方向上的盒子选完。如果两人一共拿走了奇数个盒子，那么先手交出先手权利。

考虑如果先手交出先手权利，那么后手一定可以通过取剩下盒子最左边/最右边来转化成先手一开始就取整个大区间的最左边/最右边的情况。所以先手一定不会交出先手权。

那么当 n 为偶数的时候，显然先手一开始只能选择最左边/最右边的盒子，因为其他无论哪个位置都会交出先手权。

当 n 为奇数的时，先手一定在前面几次操作中一直选白盒子，然后最后若干次操作选择一个区间的黑盒子。

但是决定每次消灭区间是哪侧的权利在后手，那么如何判断先手能否取到呢？

考虑二分先手能在取全黑的基础上能多得多少。

先把白盒子里的 a_i 变成 -a_i。假设二分的值为 x，如果存在若干个区间 [l_1,r_1],[l_2,r_2],\cdots,[l_k,r_k] 满足 l_1=1,r_k=n,r_i+1=l_{i+1}-1 且 \forall 1\leq i\leq k，x\leq\sum_{j=l_i}^{r_i} a_j，那么就说明可行了，因为后手无论怎么操作都会使先手拿到这些区间中的其中一个。

这个可以通过 dp 求解，然后用前缀 \min 优化到线性。

时间复杂度：\mathcal{O}(n\log n)。

code