Bash Game-Plus
Bash Game-Plus 洛谷
题目描述
巴什博弈：有一堆 \(n\) 个物品，两名玩家轮流从中拿取物品。每次至少拿 \(1\) 个，至多拿 \(m\) 个，不能不拿，最终将物品拿完者获胜。
我们给这个游戏增加一些规则：
有一堆 \(n\) 个物品，甲和乙轮流从中拿取物品，甲先拿。每次至少拿 \(1\) 个，至多拿 \(m\) 个，最终将物品拿完者获胜。
现在新加入一条规则：也可以不拿，但每当有一名玩家选择不拿物品时，接下来的 \(k\) 次操作中两名玩家都不可以不拿。
举个例子，当 \(k=3\) 时，如果甲在某一次操作中没有拿物品，那么接下来乙、甲、乙三轮都必须拿至少 \(1\) 件物品。然后又轮到甲了，这次甲就可以再次选择不拿。
甲乙两人一共进行了 \(t\) 次游戏。对于每次游戏，你需要告诉甲他有没有必胜策略。
输入格式
第一行两个正整数 \(t,op\)。\(op=1\) 时取消新增加的规则，但是也需要正常读入 \(k\)。
接下来的 \(t\) 行，每行三个正整数 \(n,m,k\)。
输出格式
对于每轮游戏，如果甲有必胜策略，那么输出 Yes。否则输出 No。
样例输入
6 0
2 2 2
3 2 2
4 2 2
7 2 3
13 2 6
14 2 6
样例输出
Yes
Yes
No
Yes
Yes
No
提示
对于所有数据：\(t\le10^5\)，\(1\le n,m,k\le10^{18}\)
分析题目，如果去掉了 \(k\) 这个限制，那么就会变成一个大家很熟悉的问题。
这个问题的结论如下（知道的可以跳过）。
若 \((m+1)\mid n\)，先手必败，否则先手必胜。
策略就是两个人每次拿到的和都为 \((m+1)\)，先手肯定拿了前半段，后手拿了后半段。
这样整个 \(n\) 就被分成了若干个 \((m+1)\) 段。
如果刚好整除，那么说明后手拿了最后一段的后半段，这肯定拿到了最后一个，所这个时候以先手必败。
先手必胜只需要一开始拿走 \(n\mod (m+1)\) 即可。
那么添加回 \(k\) 这个限制，接着便要尽可能的靠近上面的思路。
我们知道，先手在某一次不拿以后，肯定要过了 \(\lfloor \frac{k}{2} \rfloor\) 回才能再一次使用。
而过的这 \(\lfloor \frac{k}{2} \rfloor\) 回可以直接用前面的策略，也就是这些回每一回都会被拿走 \((m+1)\) 个物品。
接着我们便可以把 \(n\) 分成若干个 \((\lfloor \frac{k}{2} \rfloor) \times (m+1)\) 段。
但实际上并不是，首先我们必须清楚，在前面的问题里，分成若干个 \((m+1)\) 段是因为这些在下一次的选择权都在先手手上，而这个分段下一次的选择权却在后手手上。
所以我们把 \(n\) 分成若干个 \((\lfloor \frac{k}{2} \rfloor) \times (m+1)+1\) 段，这样每一段保证了先手必败，也有下一次的选择权。
接着便可以用 \(n\mod ((\lfloor \frac{k}{2} \rfloor) \times (m+1)+1)\)，如下判断即可。
如果模数小于等于 \(1\)，可以直接判断，如果模数为 \(1\) 那么先手必胜，否则必败。
如果模数大于 \(1\)，那么这不就是 \(k> n\) 的情况吗，模一下 \((m+1)\) 再判断等不等于 \(1\) 即可。
小证明：
如果最后模数为 \(0\)，那么一来就不取，根据一开始的结论，且我方为后手，所以必胜。
如果最后模数大于 \(1\)，那么一来先取一个，剩下的肯定不能被整除，且我方为接下来的后手（以剩下的为视角），理论上必败，但是还有一次不取的机会。
如果对方不取，那么我方变为先手（以不取过后，剩下的为视角），又因为不能整除，所以必胜。
如果对方要取，为了获胜，对方肯定会将剩下的数变为 \((m+1)\) 的倍数，此时选择不取，因为剩下的数为 \((m+1)\) 的倍数，且我方为后手（以不取过后，剩下的为视角），所以必胜。
这样你也知道为什么 \(1\) 不行了吧。
那么代码自然就出来了，时间复杂度 \(O(t)\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
void print(int x){
if(x) printf("Yes\n");
else printf("No\n");
return ;
}
signed main()
{
int t,op;scanf("%lld%lld",&t,&op);
while(t--){
int n,m,k;scanf("%lld%lld%lld",&n,&m,&k);
if(op) print(n%(m+1));
else if(k==1) print(1);
else{
__int128 round=(__int128)(m+1)*(k/2)+1;//这玩意竟然需要开__int128
int check=n%round;
if(check>1) check%=m+1,check=(check!=1);
print(check);
}
}
return 0;
}
一个你可能问的问题：为什么偏偏选择了 \(1\) 呢？
如果选择了其它的数，那么可能会导致大于等于 \((m+1)\)，而 \(1\) 则没有这种烦恼。