1 条题解
-
1
题目描述
两个人轮流取石子,每人每次可以取 1 到 个石子,最后取完石子的人为负。问最终谁会赢。
具体思路
特判情况:
- 若堆数不为 1 且每堆数量都为 1,若有奇数堆,先手必败,否则,先手必胜。
- 若堆数不为 1 且只有一堆不是 1,若有奇数堆,那堆先手拿剩一个,若有偶数对,那堆先手拿完。都可以转化为第一种情况,先手必胜。
一般情况:
- 若异或和为 0,无论怎么取,对方总能让你异或和为 0,先手必败。
- 若异或和不为 0,首先可以保证对方异或和为 0。
考虑先手状态:
- 偶数个 1,先手必胜。
- 奇数个 1,那么对方取之前异或和一定不为 0(可以手模),不成立。
- 特判情况 2,先手必胜。
综上所述,若异或和不为 0,先手必胜。
Code
#include<bits/stdc++.h> using namespace std; const int N=51; int a[N]; int main(){ int t;scanf("%d",&t); while(t--){ int n,ans=0,sum=0;scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); ans=ans^a[i]; sum=sum+a[i]; } if(sum==n){ if(n&1)puts("Brother"); else puts("John"); } else{ if(ans)puts("John"); else puts("Brother"); } } return 0; }
- 1
信息
- ID
- 1022
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 1
- 标签
- (无)
- 递交数
- 31
- 已通过
- 26
- 上传者