去掉限制+让赢家保持局面不变：P4101
去掉限制+让赢家保持局面不变：P4101
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133711268
假如没有限制，就和 的奇偶有关。
博弈论的构造我们做的是什么？无论对手做什么，我都可以通过一些操作使得某种形式的局面不变。
考虑一开始会怎样。第一步只能合并两个1。变成 2 1 1 1 1 ...
考虑现在有个人操作，他就有两种选择。合并两个1，或者合并1和2。分别变成 3 1 1 1 1... 或 2 2 1 1 1 1...
考虑现在到对手。我们假设对手是winner，则他必然可以通过一些操作，使上述局面回归到同样的局面。那么只能是变成 4 1 1 1 1 ...
推广下去，然后我们发现winner总能构造出 m m m k 1 1 1 1...
然后计算这种情况下的合并轮数即可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2022-03-17
【BZOJ：1299 [LLH邀请赛]巧克力棒 】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16018140.html 题目链接 题目 TBL和X用巧克力棒玩游戏。每次一人可以从盒子里取出若干条巧克力棒，或是将一根取出的巧克力棒吃掉正整数长度。TBL先手两人轮流，无法操作的人输。 他们以最佳策略一共进行了10轮（每次一盒）。你能预测胜负吗？ 思路 以下写作中，“石子”与“巧克力”的意思相同。 先考虑一种特殊情况。 假设此时巧克力全部取出来，则这就是一个Nim游戏。 按照Nim游戏的做法，如果此时石子异或和为0，先手必败。 那如何使巧克力全...
2022-03-16
【BZOJ 1874：[BeiJing2009 WinterCamp]取石子游戏 】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16013639.html 题目链接 题目 小H和小Z正在玩一个取石子游戏。 取石子游戏的规则是这样的，每个人每次可以从一堆石子中取出若干个石子，每次取石子的个数有限制，谁不能取石子时就会输掉游戏。 小H先进行操作，他想问你他是否有必胜策略，如果有，第一步如何取石子。 思路 博弈论，考虑把题目变成Nim游戏。 把 [0,1000][0, 1000][0,1000] 按可行操作变成一个有向图，然后处理出它们的SG函数。 然后，把原先的每堆石子通过SG...
2023-12-19
数学方法转化限制条件（使大于小于等于号左右互为相反数，变成绝对值）+加减交错法构造博弈论下界推出最优解再用限制代入：AT_agc056_d
数学方法转化限制条件（使大于小于等于号左右互为相反数，变成绝对值）+加减交错法构造博弈论下界推出最优解再用限制代入：AT_agc056_d 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135089890 https://vj.imken.moe/contest/600552#problem/G 考虑对题目进行转化 L≤Sa≤RL \le S_a \le RL≤Sa≤R 2L≤2Sa≤2R2L\le 2S_a \le 2R2L≤2Sa≤2R 2L+Sb≤...
2023-09-27
博弈论（奇偶考虑法）+计数+DP（判定转DP）：CF838C
博弈论（奇偶考虑法）+计数+DP（判定转dp）：CF838C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133362167 首先题目有博弈，先分析一波最优策略（步骤：分析性质）。 两个人，所以显然考虑奇偶考虑法+递归考虑。 首先删就是使子问题-1，重新排列是在当前子问题里的。 一个串的排列是有限的，所以这里就可以上奇偶考虑法。如果有偶数种串，则必然是后手先“被迫“进入子问题（要算上初始情况） 考虑假设法：我们可以先假设进入子问题： 必赢。先手进！ ...
2023-09-27
图论+博弈论上DP：CF536D
图论+博弈论上dp：CF536D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133364509 此题其实比较板，只是我没看出来 首先肯定要跑个最短路，然后发现可以离散化把值域缩小 然后 nnn 很小，直接暴力列个 n2n^2n2 dp。 转移要注意的是必须从大往小dp。从小到大会产生后效性。 然后拿个双指针优化下转移就行。 123456789101112131415161718192021222324252627282930313233343536373...
2022-03-14
Nim游戏
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16004931.html 题目 NNN 堆石子，两人轮流从其中一堆取至少一个石子，问先手是否存在必胜策略。 结论 异或不为0，先手必胜。 证明 设 kkk 为某一堆取完后的剩余个数，iii 为被取那堆石子的编号，则取完后的异或和为 x1 xor x2 xor…xor xi−1 xor xi+1 xor…xor xn xor kx_1\;xor\;x_2\;xor\dots xor\;x_{i-1}\;xor\;x_{i+1}\...