2021年4月30日 The Fair Nut and Strings

题号 NC113276
名称 The Fair Nut and Strings
来源 0

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

给你两个长度为n的只由字母'a'和'b'组成的字符串 $A，B$ ，要求你选出 $k$ 个长度为 $n$ 且字典序大小不大于 $A$ 且不小于 $B$ 的字符串

现给出一个”满足要求的字符串“的定义：对于任意一个满足要求的字符串，它至少是选出来的k个字符串的其中一个字符串的前缀

如果一个满足要求的字符串它是这 $k$ 个字符串中多个字符串的前缀，这个满足要求的字符串只会被计算一次

求如何选可以得到最多的”满足要求的字符串“，输出最多的个数作为答案。

样例

输入
2 4
aa
bb
输出
6

输入
3 3
aba
bba
输出
8

输入
4 5
abbb
baaa
输出
8

算法1

(找公式 + 递推)

挖掘性质

我们发现给定的两个长度为 $n$ 的字符串有个很强的性质就是只由'a'和'b'组成

那么我们完全可以将这两个字符串看成两个二进制串

'a'看成二进制表示中的0，'b'看成二进制表示中的1

这样做的好处就是可以将两个字符串的字典序比较转化成二进制表示的数值比较（两种比较结果也可以一一对应）

转化到了二进制数值比较就能将问题公式化

找公式

假设开始我们有两个长度为1的字符串 $A = "a",B = "b"$

转化到对应的二进制序列 $A \rightarrow X = 0$ , $B \rightarrow Y = 1$

那么字典序不小于 $A$ ，不大于 $B$ 的字符串有多少？

有 $Y - X + 1$ 个（这里是数值加减）

我们令 $Y_1 = 1,X_1 = 0,Z_1 = Y_1 - X_1 + 1$ （ $Z_1为长度为1的字符串不同个数$ ）

假如我们往 $A$ 后面加一个字符'a', $B$ 后面加一个字符'b',对应的 $X_2 = 00$ , $Y_2 = 11$

字典序不小于 $A$ ，不大于 $B$ 的字符串的个数就为

$Z_2 = Y_2 - X_2 + 1$

$Z_2 = (Y_1 * 2 + 1) - (X_1 * 2 + 0) + 1$ （类似秦九昭算法）

$Z_2 = 2 * Y_1 - 2 * X_1 + 2$

$Z_2 = 2 * Z_1$
假如我们往 $A$ 后面加一个字符'a', $B$ 后面加一个字符'b',对应的 $X_2 = 00$ , $Y_2 = 10$

字典序不小于 $A$ ，不大于 $B$ 的字符串的个数就为

$Z_2 = Y_2 - X_2 + 1$

$Z_2 = (Y_1 * 2 + 0) - (X_1 * 2 + 0) + 1$

$Z_2 = 2 * Y_1 - 2 * X_1 + 1$

$Z_2 = 2 * Z_1 - 1$
假如我们往 $A$ 后面加一个字符'b', $B$ 后面加一个字符'b',对应的 $X_2 = 01$ , $Y_2 = 11$

字典序不小于 $A$ ，不大于 $B$ 的字符串的个数就为

$Z_2 = Y_2 - X_2 + 1$

$Z_2 = (Y_1 * 2 + 1) - (X_1 * 2 + 1) + 1$

$Z_2 = 2 * Y_1 - 2 * X_1 + 1$

$Z_2 = 2 * Z_1 - 1$
假如我们往 $A$ 后面加一个字符'b', $B$ 后面加一个字符'a',对应的 $X_2 = 01$ , $Y_2 = 10$

字典序不小于 $A$ ，不大于 $B$ 的字符串的个数就为

$Z_2 = Y_2 - X_2 + 1$

$Z_2 = (Y_1 * 2 + 0) - (X_1 * 2 + 1) + 1$

$Z_2 = 2 * Y_1 - 2 * X_1$

$Z_2 = 2 * Z_1 - 2$

推广到 $n$ ,我们就得到如下递推式：

* $A[i]$ , $B[i]$ 表示字符串的第 $i$ 个字符

当 $A[i]$ == 'a' , $B[i]$ == 'b' 时, $Z_i = Z_{i - 1} * 2$
当 $A[i]$ == $B[i]$ 时, $Z_i = Z_{i - 1} * 2 - 1$
当 $A[i]$ == 'b' , $B[i]$ == 'a' 时, $Z_i = Z_{i - 1} * 2 - 2$

求解答案

有了上面的递推式我们就可以求出给定的长度为 $n$ 的 $A$ , $B$ 字符串之间有多少个长度为 $n$ 的字符串了

更进一步说我们是知道任意长度（包括长度为n）的前缀字符串有多少了

回到问题，题目要求我们选出 $k$ 个长度为 $n$ 的字符串然后使得构成这些字符串的前缀的不同字符串最多

我们就考虑每一个长度的前缀最多能选多少个

对于长度为 $i$ 的所有字符串，其个数为 $Z_i$

如果 $k >= Z_i$ ，长度为i的满足条件的不同字符串我们最多只能找到 $Z_i$ 个(长度为 $i$ 的不同字符串只有 $Z_i$ 个，意味着这 $k$ 个字符串长度为 $i$ 的前缀会有重复)

如果 $k < Z_i$ ,那么长度为i的满足条件的不同字符串我们最多只能找到 $k$ 个(前缀只有k个)

那么答案 $ans = \sum_{i = 1}^{n}min(Z_i,k)$

细节:
由于z[i]是单调的，当Z[i]的值大于k时就不必再再计算Z[i + 1]了（否则会溢出），必定是加k
Z[i]的计算只会用到前一项所以用一个变量res维护即可

时间复杂度 $O(N)$

参考文献

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <deque>

using namespace std;
typedef unsigned long long LL;
const int N = 500010;
char A[N],B[N];
int n;
LL k;

int main()
{
    cin >> n >> k ;
    scanf("%s%s",A,B);
    LL res = 0,ans = 0;
    for(int i = 0;i < n;i ++ )
    {
        if(res <= k)
        {
            if(i == 0)
            {
                if(A[i] == B[i]) res = 1;
                else res = 2;
            }else
            {
                if(B[i] == 'b' && A[i] == 'a') res = res * 2ll;
                else if(B[i] == A[i]) res = 2ll * res - 1ll;
                else res = 2ll * res - 2ll;
            }
        }
        ans += min(res,k);
    }
    cout << ans << endl;
    return 0;
}