题解：CF2065F Skibidus and Slay

· · 题解

结论题。

看完题目觉得十分困难，难道是树剖？但这是 Div.4，不会太困难，直接大胆猜测：对于一条路径不需要全部遍历，只需要找一部分。

那要找的长度到底是多少？考虑一条合法的路径的性质。

用 1 表示多数元素，0 表示非多数元素，因为 1 出现了总数的一半以上，所以有很大概率会有 2 个甚至更多的 1 在一起，最差情况也会是 1 和 0 交替出现。换而言之，合法路径必然包含 1,1 或 1,0,1 类型的子序列。

设路径长度为 n，更详细的说：

若 n 为奇数（这部分来源于官解），设其中有 k 个 1，n-k 个 0，已知 k>n-k，那么 2k>n，若不包含 1,1，那么每个 1 之间都需要 0，所以 n-k\ge k-1，可得 2k \le n+1。综合可得 n<2k \le n+1，则 k 唯一取值为 \frac{n+1}{2}，此时路径为 1,0,1,0...，包含 1,0,1。

若 n 为偶数，则 1 出现至少 n\div 2+1 次，但不重叠的长度为 2 的段只有 n\div 2 个，根据抽屉原理，必然有至少一段出现 2 个 1，也就是出现 1,1。

综上，可以得到一个一般结论：若存在一条多数元素为 i 的路径，则必然存在两个相邻节点的数都为 i，或一条长度为 3 的路径，其两端的数为 i。

然后就可以枚举着找了，判断数字可以用 map，具体可以看官解或别的题解，这里不放代码了。