1 条题解

  • 1
    @ 2022-8-30 10:04:57
    #include<bits/stdc++.h>
    using namespace std;
    #define MN 605
    int add[MN][26],fail[MN],state[MN],nod,ans[MN*(1<<12|1)],fa[MN*(1<<12|1)],n,cnt,tot;
    //add:Trie树中的地址(address)
    bool vis[MN][1<<12|1];
    char C[MN],ch[51];
    queue<int>Q,Q1,Q2;
    void getfail(){
        for(int i=0;i<26;++i)
            if(add[0][i])Q.push(add[0][i]);
        while(!Q.empty()){
            int x=Q.front();
            Q.pop();
            for(int i=0;i<26;++i)
                if(add[x][i]){
                    fail[add[x][i]]=add[fail[x]][i];
                    state[add[x][i]]|=state[add[fail[x]][i]];//它的fail指针包含的字符串它也包含
                    Q.push(add[x][i]);
                }
                else add[x][i]=add[fail[x]][i];
        }
    }//AC自动机建fail树
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;++i){
            scanf("%s",ch);
            int now=0,ln=strlen(ch);
            for(int j=0;j<ln;++j){
                if(!add[now][ch[j]-'A'])add[now][ch[j]-'A']=++cnt;
                now=add[now][ch[j]-'A'];
            }
            state[now]|=1<<(i-1);//i-1也不会冲突,省一点空间
            //有重复的,要用|
        }//建trie树
        getfail();
        Q1.push(0);
        Q2.push(0);
        //Q1:在Trie中的位置
        //Q2:状态压缩,表示当前包含了哪些要求的字符串
        vis[0][0]=1;
        int Ti=0;
        while(!Q1.empty()){
            int now=Q1.front(),St=Q2.front();
            Q1.pop();Q2.pop();
            if(St==((1<<n)-1)){
                while(Ti){
                    C[++nod]=ans[Ti];
                    Ti=fa[Ti];
                }//递归回去求答案
                for(int i=nod;i>0;--i)putchar(C[i]+'A');
                return 0;
            }
            for(int i=0;i<26;++i){
                if(!vis[add[now][i]][St|state[add[now][i]]]){
                    vis[add[now][i]][St|state[add[now][i]]]=1;
                    Q1.push(add[now][i]);
                    Q2.push(St|state[add[now][i]]);
                    //找出现新的状态
                    fa[++tot]=Ti;
                    ans[tot]=i;
                    //记录当前搜到的字符,同时建1棵关于答案的树,便于最后查询
                }
            }
            ++Ti;//Ti表示当前的搜索到的编号
        }
        return 0;
    }
    
    • 1

    信息

    ID
    1195
    时间
    1000ms
    内存
    32MiB
    难度
    7
    标签
    (无)
    递交数
    34
    已通过
    9
    上传者