题目链接
后手必胜 (先手必败, P-position) 当且仅当 n 堆石子数异或和为 0
首先 0 一定是 P-position,
假设 a1^a2^a3^...^an=K
若 K!=0, 则一定可以找到一个 ai,ai 在 K 的最高位的 1 上为 1, 显然 ai > ai^K, 那么可以把 ai 变成 ai^K, 局面就成了 a1^a2^...^an^ai^K = K^K = 0 (后手就处于 P-position)
若 K==0, 至少取一个显然不能使 K 仍为 0
- #include <cstdio>
- #include <cctype>
- #define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
- const int MAXIN=1e6;
- char IN[MAXIN],*SS=IN,*TT=IN;
- inline int read()
- {
- int now=0;register char c=gc();
- for(;!isdigit(c);c=gc());
- for(;isdigit(c);now=now*10+c-'0',c=gc());
- return now;
- }
- int main()
- {
- int t=read(),n,res;
- while(t--)
- {
- n=read(), res=0;
- while(n--) res^=read();
- puts(res?"Yes":"No");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2505933.html