我真的是。。调了一百年。。

傻逼的人生。。

而且这题好像可以用sam做哎！我Y出了一个奇怪的办法。。

好吧sam是不能做这题的。搞错了。

说说后缀数组好了。。

 

搞后缀数组

然后我们要二分一个子串，判断是否有一种划分方法，满足划分出来的所有串的最大子串不超过这个串。

二分是第now个后缀

二分第now个多长的前缀

————确定了一个子串

首先，这题具有单调性，而且是求最大串最小，所以我们可以二分答案串。

　　怎么二分答案串呢，我们不是已经用后缀数组求出了sa数组吗，sa数组表示的串是排过序的，其中每个后缀的前缀子串大小按长度的递增而递增，所以可以在sa数组里面二分。（我是先二分后缀，再二分长度）

　　然后是判断，怎么判断是不是可以划分成至多k个串使他们都不超过二分串。

　　还是在sa上做。

　　如果他的sa位置小于mid，那么不用管，因为它怎么样都是小于二分串的。

　　如果他的sa位置大于等于mid，而且他跟二分串没有LCP，那么这个二分一定没有答案，因为最小二分都使他不符合。

　　除此之外，求出sa位置大于等于mid的所有串跟二分串的LCP，在sa[i]~sa[i]+lcp-1的位置上一定要至少打一个标记，因为不打标记它就会比二分串大了。

　　

　　所以最后我们会得到很多个区间，在这些区间里面至多打k-1个标记，使得每个区间中有含有一个标记。

 

　　转化成了这样，就很容易做了。貌似是smg区间覆盖之类的问题。排个序，去个重，判断+累加一下就可以了。

 

引用自

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 using namespace std; 8 9 const int N=100100,Inf=(int)1e9; 10 int K,n,cl,ed,r[N],h[N],t[N],rk[N],Rs[N],sa[N],y[N],wr[N]; 11 char c[N]; 12 13 int minn(int x,int y){ return x
           
            =1;i--) sa[Rs[rk[i]]--]=i;//debug 22 23 int ln=1,p=0; 24 while(p
            
             ln) y[++k]=sa[i]-ln; 30 for(int i=1;i<=cl;i++) wr[i]=rk[y[i]]; 31 32 for(int i=1;i<=m;i++) Rs[i]=0; 33 for(int i=1;i<=cl;i++) Rs[wr[i]]++; 34 for(int i=2;i<=m;i++) Rs[i]+=Rs[i-1]; 35 for(int i=cl;i>=1;i--) sa[Rs[wr[i]]--]=y[i];//debug 36 37 for(int i=1;i<=cl;i++) wr[i]=rk[i]; 38 for(int i=cl+1;i<=cl+ln;i++) wr[i]=0; 39 rk[sa[1]]=1; 40 p=1; 41 for(int i=2;i<=cl;i++) 42 { 43 if(wr[sa[i]]!=wr[sa[i-1]] || wr[sa[i]+ln]!=wr[sa[i-1]+ln]) p++; 44 rk[sa[i]]=p; 45 } 46 ln*=2;m=p; 47 // for(int i=1;i<=cl;i++) printf("%d ",rk[i]);printf("\n"); 48 // for(int i=1;i<=cl;i++) printf("%d ",sa[i]);printf("\n"); 49 } 50 sa[0]=rk[0]=0; 51 } 52 53 void get_h() 54 { 55 int k=0; 56 for(int i=1;i<=cl;i++) if(rk[i]!=1) 57 { 58 int j=sa[rk[i]-1]; 59 if(k) k--; 60 while(c[i+k]==c[j+k] && i+k<=cl && j+k<=cl) k++; 61 h[rk[i]]=k; 62 } 63 h[1]=0; 64 } 65 66 bool ok(int ll,int rr) 67 { 68 int k=rr-ll+1; 69 memset(t,0,sizeof(t)); 70 memset(r,0,sizeof(r)); 71 for(int i=rk[ll];i<=cl;i++) 72 { 73 if(i!=rk[ll]) k=minn(k,h[i]); 74 else if(rr==cl) continue; 75 if(k==0) return 0; 76 if(t[sa[i]]==0 || sa[i]+k-1
             
              =1;i--) 80 { 81 if(!t[i]) continue; 82 if(!pr) {pr=i;continue;} 83 if(pr<=t[i]) t[i]=0; 84 pr=t[i]; 85 } 86 for(int i=1;i<=cl;i++) if(t[i]) r[t[i]]=i; 87 pl=0,pr=0,cut=0,ans=0; 88 for(int i=cl;i>=1;i--) 89 { 90 if(!r[i]) continue; 91 if(!pl) {pl=r[i],pr=i;cut=r[i];ans++;continue;} 92 if(i
              
               =r[i] && cut<=i)) cut=r[i],ans++; 96 } 97 pl=r[i],pr=i; 98 } 99 if(ans<=K-1) return 1;100 return 0;101 }102 103 int check(int now)104 {105 int ll=sa[now]+h[now],rr=cl,mid;106 while(ll<=rr)107 {108 mid=(ll+rr)/2;109 if(ok(sa[now],mid)) 110 {111 rr=mid;112 if(ll==rr) return ll;113 }114 else ll=mid+1;115 }116 if(ll<=rr) return ll;117 return 0;118 }119 120 int main()121 {122 // freopen("a.in","r",stdin);123 freopen("magic.in","r",stdin);124 freopen("magic.out","w",stdout);125 scanf("%d",&K);126 scanf("%s",c+1);127 cl=strlen(c+1);128 get_sa(26);129 get_h();130 int ll=1,rr=cl,mid,now;131 while(ll
              
             
            
           
          
         
        
       
      
     

 

贴一下代码啦。