Codeforces 1083B The Fair Nut and Strings

Description

给定两个由 \('a'\), \('b'\) 组成的字符串 \(a\), \(b\),以及两个整数 \(n\) 和 \(k\)

\(n\) 表示字符串 \(a\),\(b\) 的长度, 要求你最多 选 \(k\) 个 字符串 \(t_i\) 满足 \(a<=t_i<=b\), 并且使得这些字符串的前缀的数量最大

Solution

很妙的解法。

所有可以选择的字符串可以看成一棵字典树。

我们发现, 如果第\(i\)层的节点数 \(<=k\), 那么这一层的前缀都可以加入集合

反之, 第\(i\)层的节点数 \(>k\), 那么这一层的前缀最多有\(k\)个加入集合。这些前缀长度为 \(i\) 且互不相等

所以只需要算出每一层节点的个数并加入贡献, 就能得到答案

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define up(a, b) (a = a > b ? a : b)
#define down(a, b) (a = a > b ? b : a)
#define cmax(a, b) (a > b ? a : b)
#define cmin(a, b) (a > b ? b : a)
#define Abs(a) ((a) > 0 ? (a) : -(a))
#define rd read()
#define db double
#define LL long long
using namespace std; LL read() {
LL X = 0, p = 1; char c = getchar();
for (; c > '9' || c < '0'; c = getchar())
if (c == '-') p = -1;
for (; c >= '0' && c <= '9'; c = getchar())
X = X * 10 + c - '0';
return X * p;
} const int N = 5e5 + 5; char a[N], b[N]; int main()
{
int n = rd, k = rd;
scanf("%s%s", a + 1, b + 1);
LL ans = 0, tmp = 1;
for (int i = 1; i <= n; ++i) {
tmp *= 2;
if (b[i] == 'a')
tmp--;
if (a[i] == 'b')
tmp--;
if (tmp > k)
tmp = k + 1;
ans += cmin(tmp, k);
}
printf("%lld\n", ans);
}
上一篇:通用mapper的使用


下一篇:第八章| 3. MyAQL数据库|Navicat工具与pymysql模块 | 内置功能 | 索引原理