自动搬运

查看原文

来自洛谷，原作者为

	Wanderer_01 **

搬运于2025-08-24 22:38:36，当前版本为作者最后更新于2023-08-16 13:42:26，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意：

题目传送门

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