Codeforces Global Round #12

C. Errich-Tac-Toe

考虑对所有格子按 ((i + j)mod 3) 分类。

选取两个类，一类中 O 全部变成 X，一类中 X 全部变成 O。

考虑连续的三个棋子，必定被包含在 (3) 个类中，且不会出现连续的 (3) 个相同。

将 (a_i) 奇偶分类，容易发现原图是二分图。

构造差分约束。

对于有向边 (u o v)，构造两条边 ((u, v, 1), (v, u, -1))，即保证了 (a_u = a_v +1)。
对于无向边 ((u, v))，构造两条边 ((u, v, 1), (v, u, 1))，即保证了 (|a_u - a_v| le 1)，同时在二分图上最短路保证了 (a_u eq a_v)，可以满足条件。

那么先判二分图，然后用 Floyd 求最短路，有负环则无解，否则令最长路径端点 (u)，(a_u = 0)，其他取到 (a) 的最短路即可。

有解的充要条件是众数出现次数 (le leftlceil {frac n2} ight ceil)。

在满足 (a_i = a_{i+1}) 的 ((i, i + 1)) 间加分隔符，设划分成了 (k) 个连续段。

需要重排连续段，使得两两之间可以连接，充要条件是出现最多的端点出现次数 (cnt le k +2) 次。

证明：

对于 (k = 0, cnt = 2) 显然成立；
对于 (k > 0, cnt le k - 2)，可以将一个出现次数最多的端点与另一个端点之间连接，使 (n leftarrow n - 1, k leftarrow k - 1)。

所以判断有解后，一定存在 (i)，使 ((i, i+ 1)) 不同且均不为众数（否则必定无解），可以通过拆开这样的对使得 (k leftarrow k + 1, cnt leftarrow cnt + 2)，因此答案为 (k + max{0, cnt - k - 2})。

咕

考虑贪心求解。我们每次将相邻的两个 w 或 b 连一条边并删掉，剩下来的一定黑白交替。

给序列中每个点赋上 ((-1)^i) 的权值，那么答案为黑色（或白色）权值和绝对值的一半，因为这样中间一段偶数不影响答案（和为 (0)，且不影响两边奇偶性），而中间出现一段奇数会改变奇偶性，如 wwwbwwwb，w 的权值为 (2)。

考虑先给 ? 在奇数位置的填白，偶数位置填黑，然后选择一个子集翻转，可以发现每次翻转一个元素会使上述权值和减 (1)，因此用一个组合数计算即可。

咕咕