ABC354 E - Remove Pairs 做题笔记
对于这种带有博弈论的 dp，考虑这样设计状态：令 \(f_s \in \{1, 0\}\) 表示“游戏局面”为 \(s\) 时，先手必胜还是必败。本题中，“游戏局面”可以表示为剩余卡牌的编号集合。又因为本题中 \(N\) 很小，通过状压，可以直接用一个 int 表示游戏局面。
下面讨论 dp 的三要素：答案统计、初始化、转移。
-
答案统计：因为游戏开始时所有卡牌都没有被拿走，所以初始状态为 \(\{1, 2, \cdots, N\}\)，答案为 \(f_{\{1, 2, \cdots, N\}}\)。（代码实现上可以把初始状态写成
(1 << n) - 1）。 -
初始化：对于所有不能继续进行游戏的状态（也就是不存在数字相同的牌可以选了），设为 \(0\)，表示先手必输。但代码实现上不用特别去初始化，因为全局变量初值本就为 0。
-
转移：转移方程为 \(f_s = \operatorname{OR}_{t \in nxt(s)} \lnot f(t)\)，其中 \(nxt(s)\) 表示从 \(s\) 可以一步到达的游戏局面的集合，“\(\lnot\)” 表示逻辑非。
可以这么理解：因为玩家会最优地选择策略，所以在他所有能到达的下一步游戏局面中，如果存在一个先手必输的情况，他必然会选择到达这个情况。这样等到下一个回合时，他的对手就面临了一个先手必输的局面，因此对手必败，也就是他必胜。否则，若不存在这样的下一步局面，就说明他无论怎么走都会到达一个先手必胜的局面，他就必输了。
代码实现上，可以用记忆化搜索和 dp。
记忆化搜索：
bool dfs(int s)
{
if(vis[s]) return f[s];
for(int i = 0; i < n-1; i++)
{
if(!(s & (1 << i))) continue;
for(int j = i+1; j < n; j++)
{
if(!(s & (1 << j))) continue;
if(p[i].a != p[j].a && p[i].b != p[j].b) continue;
int nxt = s ^ (1 << i) ^ (1 << j);
f[s] |= (!dfs(nxt));
}
}
vis[s] = true;
return f[s];
}
dp：
for(int s = 0; s < S; s++) // 从小到大枚举状态
{
for(int i = 0; (1 << i) <= s; i++)
{
if(!(s & (1 << i))) continue;
for(int j = i+1; (1 << j) <= s; j++)
{
if(!(s & (1 << j))) continue;
if(p[i].a != p[j].a && p[i].b != p[j].b) continue;
int nxt = s ^ (1 << i) ^ (1 << j);
f[s] |= !f[nxt];
}
}
}
需要注意的是，这样从小到大枚举状态是可行的，也就是可以保证 \(\forall t \in nxt(s), t < s\)。证明很简单：\(nxt(s)\) 中的元素都是把 \(s\) 的两个二进制位从 1 变成 0 得到的，因此一定小于 \(s\)。
闲话
这场 ABC 的 D 题非常恶心，没有做出来；一怒之下去做 E，但是对这类题不太熟，乱搞了一个记搜，而且脑子进水了没想到状压，用了一个 map<vector<int>, bool> 来存状态，最后 5 分钟交上去 AC * 28，TLE * 2。因为 T 的点也只有 2208ms，我怀疑 T 了只是因为常数比较大，稍微改了一下交上去还是 TLE * 2，彻底绷不住了。最终达成了 ABC 只做出 ABC 的惨剧（