YJC最近写了一篇关于游戏的论文。CJY看他那么喜欢游戏，决定出一道题考考他。 CJY给出了一种两个人玩的游戏。定义游戏规则如下：给一张n个点，m条边的有向无环图，每条边有颜色ci。在图上放了q颗石子，每颗石子在一个点上。每次操作时，选择一个有出边且点上有石子的点x，从点上取走一颗石子，然后选择一个颜色集合S，如果x的某条出边i的颜色 ，则在边i的终点上放上一颗石子。双方轮流操作，不能操作者负。CJY问YJC是先手胜还是后手获胜。YJC很轻松地解决了这个问题。CJY表示很不爽，于是他把数据范围放大了。YJC发现现在不会做了，于是他来向你求助。
经典博弈题！ 对于一个点怎么求sg呢？把相同颜色出边的sg异或在一起，那么就是做个线性基，看看不能被表示出的最小数。 容易从线性基角度理解出sg值一定是2的幂次。 于是用bitset做。 注意没有出边的点需要特判。
#include<cstdio> #include<algorithm> #include<bitset> //#include<ctime> #define fo(i,a,b) for(i=a;i<=b;i++) #define fd(i,a,b) for(i=a;i>=b;i--) using namespace std; const int maxn=200+10,maxm=5000+10; int h[maxn],go[maxm],dis[maxm],next[maxm]; int d[maxn],chu[maxn],dl[maxn]; struct dong{ int x,y; } b[maxm]; bitset<maxn> sg[maxn],a[maxn],zlt,emp; bool bz[maxn]; int i,j,k,l,t,n,m,q,tot,top,head,tail,now; void add(int x,int y,int z){ d[y]++; go[++tot]=y; dis[tot]=z; next[tot]=h[x]; h[x]=tot; } bool cmp(dong a,dong b){ return a.y<b.y; } void insert(){ int i; fd(i,n,0){ if (zlt[i]==1){ if (!a[i].any()){ a[i]=zlt; break; } else zlt=zlt^a[i]; } } } int main(){ freopen("game.in","r",stdin);freopen("game.out","w",stdout); scanf("%d%d",&n,&m); fo(i,1,m){ scanf("%d%d%d",&j,&k,&l); chu[j]++; add(j,k,l); } fo(i,1,n) if (!d[i]) dl[++tail]=i; while (head<tail){ now=dl[++head]; t=h[now]; while (t){ d[go[t]]--; if (!d[go[t]]) dl[++tail]=go[t]; t=next[t]; } } fd(i,tail,1){ now=dl[i]; if (!chu[now]) continue; fo(j,0,n) a[j].reset(); t=h[now]; top=0; while (t){ b[++top].x=go[t]; b[top].y=dis[t]; t=next[t]; } sort(b+1,b+top+1,cmp); fo(j,1,top){ if (b[j].y!=b[j-1].y){ if (j>1) insert(); zlt.reset(); } zlt=zlt^sg[b[j].x]; } insert(); fo(j,0,n) if (!a[j].any()) break; sg[now][j]=1; } zlt=emp; scanf("%d",&q); fo(i,1,q){ scanf("%d",&t); zlt=zlt^sg[t]; } if (!zlt.any()) printf("0\n");else printf("1\n"); //printf("%d\n",clock()); }