题解 | #The Fair Nut and Strings#

题意：在所有长度为n，字典序在s和t的，只有'a','b'组成的字符串中，选取k个，然后让他们前缀组成的集合最大。

思路：如果我们把字符二叉树画出来，一个字符串对应根到叶子的一条路径。

我们发现如果某一层的节点数比k小，那么这一层的节点都可以被经过。按照题意处理即可。

#include<bits/stdc++.h>
#define maxn 500010
using namespace std;
typedef long long LL;
LL n,k;
char a[maxn],b[maxn]; 
LL res,ans;
int main(){
    scanf("%d%d%s%s",&n,&k,a+1,b+1);
    res = 1;
    for(int i=1;i<=n;i++){
        res*=2;  //每一层的节点数
        if(a[i]=='b') res--;
        if(b[i]=='a') res--;
        if(res>1E9) res=1E9;
        ans += min(res,k);
    }
    cout<<ans<<endl;
    return 0;
}