[CSP-S 2019] 补全程序 T2 Solution

千华缭乱 · 2019-10-19 20:39:39 · 个人记录

1. 初始的DP

先考虑下, 不状态压缩, 这个东西怎么做.

称一步转移为 : 选择了任意一个满足要求的规则二元组(a_j, b_j), 使得石子数从 i 变成i-b_j;

称一个状态为 : 当前的石子数 到游戏结束时 必定胜利或必定失败.

对于一个确定的石子数 i, 显然这个石子数能使用的转移被这个数限制 (a_j \leq i 才能使用 b_j) , 也就是说一个石子数的转移来源是也是确定的, 把限制二元组按 a 排序, 能使用的转移的个数随着 i 递增, 下文指明由此我们能确定这个状态到底必胜还是必败.

我们考虑必胜态和必败态 :

当其中一人A行动完, 下一个人B视作新一轮行动的先手.

换言之, 考察当前石子数如何决定这一步胜负 ( 因为石子数可以确定所有可能的转移 ), 而非考虑每个人如何行动.

假设A无论使用哪个 b_j, B都会达到A转移到的必定失败的状态, 这个状态对A就是必胜态. 反之, 如果A这一步无论怎样行动, 下一步都会转移到先手必胜的情况, A现在就处于必败态 ( 当然, 必败态的定义是非必胜的状态, 为了容易理解故未这样写 ) , 因为B会达到A转移到的必定胜利的情况.

新一轮行动的先手胜负只和当前的石子数有关, 而通过 DP 我们能确认每个石子数的状态.

我们枚举当前石子数可用的所有转移, 假设其中有必败的状态, 显然我们可以转移到这个状态使得对手下一步必败.换言之, 这个石子数是必胜态.

而假设这里面没有必败的状态, 也就是无论我们作何选择, 对手下一步总是必胜, 这个石子数就是必败态.

这样就是一道简单的 DP.

这个状态的必胜或必败 取决于行动至此所余下的石子数, 而非现在行动的是哪个人.

2. 状压优化

现在我们发现, b_j \leq 64 , 也就是说, 对于当前的状态 i , 能转移到它的至多只有 i-1 到 i - 64 这些状态.

必败态和必胜态显然可以用 0/1 各自表示, 也就是能用一个 ull 记录当前 i 这个状态所有的可能来源.

我们记这个 ull 是 status , 再把当前能用的所有 b_j 也压成一个 ull, 记为 trans.

处于状态 0 时不能再取石子, 所以初始的 status 除了最低位都是 1, 意即状态 0 必败.

status = ~0ull ^ 1;

记二进制下最低位编号0, 最高位编号63, 从低到高存储 i-1 到 i - 64 每一位必胜或必败.

这样每次更新 i 的时候, 先把更新了 i 就满足了限制的 b_j 丢进 trans :

trans |= 1 << (b[j] - 1);

然后考虑一个 win ( 注意这是个 bool ), 记录当前的 i 是否必胜. status 取反和 trans 按位与一下, 然后用 win 记录这个值 :

win = ~status & trans;