WA 了 5 个点求助
查看原帖
WA 了 5 个点求助
502658
Ray662楼主2024/11/18 12:56

爆搜,set + 序列哈希

#include <bits/stdc++.h>
#define _for(i, a, b)  for (int i = (a); i <= (b); i ++ )
#define For(it, a)  for (ms :: iterator it = a.begin(); it != a.end(); it ++ )
#define ull unsigned long long
#define ms multiset<int>
using namespace std;
const int N = 15, inf = 2e9 + 5, B[2] = {917120411, (int)1e9 + 7}, V1 = 998442353, V2 = 200811057, V3 = 200901051;
ms c; map<ull, map<ull, bool> > f[N][N];
bool dfs(int o, int n[2], ms a[2]) {
	if (! n[o])  return 0;
	if (! n[o ^ 1])  return 1;
	int res = 0; ull h[2] = {0, 0};
	_for (i, 0, 1)  For (it, a[i])  h[i] = h[i] * B[i] + ( * it);
	if (f[n[0]][n[1]][h[0]].count(h[1]))  return f[n[0]][n[1]][h[0]][h[1]]; ms b[2], cc = c; b[0] = a[0], b[1] = a[1];
	For (it, b[o]) {
		int val = * it, val2; c.insert(val), a[o].erase(a[o].find(val)), n[o] -- , res |= ! dfs(o ^ 1, n, a);
		if (cc.size())  For (it2, cc)  if (( * it2) < val) {
			val2 = * it2, a[o].insert(val2), c.erase(c.find(val2)), n[o] ++ , res |= ! dfs(o ^ 1, n, a), n[o] -- , a[o].erase(a[o].find(val2)), c.insert(val2);
			if (res)  break;
		}
		n[o] ++ , c.erase(c.find(val)), a[o].insert(val), c = cc;
		if (res)  break;
	}
	return a = b, f[n[0]][n[1]][h[0]][h[1]] = res;
}
int main() {
	ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int n, m, l; cin >> n >> m >> l; ms A[2]; int x, t[2] = {n, m};
	_for (i, 1, n)  cin >> x, A[0].insert(x);
	_for (i, 1, m)  cin >> x, A[1].insert(x);
	_for (i, 1, l)  cin >> x, c.insert(x);
	return cout << (dfs(0, t, A) ? "Takahashi" : "Aoki") << "\n", 0;
}

2024/11/18 12:56
加载中...