脚本宝典收集整理的这篇文章主要介绍了cf1083 B. The Fair Nut and Strings（思维），脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

题意：

k个长为n的字符串（未知），只由字母a和b组成，且字典序均介于串A和串B之间。问集合 (S={ p:p为至少一个串的前缀 }) 最大能是多少。

思路：

想象一棵trie，若无字典序限制则每层的节点数是上一层的2倍。考虑字典序，则只有两种边界情况非法。

每层最多能取k个

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
long long n, k, res, ans, M = 1e9;
char a[N], b[N];
signed main()
{
    scanf("%lld%lld%s%s", &n, &k, a + 1, b + 1);

    res = 1;
    for(int i = 1; i <= n; i++)
    {
        res *= 2;
        res -= a[i]=='b';
        res -= b[i]=='a';
        res = min(M, res);
        ans += min(k, res);
    }

    printf("%lld", ans);

    return 0;
}

脚本宝典总结

以上是脚本宝典为你收集整理的cf1083 B. The Fair Nut and Strings（思维）全部内容，希望文章能够帮你解决cf1083 B. The Fair Nut and Strings（思维）所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。