专栏文章

CF2157I

xxujindong_
CF2157I题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min0x4a3
此快照首次捕获于
2025/12/01 18:45
3 个月前
此快照最后确认于
2025/12/01 18:45
3 个月前
查看原文
首先对偶数的 mm，可以用巴什博弈的策略，(m+1)∣n(m+1)\mid n 时必败。下面假设 mm 是奇数。
我们计算每个状态 (n,ban)(n,ban) 是必胜态或必败态，banban 为上一次取的数量。注意到对于一个 nn，要么总是必败态，要么只有不超过一个 banban 是必败的。从前往后考虑，遇到一个必败的 nn，则 n+ban(1≤ban≤m)n+ban(1\leq ban\leq m) 只有 (n+ban,ban)(n+ban,ban) 可能失败。遇到一个必败的 (n,ban)(n,ban)，则 n+bann+ban 只有 (n+ban,ban)(n+ban,ban) 可能失败。
考虑一个必败的 nn 会造成什么影响。首先对 n+1≤n′≤n+mn+1\leq n'\leq n+m，只有 (n′,n′−n)(n',n'-n) 可能失败。对于 n+m+1n+m+1，要赢必须跳到 (n+m+12,m+12)(n+\frac{m+1}2,\frac{m+1}2)，否则对方可以跳到 nn，因此 (n+m+1,m+12)(n+m+1,\frac{m+1}2) 必败。若 n+m+1n+m+1 不是全部必败，可推出 n+m+2n+m+2 全部必败，因为跳到 n+m+1n+m+1 或 [n+1,n+m][n+1,n+m] 都输。
我们考虑求出每个 mm 的所有必败的 nn，因为相邻两个必败的 nn 距离 m+1m+1 或 m+2m+2，数量是 O(mlog⁡m)O(m\log m) 的。
设上一个必败的 nn 是 nin_i，尝试对 ni+m+1n_i+m+1 找一个必胜策略。令 f(n)f(n) 表示 nn 不能走到上一个必败的 nin_i 还能不能赢，有三种办法：走到 n+ni2\frac{n+n_i}2、走到 n+ni−12\frac{n+n_{i-1}}2、走到 ni−1n_i-1，其中第三种因为 ni−1n_i-1 必败可能是 ni−ni−1=m+1n_i-n_{i-1}=m+1 时 (ni−1,m)(n_i-1,m)，或 ni−ni−1=m+2n_i-n_{i-1}=m+2。前者被第二种情况覆盖，后者因为 ni−1−m+1n_{i-1}-m+1 不必败，只有 (ni−1,m+12)(n_i-1,\frac{m+1}2) 必败，因此可 O(1)O(1) 判断。直接递归即可。
这个递归次数是难以计算的，10610^6 时最大递归次数是 13391339 次，但平均递归次数约为 5.1875.187，因为两次递归发生的概率不高，而且也是比较随机的，可以通过。
CPP
#include<bits/stdc++.h>
using namespace std;
int t,n,m;
vector<int>p[1000005];
bool calc(int n,int m,int pos){
  return n<m||(~(n-p[m][pos])&1&&!calc((n+p[m][pos])/2,m,pos))||(pos&&((p[m][pos]==p[m][pos-1]+m+2&&n-p[m][pos]==(m-1)/2)||(~(n-p[m][pos-1])&1&&n-p[m][pos-1]<=2*m&&!calc((n+p[m][pos-1])/2,m,pos-1))));
}
int main(){
  for(int i=3;i<=1000000;i+=2){
    p[i].push_back(0);
    while(p[i].back()<=1000000)p[i].push_back(p[i].back()+i+1+calc(p[i].back()+i+1,i,p[i].size()-1));
  }
  cin>>t;
  while(t--)cin>>n>>m,puts((m&1?!binary_search(p[m].begin(),p[m].end(),n):n%(m+1))?"Yes":"No");
  return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...