G3017 [GESP202506 三级] 奇偶校验 题解

知识点：二进制、位运算、奇偶校验。

解题思路

累计所有输入整数二进制中1的数量sum，输出sum及sum%2作为所需校验位。

为什么正确

加上sum%2后，1的总数量为偶数，恰满足偶校验要求。

易错点

统计二进制位，不是十进制数位；总计数和校验位是两个输出。

复杂度

时间O(nw)，w为机器字长；空间O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,v,sum=0;
    cin>>n;
    while(n--) {
        cin>>v;
        sum+=__builtin_popcount((unsigned)v);
    }
    cout<<sum<<" "<<sum%2;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用6个自行生成的测试点。