题解 P6930 【[WF2017] Get a Clue!】

Leasier · 2023-07-10 19:13:08 · 题解

我们可以将题意及限制抽象成：

• 第 1, 2, 3, 4 个人依次选择 A \sim U 中卡牌（分别去掉三张 A \sim F, G \sim L, M \sim U 中的卡牌后）的 5, 5, 4, 4 张。
• 第 1 个人的选择固定。
• 每个人有一些必须选的，有一些卡牌集至少选一张的，还有一些必须不选的。
• 求去掉的三张卡牌依次可能是啥，或报告多解。

直接状压爆搜每个人的选择即可，但这样时间复杂度理论上是不对的，如果想要对可以一个一个人爆搜后 FWT 起来。

代码：

#include <iostream>
#include <vector>

using namespace std;

int known = 0;
int cnt[57], bans[7];
char s[17], guess[57][7], result[57][7];
bool no[27], ok1[7], ok2[17], ok3[27];
vector<int> v[7];

bool dfs0(int cur, int pre, int state, int ban){
    if (cur == 19){
        int size = v[0].size();
        for (int i = 0; i < size; i++){
            if ((state & v[0][i]) == 0) return false;
        }
        return true;
    }
    int cur_i = cur + 1;
    for (int i = pre + 1; i <= 21; i++){
        if (!(state >> (i - 1) & 1) && !(ban >> (i - 1) & 1) && !(bans[0] >> (i - 1) & 1) && dfs0(cur_i, i, state | (1 << (i - 1)), ban)) return true;
    }
    return false;
}

bool dfs3(int cur, int pre, int state, int ban){
    if (cur == 15){
        int size = v[3].size();
        for (int i = 0; i < size; i++){
            if ((state & v[3][i]) == 0) return false;
        }
        return dfs0(15, 0, 0, ban | state);
    }
    int cur_i = cur + 1;
    for (int i = pre + 1; i <= 21; i++){
        if (!(state >> (i - 1) & 1) && !(ban >> (i - 1) & 1) && !(bans[3] >> (i - 1) & 1) && dfs3(cur_i, i, state | (1 << (i - 1)), ban)) return true;
    }
    return false;
}

bool dfs2(int cur, int pre, int state, int ban){
    if (cur == 11){
        int size = v[2].size();
        for (int i = 0; i < size; i++){
            if ((state & v[2][i]) == 0) return false;
        }
        return dfs3(11, 0, 0, ban | state);
    }
    int cur_i = cur + 1;
    for (int i = pre + 1; i <= 21; i++){
        if (!(state >> (i - 1) & 1) && !(ban >> (i - 1) & 1) && !(bans[2] >> (i - 1) & 1) && dfs2(cur_i, i, state | (1 << (i - 1)), ban)) return true;
    }
    return false;
}

inline bool check(int x, int y, int z){
    int ban = (1 << (x - 1)) | (1 << (y - 1)) | (1 << (z - 1));
    if (no[x] || no[y] || no[z] || (known & ban) != 0) return false;
    return dfs2(6, 0, 0, ban | known);
}

int main(){
    int n;
    char ans1 = '\0', ans2 = '\0', ans3 = '\0';
    cin >> n;
    cin.getline(&s[1], 2, '\n');
    cin.getline(&s[1], 11, '\n');
    for (int i = 1; i <= 5; i++){
        int ch = s[i * 2 - 1] - 'A' + 1;
        known |= 1 << (ch - 1);
        no[ch] = true;
    }
    for (int i = 1; i <= n; i++){
        cin.getline(&s[1], 13, '\n');
        for (int j = 1; j <= 3; j++){
            guess[i][j] = s[j * 2 - 1];
        }
        do {
            cnt[i]++;
            result[i][cnt[i]] = s[cnt[i] * 2 + 5];
            if (cnt[i] == 3) break;
        } while (result[i][cnt[i]] == '-');
    }
    for (int i = 1; i <= n; i++){
        int state = 0;
        for (int j = 1; j <= 3; j++){
            state |= 1 << (guess[i][j] - 'A');
        }
        for (int j = 1; j <= cnt[i] && result[i][j] == '-'; j++){
            bans[(i + j) % 4] |= state;
        }
        if (result[i][cnt[i]] != '-'){
            if (i % 4 == 1){
                int ch = result[i][cnt[i]] - 'A' + 1;
                no[ch] = true;
                v[(i + cnt[i]) % 4].push_back(1 << (ch - 1));
            } else {
                v[(i + cnt[i]) % 4].push_back(state);
            }
        }
    }
    for (int i = 1; i <= 6; i++){
        for (int j = 7; j <= 12; j++){
            for (int k = 13; k <= 21; k++){
                if (check(i, j, k)) ok1[i] = ok2[j] = ok3[k] = true;
            }
        }
    }
    for (int i = 1; i <= 6; i++){
        if (ok1[i]){
            if (ans1 == '\0'){
                ans1 = i + 'A' - 1;
            } else {
                ans1 = '?';
                break;
            }
        }
    }
    for (int i = 7; i <= 12; i++){
        if (ok2[i]){
            if (ans2 == '\0'){
                ans2 = i + 'A' - 1;
            } else {
                ans2 = '?';
                break;
            }
        }
    }
    for (int i = 13; i <= 21; i++){
        if (ok3[i]){
            if (ans3 == '\0'){
                ans3 = i + 'A' - 1;
            } else {
                ans3 = '?';
                break;
            }
        }
    }
    cout << ans1 << ans2 << ans3;
    return 0;
}