Codeforces 1084E - The Fair Nut and Strings - 思维

题解链接

https://lucien.ink

题目链接

https://codeforces.com/contest/1084/problem/E

题意

给你一个区间 $[s, t]$，其中 $s$ 和 $t$ 都是字符串，且长度为 $n$，只包含 ab 两种字符，问从这个区间内长度为 $n$ 的字符串中挑出 $k$ 个，最多可以有多少个不同的前缀。

思路

翻译一下，其实就是给你一个有左右边界且叶子数量必须小于等于 $k$ 个的字典树，最多能有多少个节点，模拟一下即可。

实现

https://pasteme.cn/2422

#include <bits/stdc++.h>
typedef long long ll;
const int maxn = int(5e5) + 7;
ll n, k, ans;
char a[maxn], b[maxn];
bool flag = true;
int main() {
    scanf("%lld%lld%s%s", &n, &k, a + 1, b + 1);
    ll sum = -1, cur = 1;
    while (cur <= n && a[cur] == b[cur]) cur++, ans++;
    for (ll i = cur; i <= n && flag; i++) {
        sum = sum * 2 + 'b' - a[i] + b[i] - 'a';
        if (sum + 2 >= k) ans += (n - i + 1) * k, flag = false;
        else ans += sum + 2;
    }
    printf("%lld\n", ans);
    return 0;
}