# 补题

# 题目链接：左右脑互博 HDU1004

# 题目大意

核心玩法：给定一个包含 n 个正整数的集合，两人轮流从集合中取走一个数 $a_i$ ，满足：

$a_i$ >(剩余元素的异或和)

若集合只剩 1 个数，可直接取走。

无法操作者输。

# 核心思路

关键性质：n 很小，考虑状态压缩，再结合只要对于当前状态，可以转移到至少一个必败态，则当前状态为必胜态，否则为必败态，可解
算法选择：状态压缩 + 记忆化搜索

# 易错点 / 坑点

状压后扫描每个位置是否取过的时候，i 应该从 0 开始

点击查看代码

	for (int i = 0; i < n; i++)
	{
	if (((u >> i) & 1) && (a[i + 1] > (now ^ a[i + 1])))
	{
	if (dfs(u ^ (1 << i), now ^ a[i + 1]) == 0)
	{
	dp[u] = 1;
	break;
	}
	}
	}

# AC 代码

点击查看代码

#include #define int long long #define endl '\n' using namespace std;

const int N = 2e6 + 10;
int a[30], dp[N], vis[N];
int s = 0;
int n;
bool dfs(int u, int now)
if (u == 0) return 0; if (vis[u]) return dp[u]; vis[u] = 1; dp[u] = 0; for (int i = 0; i < n; i++) { if (((u >> i) & 1) && (a[i + 1] > (now 【 a[i + 1]))) { if (dfs(u ^ (1 << i), now ^ a[i + 1]) == 0) { dp[u] = 1; break; 】
}
}
return dp[u];
}
void solve()
{

cin >> n;
s = 0;
for (int i = 1; i <= n; i++)
{
    cin >> a[i];
    s ^= a[i];
}
int t = 1 << n;
int ans = dfs(t - 1, s);
if (ans)
    cout << "Left" << endl;
else
    cout << "Right" << endl;

}
signed main()
{
cin.tie(0)->ios::sync_with_stdio(0);
int T;
cin >> T;
while (T–)
solve();
return 0;
}

补题