电脑报价网站,什么时候友情链接,图书馆新生专栏网站建设,网站源码中国有限公司正题
题目链接:https://www.luogu.com.cn/problem/P4762 题目大意
长度为nnn的目标串#xff0c;开始一个空串#xff0c;可以执行以下操作
在头或者尾加一个字符复制一个该串的逆串放在后面
求最少操作次数。 解题思路
我们可以知道答案肯定是一个回文串然后剩下的暴力…正题
题目链接:https://www.luogu.com.cn/problem/P4762 题目大意
长度为nnn的目标串开始一个空串可以执行以下操作
在头或者尾加一个字符复制一个该串的逆串放在后面
求最少操作次数。 解题思路
我们可以知道答案肯定是一个回文串然后剩下的暴力加上。
我们构建一个PAMPAMPAM然后用fif_{i}fi表示带该回文串需要的最少次数。
对于一个节点的转移有fymin{fx1}f_{y}min\{f_{x}1\}fymin{fx1} 就是该回文串头尾各加上一个字符。
该回文串还有可能是一个双倍回文即一个回文串在复制一个逆串后回文那么有我们要像[SHOI2011]双倍回文这道题目一样维护一个最长的不超过该串一半的回文后缀的节点halfihalf_ihalfi。
然后有转移 fxmin{fhalfx1lenx2−lenhalfx}f_{x}min\{f_{half_x}1\frac{len_x}{2}-len_{half_x}\}fxmin{fhalfx12lenx−lenhalfx}
然后答案就是min{n−lenxfx}min\{n-len_xf_{x}\}min{n−lenxfx}
时间复杂度O(4Tn)O(4Tn)O(4Tn)
如果用stdstdstd自带队列会比较慢需要自行卡常。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includequeue
using namespace std;
queueint q;
const int N1e510;
int T,n,m,half[N],f[N],ans;
int len[N],fail[N],next[N][4],cnt;
char s[N];
int z(char x){if(xA) return 0;if(xC) return 1;if(xG) return 2;if(xT) return 3;
}
int get_fail(int x,int n){while(s[n-len[x]-1]!s[n])xfail[x];return x;
}
void Make_PAM(){int last0;len[1]-1;s[0]#;cntfail[0]1;for(int i1;in;i){int valz(s[i]),xget_fail(last,i);if(!next[x][val]){len[cnt]len[x]2;int yget_fail(fail[x],i);fail[cnt]next[y][val];if(len[cnt]2) half[cnt]fail[cnt];else{int zhalf[x];while(s[i-len[z]-1]!s[i]||((len[z]2)1)len[cnt])zfail[z];half[cnt]next[z][val];}next[x][val]cnt;}lastnext[x][val];}return;
}
void Solve(){ansn;for(int i2;icnt;i)f[i]len[i];f[0]1;q.push(0);while(!q.empty()){int xq.front();q.pop();f[x]min(f[x],f[half[x]]1len[x]/2-len[half[x]]);ansmin(ans,n-len[x]f[x]);for(int i0;i4;i){int ynext[x][i];if(!y) continue;f[y]min(f[y],f[x]1);q.push(y);}}return;
}
int main()
{scanf(%d,T);while(T--){for(int i0;icnt;i)for(int j0;j4;j)next[i][j]0;scanf(%s,s1);nstrlen(s1);Make_PAM();Solve();printf(%d\n,ans);}return 0;
}
