P8382

· · 题解

题意：

题目传送门

P8382

每个棋子都是单项移动的，可以看出此题是一个阶梯博弈。

思路：

看一眼数据范围 n\le 10^6,暴力使用 sg 函数可过，但 m\le 10^9 是什么鬼啊！数组开不下啊！考虑离散化操作。

相邻的几个棋子到终点的距离相等，可以看作一个位置。

间隔为奇数的两个点，可以看作两个相邻的位置。

间隔为偶数的两个点，可以看作两个相邻的同奇偶位置，即两者之间有一个间隔。

那么如何计算先手有多少个必胜的第一步呢？

阶梯博弈的胜负判断是把所有 i 为奇数的 sg_i 异或起来。若异或和为 0，则先手无必胜操作，若不为 0，则先手有必胜操作。

当先手必胜时当且仅当先手操作后留下的局面是先手必败，即异或和为 0。

那么计算时只需枚举每一个奇数位，判断其减少是否能使异或和为 0。若能答案加一。

if((sg[i]^check)<sg[i]) ans++;      //check记录异或和

再枚举每一个偶数位，判断其使下一位即奇数位增加是否能使异或和为 0。若能答案加一。

if(i<tot&&(sg[i]^check)>sg[i]&&sg[i+1]>=(sg[i]^check)-sg[i]) ans++;     //tot为位置总数

注意到一点，间隔为奇数的两个棋子不能直接当成相邻的两点。

只有间隔为一的两点才能，而其他的应视为间隔为二的两个位置。

这样 sg 数组最大只需开到 3n，空间问题就解决了。

然后这题就做完了。

还有一个细节需要考虑，若有棋子一步便可获胜，那么先手必须一步获胜，这里需要特判。

if(a[n]==m-1) for(int i=n; i&&a[i]==m-n+i-1; i--) ans++;

以下是完整代码，时间复杂度为 O(n)。

code

#include <bits/stdc++.h>
using namespace std;
bool f1;
int m,n,ans;
int a[1000005];
int sg[3000005],tot;
int check;
bool f2;
int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||'9'<ch){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while('0'<=ch&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch&15);
        ch=getchar();
    }
    return x*f;
}
int main(){
//  printf("%.8lfMB\n",(&f2-&f1)/1024.0/1024.0);
    m=read(),n=read();
    for(int i=1; i<=n; i++) a[i]=read();
    if(a[n]==m-1) for(int i=n; i&&a[i]==m-n+i-1; i--) ans++;
    else{
        a[n+1]=m-1;
        for(int i=n; i; i--){
            if(a[i]==a[i+1]-1) sg[tot]++;
            else if(a[i]==a[i+1]-2) sg[++tot]=1;
            else if((a[i+1]-a[i]-1)&1) tot+=3,sg[tot]=1;
            else tot+=2,sg[tot]=1;
        }
        for(int i=1; i<=tot; i+=2) check^=sg[i];
        if(check){
            for(int i=1; i<=tot; i+=2){
                if((sg[i]^check)<sg[i]) ans++;
                if(i<tot&&(sg[i]^check)>sg[i]&&sg[i+1]>=(sg[i]^check)-sg[i])
                    ans++;
            }
        }
    }
    printf("%d\n",ans);
}