B. The Fair Nut and Strings
题意：
在给定的字符串a和字符串b中找到最多k个字符串，使得不同的前缀字符串的数量最多。
分析：
建出trie树，给定的两个字符串就是trie树上的两条长度为n路径，那么就是在第n层的所有节点中，找到不大于k个点，（第n层的每个点向上到根的路径的路径上的字符组成一个长度为n字符串）。
两个第n层的节点一共会构成2n-lca个不同的前缀。所有可以根据这个贪心的选。每次尽量选已经走过的路径尽量少的路径。
从n往后枚举，计算长度为答案为i的可以选几个。
注意判断一下最后是否可以选择k个， 和已经选了的路径。
代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<map>
#include<queue>
#include<vector>
#define fi(s) freopen(s,"r",stdin)
#define fo(s) freopen(s,"w",stdout)
using namespace std;
typedef long long LL; inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} const int N = ;
char a[N], b[N]; int main () {
int n = read(); LL k; cin >> k;
scanf("%s%s", a + , b + ); LL now = , ans = , tot = ; for (int i = ; i <= n; ++i) {
now = now * ;
if (a[i] == 'b') now --;
if (b[i] == 'a') now --;
if (now >= k) { tot = k; break; }
}
if (tot == ) tot = now; now = ;LL last = ;
for (int i = ; i <= n; ++i) {
now = 1ll * now * ;
if (a[i] == 'b') now --;
if (b[i] == 'a') now --;
LL t = min(k, now); t = min(t, tot); t = min(t, now - last); t = max(t, 0ll);
ans += 1ll * t * (n - i + );
k -= t; tot -= t; last += t;
if ((!k) || (!tot)) break;
}
cout << ans;
return ;
}