题目大意

一片森林。 每颗树有两个系数n和k，表示这颗树有n个节点，第i个节点父亲为第max(1,i/k)个节点。 两人进行游戏，每次可以删除一颗树（该数必须存在非叶子）或树中一个叶子，无法操作者输。 叶子的定义是度数为1的节点。 求先手是否必胜。

结论

考虑一颗大小为n的树，n=1sg值为1，n=2sg值为0，那么n>2呢？ 有两种决策：减到n-1，或者直接变没（一定存在非叶子） sg(n)=mex{sg(n-1),0} 可以得到结论n为奇数时sg为1否则为2。 有了sg就很容易算先手是否必胜了。

#include<cstdio> #include<algorithm> #define fo(i,a,b) for(i=a;i<=b;i++) using namespace std; int i,j,k,l,t,n,m,ca; int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); } return x*f; } int main(){ ca=read(); while (ca--){ n=read(); t=0; fo(i,1,n){ j=read();k=read(); if (j==1) t^=1; else if (j>2){ if (j%2==1) t^=1; else t^=2; } } if (t) printf("BOB\n");else printf("BEN\n"); } }