[hackerrank]Bob and Ben

    xiaoxiao2021-12-12  7

    题目大意

    一片森林。 每颗树有两个系数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"); } }
    转载请注明原文地址: https://ju.6miu.com/read-900061.html

    最新回复(0)