HDU1536/POJ2960 S-Nim

题目大意

有一个集合$S$，其元素个数为$k$。两个人玩$m$轮游戏，每轮游戏有$n$堆石子，每次游戏两个人轮流在这$n$堆石子中选一堆，从这一堆中取走若干个石子，取走石子的个数必须为$S$集合中的一个元素的值。双方都采用最优策略，问先手是否必胜。必胜则输出$W$，否则输出$L$。

有多组数据。

数据范围

1≤k≤100,1≤si≤100001\\leq k\\leq 100,1\\leq s_i\\leq 100001≤k≤100,1≤si​≤10000

1≤m≤100,1≤n≤100,0≤ai≤100001\\leq m\\leq 100,1\\leq n\\leq 100,0\\leq a_i\\leq 100001≤m≤100,1≤n≤100,0≤ai​≤10000

题解

假设只有一堆石子，令sgisg_isgi​表示这一堆中有$i$个石子时的状态，则有

sgi=mex{sgi−j∣j∈S}sg_i=mex\\{sg_{i-j}|j\\in S\\}sgi​=mex{sgi−j​∣j∈S}

初始值sg0=0sg_0=0sg0​=0

像这样，用一个背包就能够将一堆石子的$sg$值可以求出。

因为$k$堆石子的$sg$值就是各堆石子的$sg$值的异或和，所以我们将各堆石子的$sg$值求异或和，如果异或和为$0$，则先手必败，否则先手必胜。

时间复杂度为$O(\sum (k+\sum n))$。

code

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
int k,T,n,ans,s[105],sg[10005],z[10005];
int main()
{while(scanf("%d",&k)&&k){for(int i=1;i<=k;i++){scanf("%d",&s[i]);}sort(s+1,s+k+1);for(int i=1;i<=10000;i++){for(int j=1;j<=k;j++){if(i-s[j]<0) break;z[sg[i-s[j]]]=1;}int x;for(x=0;z[x];x++);sg[i]=x;for(int j=1;j<=k;j++){if(i-s[j]<0) break;z[sg[i-s[j]]]=0;}}scanf("%d",&T);while(T--){scanf("%d",&n);ans=0;for(int i=1,x;i<=n;i++){scanf("%d",&x);ans^=sg[x];}if(ans) printf("W");else printf("L");}printf("\\n");}return 0;
}