本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷B4358 [GESP202506 三级] 奇偶校验 - 洛谷【题目描述】数据在传输过程中可能出错因此接收方收到数据后通常会校验传输的数据是否正确奇偶校验是经典的校验方式之一。给定n nn个非负整数c 1 , c 2 , … , c n c_1,c_2,…,c_nc1​,c2​,…,cn​代表所传输的数据它们的校验码取决于这些整数在二进制下1 11的数量之和的奇偶性。如果这些整数在二进制下共有奇数个1 11那么校验码为1 11否则校验码为0 00。你能求出这些整数的校验码吗【输入】第一行一个正整数n nn表示所传输的数据量。第二行n nn个非负整数c 1 , c 2 , … , c n c_1,c_2,…,c_nc1​,c2​,…,cn​表示所传输的数据。【输出】输出一行两个整数以一个空格分隔第一个整数表示c 1 , c 2 , … , c n c_1,c_2,…,c_nc1​,c2​,…,cn​在二进制下1 11的总数量第二个整数表示校验码0 00或1 11。【输入样例】4 71 69 83 80【输出样例】13 1【核心思想】问题分析给定n nn个非负整数需要计算所有整数二进制表示中1 11的总数量并根据总数的奇偶性输出校验码奇数为1 11偶数为0 00。这是一个位运算统计问题核心在于高效计算每个整数二进制中1 11的个数并累加。算法选择逐位检查对每个整数通过不断右移并检查最低位统计二进制中1 11的个数奇偶性判定对总数量取模2 22判断奇偶性关键步骤读入数据读取n nn和数组c [ 1.. n ] c[1..n]c[1..n]统计1 11的总数i ii从1 11到n nna n s ← a n s c a l ( c i ) ans \leftarrow ans cal(c_i)ans←anscal(ci​)其中c a l ( x ) cal(x)cal(x)计算x xx的二进制中1 11的个数计算校验码c o d e a n s m o d 2 code ans \bmod 2codeansmod2输出结果a n s ansans和c o d e codecode时间/空间复杂度时间复杂度O ( n ⋅ log ⁡ V ) O(n \cdot \log V)O(n⋅logV)其中V VV为整数最大值每个数统计1 11的个数为O ( log ⁡ V ) O(\log V)O(logV)空间复杂度O ( n ) O(n)O(n)存储输入数组位运算统计的核心思想逐位检查法通过x 1检查最低位是否为1 11然后x 1右移一位处理下一位循环直到x 0 x 0x0。这种方法直观且适用于任意非负整数奇偶校验原理奇偶校验通过统计所有数据位中1 11的个数的奇偶性来检测错误。若传输过程中有奇数个位翻转则校验码会改变从而发现错误累加后判定先累加所有数中1 11的总数再对总数判断奇偶等价于对每个数分别判断后异或但累加方式更直观内置函数优化实际竞赛中可使用__builtin_popcount(x)GCC 内置函数在O ( 1 ) O(1)O(1)时间内计算1 11的个数效率更高适用于基础位运算、数据校验类入门问题【算法标签】#入门 #位运算【代码详解】#includebits/stdc.husingnamespacestd;constintN105;// 定义数组最大长度intn;// 输入的数字个数intans0;// 存储所有数字二进制中1的总个数inta[N];// 存储输入的数字数组// 计算数字x的二进制表示中1的个数intcal(intx){intres0;// 计数器记录1的个数// 循环处理每一位while(x){// 检查最低位是否为1if(x11)res;// 右移一位处理下一位x1;}returnres;}intmain(){cinn;// 输入数字个数// 输入n个数字for(inti1;in;i)cina[i];// 计算所有数字二进制中1的总个数for(inti1;in;i)anscal(a[i]);// 输出总1的个数和其奇偶性coutans ;// 判断总1个数的奇偶性if(ans%20)cout0endl;// 偶数输出0elsecout1endl;// 奇数输出1return0;}【运行结果】4 71 69 83 80 13 1