题目链接在这里:
我们首先想到经典的取石子问题,考虑的是所有石子堆异或起来是不是0,如果为0就说明先手必败。这里面的逻辑和上一篇总结的博弈论基本规律是一样的,因为异或是相同为0,不同为1,因此如果异或和为0的话说明每一位上的1如果有人选了,那另一方一定能选一个对称的1。而本题中限制了先手必须选择哪个堆,我们就把其他的堆先异或和了,然后看当前堆能否转化为这个异或和,由结论,如果当前堆的个数大于异或和,那么一定能转化为异或和。
1 #include "bits/stdc++.h" 2 using namespace std; 3 const int MAX=1e5+5; 4 int t,n,k,a[MAX]; 5 int main(){ 6 int i,j,zt; 7 scanf("%d",&t); 8 while (t--){ 9 scanf("%d%d",&n,&k); 10 for (i=1;i<=n;i++) scanf("%d",&a[i]); 11 zt=0; 12 for (i=1;i<=n;i++){ 13 if (i==k) continue; 14 zt^=a[i]; 15 } 16 if (zt>=a[k]) cout<<"No"<<endl; 17 else cout<<"Yes"<<endl; 18 } 19 return 0; 20 }
标签:std,石子,int,scanf,博弈论,异或,栗酱 From: https://www.cnblogs.com/keximeiruguo/p/16901110.html