题解：洛谷 P14074 [GESP202509 五级] 有趣的数字和

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P14074 [GESP202509 五级] 有趣的数字和 - 洛谷【题目描述】如果一个正整数的二进制表示包含奇数个1 11那么小 A 就会认为这个正整数是有趣的。例如7 77的二进制表示为( 111 ) 2 (111)_2(111)2​包含1 11的个数为3 33个所以7 77是有趣的。但是9 ( 1001 ) 2 9(1001)_29(1001)2​包含2 22个1 11所以9 99不是有趣的。给定正整数l , r l,rl,r请你统计满足l ≤ n ≤ r l≤n≤rl≤n≤r的有趣的整数n nn之和。【输入】一行两个正整数l , r l,rl,r表示给定的正整数。【输出】一行一个正整数表示l , r l,rl,r之间有趣的整数之和。【输入样例】3 8【输出样例】19【算法标签】#普及 #前缀和【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglong// 使用长整型防止溢出intl,r;// 输入的数字区间[l, r]intans;// 存储计算结果intb;// 计算第b个区间intv[9]{0,1,3,3,7,7,7,14,22};// 预计算的小数值结果1-8的答案/** * 计算数字x的二进制表示中1的个数汉明重量 * param x 要计算的数字 * return 二进制中1的个数 */intcheck(intx){intcnt0;// 计数器记录1的个数while(x0){if(x1)// 检查最低位是否为1cnt;// 如果是1计数器加1xx1;// 右移一位相当于除以2}returncnt;}/** * 计算从1到x的所有满足条件的数的和 * param x 上界 * return 计算结果 */intf(intx){// 如果x小于等于8直接返回预计算的结果if(x8)returnv[x];// 计算区间个数默认向下取整bx/4;// 计算从第1到第b个区间的总和ans(b*b)*4-b;// 计算剩余部分的值从b*4到xfor(inti(b*4);ix;i){// 如果二进制1的个数为奇数则累加if(check(i)%2)ansi;}returnans;}signedmain(){// 输入区间范围cinlr;// 输出区间内满足条件的数的和前缀和思想coutf(r)-f(l-1);return0;}【运行结果】3 8 19