盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码
  5. 更新日志

HDU 4994 Revenge of Nim(博弈)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=4994

题意

有n堆石头,从左往右排列,每堆石头有ai个石头(ai>0)。现在两个人轮流取石头,规定每次只能从最左边的一堆取若干个(可以取完,最少取一个)。问先手赢还是输?

思路

假设当前堆的石头个数大于1,那么这个人必赢。因为除了这堆、剩下的如果为必败态,那么可以将这堆取完,让对手面临必败态,反之,可以取到只剩下一个,然后让对手取一个石头,自己面临必胜态。注意有可能全是1的情况

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#define pb push_back
#define debug puts("=====================");
using namespace std;
int t, n, a[1111];
int main () {
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
int x = 1111;
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
if (a[i] != 1) x = min(i, x);
}
if (x == 1111) {
if (n % 2) puts("Yes");
else puts("No");
}
else if (x % 2) puts("Yes");
else puts("No");
}
return 0;
}

更新日志

  • 14346124 2015-08-04 21:34:58 Accepted 4994 15MS 1576K 569 B G++ SIO__Five