蒟蒻第一次打codeforces结果爆零….
今天早上看一下测试点发现原来是int存不下,我昨天怎么没发现呢!!!
题目大意
大概就是有两个人在玩选数游戏,Raze
先开始选择,他只能选择奇数位上的数,而Breach
只能选择偶数位上的数。
最后要保留一位数进行奇偶校验!
如果最后一位是偶数,那么Breach
赢,输出2
;如果最后一位是奇数,那么Raze
赢,输出1
。
他们非常聪明,都会让自己尽可能的赢。
题目分析
我们可以看出,如果要让自己赢,则:
Raze
每次选择数字是要尽可能的选择偶数,使得数字中的偶数尽可能少。
Breach
每次选择数字是要尽可能的选择奇数,使得数字中的奇数尽可能少。
如果数字只有一位就可以直接判断输出了qwq
题目代码
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83
| #include <iostream> #include <cstring> #include <cstdio> using namespace std;
int main() { int t; cin >> t; while (t--) { int n = 0; string a; cin >> n >> a;
if (n == 1) { if ((a[0] - '0') % 2 == 0) cout << 2 << endl; else cout << 1 << endl; continue; }
int book[5005]; memset(book, 0, sizeof(book)); for (int k = n / 2; k > 0; k--) { int flaga = 0, flagb = 0;
for (int i = 1; i <= n; i += 2) { if ((a[i - 1] - '0') % 2 == 0) { if (book[i] == 0) { book[i] = 1; flaga = 1; break; } } }
if (!flaga) { for (int i = 1; i <= n; i += 2) { if (book[i] == 0) { book[i] = 1; break; } } }
if (n % 2 == 0 && k == 1) break; for (int i = 2; i <= n; i += 2) { if ((a[i - 1] - '0') % 2 == 1) { if (book[i] == 0) { book[i] = 1; flagb = 1; break; } } }
if (!flagb) { for (int i = 2; i <= n; i += 2) { if (book[i] == 0) { book[i] = 1; break; } } } }
for (int i = 1; i <= n; i++) { if (book[i] == 0) { if ((a[i - 1] - '0') % 2 == 0) { cout << 2 << endl; } else { cout << 1 << endl; }
break; } } }
return 0; }
|