Codeforces 1083B The Fair Nut and Strings

时间：2021-07-05 13:55:46

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);

}

相关文章