自动搬运

查看原文

来自洛谷，原作者为

	P_Bisector 天天爱打卡？

搬运于2025-08-24 22:22:11，当前版本为作者最后更新于2025-08-20 11:47:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

奇偶分析入门题。

先给出结论：后手必胜。

$n$ 为偶数的时候直接走与对方相对称的位置即可。以下只分析 $n$ 为奇数的情况。

正文

考虑所有可以填放的位置全部被填满的情况。

• 如果有偶数个位置被填放，后手获胜。
• 如果有奇数个位置被填放，那么除非所有位置电荷相同，否则先手获胜。

我们考虑所有无法放置的位置，显然这个位置两侧的电荷不等，也就是说，如果我们从左往右看，那么每个无法放置的位置意味着电荷的反转。

由于我们希望有偶数个位置被填放，即奇数个位置无法放置，那么电荷一定被反转奇数次，因此首尾两个位置的电荷必不相同，否则所有电荷均相同。相反地，对手一定希望首尾两个位置的电荷相同。

于是我们发现两人都不希望走到边缘的四个位置，一旦走到这四个位置，除非当后手走的时候其他位置已经做到所有电荷均相等，否则必败。

那么为了逼迫对手走到这四个位置，我们需要构造使得第三个和倒数第三个位置的电荷相反，易证此时中间一定恰好填了偶数个位置，此时对手行棋，其必败。

归纳分析可以发现，假设所有电荷都位于 $[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[代码如下]

#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;
}

::::