[ABC354E] Remove Pairs

· · 题解

AT_abc354_e Remove Pairs

题意简述

给定 n 张卡片，每张卡片正反面个有一个数字，由 Takahashi 先手，每次操作可以选择两张正面数字相同或者反面数字相同的卡片来删除。求出全部采取最优策略时谁能获胜。

思路

暴力（ 16/30 个点）

首先我们可以先想着暴力的直接搜索。由于 n 很小，我们可以用状态压缩来进行搜索。状态数字二进制第 k 位 1/0 表示第 k 位选了/没选。这样我们每次 O(n^2) 地枚举每两个未被选的位置，并且判断是否能成对地被消除。如果能组合，那就把他删去，再进行下一层的搜索。每一层的输赢完全由下一层决定。具体地来说：

  1. 没有下一层，这一层是必败状态
  2. 下一层全部是必胜状态，那么这一层是必败状态
  3. 下一层有必败状态，这一层是必胜状态

时间复杂度是阶乘级别的。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define ld long double

inline ll read(){
    ll res = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        res = res * 10 + c - '0';
        c = getchar();
    }
    return f * res;
}

const int N = 20, M = 2000010;

struct ii{
    ll a, b;
}card[N];
bool f[M];
ll n;

bool dfs(ll now){
    bool flag = 0;
    for(int i = 1; i <= n; i ++){

        if(!((now >> (i - 1)) & 1))continue;
        ll mid = now - (1 << (i - 1));

        for(int j = i + 1; j <= n; j ++){

            if(!((mid >> (j - 1)) & 1))continue;
            if(!(card[i]. a == card[j]. a || card[i]. b == card[j]. b))continue;
            ll midd = mid - (1 << (j - 1));
            if(!dfs(midd)){
                flag = 1;
            }
        }
    }
    return flag;
}

signed main(){
    n = read();
    for(int i = 1; i <= n; i ++){
        card[i]. a = read(), card[i]. b = read();
    }
    if(dfs((1ll << n) - 1)){
        cout << "Takahashi";
    }
    else{
        cout << "Aoki";
    }
    return 0;
}

正解 #1

我们都把状态用二进制表示出来了，那么我们对于每一个状态只需要搜所以此就可以。所以我么们用一个 f 数组表示当前的状态是否已经搜过，并且记录它的答案。因为每一层的答案只有 0 / 1（必败 / 必胜），所以我们把f 数组赋初值为 -1，表示没搜过当前状态。

代码 #1

#include<bits/stdc++.h>
  using namespace std;
#define ll long long
#define endl '\n'
#define ld long double

inline ll read(){
    ll res = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        res = res * 10 + c - '0';
        c = getchar();
    }
    return f * res;
}

const int N = 20, M = 2000010;

struct ii{
    ll a, b;
}card[N];
int f[M];
ll n;

bool dfs(ll now){
    if(f[now] != -1)return f[now];///////////
    bool flag = 0;
    for(int i = 1; i <= n; i ++){

        if(!((now >> (i - 1)) & 1))continue;
        ll mid = now - (1 << (i - 1));

        for(int j = i + 1; j <= n; j ++){

            if(!((mid >> (j - 1)) & 1))continue;
            if(!(card[i]. a == card[j]. a || card[i]. b == card[j]. b))continue;
            ll midd = mid - (1 << (j - 1));
            if(!dfs(midd)){
                flag = 1;
            }
        }
    }
    f[now] = flag;///////////
    return flag;
}

signed main(){
    n = read();
    memset(f, -1, sizeof f);
    for(int i = 1; i <= n; i ++){
        card[i]. a = read(), card[i]. b = read();
    }
    if(dfs((1ll << n) - 1)){
        cout << "Takahashi";
    }
    else{
        cout << "Aoki";
    }
    return 0;
}

正解 #2

都用到状压了，怎么能不用 DP 呢？

状态设计同上。我们从小到大枚举状态，再枚举物品对，那么我们在转移时（例如要从不选 i, j 转移到选 i,j），可以转移到它的状态（不选 i, j 状态的）一定是之前枚举过的（因为不选 i, j 的话那两位就是 0，其他位置一样，比目标状态小）。然后我们就可以按照上面的策略进行转移。

代码 #2

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define ld long double

inline ll read(){
    ll res = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        res = res * 10 + c - '0';
        c = getchar();
    }
    return f * res;
}

const int N = 20, M = 2000010;

struct ii{
    ll a, b;
}card[N];
bool f[M];
ll n;

bool check(){
    for(ll now = 0; now < (1 << n); now ++){
        for(int i = 1; i <= n; i ++){

            if(!((now >> (i - 1)) & 1))continue;
            ll mid = now - (1 << (i - 1));

            for(int j = i + 1; j <= n; j ++){

                if(!((mid >> (j - 1)) & 1))continue;
                if(!(card[i]. a == card[j]. a || card[i]. b == card[j]. b))continue;
                ll midd = mid - (1 << (j - 1));
                if(!f[midd])f[now] = 1;
            }
        }
    }
    return f[(1 << n) - 1];
}

signed main(){
    n = read();
    for(int i = 1; i <= n; i ++){
        card[i]. a = read(), card[i]. b = read();
    }
    if(check()){
        cout << "Takahashi";
    }
    else{
        cout << "Aoki";
    }
    return 0;
}