[GXPC-S 2024] 数字谜题 的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： admin

概述

本题要求计算给定正整数二进制表示中最长的连续 1 的个数。
核心解法是对每个数逐位检查，统计连续 1 的段长并取最大值，由于位数很少，直接模拟即可。

分析
核心观察

二进制中连续的 1 会形成若干段，只需依次遍历每一位，记录当前连续 1 的长度并更新答案。

思路

对于每个 x，从最低位开始逐位检查。若当前位为 1，则连续长度加 1；若为 0，则连续长度归零。每次更新最大长度。
将 x 右移一位继续处理，直到 x 变为 0。
因为 x \le 10^{18}，二进制位数不超过 60，单次处理极快。对于 T=10^5 组数据，总操作数约 6 \times 10^6，完全可行。

具体示例

以样例中的 10 为例，其二进制为 (1010)_2，从低位到高位依次为 0,1,0,1。
遍历过程：遇到第一个 0，连续长度为 0；遇到 1，长度变为 1，最大为 1；再遇 0 归零；最后遇 1 长度为 1，最大仍为 1。输出 1。

算法步骤
  1. 读入数据组数 T。
  2. 对于每组数据，读入整数 x。
  3. 初始化当前连续长度 cur = 0，最大长度 ans = 0。
  4. 当 x > 0 时循环：
    • 若 x & 1 为真，则 cur = cur + 1；否则 cur = 0。
    • 更新 ans = max(ans, cur)。
    • 将 x 右移一位（x >>= 1）。
  5. 输出 ans。
复杂度分析
  • 时间复杂度：O(T \log x)，单次循环 \log_2 x 次，最大约为 60。
  • 空间复杂度：O(1)。
实现注意事项
  • 使用快速输入输出，避免 T=10^5 时的 I/O 瓶颈（C++ 中关闭同步流，Python 中使用 sys.stdin.buffer.read）。
  • 数据范围 x \le 10^{18} 在 64 位有符号整数范围内，使用 long long（C++）或 int（Python 自动支持大整数）即可。
  • 右移操作对正数安全，无需处理符号位。
源代码
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        long long x;
        cin >> x;
        int cur = 0, ans = 0;
        while (x > 0) {
            if (x & 1LL) {
                ++cur;
                if (cur > ans) ans = cur;
            } else {
                cur = 0;
            }
            x >>= 1;
        }
        cout << ans << '\n';
    }
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    T = int(data[0])
    out = []
    for i in range(1, T + 1):
        x = int(data[i])
        cur = 0
        ans = 0
        while x > 0:
            if x & 1:
                cur += 1
                if cur > ans:
                    ans = cur
            else:
                cur = 0
            x >>= 1
        out.append(str(ans))
    sys.stdout.write('\n'.join(out))

if __name__ == "__main__":
    main()

评论

目前没有评论。