期望得分：100+100+20=220

实际得分：100+100+20=220

 

模拟栈

#include
      
       #include
       
        using namespace std;#define N 10002char s[N],st[N];int top;int main(){    freopen("kakutani.in","r",stdin);    freopen("kakutani.out","w",stdout);    int n,len,lt;    scanf("%d",&n);    while(n--)    {        scanf("%s",s);        len=strlen(s);        top=0;        for(int i=0;i
       
      

 

枚举i为间隔K个录像的左端点，那么间隔录像为[i,i+k-1]

设第一段为[Sa,Ta]，第二段为[Sb,Tb]，Ma为min[Sa,Ta],Mb为min[Sb,Tb]

随着Sa的左移，Ma单调不增

随着Tb的右移，Mb单调不增

如果枚举Sa，则有以下式子： Ta-Sa+1+Tb-Sb+1>=B

即Tb>=B+Sa+Sb-Ta-2

因为Tb右移，Mb单调不增，所以Tb取等号最优

所以二分Sa的位置，用st表查询Ma，Mb

#include
      
       #include
       
        #include
        
         #include
         
          #define N 1000001using namespace std;int st[N][21];int p,n;int logg2[N];void read(int &x){    x=0; char c=getchar();    while(!isdigit(c)) c=getchar();    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}void stpre(){    p=log2(n);    for(int j=1,k=2;j<=p;j++,k<<=1)        for(int i=1;i+k-1<=n;i++)            st[i][j]=min(st[i][j-1],st[i+(k>>1)][j-1]);    for(int i=1;i<=n;i++) logg2[i]=log2(i);}int getmin(int s,int t){    p=logg2[t-s+1];    int len=1<
          
           >1;            Tb=max(Sb+A-1,B+mid+Sb-Ta-2);            Ma=getmin(mid,Ta); Mb=getmin(Sb,Tb);            tmp=max(tmp,min(Ma,Mb));            if(Ma
          
         
        
       
      

 

数位DP

dp[i][j][0/1] 前i位匹配到X的第j位，是否已经包含1个X的数的个数

二分，计算<=mid的数里的答案

其中的匹配用kmp

#include
      
       #include
       
        using namespace std;typedef long long LL;LL L,R,K;LL dp[19][19][2];int len,f[19];char X[19];int a[19],cnt;void kmp(){    len=strlen(X);    int j;    for(int i=1;i
        
         >1;        if(query(mid)-tmp