F - A Simple Game HDU - 1851----------------------思维(尼姆博弈+巴什博弈)

    科技2026-01-28  8

    题意: n堆物品,每堆至少取一个,最多取k个,谁先取完谁就获胜。

    解析: 巴什博弈:对于每堆物品,至少取一个,最多取k个,根据定义 n%(k+1) 尼姆博弈:根据巴什博弈公式 n%(k+1)的余数r (1<=r<=k) 那么就是说剩下来的至少取一个,或者不限取

    所以先根据巴什博弈求出余数,然后把所有余数异或起来,如果异或=0 说明是奇异局势,先手必败

    #include<bits/stdc++.h> using namespace std; int t; int n,x,y; int main() { scanf("%d",&t); while(t--) { scanf("%d",&n); int sum=0; int r=0; for(int i=1;i<=n;i++) { scanf("%d %d",&x,&y); r=x%(y+1); sum^=r; } if(sum==0) puts("Yes"); else puts("No"); } }
    Processed: 0.022, SQL: 9