题号 NC113276
名称 The Fair Nut and Strings
来源 0
每日一题三期汇总贴~


如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解

作者：jxnu19-软技1班-刘晟

Solution

如果我们把看作的话，我们就可以构建一颗满二叉树。那么其实我们对应的在满二叉树中有自己的对应编号。

其实就是问你给你两个这样的端点前面你可以选择的节点数一共有多少个。

那么当我们当前可选的区间长度一直都不足的时候，我们就可以把这一层全部的可选节点数都加上。

当我们当前可选区间的长度第一次大于等于之后，因为你上方全部的节点都已经被你计算过了，所以你最多只能在当前层选择个节点，那么这种时候你就不能把这一层可选的节点都拿上去了，只能选择其中的个，那么与之对应，其实你下一层如果还要选，那么节点数也一定大于等于，你从其中挑出个叶子之后，你会发现叶子节点上方的父亲在你上一次就要被选过，不然你这次就不可能拿到这个叶子，所以这对应着你这次任然只能选其中的个节点。

最后总结一下就是，使用二进制判断当前层数可选的节点数，如果小于，直接累加。

如果大于等于，那么现在这一层以及下面的你还没选的层数，每层你都只能选择个节点。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }

const int N = 5e5 + 7;
ll n, k;
char s[N], t[N];

int main() {
    n = read(), k = read();
    scanf("%s", s + 1);
    scanf("%s", t + 1);
    ll ans = 0, len, a = 0, b = 0;
    rep(i, 1, n) {
        a <<= 1, b <<= 1;
        if (s[i] == 'b')    ++a;
        if (t[i] == 'b')    ++b;
        len = b - a + 1;
        if (len >= k) {
            ans += (n - i + 1) * k;
            break;
        }
        ans += len;
    }
    print(ans);
    return 0;
}

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目5月7日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴