Problem Statement
Takahashi and Aoki are playing a game using \(N\) cards. The front side of the \(i\)-th card has \(A_i\) written on it, and the back side has \(B_i\) written on it. Initially, the \(N\) cards are laid out on the table. With Takahashi going first, the two players take turns performing the following operation:
- Choose a pair of cards from the table such that either the numbers on their front sides are the same or the numbers on their back sides are the same, and remove these two cards from the table. If no such pair of cards exists, the player cannot perform the operation.
The player who is first to be unable to perform the operation loses, and the other player wins. Determine who wins if both players play optimally.
Constraints
- \(1 \leq N \leq 18\)
- \(1 \leq A_i, B_i \leq 10^9\)
- All input values are integers.
问题陈述
高桥和青木正在玩一个使用 \(N\) 张卡片的游戏。 \(i\) 这张牌的正面写着 \(A_i\) ，背面写着 \(B_i\) 。最初， \(N\) 这张牌摆在桌子上。高桥先出，两位玩家轮流进行以下操作：
- 从桌上选择一对正面数字相同或背面数字相同的牌，然后从桌上拿走这两张牌。如果没有这样的一对牌，玩家就不能进行操作。
最先无法进行操作的玩家输，另一名玩家赢。如果双方都以最佳方式出牌，谁会赢？
需要用到状态压缩技巧的记忆化搜索
看来真比同场 D 题简单多了
点击查看代码
// Created by qyy on 2024/5/18.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int, int>
#define endl "\n"
const long long inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
string st = "Takahashi";
string sa = "Aoki";
int n;
ll a[N], b[N];
int mp[20][20];
bool dp[1<<19];
bool dfs(ll x){
// 判断先手会不会赢
// flag = 1 --> Tak, 0 --> Aoki;
bool ans = false; // 只要后手必输，那么先手就必赢，否则先手必输
for(int i = 0; i <= 17; i++){
for(int j = 0; j < i; j++){
if(mp[i][j])
if(x&(1LL<<i) && x&(1LL<<j)){
ll new_x = x - (1LL << i) - (1LL << j);
bool tmp;
if(!dp[new_x]){
tmp = dfs(new_x);
dp[new_x] = tmp;
}else tmp = dp[new_x];
if(!tmp) ans = true;
}
}
}
dp[x] = ans;
return ans;
}
void solve() {
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i] >> b[i];
for(int i = 0; i < n; i++){
for(int j = 0; j < i; j++){
if(a[i] == a[j]) mp[i][j] = mp[j][i] = 1;
if(b[i] == b[j]) mp[i][j] = mp[j][i] = 1;
}
}
ll t = (1LL << 18) - 1;
if(dfs(t)) cout << "Takahashi\n";
else cout << "Aoki\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}