CF1932D Card Games 题解

思路

赛时没想出来贪心，于是写了爆搜但一直 WA，赛后发现是 dfs 函数忘记回溯了。

时间复杂度看起来是假的，但是跑得很快，推测是一堆卡牌里面能够进行匹配的数量实际上并没有那么多，实测最慢的点才 15ms，提交记录：link

爆搜的方法就是先用 (2n)2(2n)^2 的时间预处理每两张牌是否能够匹配（匹配条件即两张牌中有且只有一张能赢过对方），然后再从第一张牌开始搜：对于每一张牌枚举和它匹配的另一张牌，标记之后接着搜下一张，搜不到就回溯继续搜，终止条件就是搜到第 2n2n 张牌时 return 1 以及无解时 return 0。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
constexpr int N = 40;

char trump;
int n;

struct card{
    char suit;int rank;
    inline void print(){cout<<rank<<suit;}
}c[N];

inline int win(card a,card b){    //a能否赢过b
    if(a.suit==b.suit)	return (a.rank>b.rank)?1:0;
    else if(a.suit==trump)	return 1;
    else return 0;
}

bool vis[N],leg[N][N];    //leg代表是否合法，vis代表是否被搜到过
int with[N];    //with[i]代表第i张牌被匹配的牌

bool dfs(int now){
    if(now==n*2)	return 1;	//有解
    if(vis[now])	return dfs(now+1);	//这张牌已经被匹配过了
    for(int i=1;i<=n*2;i++){
        if(leg[now][i] && !vis[i]){
            with[now] = i;
            vis[now] = vis[i] = 1;
            if(dfs(now+1))	return 1;	//搜索下一张牌
            with[now] = 0;	//一定记得回溯
            vis[i] = 0;
        }
    }
    vis[now] = 0;
    return 0;	//无解
}

void solve(){
    reset(with,0);reset(vis,0);
    cin>>n;
    cin>>trump;
    for(int i=1;i<=n*2;i++){
        cin>>c[i].rank>>c[i].suit;
    }
    for(int i=1;i<=n*2;i++){	//预处理，实际上放在搜索函数里判断也行
        bool have = 0;
        for(int j=1;j<=n*2;j++){
            if(i==j)	leg[i][j] = 0;
            else{
                if(win(c[i],c[j])+win(c[j],c[i])==1){
                    leg[i][j] = 1;
                    have = 1;
                }
                else leg[i][j] = 0;
            }
        }
        if(!have){cout<<"IMPOSSIBLE\n";return;}
    }
    if(!dfs(1))	cout<<"IMPOSSIBLE\n";	//无解
    else{
        for(int i=1;i<=n*2;i++){	//输出答案，记得能赢的那一张放在后面输出
            if(with[i]==0)	continue;
            int p2 = i,p1 = with[i];
            if(!win(c[i],c[with[i]]))	swap(p1,p2);
            c[p1].print();cout<<" ";
            c[p2].print();cout<<"\n";
        }
    }
}