【题解】一本通例题 S-Nim

\(\color{purple}{Link}\)

\(\text{Solution:}\)

这个题就是给\(Nim\)游戏做了一个限制。

考虑一下\(\text{SG}\)函数：给定的局面下对应的\(SG\)函数值，若\(=0\)则必败。

又有：许多子游戏组成的一个游戏的\(SG=\text{xor}_{i=1}^n SG_i.\)

那么对于这个题，第一次的想法是对于每一个子游戏求一下是不是必胜。这显然是一个对\(SG\)函数了解不足的问题。

那么考虑一下如何求\(SG\)函数：

\(SG(0)=0\)显然。那么对于后面的数，由于\(s,k\)都很小，我们可以暴力枚举求\(SG.\)

求出\(SG\)之后，剩下的就是处理询问：\(m\)个局面，把每个局面的\(a_i\)异或起来，\(0\)为必败，输出答案即可。

#include<bits/stdc++.h>

using namespace std;

int k,s[500],m,n;

int f[10002];

int main(){

	while(1){

		scanf("%d",&k);

		if(!k)return 0;

		int mx=-1,mi=(1<<30);

		string Ans="";

		for(int i=1;i<=k;++i)scanf("%d",&s[i]),mx=max(mx,s[i]),mi=min(mi,s[i]);

		sort(s+1,s+k+1);

		for(int i=0;i<=10000;++i){

			bitset<100001>vis;

			for(int j=1;j<=k;++j){

				if(i<s[j])break;

				vis[f[i-s[j]]]=1;

			}

			for(int j=0;j<=mx+1;++j)if(vis[j]!=1){f[i]=j;break;}

		}

		scanf("%d",&m);

		for(int i=1;i<=m;++i){

			scanf("%d",&n);

			int x,sg=0;

			for(int j=1;j<=n;++j){

				scanf("%d",&x);

				sg^=f[x];

			}

			if(!sg)cout<<'L';

			else cout<<"W";

		}

		cout<<endl;

	}

	return 0;

}

巴特西

【题解】一本通例题 S-Nim

最新文章

热门文章