预处理+暴力+模拟——UCF2018 Team Shirts/Jerseys

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define N 30

int cnt[N],len,n,vis[N],a[N],t;
char s[N];
vector<int>v1,v2;
set<int>f;

void solve(int i=-1,int j=-1,int k=-1,int l=-1){
    int pos=0,S=0;
    int a=v2[i]/10,b=v2[i]%10;
    for(;pos<len-1;pos++){
        if(s[pos]-‘0‘==a && s[pos+1]-‘0‘==b){
            S|=(1<<pos);
            S|=(1<<pos+1);
            pos+=2;
            break;
        }
    }
    if(j==-1 || pos==len-1){f.insert(S);return;}
    
    a=v2[j]/10,b=v2[j]%10;
    for(;pos<len-1;pos++){
        if(s[pos]-‘0‘==a && s[pos+1]-‘0‘==b){
            S|=(1<<pos);
            S|=(1<<pos+1);
            pos+=2;
            break;
        }
    }
    if(k==-1 || pos==len-1){f.insert(S);return;}
    
    a=v2[k]/10,b=v2[k]%10;
    for(;pos<len-1;pos++){
        if(s[pos]-‘0‘==a && s[pos+1]-‘0‘==b){
            S|=(1<<pos);
            S|=(1<<pos+1);
            pos+=2;
            break;
        }
    }
    if(l==-1 || pos==len-1){f.insert(S);return;}
    
    a=v2[l]/10,b=v2[l]%10;
    for(;pos<len-1;pos++){
        if(s[pos]-‘0‘==a && s[pos+1]-‘0‘==b){
            S|=(1<<pos);
            S|=(1<<pos+1);
            pos+=2;
            break;
        }
    }
    f.insert(S);
}

int main(){
    cin>>t>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]>=10)v2.push_back(a[i]);
        else v1.push_back(a[i]);
    }
    
    while(t){
        s[len++]=t%10+‘0‘;
        t/=10;
    }
    s[len]=0;
    int i=0,j=len-1;
    while(i<j)swap(s[i],s[j]),i++,j--;
    
    //用长度为2的数预处理出所有状态
    f.insert(0); 
    if(v2.size()>=1){
        for(int i=0;i<v2.size();i++)
            solve(i);
    }
    if(v2.size()==2){
        for(int i=0;i<v2.size();i++)
            for(int j=0;j<v2.size();j++)
                if(i!=j)solve(i,j);
    }
    if(v2.size()==3){
        for(int i=0;i<v2.size();i++)
            for(int j=0;j<v2.size();j++)
                for(int k=0;k<v2.size();k++)
                    if(i!=j && i!=k && j!=k)solve(i,j,k);
    }
    if(v2.size()>=4){
        for(int i=0;i<v2.size();i++)
            for(int j=0;j<v2.size();j++)
                for(int k=0;k<v2.size();k++)
                    for(int l=0;l<v2.size();l++)
                        if(i!=j && i!=k && i!=l && j!=k && j!=l && k!=l)
                            solve(i,j,k,l);
    }
    //cout<<f.size()<<‘\n‘; 
    
    for(auto x:v1)cnt[x]++;
    for(auto S:f){
        for(int pos=0;pos<len-1;pos++)if(s[pos]!=‘0‘ && !(S>>pos & 1) && !(S>>pos+1 &1)){//可以遮掉不是0开头的两位 
             int tmp[10]={};
             for(int i=0;i<pos;i++)
                 if(!(S>>i & 1))
                     tmp[s[i]-‘0‘]++;
            for(int i=pos+2;i<len;i++)
                if(!(S>>i & 1))
                    tmp[s[i]-‘0‘]++;
            int flag=0;
            for(int i=0;i<=9;i++)
                if(tmp[i]>cnt[i])flag=1;
            if(!flag){
                cout<<1;return 0;
            }
        }
        for(int pos=0;pos<len;pos++)if(s[pos]!=‘0‘ && !(S>>pos & 1)){//可以遮掉不是0开头的1位 
             int tmp[10]={};
             for(int i=0;i<pos;i++)
                 if(!(S>>i & 1))
                     tmp[s[i]-‘0‘]++;
            for(int i=pos+1;i<len;i++)
                if(!(S>>i & 1))
                    tmp[s[i]-‘0‘]++;
            int flag=0;
            for(int i=0;i<=9;i++)
                if(tmp[i]>cnt[i])flag=1;
            if(!flag){
                cout<<1;return 0;
            }
        }
    }
    cout<<0;
}