【题解】HackerRank - New Year Game

Posted on Edited on In Disqus:

题目

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");
    }
}