「2018山东一轮集训」Game

%%神仙题

首先转化一波模型：可以把原问题看成，初始每个位置有0/1个石子，1操作看成从一个位置拿走一个石子，2操作看成从l[i]拿走一个石子，并在[ l[i]+1 , r[i] ]的每个位置放上一个石子。然后在这上面进行游戏，不能操作者输。。。。

为什么可以这么转化呢QWQ

最后显然每个位置都不能剩石子，不然是可以接着操作的。。。。。

然后如果一个位置有偶数个石子的话最后的nim和里是会消去的，所以符合了原位置是0就不能操作。。。

所以直接倒着推一遍nim和就好啦。。。

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<vector>

#define ll long long

using namespace std;

#define pb push_back

const int maxn=1e6+5;

vector<int> g[maxn];

int n,v[maxn],dc,sg[maxn],ans,m;

bool c[maxn];

inline int read(){

	int x=0; char ch=getchar();

	for(;!isdigit(ch);ch=getchar());

	for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';

	return x;

}

int main(){

//	freopen("game.in","r",stdin);

//	freopen("game.out","w",stdout);

	n=read(),m=read();

	for(int i=1;i<=n;i++) c[i]=read();

	int L,R;

	for(int i=1;i<=m;i++) L=read(),R=read(),g[L].pb(R);

	for(int i=n,now;i;i--){

		now=1,dc++;

		for(int j:g[i]) v[sg[i+1]^sg[j+1]]=dc;

		while(v[now]==dc) now++;

		sg[i]=now^sg[i+1];

	}

	for(int i=1;i<=n;i++) if(c[i]) ans^=sg[i]^sg[i+1];

	if(ans) puts("First");

	else puts("Second");

	return 0;

}

巴特西

「2018山东一轮集训」Game

最新文章

热门文章