搜索敏感词后很多网站打不开了,科技公司网站设计公司,做网站 什么语言好,网站加地图标记正题
题目链接:https://www.luogu.com.cn/problem/P6698 题目大意
有一个包含0∼G−10\sim G-10∼G−1的字符集#xff0c;其中有nnn种变换#xff0c;能够将一个字符ai(ai1)a_i(a_i1)ai(ai1)变为一串字符bib_ibi#xff0c;当一个字符串中只剩下000和1…正题
题目链接:https://www.luogu.com.cn/problem/P6698 题目大意
有一个包含0∼G−10\sim G-10∼G−1的字符集其中有nnn种变换能够将一个字符ai(ai1)a_i(a_i1)ai(ai1)变为一串字符bib_ibi当一个字符串中只剩下000和111时变换就结束了。
然后给出mmm个匹配串cic_ici。现在对于每个字符i∈[2,G−1]i\in[2,G-1]i∈[2,G−1]是否字符iii无论变化结束时都含有至少一个匹配串如果不是求一个最短的不包含任何匹配串的最终串长度。
保证每个在[2,G−1][2,G-1][2,G−1]的字符都能进行变化匹配串中只包含0/10/10/1。
∑ti≤50,∑∣bi∣≤100,n≤100,2G≤n2\sum t_i\leq 50,\sum |b_i|\leq 100,n\leq 100,2G\leq n2∑ti≤50,∑∣bi∣≤100,n≤100,2G≤n2 解题思路
有匹配的问题我们先拿所有的cic_ici出来建一棵AC自动机然后考虑怎么计算每个字符能从哪个状态跳到哪个状态。
注意我们在AC自动机上走状态时不能走到包含匹配串的状态这样我们可以将无论如何都包含匹配串视为最短不包含匹配串的长度无穷大。
那么我们考虑dp这个最短的长度设fi,s,tf_{i,s,t}fi,s,t表示字符iii经过变换后能从状态sss走到状态ttt的最短长度。
转移时我们考虑枚举一个变换iii再枚举一个起点sss然后设gj,xg_{j,x}gj,x表示现在走到bi,jb_{i,j}bi,j在状态xxx时的最短长度那么转移时就有 gj1,ymin{gj,xfbi,j,x,y}g_{j1,y}min\{g_{j,x}f_{b_{i,j},x,y}\}gj1,ymin{gj,xfbi,j,x,y}
但是会注意到fi,s,tf_{i,s,t}fi,s,t之间的转移并不是一个单向的关系会发现这是一个和最短路很类似的转移我们考虑魔改一下SPFA。
我们先把0,10,10,1加入队列然后每次取出队头xxx我们把所有包含字符xxx的bib_ibi都拿出来跑一次ggg如果这次跑出来的ggg能够更新fai,s,tf_{a_i,s,t}fai,s,t那么我们就把aia_iai入队如果之前aia_iai不在队列中。
我们视SPFA的复杂度为O(n2)O(n^2)O(n2)记AC自动机状态数为kkk每做一次转移应该是O(∣bi∣k3)O(|b_i|k^3)O(∣bi∣k3)那么这题中SPFA的复杂度应该就是O(G∑∣bi∣k3)O(G\sum |b_i|k^3)O(G∑∣bi∣k3)实际上跑起来常数会很小可以通过本题。 code
#includecstdio
#includecstring
#includealgorithm
#includequeue
#includevector
#define ll long long
using namespace std;
const ll N105,inf1e18;
ll G,n,m,a[N],f[N][N][N],g[N][52];
ll cnt,ch[N][2],fail[N];bool ed[N],v[N];
queueint q;vectorint b[N],T[N];
void ins(ll n){ll x0;for(ll i1,c;in;i){scanf(%lld,c);if(!ch[x][c])ch[x][c]cnt;xch[x][c];}ed[x]1;return;
}
void getfail(){for(ll i0;i2;i)if(ch[0][i])q.push(ch[0][i]);while(!q.empty()){ll xq.front();q.pop();ed[x]|ed[fail[x]];for(ll i0;i2;i){if(ch[x][i]){fail[ch[x][i]]ch[fail[x]][i];q.push(ch[x][i]);}else ch[x][i]ch[fail[x]][i];}}return;
}
bool solve(int i){bool flag0;for(ll s0;scnt;s){if(ed[s])continue;memset(g,0x3f,sizeof(g));g[0][s]0;for(ll j0;jb[i].size();j){for(ll x0;xcnt;x){if(g[j][x]inf)continue;for(ll y0;ycnt;y)g[j1][y]min(g[j1][y],g[j][x]f[b[i][j]][x][y]);}}for(ll x0;xcnt;x){flag|(g[b[i].size()][x]f[a[i]][s][x]);f[a[i]][s][x]min(f[a[i]][s][x],g[b[i].size()][x]);}}return flag;
}
void SPFA(){q.push(0);q.push(1);v[0]v[1]1;while(!q.empty()){int xq.front();q.pop();v[x]0;for(int i0;iT[x].size();i){int yT[x][i];if(solve(y)!v[a[y]])q.push(a[y]),v[a[y]]1;}}return;
}
signed main()
{scanf(%lld%lld%lld,G,n,m);for(ll i1,k;in;i){scanf(%lld%lld,a[i],k);for(ll j1,x;jk;j){scanf(%lld,x),b[i].push_back(x);T[x].push_back(i);}}for(ll i1,k;im;i){scanf(%lld,k);ins(k);}getfail();ll k0;memset(f,0x3f,sizeof(f));for(ll i0;icnt;i){if(ed[i])continue;if(!ed[ch[i][0]])f[0][i][ch[i][0]]1;if(!ed[ch[i][1]])f[1][i][ch[i][1]]1;}SPFA();for(ll i2;iG;i){ll ansinf;for(ll x0;xcnt;x)ansmin(ans,f[i][0][x]);if(ansinf)puts(YES);else printf(NO %lld\n,ans);}return 0;
}
