ARC219A

Magus · 2026-05-13 14:14:31 · 题解

题意

给你 N 个 01 串，要求你构造一个 01 串 S 使得对于任意一个串，S 中都有一个字符与其相同。

题解

看这个东西显然很难搞，正难则反，把这个问题转化一下，预处理出来所有原字符串的反串，这个用一个 set 存，原问题便转化为了让你构造一个串，使其不等于 set 中的任意一个串。

对于长度为 M 的 01 串共有 2^M 种可能，那么无解的情况就出来了，当且仅当这 2^M 种可能 set 中都有时无解。发现 N \leq 2 \times 10^4，所以对于有解的情况直接爆搜哪个串没在 set 中出现即可。需要注意的是 2^M 可能会爆 long long。

代码很丑陋。

#include<bits/stdc++.h>
//#pragma GCC optimize(3)
#define FastIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define int long long
#define I using
#define AK namespace
#define this_contest std
I AK this_contest;
const int maxn=1e6+10,maxm=1e3+10,mod=998244353;
int t,n,m,x,y,u,v,w,flag,ans,arr[maxn];
string s;
unordered_set<string>mp;
string solve()
{
    for(int i=0;i<(1ll<<m);i++)
    {
        string res="";
        for(int j=m-1;j>=0;j--)res+=(i>>j)&1?'1':'0';
        if(flag){if(!mp.count(res))return res;}
        else
        {
            string f="";
            for(char c:res)f+=c^1;
            if(!mp.count(f))return res;
        }
    }
    return "fuck";
}
signed main()
{
    FastIO;
    cin>>n>>m;
    if(m>60)
    {
        for(int i=1;i<=n;i++)
        {
            cin>>s;
            mp.insert(s);
        }
        cout<<"Yes\n";
        for(int i=0;i<(1ll<<60);i++)
        {
            string res="";
            for(int j=m-1;j>=0;j--)res+=(i>>j)&1?'1':'0';
            if(flag){if(!mp.count(res)){cout<<res;return 0;}}
            else
            {
                string f="";
                for(char c:res)f+=c^1;
                if(!mp.count(f)){cout<<res;return 0;}
            }
        }
        return 0;
    }
    if(n<(1ll<<m))
    {  
        flag=0;
        for(int i=1;i<=n;i++)
        {
            cin>>s;
            mp.insert(s);
        }
        cout<<"Yes\n";
        cout<<solve()<<"\n";
    }
    else
    {
        ans=0;
        flag=1;
        mp.clear();
        for(int i=1;i<=n;i++)
        {
            cin>>s;
            string f="";
            for(char c:s)f+=c^1;
            if(mp.count(f))ans=1;
            mp.insert(f);
        }
        if(!ans)cout<<"No\n";
        else
        {
            cout<<"Yes\n";
            cout<<solve()<<"\n";
        }
    }
    return 0;
}