自动搬运

查看原文

来自洛谷，原作者为

	chenxi797 壶关条件见主页，私||关我可得2小号回关，私||初三蒟蒻||ENTP||天秤座

搬运于2025-08-24 23:11:15，当前版本为作者最后更新于2025-08-07 16:33:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P11903 [NHSPC 2023] B. 人工智能模拟 题解

题意

构造一个长度为 $k$ 的 $01$ 串，任意取 $t$ 个位置，要求在所给的 $n$ 个串中能找到至少一个串的 $t$ 个位置和构造的串相同，并且构造的这个串不能与给出的串重复，构造的串中只能包含最多 $3$ 个 $1$。

思路

首先，枚举 $q$ 的可能取值。由于 $q$ 最多有 $3$ 个 $1$，于是可以用三重循环枚举每个 $1$ 出现的位置。注意要枚举全 $0$ 的情况。

对于一种 $q$，判断其是否满足条件。首先循环看一遍有没有 $b_i=q$，然后可以 dfs 检查所有大小为 $t$ 的特征集是否有 $b_i$ 满足。

关于 __builtin_popcount() 这个函数，作用是可以直接检查一个数二进制下 $1$ 的个数。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 105;
int b[N];
int n,k,t,q;
bool dfs(int x,int s)
{
	if (x == k)
	{
		if (__builtin_popcount(s) != t) return 1;
		for (int i = 1;i <= n;i++)
			if (((~(q ^ b[i])) & s) == s) return 1;
		return 0;
	}
	if (!dfs(x + 1,s)) return 0;
	if (__builtin_popcount(s) < t) return dfs(x + 1,s | (1 << x));
	return 1;
}
void check()
{
	for (int i = 1;i <= n;i++)
		if (q == b[i]) return;
	if (dfs(0,0))
	{
		for (int i = 0;i < k;i++) cout << bool(q & (1 << i));
		exit(0);
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n >> k >> t;
	string s;
	for (int i = 1;i <= n;i++)
	{
		cin >> s;
		for (int j = 0;j < k;j++)
			if (s[j] == '1') b[i] |= (1 << j);
	}
	check();
	for (int i = 0;i < k;i++)
	{
		for (int j = i;j < k;j++)
		{
			for (int l = j;l < k;l++)
			{
				q = (1 << i) | (1 << j) | (1 << l);
				check();
			}
		}
	}
	cout << "none";
	return 0;
}