CF388C Fox and Card Game
24-7-14-14
博弈论的题的核心在于双方都聪明且知道对方聪明
于是就有两个切入点
- 我一定选使对方最优决策最劣的方案 （过程向
- 如果存在界，打破界会变劣的一方一定会维护界。
如果维护不了，就是必败界
如果一定能维护，就是平衡界 （结果向
思考这题时陷入了第一点，看题解后wssb。
明明做过的博弈题九成九是结论题，还在那儿想过程，无语了。
考虑过通过第一点写个暴力找规律，可能有用
考场遇到这种情况一定不能犹豫
P2490 黑白棋
24.7.14.15
先考虑必败界，再dp一下就行
如果没理解错的话
有 k/2 堆棋子，每次可以在最多 d 堆中取走任意数量的棋子
记得 nim 好像有异或和为 0 的界？
还记得 d取 的问题有 d+1 的界？
这题不太能写暴力罢
仅有不超过 d 堆有多于0枚棋子时，直接秒
有且仅有 d+1的倍数 堆且都只剩1枚棋子，直接投
仅有不超过 d 堆有多于1枚棋子时，直接秒
有且仅有 d+1的倍数 堆且都只剩2枚棋子，直接投
应该是有 d+1 的界，难道依次判每个数是否在界上？
推不下去了
看题解
我真厉害，两个界糊一起就对了……所谓 k-nim
首先将各堆石子数用二进制表示。
令 𝑟_𝑖 表示每堆石子二进制表示的第 𝑖 位上数字之和 mod(𝑘+1) 的值。
如果有任意一个 𝑟_𝑖≠0，先手必胜；否则先手必败。
结论和证明都很好理解
思考时没分析第一个界，如果能想到二进制拆分，就能填补第二个界的漏洞
啊啊啊，dp部分自己想罢
堆数 m = k/2 <= 50, 棋子数上限 n-k <= 10000
总方案数 （n, k）
dp 是按二进制位考虑还是按堆数？
二进制位 棋子数？ log((n-k)/(d+1)) * (k/2/(d+1)) * (n-k)
令 n = n - k, m = k / 2, d = d - 1
O( nm(logn-logd) / d )
d=1时复杂度最大，就是 普通nim
从这个复杂度来看的确应该分析一下 普通nim
复杂度算错了，但应该能过
P6902 Surveillance
24.7.21.2
看到倍增标签了，都没想出来……
个人思路是维护一个个区间对。但是这样信息难以标识和合并。
正解：把区间考虑成从左端点跳到右端点，倍增跳几次。
CF710F String Set Queries
24.7.21.3
如果没有强制在线，那么就直接秒了。
在强制在在线的情况下，可以考虑根号重构。但不是很想写。
删除可以直接取关。可以实现动态插入 ACAM 吗？
罢了，还是根号重构
直接最优解？那些 nlogn 做法的在干嘛
CF983E NN country
P6651 Chain
这次是被标签中的容斥给误导了……或者说我对容斥的认识比较偏激？
显然是可以 2^k 容斥，但时间复杂度显然是不对的。
这里应当依次单独考虑每个点主导的贡献。
这里，认为一个不合法链被其上第一个被ban掉的点主导。自然想到以拓扑序的顺序计数。
f 为前方案数，g 为后方案数， h 为中方案数，f` 为前主导方案数, 则有
计数方法一共就那么几种，一定要挨个尝试一遍。
CF1817C Similar Polynomials
tag:
- 拉插
今天终于是把拉格朗日插值学了……
拉插的思路还是很好懂的。
不对，这到题的思路不在拉插上？
以后推柿子是要留心一下有枚举范围缩小的极限情况
这题对拉插的理解考察很有意思
P4139 上帝与集合的正确用法
推柿子
推不出来。考虑牛顿迭代
毛线哦，暴力打表找规律
好好好，又是奇怪定理，玩不起
扩展欧拉定理
AT_agc064_d Red and Blue Chips
tag:
- 计数
遇到此类求本质不同结果的题，先考虑如何 check 一个结果序列合法。
— stntn对排序后的数组计数是简单的。
— FstAutoMaton