[atARC058F]Lroha Loves Strings

贪心，求出前$i$个字符串所能组成的字典序最小的字符串$ans$（特别的，这里的字典序有$ab>abc$），同时保证剩下的长度能通过$l_{i+1},...,l_{n}$拼接

考虑插入一个字符串$s_{i+1}$，在$ans$的任意拼接处（包括开头）可以替换上这个串，之后使得$ans$的字典序最小且长度合法，容易发现有：第一个能使$ans$字典序变小（这里指严格变小）的位置一定是使得$ans$字典序最小的位置（如果不存在就加在最后）

枚举插入的位置（所有合法断点的位置），相当于要判断插入后能否让$ans$更小，由于前半部分相同，即比较$s_{i+1}$和$ans$的一个后缀，暴力比较复杂度为$o(n^{2}k)$，无（ke）法（yi）通过

考虑二分+hash找到lcp，之后判断下一个字符即可，这样复杂度为$o(nk\log_{2}k)$（这里不是$o(n^{2}\log_{2}k)$的原因是需要计算hash值），常数比较优秀可以通过

还可以发现这是一个exkmp的模板题，时间复杂度可以做到$o(nk)$

然而这道题还有很多的细节，这里给出几组毒瘤的数据（/为回车）：3 3/abd/ab/c，3 3/abc/ab/d，4 3/a/b/abd/c，3 3/a/aa/ab，4 4/a/a/aa/b，4 4/a/aa/c/ab（答案自己手算）

（不过atcoder的数据极水，这些数据全错+暴力求lcp都是可以通过的）

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 10005

 4 int n,k,len,l[N],a[N],b[N],extend[N],f[2005][N];

 5 char s[2005][N],ans[N];

 6 void calc(int l1,char *s1,int l2,char *s2){

 7     memset(extend,0,sizeof(extend));

 8     for(int i=0;i<l1;i++)

 9         while ((i+extend[i]<l1)&&(extend[i]<l2)&&(s1[i+extend[i]]==s2[extend[i]]))extend[i]++;

10 }

11 int main(){

12     scanf("%d%d",&n,&k);

13     for(int i=1;i<=n;i++){

14         scanf("%s",s[i]);

15         l[i]=strlen(s[i]);

16     }

17     f[n+1][0]=1;

18     for(int i=n;i;i--)

19         for(int j=k;j>=0;j--){

20             f[i][j]=f[i+1][j];

21             if (j>=l[i])f[i][j]|=f[i+1][j-l[i]];

22         }

23     len=a[0]=0;

24     for(int i=1;i<=n;i++){

25         calc(len,ans,l[i],s[i]);

26         b[0]=0;

27         int flag=0,lll=0,aa=0,bb=0;

28         for(int j=0,ll=0;j<=a[0];ll+=a[++j]){

29             if ((k<ll+l[i])||(!f[i+1][k-ll-l[i]])){

30                 if (j<a[0])b[++b[0]]=a[j+1];

31                 continue;

32             }

33             int x=extend[ll];

34             if (x==l[i]){

35                 b[++b[0]]=a[j+1];

36                 continue;

37             }

38             if (ll+x==len){

39                 flag=1;

40                 aa=j;

41                 bb=b[0];

42                 lll=ll;

43                 if (j<a[0])b[++b[0]]=a[j+1];

44                 continue;

45             }

46             if (ans[ll+x]>s[i][x]){

47                 flag=0;

48                 len=ll+l[i];

49                 for(int p=0;p<l[i];p++)ans[ll+p]=s[i][p];

50                 while ((j<a[0])&&(a[j+1]<=x)){

51                     x-=a[++j];

52                     l[i]-=a[j];

53                     b[++b[0]]=a[j];

54                 }

55                 b[++b[0]]=l[i];

56                 break;

57             }

58             if (j<a[0])b[++b[0]]=a[j+1];

59         }

60         if (flag){

61             int x=extend[lll],j=aa,ll=lll;

62             b[0]=bb;

63             len=ll+l[i];

64             for(int p=0;p<l[i];p++)ans[ll+p]=s[i][p];

65             while ((j<a[0])&&(a[j+1]<=x)){

66                 x-=a[++j];

67                 l[i]-=a[j];

68                 b[++b[0]]=a[j];

69             }

70             b[++b[0]]=l[i];

71         }

72         mempcpy(a,b,sizeof(a));

73     }

74     printf("%s",ans);

75 }

巴特西

[atARC058F]Lroha Loves Strings

最新文章

热门文章