luogu-B4358 [GESP202506 三级] 奇偶校验

GESP C++三级，2025年6月真题，进制转换，难度★★☆☆☆。

luogu-B4358 [GESP202506 三级] 奇偶校验

题目要求

题目描述

数据在传输过程中可能出错，因此接收方收到数据后通常会校验传输的数据是否正确，奇偶校验是经典的校验方式之一。

给定 $n$ 个非负整数 $c_1, c_2, \ldots, c_n$ 代表所传输的数据，它们的校验码取决于这些整数在二进制下 1 的数量之和的奇偶性。如果这些整数在二进制下共有奇数个 1，那么校验码为 1；否则校验码为 0。你能求出这些整数的校验码吗？

输入格式

第一行，一个正整数 $n$，表示所传输的数据量。

第二行，$n$ 个非负整数 $c_1, c_2, \ldots, c_n$，表示所传输的数据。

输出格式

输出一行，两个整数，以一个空格分隔：

第一个整数表示 $c_1, c_2, \ldots, c_n$ 在二进制下 1 的总数量；

第二个整数表示校验码（0 或 1）。

输入输出样例 #1

输入 #1

4
71 69 83 80

输出 #1

13 1

输入输出样例 #2

输入 #2

6
1 2 4 8 16 32

输出 #2

6 0

说明/提示

对于所有测试点，保证 $1 \leq n \leq 100$，$0 \leq c_i \leq 255$。

题目分析

解题思路

本题的解题思路如下：

1. 问题本质：

   • 输入一个正整数 $n$ 表示数据量
   • 输入 $n$ 个非负整数，每个整数范围在 [0,255]
   • 需要统计这些数字二进制表示中 1 的总数，并判断奇偶性

2. 解题关键：

   • 核心思路 - 二进制处理：
     1. 读取输入数据：
        • 首先读取数据量 $n$
        • 然后依次读入 $n$ 个整数
     2. 统计二进制 1 的个数：
        • 对每个数字进行二进制分解
        • 可以通过除 2 取余或位运算统计 1 的个数
        • 累加所有数字中 1 的个数
     3. 判断奇偶性：
        • 如果 1 的总数是奇数，校验码为 1
        • 如果 1 的总数是偶数，校验码为 0

3. 复杂度分析：

   • 时间复杂度：$O(n \log M)$，其中 $M$ 是输入整数的最大值（此题中为255）
   • 空间复杂度：$O(1)$，只需要常数级别的变量

{% include custom/custom-post-content-inner.html %}

示例代码

#include <iostream>

int main() {
    // 读取数据个数
    int n;
    std::cin >> n;
    
    // 统计所有数字二进制中1的总数
    int count = 0;
    for (int i = 0; i < n; i++) {
        // 读取每个数字
        int c;
        std::cin >> c;
        
        // 对每个数字进行二进制分解，统计1的个数
        while (c) {
            // 获取最低位
            int bit = c % 2;
            // 如果最低位是1，计数加1
            if (bit == 1) {
                count++;
            }
            // 右移一位，继续处理
            c /= 2;
        }
    }
    
    // 根据1的总数判断校验码：偶数个1校验码为0，奇数个1校验码为1
    int y = count % 2 == 0 ? 0 : 1;
    // 输出1的总数和校验码
    std::cout << count << " " << y << std::endl;
    return 0;
}          

{% include custom/custom-post-content-footer.md %}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP 认证学习微信公众号