DDOSvoid's Blog

hdu 3032 Nim or not Nim?

发表于 分类于
本文字数： 801 阅读时长 ≈ 1 分钟

题目描述

https://acm.hdu.edu.cn/showproblem.php?pid=3032

简要题意：给 $n$ 堆石子，每次操作可以 $n$ 堆石子中取若干个石子或者将一堆石子数大于等于 $2$ 的石子分成两堆石子

$n\le 10^6$

Solution

最经典的 $multi-sg$，但是并没有什么有用的结论，所以我们直接打表找规律即可，能够得到

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
#include <iostream>
#define maxn 1000010
using namespace std;

int n, a[maxn];

void work() {
    cin >> n; int sgsum = 0; 
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) {
        switch (a[i] % 4) {
        case 0 : sgsum ^= a[i] - 1; break;
        case 1 :
        case 2 : sgsum ^= a[i]; break;
        case 3 : sgsum ^= a[i] + 1; break;
        }
    } cout << (sgsum ? "Alice" : "Bob") << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work(); 
}