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

· · 题解

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

题目大意

给定 n 个长度为 k 的 01 字符串，要求构造一个长度为 k 的字符串，满足：

另外，构造字符串中 1 的个数最多不超过 3。

解题思路

暴力题。

由于 k 较小，且候选序列中最多只有 3 个 1，可枚举所有满足“最多 3 个 1”条件的字符串。

对于每个字符串 S：

  1. 判断 S 是否与某个字符串 T_i 相同，若相同则淘汰；
  2. 使用 DFS 枚举从 k 个位置中挑选 t 个位置的所有组合，对于每个组合检查是否存在至少一位受访者，其在这 t 个位置上的特征值与 S 完全匹配；

只要 S 在所有 t 个位置组合下都满足条件，则输出该序列；若均不合法，则输出 none。

#include<bits/stdc++.h>
using namespace std;

int n,k,t;
vector<string> a;
string cur;
vector<int> pos;

bool dfs(int st,int nd){
    if(!nd){
        for(auto &p:a){
            bool ok=1;
            for(auto &i:pos)
                if(p[i]!=cur[i]){ok=0;break;}
            if(ok)return 1;
        }
        return 0;
    }
    for(int i=st;i+nd-1<k;i++){
        pos.push_back(i);
        if(!dfs(i+1,nd-1)){
            pos.pop_back();
            return 0;
        }
        pos.pop_back();
    }
    return 1;
}

bool check(const string &s){
    cur=s;
    for(auto &p:a)
        if(p==cur)return 0;

    pos.clear();
    return dfs(0,t);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n>>k>>t;

    a.resize(n);
    for(int i=0;i<n;i++)
        cin>>a[i];

    for(int m=0;m<(1<<k);m++){
        if(__builtin_popcount(m)<=3){
            string s(k,'0');
            for(int j=0;j<k;j++)
                if(m&(1<<j))s[j]='1';

            if(check(s)){
                cout<<s<<"\n";
                return 0;
            }
        }
    }

    cout<<"none\n";
    return 0;
}