【题解】HackerRank - New Year Game

题目

https://www.hackerrank.com/challenges/newyear-game

题意

给一列数,A 和 B 轮流取,如果每个人取的数之和之差的绝对值被 3 整除,则 B 赢,反之 A 赢。

题解

  • 绝对值没有用,去掉
  • 对于每个数,只关心它模 3 的余数
  • 由于胜利条件不是无法操作,所以和 sg 无关
  • 如果枚举每个状态,复杂度 $O(n^3)$,会超时。
    • 但是如果找规律的话,能得出一个 $O(n)$ 的做法,然后就 AC 了
  • 对于模 3 余 0 的数,如果有偶数个就不影响胜负(显然),如果有奇数个就当成 1 个。所以复杂度变成了 $O(n^2)$
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
#include <bits/stdc++.h>
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
using namespace std;
const int maxn = 2000 + 5;
int a[3], T, n, t, k;
bool dp[2][maxn][maxn][2][3];

inline int f(int x) { return (x + 3) % 3; }

void init() {
dp[0][0][0][0][1] = dp[0][0][0][0][2] = 1; // first person win
dp[0][0][0][1][0] = 1; // second person win
FOR(t, 0, 2) // 0
FOR(i, 0, maxn) // 1
FOR(j, 0, maxn) // 2
FOR(r, 0, 2) // 0: first, 1: second
FOR(v, 0, 3) { // S_first - S_second (mod 3)
int s = r ? 1 : -1;
bool &u = dp[t][i][j][r][v];
if (t) u |= !dp[t - 1][i][j][r ^ 1][f(v - s * 0)];
if (i) u |= !dp[t][i - 1][j][r ^ 1][f(v - s * 1)];
if (j) u |= !dp[t][i][j - 1][r ^ 1][f(v - s * 2)];
}
}

int main() {
init();
cin >> T;
while (T--) {
cin >> n;
memset(a, 0, sizeof a);
FOR(i, 0, n) {
scanf("%d", &t);
++a[t % 3];
}
if (dp[a[0] % 2][a[1]][a[2]][0][0]) puts("Balsa"); else puts("Koca");
}
}