正解:AC自动机+最短路
解题报告:
这题之前考试考到辣,,,我连题目都没看懂这种傻逼事儿就不要说了QAQ
然后就港正解辣
首先这题可以用dp做?等下写
但是一般来说看到这种,第一反应就,先建个AC自动机呗
然后建完之后想怎么做呢
又有两个方法,分别港下
法一,最短路+dfs
首先想怎么样会变短呢,就是假如fail指针指向了某个串的中间一个节点,那么这个串的前面一段就可以省掉了,然后就变短了,是趴
那要保证最短,就可以直接在trie图上跑个最短路(要用spfa因为有环)
然后关于字典序最小,就用dfs暴力搜就好了
法二,利用bfs遍历
想到利用fail的时候的特点,在配fail的时候预处理出选择每个节点之后能覆盖的所有串
然后bfs地处理就好辣!
对辣有个小细节还比较难拍出来来着QAQ,,,
就是因为可能有同样的字符串,所以在建trie树的时候是|不是=
over!
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define rg register
#define rp(i,x,y) for(rg ll i=x;i<=y;++i) ll n,cnt,pre1[],pre2[],cntnod;
bool vis[][(<<)+];
struct tre{ll to[],fil,ed,lst;tre(){memset(to,,sizeof(to));ed=;fil=;}}tr[];
struct nd{ll id,tre,stat;}; inline ll read()
{
rg char ch=getchar();rg ll x=;rg bool y=;
while(ch!='-' && (ch>'' || ch<''))ch=getchar();
if(ch=='-')ch=getchar(),y=;
while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=getchar();
return y?x:-x;
}
inline void bd(string x,ll id)
{
ll lth=x.length()-,nw=;
rp(i,,lth){if(!tr[nw].to[x[i]-'A'])tr[nw].to[x[i]-'A']=++cnt;nw=tr[nw].to[x[i]-'A'];}
tr[nw].ed|=(ll)(<<id);
}
inline void fl()
{
queue<ll>Q;rp(i,,)if(tr[].to[i])Q.push(tr[].to[i]);
while(!Q.empty())
{
ll nw=Q.front();Q.pop();
//printf("nw=%lld fail=%lld last=%lld end=%lld\n",nw,tr[nw].fil,tr[nw].lst,tr[nw].ed);
rp(i,,)
{
if(tr[nw].to[i])
tr[tr[nw].to[i]].fil=tr[tr[nw].fil].to[i],
Q.push(tr[nw].to[i]),
tr[tr[nw].to[i]].lst=tr[tr[tr[nw].to[i]].fil].ed?tr[tr[nw].to[i]].fil:tr[tr[tr[nw].to[i]].fil].lst,
tr[tr[nw].to[i]].ed|=tr[tr[tr[nw].to[i]].lst].ed;
else tr[nw].to[i]=tr[tr[nw].fil].to[i];
}
}
}
inline void print(ll x){if(!x)return;print(pre1[x]);printf("%c",(char)(pre2[x]+'A'));}
inline void bfs()
{
queue<nd>Q;
Q.push((nd){,,tr[].ed});
while(!Q.empty())
{
nd nw=Q.front();Q.pop();
//printf("nw.tre=%lld nw.state=%lld nw.id=%lld\n",nw.tre,nw.stat,nw.id);
if(nw.stat==(<<n)-)return void(print(nw.id));
rp(i,,)
{
nd nodto;nodto.tre=tr[nw.tre].to[i];nodto.stat=(ll)nw.stat|tr[nodto.tre].ed;
if(vis[nodto.tre][nodto.stat])continue;
vis[nodto.tre][nodto.stat]=;nodto.id=++cntnod;pre1[nodto.id]=nw.id;pre2[nodto.id]=i;Q.push(nodto);
}
}
return;
} int main()
{
n=read();rp(i,,n){string x;cin>>x;bd(x,i-);}fl();bfs();
return ;
}
//发现命名什么的还是要下划线,,,决定开始使用下划线QwQ!
放的$code$是法二的!