题解：P6585 中子衰变
P_Bisector
·
·
题解
奇偶分析入门题。
先给出结论：后手必胜。
# 正文
考虑所有可以填放的位置全部被填满的情况。
- 如果有偶数个位置被填放，后手获胜。
- 如果有奇数个位置被填放，那么除非所有位置电荷相同，否则先手获胜。
我们考虑所有无法放置的位置，显然这个位置两侧的电荷不等，也就是说，如果我们从左往右看，那么每个无法放置的位置意味着电荷的反转。
由于我们希望有偶数个位置被填放，即奇数个位置无法放置，那么电荷一定被反转奇数次，因此首尾两个位置的电荷必不相同，否则所有电荷均相同。相反地，对手一定希望首尾两个位置的电荷相同。
于是我们发现两人都不希望走到边缘的四个位置，一旦走到这四个位置，除非当后手走的时候其他位置已经做到所有电荷均相等，否则必败。
那么为了逼迫对手走到这四个位置，我们需要构造使得第三个和倒数第三个位置的电荷相反，易证此时中间一定恰好填了偶数个位置，此时对手行棋，其必败。
归纳分析可以发现，假设所有电荷都位于 $[l,n+1-l]$ 这个区间中，那么只要构造两端电荷不同或者所有电荷相同即可胜利。
以下给出具体策略：
游戏开始时，设 $l=\frac{n+1}{2}$，设 $r$ 恒等于 $n+1-l$。
- 如果先手行棋在 $[l,r]$ 内：
- 如果 $[l,r]$ 区间未满（可以行棋），任选区间内的一个点进行行棋；
- 如果 $[l,r]$ 区间已满（无法行棋），由于此时为后手行棋，必然是 $l,r$ 两处电荷相同。由于我们前面保证此状态下区间内电荷都相同，于是我们选择在 $r+1$ 处行棋。此时，由于 $[l-1,r+1]$ 范围内只有一个位置没有电荷并且其右侧有电荷，因此对方无法破坏区间内电荷相同的条件。
- 如果先手行棋在 $[l,r]$ 外，设其行棋位置为 $x$：
- 如果可以在 $n+1-x$ 处填与之相反的电荷，则填入；
- 如果不可以在 $n+1-x$ 处填与之相反的电荷，易证 $x=l-1$ 或 $x=r+1$。分析 $x=l-1$ 的情况。此时显然不满足 $l$ 和 $r$ 两处相反，因此一定是区间内所有电荷均相等。为了保持阵型，在 $[l,r]$ 中任选一个点行棋。
::::info[代码如下]
```cpp
#include<bits/stdc++.h>
#define B7 __int128
#define pb push_back
#define PLL pair<int,int>
#define U6 unsigned long long
#define f first
#define s second
#define Qin ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;void solve();void init();
void file(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
int main(){Qin;init();int t,M=0;M?(cin>>t,0):t=1;while(t--)solve();return 0;}
#define int long long
const int inf=1e18,N_=100050,mod=998244353,P=1e9+7,N=1e6+50,N2=5050;
void init(){}
int a[N],n;
int check(){
for(int i=1;i<=n;i++){
// assert(a[i]==0||a[i]!=-a[i+1]);
if(a[i]==0&&(a[i-1]==0||a[i+1]==0||a[i-1]==a[i+1]))return 1;
}
return 0;
}
void evensolve(){
cout<<1<<endl;
while(check()){
int x,y;
cin>>x>>y;
a[x]=y;
cout<<n+1-x<<" "<<y<<endl;
a[n+1-x]=y;
}
}
void random_put(int x){
if(a[x-1]==0)cout<<x<<" "<<1<<endl,a[x]=1;
else cout<<x<<" "<<a[x-1]<<endl,a[x]=a[x-1];
}
int checkput(int x,int y){
if(a[x-1]!=-y&&a[x+1]!=-y&&a[x]==0){
cout<<x<<" "<<y<<endl;
a[x]=y;
return 1;
}
return 0;
}
int random_put(int l,int r){
for(int i=l;i<=r;i++){
if(checkput(i,1))return 1;
if(checkput(i,-1))return 1;
}
return 0;
}
void midsolve(){
int l=(n+1)/2,r=(n+1)/2,mid=(n+1)/2;
while(check()){
int x,y;
cin>>x>>y;
a[x]=y;
if(!check())return;
if(x<l||x>r){//不在范围内
l=min(l,min(x,n+1-x));
r=n+1-l;
if(!checkput(n+1-x,-y)){
random_put(l,r);
}
}else{
if(!random_put(l,r)){
r++,l--;
checkput(r,1);
checkput(r,-1);
}
}
}
}
void solve(){
cin>>n>>a[n+2];
if(n%2==0)return evensolve();
cout<<1<<endl;
midsolve();
return;
}
```
::::