知识储备:
Anti-SG 游戏和 SJ 定理
[定义](anti-nim 游戏)
桌子上有 N 堆石子,游戏者轮流取石子。
每次只能从一堆中取出任意数目的石子,但不能不取。
取走最后一个石子者败。
[结论]
先手必胜当且仅当:
(1)所有堆的石子数都为 1 且游戏的 SG 值为 0;
(2)有些堆的石子数大于 1 且游戏的 SG 值不为 0。
叶子节点的 SG 值为 0;中间节点的 SG 值为它的所有子节点的 SG 值加 1 后的异或和。
只能说入门时候的搜索是硬伤Orz,写个Dfs都得参考
更严谨的代码(考虑到输入顺序不一定从根节点到叶子结点):
#include<iostream>
#include<cstdlib>
#include<stdio.h>
#include<vector>
using namespace std;
vector<int>v[];
int dfs(int x,int pre)
{
int ans=;
for(int i=; i<v[x].size(); i++)
{
//printf()
if(v[x][i]!=pre)
ans^=(+dfs(v[x][i],x));
}
return ans;
}
int main()
{
int n,m,a,b;
while(scanf("%d",&n)!=EOF)
{
int ans=,cnt=;
while(n--)
{
scanf("%d",&m);
for(int i=; i<=m; i++)
v[i].clear();
for(int i=; i<m; i++)
{
scanf("%d%d",&a,&b);
v[a].push_back(b);
v[b].push_back(a);
}
int s=dfs(,-);
if(s>)cnt=;
ans^=s;
}
if((ans&&!cnt)||(!ans&&cnt))printf("PP\n");
else printf("QQ\n");
}
}