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

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

题目大意

给定

n

个长度为

k

的 01 字符串，要求构造一个长度为

k

的字符串，满足：

与任一给出字符串不完全相同；
对任意选择的 $t$ 个位置，能在所有字符串中找到一个在这 $t$ 个位置上的特征与所构造字符串完全一致；

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

3

。

解题思路

暴力题。

由于

k

较小，且候选序列中最多只有

3

个 1，可枚举所有满足“最多

3

个 1”条件的字符串。

对于每个字符串

S

：

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

只要

S

在所有

t

个位置组合下都满足条件，则输出该序列；若均不合法，则输出 none。

CPP

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

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

文章操作

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

题目大意

解题思路

相关推荐

评论

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