题目大意
有一个字符串\(p\)。一开始字符串\(s\)为空串。
接下来进行若干次操作：在\(s\)的某个空隙中插入\(p\)。 给出操作后的\(s\)，问长度最小的\(p\)。思考历程
感觉是一道神仙题。
于是考虑暴力。 在\(s\)前面找连续的最长串，作为\(p\)的前缀。显然这个串中只出现过一次\(s_1\) 同样地，在后面也找一条，作为后缀。 将前缀出现的位置和后缀出现的位置标记一下。 统计每个字符出现的个数，求最大公因数\(g\)，表明操作的次数为\(g\)的因数。 然后按照长度从小到大枚举子串，如果当前子串的头和尾都被标记了，并且中间的字符个数的比例和整个字符串的比例相等，就取这个字符串作为\(p\)暴力判断。 暴力判断的时候，每次用\(KMP\)找出一个子串，将它删去，递归。 如果有多个这样的子串，那就分别搞。然而出现了某细节错误，导致只有\(10\)分。
正解
这题的正解居然是\(DP\)！
考虑一个字符串，它的所有元素会在后面的操作中逐渐分离，但是它们的相对顺序是不变的。 而且它原来相邻的两个元素在后面的操作之后，两个元素之间的空间可以转化成个子问题。如果可行，则这个子问题也必定可行。 先考虑普通的\(DP\)思路：\(f_{l,r,k}\)表示区间\([l,r]\)中，有零散的\(k\)个字母拼起来等于\(p_{1..k}\)，其它的都合法，是否可行。 转移有两种：一种是从\(f_{l,r-1,k-1}\)转移过来，条件是\(s[j]=p[k]\)，就是加上一个零散的元素。 另一种是从\(f_{l,j,k} \ and \ f_{j,r,0}\)，就是在后面拼一个合法的。 然而这样会\(TLE\)。 紧接着我们发现，实际上，\(k=(r-l+1)\mod len\) 所以就可以省去一维，然后就可以\(AC\)了。代码
using namespace std;#include#include #include #include #define N 210inline int gcd(int a,int b){ while (b){ int k=a%b; a=b; b=k; } return a;}int n,nt;char s[N],t[N],s2[N][N];int buc[255],b2[255];int m;char c[255];bool beg[N],end[N];int p[N];bool f[N][N];inline bool work(int k,int len){ nt=len; for (int i=1;i<=nt;++i) t[i]=s[k+i-1]; memset(f,0,sizeof f); for (int i=n;i>=1;--i){ f[i][i]=(s[i]==t[1]); for (int j=i+1;j<=n;++j){ f[i][j]|=(f[i][j-1]&&s[j]==t[(j-1-i+1)%nt+1]); for (int k=i+(j-i)%nt;k 1 && s[r-1]!=s[n]) --r; memset(beg,0,sizeof beg); memset(end,0,sizeof end); for (int i=1,j;i+l-1<=n;++i){ for (j=1;j<=l;++j) if (s[i+j-1]!=s[j]) break; if (j<=l) continue; beg[i]=1; } for (int i=n,j;i+r-n>=1;--i){ for (j=n;j>=r;--j) if (s[i+j-n]!=s[j]) break; if (j>=r) continue; end[i]=1; } for (int len=max(l,n-r+1);len<=n;++len) if (n%len==0 && g%(n/len)==0){ int t=n/len,hg=0; memset(b2,0,sizeof b2); for (int i=1;i<=len;++i) b2[s[i]]++; for (int i=1;i<=m;++i) if (b2[c[i]]*t==buc[c[i]]) hg++; int i; for (i=1;i+len-1<=n;++i){ if (beg[i] && end[i+len-1] && hg==m){ if (work(i,len)){ for (int j=i;j
总结
这都想不出来……我真是太菜了……