P1062 · OFFICIAL SOLUTION

P1062 卡牌游戏官方题解

Gioush OJ · P1062 卡牌游戏

【题意简述】

两名玩家轮流拿走一对正面数值相同或背面数值相同的牌，无法操作者失败，判断先手是否必胜。

【正解】

用位掩码 $mask$ 表示仍在牌堆中的牌。预处理所有合法牌对对应的二进制掩码。定义 $win(mask)$ 表示当前状态是否为必胜态，则

win(mask)=\bigvee_{e\subseteq mask,\ e\text{ 为合法牌对}}\neg win(mask\setminus e).

没有合法牌对时为必败态。记忆化搜索所有可达状态即可。

【正确性】

若存在一步走到必败态，当前玩家选择该步即可获胜；若所有合法操作都走到必胜态，对手总能获胜，当前状态必败。递推与最优策略定义完全一致。

【复杂度】

设合法牌对数为 $m$ ，时间复杂度 $\mathcal O(m2^n)\subseteq\mathcal O(n^2 2^n)$ ，空间复杂度 $\mathcal O(2^n)$ 。

【参考代码】

1/*2Author:Ehundategh3Date:2026/8/174Name:poker.cpp5You steal,I kill.6*/7#include <vector>8#include <cstdio>9#include <cstring>10#define MAXN 2111using namespace std;12int c,T,n,a[MAXN],b[MAXN];13signed char Dp[1<<20];14vector <int> Pair;15 16int Calc(int Now){17    if(Dp[Now]!=-1) return Dp[Now];18    for(int i=0;i<(int)Pair.size();i++){19        if((Now&Pair[i])==Pair[i]&&!Calc(Now^Pair[i])) return Dp[Now]=1;20    }21    return Dp[Now]=0;22}23 24void Solve(){25    scanf("%d",&n);Pair.clear();26    for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);27    for(int i=1;i<=n;i++){28        for(int j=i+1;j<=n;j++){29            if(a[i]==a[j]||b[i]==b[j]) Pair.push_back((1<<(i-1))|(1<<(j-1)));30        }31    }32    memset(Dp,-1,sizeof(signed char)*(1<<n));33    puts(Calc((1<<n)-1)?"Ehundategh":"tfbz");34}35 36int main(){37    scanf("%d%d",&c,&T);38    while(T-->0) Solve();39    return 0;40}