题解P6585【中子衰变】
xuanxuan001
·
·
题解
第 3^2 篇题解了
一道月赛题为什么这么冷门啊，博弈论这么不受欢迎吗
正文
稍加分析可以发现这题最后的局面一定是连续的一些质子\电子，空一个，一些电子\质子，空一个，……，一些质子\电子。所以说要控制的就是空的位置的数量，而与此直接关联的就是端点上的（就是第一个和第 $n$ 个，下同）粒子（显然不会是中子）的类型是否相同。同时，与端点相邻的两个粒子（即第二个和第 $n - 1$ 个）也与胜负有关。因为选择了它们就等于决定了与它们相邻的端点粒子的种类。所以如果一个人更改了两边的 4 个粒子，那么另一个人就会立即更改另一端的粒子来让自己赢。所以说除非迫不得已，没有人会更改两边的 4 个粒子。
所以问题就变成了中间的 $n - 4$ 个粒子，你只要做到你操作了这 $n - 4$ 个粒子中的最后一个可操作的即可，那么就与前面的 $n$ 个粒子的情况一样了。
因此可以不断减小规模直到 $n \le 4$。
这时我们把最边上的 4 个粒子分为一组，较靠里的 4 个分一组，再往里的 4 个再分一组，直到最中间的那 4 个不到分为一组。
>特别地，**如果全部中子最后变成了同种粒子，那么后手获胜。**
通过手玩可以发现 $n$ 为奇数时也要选择后手，这时我们要把端点的粒子变成不同种，否则就让他整个都是同种。
首先，如果交互库没有操作正中间的粒子，那么我们可以直接操作那一组的另一边的粒子为另一类，此时交互库操作的这一组以及更靠里的若干组构成的这个区间你就必胜了（即如果只有这个区间里的粒子你就可以保证获胜了，将这个区间命名为“必胜区间”）。就可以直接跳过下面的两段了。
如果他选了正中间，那么我们就记住它把那个粒子变成了什么，设它变成了 $c$。然后从里到外将每组粒子中左边的两个中的一个变为 $c$。如果下面
1. 交互库没有操作这一组右边的那两个粒子，就直接将这一组靠右的那两个粒子变为 $a$ 的另一种粒子。然后这一组以及更靠里的若干组构成的这个区间就是“必胜区间”了。
1. 否则，如果交互库将粒子变为 $a$ 的另一种粒子，那么情形也与第一种情况一样了，然后你只要找到一个在这个区间里的另一个可操作的粒子进行操作即可。
1. 否则继续操作。
如果从始至终一直都是第一个情况的话，那么此时每组的左右两部分都各有一个粒子被变成了 $c$。所以任意一个粒子都要么被变成了 $c$，要么与一个 $c$ 相邻。所以最后就一定会是全部为 $c$，你胜。
否则接下来如果交互库选择了
1. 如果它选择了在你的“必胜区间”里的粒子，那么你也一定可以在你的区间里再选一个。
1. 否则，你只要把相应组的另一端的粒子改成相反的粒子并更新“必胜区间”即可。
好吧，然后你就胜了。
应该也没啥好说的了。
代码
-
```
#include<cstdio>
#define Ty int
#define MAXN 1026
#define FOR(i,a,b) for(Ty i=a;i<=b;i++)
#define fOR(i,a,b) for(Ty i=a;i<b;i++)
#define ROF(i,a,b) for(Ty i=a;i>=b;i--)
#define rOF(i,a,b) for(Ty i=a;i>b;i--)
using namespace std;
const Ty INF=2e6;
typedef long long ll;
typedef unsigned long long ull;
Ty abs(Ty a){return a<0?-a:a;}
Ty maxn(Ty a,Ty b){return a>b?a:b;}
Ty minn(Ty a,Ty b){return a<b?a:b;}
Ty qr(){
char ch=getchar();Ty x=1,s=0;
while(ch<'0'||ch>'9'){if(ch=='-')x=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
return x*s;
}Ty n,c,x,y,in,tmp,a[MAXN];
Ty ara(Ty a){if(a%2==0)a--;return a;}//求所在的组（返回所在组的最左边的粒子编号）
void chang(Ty x,Ty y){printf("%d %d\n",x,y);fflush(stdout);a[x]=y;}
void js(Ty x){//寻找可操作位置并直接修改（从 x 开始找）
FOR(i,x,n){
if(a[i])continue;
if(a[i-1]!=-1&&a[i+1]!=-1){chang(i,1);break;}
if(a[i-1]!=1&&a[i+1]!=1){chang(i,-1);break;}
}
}bool can(){//判断游戏是否结束（即有没有可操作粒子）
FOR(i,1,n){
if(a[i])continue;
if(a[i-1]==a[i+1])return true;
if((a[i-1]&a[i+1])==0)return true;
}return false;
}
int main(){
n=qr();qr();tmp=ara(n+1>>1);
printf("1\n");fflush(stdout);
if(n&1){
x=qr();a[x]=c=qr();//讨论交互库的第一次操作
if(x==n+1>>1){
for(tmp-=2;tmp>0;tmp-=2){//从里到外操作每一组
chang(tmp,c);
x=qr();y=a[x]=qr();
in=minn(x,n-x+1);
if(in<tmp){
tmp=ara(in);
if(x==tmp||x==tmp+1)chang(n-tmp+1,-y);
if(x==n-tmp+1||x==n-tmp)chang(tmp,-y);
break;
}if(in>tmp+1){js(tmp);break;}if(c^y){//第二种
if(y==n-tmp+1)chang(n-tmp,c);
else chang(n-tmp+1,c);
break;
}
}if(tmp<0)js(tmp=1);
}else{
tmp=ara(in=minn(x,n-x+1));
if(x==tmp||x==tmp+1)chang(n-tmp+1,-c);
if(x==n-tmp+1||x==n-tmp)chang(tmp,-c);
}
while(can()){
x=qr();y=a[x]=qr();
in=minn(x,n-x+1);
if(tmp<=in)js(tmp);//第一种
else{//第二种
tmp=ara(in);
if(x==tmp||x==tmp+1)chang(n-tmp+1,-y);
if(x==n-tmp+1||x==n-tmp)chang(tmp,-y);
}
}
}else{
while(can()){
x=qr();y=a[x]=qr();
chang(n-x+1,y);
}
}return 0;
}
```
这个交互库只考察了主要的策略，结果我第一次 A 的代码都有小漏洞，现在这个代码还是审核前改的，也不知道还有没有错，所以要是有人发现还有问题就在评论区发一下吧，谢谢。