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

· · 题解

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;
}