[HNOI2007]分裂游戏

输入文件第一行是一个整数t表示测试数据的组数，接下来为t组测试数据（t ≤ 10）。
每组测试数据的第一行是瓶子的个数n，接下来的一行有n个由空格隔开的非负整数，表示每个瓶子中的豆子数。

对于每组测试数据，输出包括两行，第一行为用一个空格两两隔开的三个整数，表示要想赢得游戏，第一步应该选取的3个瓶子的编号i,j,k，如果有多组符合要求的解，那么输出字典序最小的一组。如果无论如何都无法赢得游戏，那么输出用一个空格两两隔开的三个-1。第二行表示要想确保赢得比赛，第一步有多少种不同的取法。

C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 556K, 提交时间: 2023-08-03 05:38:49

#include <bits/stdc++.h>

using namespace std;
const int N = 30, M = 1e4 + 10;
int n, p[N], sg[N];

int g(int i) {
    if (~sg[i]) return sg[i];
    
    bool st[M];
    memset(st, 0, sizeof st);
    for (int j = i + 1; j < n; j++) {
        for (int k = j; k < n; k++) {
            st[g(j) ^ g(k)] = 1;
        }
    }
    for (int mex = 0;; mex++) if (!st[mex]) return sg[i] = mex;
}

void solve() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &p[i]);
    memset(sg, -1, sizeof sg), sg[n - 1] = 0;
    
    int nim = 0;
    for (int i = 0; i < n; i++) if (p[i] & 1) nim ^= g(i);
    if (!nim) {
        printf("-1 -1 -1\n0\n");
        return;
    }
    
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j; k < n; k++) {
                if ((nim ^ g(i) ^ g(j) ^ g(k)) == 0) {
                    if (!cnt++) printf("%d %d %d\n", i, j, k);
                }
            }
        }
    }
    printf("%d\n", cnt);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) solve();
    return 0;
}

C++ 解法, 执行用时: 4ms, 内存消耗: 416K, 提交时间: 2022-05-13 22:13:25

#include<bits/stdc++.h>
using namespace std;
#define MAXN 105
int sg[MAXN], value[MAXN];
bool mark[MAXN];
int main() {
	sg[0] = 0;
	for (int i = 1; i < MAXN; i++) {
		memset(mark, false, sizeof(mark));
		for (int j = 0; j < i; j++)
		for (int k = j; k < i; k++)
			mark[sg[j] ^ sg[k]] = true;
		int ans = 0;
		while (mark[ans]) ans++;
		sg[i] = ans;
	}
	int T;
	scanf("%d", &T);
	while (T--) {
		int n, ans = 0;
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) {
			scanf("%d", &value[i]);
			if (value[i] & 1) ans ^= sg[n - i];
		}
		if (ans == 0) {
			printf("-1 -1 -1\n0\n");
			continue;
		}
		int cnt = 0;
		for (int i = 1; i <= n; i++) {
			if (value[i] == 0) continue;
			for (int j = i + 1; j <= n; j++)
			for (int k = j; k <= n; k++)
				if ((ans ^ sg[n - i] ^ sg[n - j] ^ sg[n - k]) == 0) {
					if (cnt == 0) printf("%d %d %d\n", i - 1, j - 1, k - 1);
					cnt++;
				}
		}
		printf("%d\n", cnt);
	}
	return 0;
}

详情