题解：CF1085E Vasya and Templates

· · 题解

这题评紫纯属虚高，建议降绿。

前置知识：【5】深度优先搜索、【6】搜索的剪枝优化。

对于一个位置，如果它所对应的字符还没有匹配，就枚举所有合法的结果。如果已有匹配，也要判断其合法性。

另外一个要剪枝的地方就是如果一组数据已经找到解了，就立即退出。

具体来说，所有的位置都要维护它有没有在上下边界。类似于数位 dp 的转移。

实测 CF 过得很悬。跑了 4.3 秒以上。

笑点解析：我写了 cin/cout 的关闭同步流还在用 scanf/printf 输出。

#include<bits/stdc++.h>
#define int long long
#define mp(a,b) make_pair(a,b)
using namespace std;

int n,k;
string s,a,b;   // 三个核心字符串 
int s0[1919810],a0[1919810],b0[1919810];

int flag=0;
int cho[1919810];
int include13[1919810]; 
inline void dfs(int now,int a_,int b_){ //a_ b_ 都是边界数组  
    //两个边界情况 
    if(now==n+1){
        flag=1;
//      cout<<"谭总的世界-034"<<endl;
//      for(int i=1;i<=k;i++){
//          cout<<include13[i]<<' ';
//      }
//      cout<<endl;
        return;
    }
    int l=1,r=k;
    if(a_){
        l=a0[now];
    } 
    if(b_)  r=b0[now];  //调整边界 
    if(include13[s0[now]]){
        int sum=include13[s0[now]];
        if(sum<l||sum>r)    return;
        int da=a_*(sum==l);
        int db=b_*(sum==r); //代表两边的情况 
        dfs(now+1,da,db);
        return; 
    } 
    if(flag)    return;
    for(int i=l;i<=r;i++){
        if(!cho[i]){
            cho[i]=1;
            include13[s0[now]]=i;   //被选定的数 
            int da=a_*(i==l),db=b_*(i==r); 
            dfs(now+1,da,db);
            if(flag)    return;
            cho[i]=0;
            include13[s0[now]]=0;   //代表搜索无效时要反悔  
        }
        if(flag)    return;
    }
} 
void solve(){
    flag=0;
    cin>>k,cin>>s,cin>>a,cin>>b;
    n=s.size();
    for(int i=1;i<=n;i++){
        s0[i]=s[i-1]-'a'+1;
        a0[i]=a[i-1]-'a'+1;
        b0[i]=b[i-1]-'a'+1; //首先是初始化的过程  
    }
    for(int i=1;i<=k;i++){
        cho[i]=0;
    }
    for(int i=1;i<=k;i++){
        include13[i]=0; //代表初始时的清空  
    }
    dfs(1,1,1); //代表一上来卡满 
    if(!flag){
        cout<<"NO"<<endl;
        return;
    } 
    cout<<"YES"<<endl;
    int ptr=1;
    for(int i=1;i<=k;i++){
        if(!include13[i]){
            for(int j=ptr;j<=k;j++){
                if(!cho[j]){
                    cho[j]=1;
                    include13[i]=j;
                    ptr=j+1;
                    break;
                }
            }
        }
    }
    for(int i=1;i<=k;i++){
        printf("%c",include13[i]+96);
    }
    cout<<endl;
    return;
} 
signed main(){
//  ios::sync_with_stdio(0);
//  cin.tie(0);
//  cout.tie(0);
    int T;
    cin>>T;
    while(T--)  solve();
    cout<<endl;
    return 0;
} //一定要挽回罗琪钧的遗憾啊，一定会挽回罗琪钧的遗憾的！ 
//你还是住在的我回忆里 不出来 让我们微笑离开 让故事留下来