ARC151 题解

gyh20 · 2022-10-17 09:51:55 · 个人记录

ARC151A- Equal Hamming Distances

贪心，每次能选 0 就选，只要后面的可以及时调整即可。

https://atcoder.jp/contests/arc151/submissions/35728968

ARC151B A < AP

还是按照字典序的比较方式。

假如 a_i\neq a_{p_i}，立刻结束，此时一些元素可以随意选择，一些元素有限制。

否则 a_i=a_{p_i}，这就相当于合并了 i 和 p_i 两个连通块，动态维护连通块的个数即可。

https://atcoder.jp/contests/arc151/submissions/35729688

ARC151C 01 Game

可以发现，每一个极长的没有被填的段是独立的。可以考虑分别求 SG 函数 xor 起来。

一个段的状态之和两个边界的两个点相关，可以 DP O(n^2) 求 SG 函数，规律容易发现。知道规律之后也容易归纳。

https://atcoder.jp/contests/arc151/submissions/35730800

ARC151D Binary Representations and Queries

Key observation:若相邻的两个操作 x 不同，交换这两个操作不会影响答案。

3 -> 4

^~~~~~^

|~~~~~|

1 -> 2

具体形式就是先转移 1\rightarrow 2,3\rightarrow 4 和先转移 1\rightarrow 3，2\rightarrow 4 的效果是完全一致的。

而 x 相同的位置可以看作矩阵乘法，可以合并。

https://atcoder.jp/contests/arc151/submissions/35728581

ARC151E Keep Being Substring

首先先忽略 一直是子串 的限制。

最优的方案一定是删除直至变为 最长公共子串，然后再加回来。

这样做大部分时间是合法的，唯一的问题是 最长公共子串=0 的时候违背了题目中不能是空串的性质。

此时答案的形式一定是删除直至长度为 1，一直对这个长度为 1 的串操作直到变为一个长度为 1 的，且在第二个串中出现的串。

将一个字符变成另一个字符，可以看作每次花 2 的代价每次将一个字符变为相邻的另一个字符。这个过程就是一个最短路，bfs 一遍即可。

最开始还要求个 最长公共子串。

https://atcoder.jp/contests/arc151/submissions/35725527

ARC151F RGB Card Game

令两个人分别为 A,B，把 Card 称为石子。

如果某一堆石子其中一个人没有，那么这一堆是没有用的，直接删去。

令 A<B 的颜色数量为 A_{num}，\min(A,B) 之和为 A_{sum}，A>B 的数量为 B_{num}，\min(A,B) 之和为 B_{sum}，A=B 的数量为 C_{num}，\min(A,B) 之和为 C_{sum}。

如果有两堆石子都已经被拿完了，那么剩下的一堆谁多谁输，所以游戏的一个思路是拿自己多的。

另外如果每一堆每个人的石子数量都是 1，虽然看上去需要拿三次，但后手第一轮可以不拿让先手继续。游戏就会有变化。但这个操作在石子 >1 的时候不同，因为下一次自己拿的时候对手又可以选择让或不让。

于是大致策略就有两种：

此时两人的策略可以视为如下：尽早的拿掉自己比对方多的那些堆里的石子，因为一旦对方的某一堆变空了，自己可以一次性把那一堆的自己的石子拿完。

此时先手获胜的条件是 B_{sum}\leq A_{sum}。

若 C_{num}=3

没有人会主动将一堆自己有的石子拿空，此时对手可以选择让或不让。所以最终游戏会进行直到所有堆里的石子都剩下一个。

也就是 C_{sum} 为偶数先手剩，否则后手胜。

若 C_{num}=2（稍微重写了一下）

如果剩下的一堆一个人少，那么这个人一定获胜。否则按照 C_{num} 的奇偶性分类。

具体证明可以看作状态的转移，以先手必败为例。

如果先手选择了两人一样多的一堆，那么后手直接模仿。

如果先手一步选了自己更多的一堆：

若后手在这一堆的石子数 >1，那么直接模仿。

否则，如果拿走之后剩下两堆先手必胜，就拿，否则一定先手必败，那么可以一直让。

注意上述操作仅在有三堆的情况下成立，因为根据最初的策略每一堆石子会留一个到最后，在只剩下两堆石子的时候让或不让是没区别的。

若 C_{num}=1

若 A_{num}=2 或 B_{num}=2，少的一边一定获胜，因为操作一定能变为 C_{num}=2 的情况。

若 A_{sum}\geq B_{sum}+C_{sum}，则先手必胜，此时先手每一步一定可以减少 B_{sum}+C_{sum}，这样到最后剩下一堆的时候后手一定比先手多。