Lucien

Codeforces 1084E - The Fair Nut and Strings - 思维
Codeforces 1084E - The Fair Nut and Strings - 思维题解链接https...
扫描右侧二维码阅读全文
11
2018/12

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

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;
}
最后修改:2018 年 12 月 11 日 04 : 58 AM
谢谢老板!

发表评论