CF 705 题解
A Hulk
模拟即可.
B Spider Man
打 sg 表可以发现, 奇数个球先手必败 (sg=0), 偶数先手必胜 (sg=1). 多个组合只要把 sg 值异或起来就好.
C Thor
暴力模拟就可以了, 用队列模拟.
D Ant Man
结论: 按照编号由小到大加入链表, 每次尽量让答案最小贪心就是对的.
若原来是 \(i\rightarrow j\) , 插入 \(k\) (不妨认为 \(i < j\)), 那么贡献如下变化:
- i 变大
- 变大到 j
变成:
- i 变大
- 变大到 k
- k 变小
- 变小到 j
从变化量的角度, 你插入了 \(k\), 那么 变大到 k 和 k 变小 不管插到哪里去都不变, 唯一的差别就是 变大到 j 变成 变小到 j.
类似的分析, 若 \(i > j\), 可以认为 i 变小 会变成 i 变大.
也就是说, 每次插入, 会添加一个 变大到 和一个 变小, 会把一个 变大到 变成 变小到 或者 把一个 变小 变成 变大.
注意到这些变化是不可逆的, 那么意味着没有后效性, 因此贪心是对的.
这篇题解没有考虑和 \(s\) 和 \(e\) 的边界情况, 但是据说证明是类似的.
E Black Widow
考虑图论建模, 把每一个表达式视为一个点, 那么如果两个表达式含有相同的变量, 那么这两个表达式连一条边.
这一定是一堆链和环, 对于每一个联通块 (如果是环就破环为链), 然后设前 \(i\) 个表达式的异或和为 \(j\), 当前公用变量值为 \(k\) 的方案数为 \(f_{i,j(0/1),k(0/1)}\), 最后把每个连通块背包合并即可.
标签：变小,题解,CF,表达式,705,sg,变大到 From： https://www.cnblogs.com/snowycat1234/p/18541937