自动搬运

查看原文

来自洛谷，原作者为

	Leasier 我们所知的是沧海一粟，我们所不知的是汪洋大海。

搬运于2025-08-24 22:25:15，当前版本为作者最后更新于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;
}