专栏文章
技巧整理
算法·理论参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mimxmhlj
- 此快照首次捕获于
- 2025/12/01 17:13 3 个月前
- 此快照最后确认于
- 2025/12/01 17:13 3 个月前
技巧总结
这里主要记录一些有趣的题目和解法，适合二次刷题使用。
数据结构
搜索
数学
Problem
有 个石子，每次可以取走 个或者 个（ 为质数）。无法操作者失败，判断先手是否必胜。
。
。
Hint
由题可知，我们每一次都可以取 个。
sol
博弈论；打表找规律；利用特殊取值，构造必胜策略。
在本题中，我们发现了 的特殊性，并构造了必胜策略。
在本题中，我们发现了 的特殊性，并构造了必胜策略。
由题可知，我们每一次都可以取 个。
显然当 被 整除时后手有必胜策略。
同理在 取余 时先手将其对 取余结果变为 并成为后手，有必胜策略。
显然当 被 整除时后手有必胜策略。
同理在 取余 时先手将其对 取余结果变为 并成为后手，有必胜策略。
Problem
若当前有 个石子，设其十进制最大数码为 ，最小非零数码为 ，玩家可以取走 或 个石子。最开始有 个石子，问先后手谁会获胜？
。
。
Hint
注意到 。
sol
博弈论；状态总数较少时，暴力计算 SG 。
注意到 。
考虑将每一个状态的 值算出来。
CPP注意到 。
考虑将每一个状态的 值算出来。
for(int i=1;i<=1e6;++i){
int mx=0,mn=10,t=i;
while(t){
if(t%10)
mx=max(mx,t%10),
mn=min(mn,t%10);
t/=10;
}
dp[i]=(!dp[i-mn] or !dp[i-mx]);
}
while(n--)puts(dp[read()]?"YES":"NO");
Problem
有 堆石子，第 堆有 个石子。两名玩家依次操作：每次操作可以从某一堆中拿走至少一个石子，需要保证所有 按位或的结果时刻不变。无法操作者失败，先后手谁会获胜？
。
。
HintA
发现最后整体的状态一定是每一个最初有 的位置留下一个。
HintB
考虑钦定每一个有 的位最后留在哪里，然后剩下的 就是需要拿走的。
HintC
容易发现，这变成了一个 Nim 博弈。
sol
博弈论；Nim博弈；博弈转换。
发现最后整体的状态一定是每一个最初有 的位置留下一个。
考虑钦定每一个有 的位最后留在哪里，然后剩下的 就是需要拿走的。
容易发现，这变成了一个 Nim 博弈。
进一步发现，对于每一种钦定，对应的 Nim 博弈的必胜者都固定，则随意选择一种计算即可。
发现最后整体的状态一定是每一个最初有 的位置留下一个。
考虑钦定每一个有 的位最后留在哪里，然后剩下的 就是需要拿走的。
容易发现，这变成了一个 Nim 博弈。
进一步发现，对于每一种钦定，对应的 Nim 博弈的必胜者都固定，则随意选择一种计算即可。
Problem
有 堆石子，第 堆有 个石子。两名玩家依次操作：每次操作可以从第一堆中拿走至少一个石子，或者从第 （ ）堆中将至少一个石子移动到第 堆。无法操作者失败，先后手谁会获胜？
。
。
sol
博弈论；Nim博弈；博弈转换。
类似于 Nim 博弈中“两个相同数量石子的堆”，本博弈中“编号为偶数的堆”同样不会对结果造成任何影响。
则按照奇数堆部分进行普通 Nim 博弈处理即可。
先手必败当且仅当奇堆异或和为 。
类似于 Nim 博弈中“两个相同数量石子的堆”，本博弈中“编号为偶数的堆”同样不会对结果造成任何影响。
则按照奇数堆部分进行普通 Nim 博弈处理即可。
先手必败当且仅当奇堆异或和为 。
Problem
有 个石子，两人轮流取石子，不能取的人输。
给定正整数 ，每次取石子的个数 （ 是正整数） 必须满足如下两个条件之一：
给定正整数 ，每次取石子的个数 （ 是正整数） 必须满足如下两个条件之一：
- 是 的倍数。
- 是 的完全平方数。
进行 局游戏，每一局 不变 。
对于每一局，求先手是否存在必胜策略。
。
对于每一局，求先手是否存在必胜策略。
。
HintA
不存在两个 相同的后手必胜点。
HintB
考虑为后手必胜点找上界。
sol
博弈论；计算SG；必胜点上界。
不存在两个 相同的后手必胜点，反证易得。
所以后手必胜点有上界。
所有后手必胜点 。
考虑反证，具体证明过程如下（抄来的）。
不存在两个 相同的后手必胜点，反证易得。
所以后手必胜点有上界。
所有后手必胜点 。
考虑反证，具体证明过程如下（抄来的）。
证明：考虑反证，假设有大于这个数字的后手必胜点，那么考虑两步：
- 第一步：从后手必胜点走一步到的所有点都必须是先手必胜点，此时对于 ，有 种走法是减去 的倍数的。
- 第二步：这 个和 同余的先手必胜点，必须要能走到至少一个后手必胜点。那么再减去 的倍数是不可能的（由性质 1），只能减去完全平方数，而减去的方案数只有 。
注意 卡空间，要用 bitset 。
Problem
P13755 【MX-X17-T4】Yet another Game problem
P13755 【MX-X17-T4】Yet another Game problemAlice 和 Bob 又在玩游戏。有一个序列 和一个区间 初始为 。双方都知道所有的信息，Alice 和 Bob 将轮流对这个区间进行操作，Alice 先手。
- 若轮到 Alice 操作，她可以选择一个 （），并把区间变为 。
- 若轮到 Bob 操作，他可以选择一个 （），并把区间变为 。
当 时，游戏结束。最终得分即为 。
Alice 希望这个最终得分尽可能大，Bob 则希望最终得分尽可能小。假设双方都采用最优策略，请问最终得分会是多少？有时为了防止你蒙混过关，Alice 还要你告诉她第一步应该如何操作。
对于 的数据，，，。
Alice 希望这个最终得分尽可能大，Bob 则希望最终得分尽可能小。假设双方都采用最优策略，请问最终得分会是多少？有时为了防止你蒙混过关，Alice 还要你告诉她第一步应该如何操作。
对于 的数据，，，。
Hint
考虑套上二分转换为 01 串，判定能否拿到 。
sol
博弈论；二分；二分判定等价性质。
考虑套上二分转换为 01 串，判定能否拿到 。
进一步发现判定等价于能通过一步操作让剩下的后缀 的数量大于等于 的数量。
于是就做完了。
考虑套上二分转换为 01 串，判定能否拿到 。
进一步发现判定等价于能通过一步操作让剩下的后缀 的数量大于等于 的数量。
于是就做完了。
Problem
有 堆石子，第 堆有 个。两人轮流操作：每次可以选择一堆减少 个石子；或者选择 为偶数的堆，将其变成 堆为 的石子。无法操作者失败，问先手是否存在必胜策略。
Hint
注意到每堆石子关系独立。
sol
博弈论；每堆石子关系独立；计算 SG 。
注意到每堆石子关系独立。
考虑计算 SG 函数。
\operatorname{mex}\{SG(x-1),SG(\frac{x}{2})\},&x\bmod 2=0\text{ and }k\bmod2=1\\
\operatorname{mex}\{SG(x-1),0\},&x\bmod 2=0\text{ and }k\bmod2=0\end{cases}$$
观察 SG 的性质即可快速求得。 注意到每堆石子关系独立。
考虑计算 SG 函数。
Problem
给定一棵 个节点的树，最开始只有根节点是白色的，其余节点都为黑色。两人轮流进行操作，不可操作者输。
操作指选择一个白色的非叶子节点，将其染黑，并将其至少一个儿子染白（可以不止一个）。
询问先手是否存在必胜策略。
。
操作指选择一个白色的非叶子节点，将其染黑，并将其至少一个儿子染白（可以不止一个）。
询问先手是否存在必胜策略。
。
HintA
考虑在树上求 SG 。
定义 SG(x) 为以 x 构成的子树的游戏的 SG ，目标为 SG(Root) 。
定义 SG(x) 为以 x 构成的子树的游戏的 SG ，目标为 SG(Root) 。
HintB
观察 SG 函数的性质。
sol
博弈论；树上SG；利用 SG 函数的性质优化转移。
考虑在树上求 SG 。
定义 SG(x) 为以 x 构成的子树的游戏的 SG ，目标为 SG(Root) 。
显然 SG 函数为儿子集的子集异或和组成的集合的 Mex ，具体来说：
转移时间复杂度太高。
打表/数学归纳法/线性基知识，都可以发现一个关键性质：对于所有 ， 一定是 或者 的非负整数次幂。
于是转移优化为 ，就做完了。
考虑在树上求 SG 。
定义 SG(x) 为以 x 构成的子树的游戏的 SG ，目标为 SG(Root) 。
显然 SG 函数为儿子集的子集异或和组成的集合的 Mex ，具体来说：
转移时间复杂度太高。
打表/数学归纳法/线性基知识，都可以发现一个关键性质：对于所有 ， 一定是 或者 的非负整数次幂。
于是转移优化为 ，就做完了。
动态规划
图论
其他
相关推荐
评论
共 0 条评论，欢迎与作者交流。
正在加载评论...