题意

给出两个长度为n的01字符串S和T。

选出k个字典序在S和T之间的长度为n的01字符串，使得尽可能多的字符串满足其是所选字符串中至少一个串的前缀。

这是一道思路比较奇怪的类似计数dp的题。

首先考虑如果把选出的这些串插入到一个trie树中的话，算产生的贡献可以理解为，从根节点向下画了k条长度为n的线，最大化它们所经过的点的总个数。

进一步发现，每一层节点如果不受s和t的限制的话，一定可以满足每一层都有k个点被经过。

因此，剩下要做的就是算一下这个s和t的限制，即每一层有多少个节点。

记dp[i][0/1][0/1]表示第i层，满足前i位是否与s相同，前i位是否与t相同，按照定义转移即可，复杂度O(n)。

最后统计答案的时候把每一层的节点个数和k取min后加入答案即可。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define N 1100000#define L 1000000#define eps 1e-7#define ll long longusing namespace std;inline ll read(){ char ch=0; ll x=0,flag=1; while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;} while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*flag;}const ll inf=1e14+7;char s[N],t[N];ll dp[N][2][2];int main(){ ll n=read(),m=read(); scanf("%s",s+1);scanf("%s",t+1); dp[0][1][1]=1; for(ll i=0;i