解题思路

这个问题要求我们根据已有的猜测和提示，生成下一个可能的猜测序列。关键在于如何利用已有的信息来缩小可能的解空间，并找到满足所有约束条件的下一个猜测。

1. 理解游戏规则： • 秘密代码：由P个颜色组成的序列，颜色可以重复。

   • 猜测和提示：每次猜测后，会得到一个提示$（B, W）$，其中B表示颜色和位置都正确的数量，$W$表示颜色正确但位置不对的数量。

   • 约束条件：新的猜测必须与之前所有的猜测和提示一致。

2. 生成下一个猜测： • 初始解空间：所有可能的颜色序列，共$C^P$种可能。

   • 剪枝：根据已有的猜测和提示，排除不符合条件的序列。

   • 回溯算法：尝试生成可能的序列，并在每一步验证是否满足所有约束条件。

3. 验证猜测： • 对于每个可能的序列，检查其与之前所有猜测的提示是否一致。

   • 计算$B$和$W$的方法：首先计算颜色和位置都正确的数量$B$，然后计算颜色正确但位置不对的数量W。

4. 选择下一个猜测： • 在所有可能的序列中，选择字典序最小的一个。

   • 如果没有可能的序列，输出"$You$ $are$ $cheating!$"。

代码实现

#include <stdio.h>
#include <algorithm>
using namespace std;

const int N = 15;
const int M = 105;
int t, p, c, m, vis[M], have[M], hn, b[M], s[M], ans[N], num;

struct Mi {
	int num[N];
	int vis[M];
	int b, w;
} mi[M];

void init() {
	int i, j;
	for (i = 0; i < M; i++) vis[i] = 0;
	for (i = 0; i < M; i++) b[i] = 0;
	for (i = 0; i < M; i++) s[i] = 0;
	
	hn = 0;
	scanf("%d%d%d", &p, &c, &m);
	for (i = 0; i < m; i++) {
		for (j = 0; j < M; j++) mi[i].vis[j] = 0;
		
		for (j = 0; j < p; j++) {
			scanf("%d", &mi[i].num[j]);
			mi[i].vis[mi[i].num[j]]++;
			if (!vis[mi[i].num[j]]) {
				vis[mi[i].num[j]] = 1;
				have[hn++] = mi[i].num[j];
			}
		}
		scanf("%d%d", &mi[i].b, &mi[i].w);
	}
	for (i = 1; i <= c; i++) {
		if (!vis[i]) {
			have[hn++] = i;
			break;
		}
	}
	sort(have, have + hn);
}

bool dfs(int d) {
	if (d == p) {
		for (int i = 0; i < m; i++) {
			if (b[i] != mi[i].b || s[i] - b[i] != mi[i].w)
				return false;
		}
		for (int j = 0; j < p - 1; j++)
			printf("%d ", ans[j]);
		printf("%d\n", ans[p - 1]);
		return true;
	}
	for (int i = 0; i < hn; i++) {
		int num = have[i], flag = 0, j, flag2[M];
		
		for (j = 0; j < M; j++) flag2[j] = 0;
		
		for (j = 0; j < m; j++) {
			if (num == mi[j].num[d])
				b[j]++;
			if (mi[j].vis[num]) {
				s[j]++;
				mi[j].vis[num]--;
				flag2[j] = 1;
			}
			if (b[j] > mi[j].b || s[j] > mi[j].b + mi[j].w)
				flag = 1;
		}
		if (!flag) {
			ans[d] = num;
			if (dfs(d + 1)) return true;
		}
		for (j = 0; j < m; j++) {
			if (num == mi[j].num[d])
				b[j]--;
			if (flag2[j]) {
				s[j]--;
				mi[j].vis[num]++;
			}
		}
	}
	return false;
}

int main() {
	scanf("%d", &t);
	while (t--) {
		init();
		if (!dfs(0)) printf("You are cheating!\n");
	}
	return 0;
}