题解：P8382 [POI 2004] Gra

fish_love_cat · 2026-05-11 15:53:16 · 题解

我必须指出我完全不会博弈论。

最后一格谁到谁赢，等价于倒数第二格谁到谁输，于是变成丢掉倒数两格一路向后跑，谁不能操作谁输。

序列移动，常见的刻画方式是对点做差分，把两个点中间的看成石头堆，然后当成阶梯 nim 来做。

然后你发现这题这么刻画有大问题，这个移动方式非常恶心。

注意力大爆发！我们考虑把图翻过来考虑，把原图中有石子的点看成空，没石子的点看成有石子。

然后原先这个长的像跳棋一样的移动方式，经过反转后变成，原先的落点是被向前移动的石子移动前的位置，而原先的起点是被向前移动的石子移动后的位置。

此时我们发现这个东西变成了标准的序列移动的形状。

于是套差分和阶梯 nim 即可。蚌埠住了拼尽全力没发现这一块。

统计第一步的话，注意到走偶数位置的石子也可以扔给对面必败状态，只需要加点加到符合条件即可。

#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int main(){
    int n,m;
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    reverse(a+1,a+1+n);
    if(a[1]==m-1){
        for(int i=1;i<=n;i++)
        if(m-i!=a[i]){
            cout<<i-1;
            return 0;
        }
        cout<<n;
        return 0;
    }
    for(int i=1;i<=n;i++)
    a[i]=m-1-a[i];
    vector<int>v;
    vector<pair<int,int>>v2;
    int sum=0,lst=0,qwq=0;
    int flc=0;
    bool flg=0;
    for(int i=1;i<=n;i++){
        if(a[i]==lst+1)qwq++;
        else{
            if(sum&1)
            v.push_back(qwq),flc^=qwq;
            else if(sum){
                if(flg&&!v.empty())
                v2.push_back({qwq,*v.rbegin()});
                else v2.push_back({qwq,0});
            }
            qwq=1;
            sum+=a[i]-lst-1;
            flg=a[i]-lst-1==1;
        }
        lst=a[i];
    }
    if(sum&1)
    v.push_back(qwq),flc^=qwq;
    else{
        if(flg&&!v.empty())
        v2.push_back({qwq,*v.rbegin()});
        else if(sum)v2.push_back({qwq,0});
    }
    int ret=0;
    for(int i:v)
    ret+=i>(flc^i);
    for(pair<int,int>i:v2)
    ret+=(flc^i.second)>i.second&&(flc^i.second)<=i.first+i.second;
    cout<<ret;
    return 0;
}
//「差不多该停止了吧，妮戈兰。」

// 欧黛用责备似的声音说道。
// 妮戈兰转过头，鼓起了脸颊。

//「……真是的，有事等一下再说。
// 现在可是关系到这孩子愿不愿意再次亲近我的重要时刻。
// 要是被这孩子讨厌的话，我可是绝对不会原谅学姊你的喔。」

//「我知道，所以我觉得该把这件事告诉你比较好。」
//「什么事？」

//「那孩子好像快不行了。」