题解： P12191 [蓝桥杯 2025 省研究生组] 01 串

前言

蒟蒻手撕的第一道绿题，边写题解边打代码一共用了两个小时。

不知道咋回事，博客上所有行间公式后面都自动给我加了个编号，先不管了

题目描述

给定一个由 的二进制表示拼接而成的长度无限的 串。其前若干位形如 。

请求出这个串的前 位里有多少个 。 。

解析

以下默认讨论的是二进制数。

我们可以把这个串的前 位分割成两部分，部分(1)由所有的 位数构成，部分(2)由 位数构成。

想要求出 是多少，只需要求出：最大的 ，使得所有 位数拼接到一起的长度 。（如果 恰好等于 ，那么就只有部分(1)了）

首先考察所有 位数拼到一起的总长度 ：

位数有 个， 位数有 个， 位数有 个，观察可得：

于是

设 ，用我们小学二年级就学过的错位相减法：

则

所以

从小到大枚举 即可，这样我们就求出来了 是多少。

部分(1)

对于所有 位数，它们包含的 的数量之和 为：

要求出它的值，可以使用如下方法：

两侧同时求导，

令 可得 。

现在部分(1)只有 位的数字，让 加上 即可。

部分(2)

该部分共有 位，包含了 个数字，最后一个数字的值为 。

我们把部分(2)分为最后一个数字之前的数字，和最后一个数字来求解。

将最后一个数字表示为 ，其中 一定是 。从 遍历 ，如果 是 ，那么 都是合法的数字，这些数字共有 个，我们为 加上 。通过此法构造的数字中，最大的数字是 。

最后，我们算出最后一个数字被计入答案的位数 ，让 加上 的前这些位之和即可。

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

ull S(int n) {
    return (n-1)*(1ull<<n)+2;
}

ull D(int n) {
    return n*(1ull<<(n-1));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ull x, ans = 0;
    cin >> x;
    int n;
    for (n = 1; S(n-1) <= x; ++n) {}
    --n;
    ans += D(n-1);

    ull y = x - S(n-1);
    ull d = y/n + (y%n!=0);
    bitset<64> b((1ull<<(n-1))+d-1);
    int prefsum = 1;
    for (int i = n-2; i >= 0; --i) {
        if (b[i] == 1) {
            ans += (prefsum)*(1ull<<i) + D(i);
            prefsum++;
        }
    }
    for (int i = 0; i < y-n*(d-1); i++) {
        ans += b[n-1-i];
    }

    cout << ans;
}