题目链接：http://poj.openjudge.cn/campus2023/J/
很荣幸参与了命题。
题解的 ppt 版本在这儿：https://disk.pku.edu.cn:443/link/E4B484E7F3C58A45E9E4FB19C731BF4E.
贴一下 md 版题解，要比 ppt 版本的简略一些：
每个人能够推断出自己帽子颜色的信息，仅有两类：前面的人的帽子情况，以及其他人的报告情况。注意，这里的报告情况不仅包括每个人是否报告，也包括了每个人在哪一轮做出的报告。
梳理完毕这些信息后，我们先证明两个引理。
Lemma 1：对于进行中的任何状态，如果 \(i\) 确定了自己最终是否报告，那么 \(i + 1\) 也确定了自己最终是否报告。此处“确定”是指，\(i\) 已经报告，或者从当前到无穷的时间上，\(i\) 都不会报告。
Proof 1：设 \(i \lt j\)，由于 \(j\) 掌握的信息严格比 \(i\) 多，故虽然 \(j\) 可能无法报告，但如果 \(i\) 可以报告，则 \(j\) 一定可以知道 \(i\) 可以报告。故而说明 \(i\) 的报告对 \(j\) 做出判断没有影响。也就是说前面的人的报告情况不影响后面人的报告情况，即证明了引理 1。
Lemma 2：对于每一轮的报告，宣布报告的人一定是还未确定最终是否报告的人中的一段后缀。
Proof 2：只需证明，如果 \(i + 1\) 无法报告，则 \(i\) 也无法报告。使用反证法，不妨设 \(i\) 报告自己的帽子为白色，由于 \(i + 1\) 无法确定，则 \(i + 1\) 可能是黑色。那么从 \(i\) 的视角来看，他从 \(i + 2\) 得到的后面的报告信息，以及自己观察到的前面帽子信息中，该组合信息与 \(i\) 是黑色 \(i + 1\) 是白色完全对称（相当于 \(i\) 和 \(i + 1\) 是一个黑箱，两人交换帽子颜色对黑箱外没有影响），故该情况同样是有可能的，与 \(i\) 能确定自己的帽子颜色矛盾。故引理 2 得证。
上述两个引理告诉我们，报告不必进行无限时间，只需要考虑从后往前的若干轮，这个轮数不会超过 \(n\) 轮。这样的结果与原题目是等价的。
简单化归题目后，难点在于如何具象化这个“后面的人的报告情况”，也即，后面的报告提供了怎样有用的信息。
直观上的想法是，这个信息可以表示为 \((x, y)\) 的形式，表示剩余帽子中两种颜色的个数。由于大家都不知道 \(0\) 号帽子颜色，因此帽子的颜色是对称的，也即 \((x, y)\) 可能表示有 \(x\) 顶白帽 \(y\) 顶黑帽，也可能表示 \(x\) 顶黑帽 \(y\) 顶白帽。以下我们以具体例子算法过程，也即如何维护每个人携带的信息。
为了方便，我们假定一个虚拟的 \(2n\) 号，携带了信息 \((n, n - 1)\)，表示 \(1\) 号到 \(2n - 1\) 号当中帽子颜色个数。在最开始时，\(2n - 1\) 号获得了该信息，它根据自己所见前方帽子的颜色情况与这个信息进行推断。
- 若白色 \(n\)，黑色 \(n - 2\)，则知道自己用掉了 \(n - 1\) 中的一个东西，也就是自己帽子颜色与 \(n - 2\) 这个值相等，故而判断出自己是黑色。
- 若黑色 \(n\)，白色 \(n - 2\)，同理，判断出自己是白色。
- 若白色 \(n - 1\)，黑色 \(n - 1\)，虽然知道自己用掉的是 \(n\) 中的一个东西，但是无法判断出用的是哪一个 \(n - 1\)，故而无法判断。
接下来，\(2n - 1\) 号是否报告的结果，将一个新的信息携带到自己身上：
- 若 \(2n - 1\) 报告，说明结果要么是白色 \(n\)，黑色 \(n - 2\)；要么是黑色 \(n\)，白色 \(n - 2\)。故而携带的新信息是 \((n, n - 2)\)。事实上，可以归纳得到，此后任何情况都具有这样的白色黑色的对称性。
- 若 \(2n - 1\) 没有报告，说明结果一定是白黑各 \(n - 1\)，故而携带信息 \((n - 1, n - 1)\)。
此后，\(2n - 2\) 号利用他所知道的 \(2n - 1\) 号和 \(2n\) 号携带的信息，做类似的推理。通过计算可知，\(2n - 2\) 号一定报告。稍微有一些区别的是，如果他观察到前面的情况是 \((n - 1, n - 2)\)，那么他会要根据 \(2n - 1\) 号是否报告，也就是在 \(2n - 1\) 号身上携带的信息，才能做出判断，也就是说他会在 \(2n - 1\) 号的下一轮做出报告；但如果他观察到前面的情况是 \((n, n - 3)\)，那么他可以直接从 \(2n\) 推理过来，也就是说他会和 \(2n - 1\) 号在同一轮就做出了报告。虽然在前面的人看来，他一定做出了报告，但是由于报告时间的不同，他携带的信息要么是 \((n - 1, n - 2)\)，要么是 \((n, n - 3)\)，是有明显差异的。
这也给了我们一个启发，每个人计算自己能否报告帽子颜色及携带的信息时，需要从最后方的可以做出推断的人处获得。直觉上来看，跳过的一段区间相当于这一轮报告的区间，根据引理 2，该方法总是严格的。
于是，我们以此类推，从 \(2n - 1\) 号到 \(1\) 号逐个递推，每次判断前方帽子情况能不能由信息唯一推得，并根据自己及后方的人的报告情况计算自己将要携带什么信息即可。
朴素的实现可以做到时间复杂度 \(O(n ^ 4)\)，即可通过本题。
然而这并不是重点。这个算法可以用来证明本题结论：某个人能够确定自己的帽子颜色，当且仅当他看到的帽子颜色数量不相等。
- 必要性。必要性显然，若帽子颜色相同，则所有帽子反色后也是一种合法方案，故一定不能报告。
- 充分性。我们只需要证明一个更强的结论：每一个人携带的信息有且仅有一个信息对。考虑第二数学归纳法，对于 \(2n\) 和 \(2n-1\) 显然满足条件，对于前面的某个 \(k\)，如果他推得帽子颜色，则该轮报告的一定是一段颜色相等的后缀，那么可以唯一确定 \(k\) 的信息对；如果他无法推得帽子颜色，那么他看到的颜色一定相同（归纳可得），于是也只有一个信息对，于是证明了该结论。
综上，我们用一次 for 循环，\(O(n)\) 扫过去即可。
\(O(n ^ 4)\) 代码：
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using std::cin, std::cout;
using std::endl;
using std::pair;
using std::make_pair;
using std::swap;
using i32 = int;
template <typename T>
using vec = std::vector<T>;
void read(i32 &n, vec<i32> &a) {
cin >> n;
a.resize(2 * n);
for (i32 i = 0; i < 2 * n; i += 1) { cin >> a[i]; }
}
bool can_derive(i32 mn, i32 mx, const vec< pair<i32, i32> > &g) {
for (auto p: g) {
if (mn <= p.first && mx <= p.second) {
return true;
}
}
return false;
}
bool can_infer(i32 mn, i32 mx, const vec< pair<i32, i32> > &g) {
if (mn == mx) { return false; }
bool possible_mn = false, possible_mx = false;
for (auto p: g) {
if (p.first >= mn + 1 && p.second >= mx) {
possible_mn = true;
}
if (p.first >= mn && p.second >= mx + 1) {
possible_mx = true;
}
}
if (possible_mn != possible_mx) { return true; }
else { return false; }
}
void derive(i32 n, i32 sum, bool inferred, vec< vec< pair<i32, i32> > > &info, i32 frm, i32 tar) {
info[tar].clear();
for (i32 mn = 0; mn <= sum; mn += 1) {
i32 mx = sum - mn;
if (mx > n) { continue; }
if (mn > mx) { break; }
if (can_derive(mn, mx, info[frm]) == false) { continue; }
if (can_infer(mn, mx, info[frm]) == inferred) {
bool check_this_round = true;
if (inferred == true) {
for (i32 i = frm + 1; i <= 2 * n; i += 1) {
if (can_infer(mn, mx, info[i]) == true) {
check_this_round = false;
}
}
}
if (check_this_round == true) { info[tar].emplace_back(mn, mx); }
}
}
}
i32 solve(i32 n, const vec<i32> &a) {
vec< vec< pair<i32, i32> > > info(2 * n + 1);
info[2 * n].emplace_back(n - 1, n);
i32 ans = 0;
for (i32 i = 2 * n - 1; i >= 1; i -= 1) {
i32 count_black = 0;
for (i32 j = 1; j < i; j += 1) {
count_black += a[j];
}
i32 count_white = i - 1 - count_black;
if (count_black > count_white) {
swap(count_black, count_white);
}
bool can_guess = false;
for (i32 j = 2 * n; j > i; j -= 1) {
if (can_infer(count_black, count_white, info[j]) == true) {
ans += 1;
can_guess = true;
derive(n, i - 1, true, info, j, i);
break;
}
}
if (can_guess == false) {
derive(n, i - 1, false, info, i + 1, i);
}
}
return ans;
}
i32 main() {
i32 n;
vec<i32> a;
read(n, a);
i32 ans = solve(n, a);
cout << ans << endl;
return 0;
}
\(O(n)\) 代码：
#include <cstdio>
int main() {
int n;
int a[200];
scanf("%d", &n);
for (int i = 0; i < 2 * n; i ++) {
scanf("%d", &a[i]);
}
int ans = 0;
for (int i = 1, black = 0; i < 2 * n; i ++) {
if (black * 2 != (i - 1)) {
ans ++;
}
black += a[i];
}
printf("%d\n", ans);
return 0;
}