企业官网建设流程全解析

重庆江北营销型网站建设公司哪家好,广告设计好学吗难不难,广州网站开发哪家强,莆田网站自助建站#x1f3af; 一、题目理解#xff1a;《谁是“有趣的数字”#xff1f;》 1、#x1f9f8; 小故事 小 A 很喜欢玩 二进制游戏 #x1f3ae; 他规定了一条奇怪的规则#xff1a; #x1f449; 如果一个数字的 二进制表示中 #x1f449; 1 的个数是奇数 #x1f449;… 一、题目理解《谁是“有趣的数字”》1、 小故事小 A 很喜欢玩二进制游戏他规定了一条奇怪的规则 如果一个数字的二进制表示中1 的个数是奇数 那这个数字就是 ——有趣的数字2、 举例十进制二进制1 的个数有趣吗51012❌71113✅810001✅3、老师现在给你一个区间[l, r]问你从 l 到 r 之间所有“有趣数字”的总和是多少 二、把题目翻译成“人话”原题简化给定两个整数 l 和 r对区间 [l, r]找出所有二进制中 1 的个数为奇数的数把这些数加起来⚠️ 三、第一反应 大坑1、 同学们的第一想法很自然for (int i l; i r; i) { if (二进制中1的个数是奇数) ans i; }2、❌ 但是题目里l、r非常大r 可以到10⁹ 甚至更大 这样循环直接超时不能满分 四、真正的挑战是什么这道题不是考你会不会数 1而是考你能不能“整体思考一大堆数字” 五、关键魔法概念 ①奇偶性1、✨ 重要发现我们不关心有多少个 1我们只关心是奇数个还是偶数个2、 举例3 个 1 → 奇数 ✅4 个 1 → 偶数 ❌只分两类 六、关键魔法概念 ②从 0 到 n 统一算1、 超重要技巧 不直接算[l, r] 而是算sum(0 ~ r) − sum(0 ~ (l − 1))就像从 0 数到 100减去 0 数到 49剩下的就是 501002、 伪代码 Part 1主流程输入 L, R 答案 计算(0 ~ R 的有趣数字之和) - 计算(0 ~ L-1 的有趣数字之和) 输出 答案3、 伪代码 Part 2核心函数 calculate(n)calculate(n) 表示 计算 0 ~ n 中 所有“有趣数字”的【总和】函数 calculate(n): 如果 n 很小n ≤ 1: 直接算返回结果 找到最大的 2 的幂 x使得 x ≤ n 例如 n13x8 第一部分 0 ~ x-1 最高位是 0不影响奇偶性 第二部分 x ~ n 最高位是 1奇偶性会翻转 返回 第一部分结果 第二部分结果 第二部分中每个数都多出来的 x4、 伪代码 Part 3小范围快速计算 small(n)当范围非常小时直接用数学规律算函数 small(n): 如果 n 0: 如果 0 是有趣的: 返回 (数量1, 总和0) 否则: 返回 (数量0, 总和0) 如果 n 1: 判断 1 是不是有趣的 返回对应的数量和总和 如果 n ≥ 2: 有趣数字大约占一半 用公式直接算数量和总和 七、用“翻转”的方式讲给大家我们可以这样说 把 0~n 的数字 从中间“一刀切开”左边最高位是 0 不改变“有趣 / 没趣”右边最高位是 1奇数变偶数偶数变奇数就像戴了一顶“翻转帽子” 八、使用分治递归这种方法为何很快1、第一层直观想象1 慢方法暴力想象你要数1 ~ 1 000 000 000每个数字都要转成二进制数 1 的个数判断奇偶再加到答案里 就像数一座山的每一粒沙子2 快方法分治递归这道题做了什么把一座山直接切成二整块石头分别再去计算着两块大石头不用数每一粒沙2、第二层代码思想我们对比两种算法 1❌ 方法 1暴力枚举for i L to R: 如果 i 是“有趣数字”: ans i⏱ 时间复杂度超时❌ 直接凉了2✅ 方法 2分治递归的算法核心操作只有两件找最大的 2 的幂把区间一分为二递归3关键点来了 ❗❗❗每一层递归n 都在做什么n → n / 2就像1 000 000 000 → 500 000 000 → 250 000 000 → ...你知道这意味着什么吗3、第三层真正“省时间”的数学原因 ⚡ 时间复杂度对比方法操作次数暴力枚举10^9 次本题算法log₂(10^9) ≈ 30 次差了 3 千万倍4、 为什么“2 的幂”这么神1因为在二进制中0 ~ (2^k - 1) 每一位的 0 和 1 出现次数完全对称2所以有趣数字 ≈ 一半总和可以用公式算不用枚举5、 “翻转奇偶性”也在省时间最高位是 1 时原来是奇数 → 变偶数 原来是偶数 → 变奇数不用重新算二进制 只用一个p变量记录就可以 九、参考程序#include algorithm #include cstdio using namespace std; int l, r; int ans; // 最终答案有趣数字的总和 /* cal2(n, p) 的作用 在【0 ~ n】这个小范围内 - 统计“有趣数字”的个数 - 统计这些有趣数字的“和” 参数说明 n当前范围的最大值 p表示当前“奇偶状态” p 1表示“1 的个数是奇数”为有趣 p 0表示“1 的个数是偶数”为有趣 返回值 first 有趣数字的数量 second 有趣数字的总和 */ pairint, int cal2(int n, int p) { // 只有 0 这个数 if (n 0) { // 0 的二进制没有 1 // 如果 p 0偶数个 1 才算有趣那 0 是有趣的 return {1 - p, 0}; } // 范围是 0 和 1 if (n 1) { // 1 的二进制是 1一个 1 // 如果 p 1奇数个 1 才算有趣那 1 是有趣的 return {1, p}; } // 对于 n 2 的情况 // 在 0 ~ n 中有一半左右的数满足条件 // (n 1) / 2 有趣数字的数量 // n * (n 1) / 4 这些数字的总和数学公式 return {(n 1) / 2, 1ll * n * (n 1) / 4}; } /* cal(n, p) 的作用 计算【0 ~ n】之间所有“有趣数字”的 - 个数 - 总和 这是一个【递归 分治】的函数 */ pairint, int cal(int n, int p) { // 小范围直接用 cal2 解决 if (n 1) { return cal2(n, p); } // 找到不超过 n 的最大 2 的幂 // 例如n 13x 8二进制 1000 int x 1ll (31 - __builtin_clz(n)); // 第一部分0 ~ x-1最高位是 0 auto left cal2(x - 1, p); // 第二部分x ~ n最高位是 1 // 因为多了一个 1奇偶性会翻转所以 p 变成 1 - p auto right cal(n - x, 1 - p); // 合并两部分的结果 return { left.first right.first, // 有趣数字的总个数 left.second right.second x * right.first // 有趣数字的总和 }; } int main() { // 输入区间 [l, r] scanf(%d%d, l, r); // 先减去 [0 ~ l-1] 的有趣数字之和 ans - cal(l - 1, 1).second; // 再加上 [0 ~ r] 的有趣数字之和 ans cal(r, 1).second; // 输出 [l ~ r] 区间内有趣数字的总和 printf(%lld\n, ans); return 0; } 十、两个函数在干嘛1、参考代码里有两个函数1️⃣cal2(n, p) 用来算数量总和在非常小的范围里2️⃣cal(n, p) 用来递归拆分一半最高位是 0一半最高位是 1奇偶翻转2、那为什么不把cal2写进cal里原因 1逻辑更清楚 cal 负责拆问题递归 cal2负责算结果公式分工明确比一坨 if 好讲 原因 2减少递归层数 如果什么都递归会调用很多次效率慢容易爆栈现在小范围 →一步到位原因 3这是“竞赛常见写法” 在 CCF / NOI / ICPC 里非常常见这是高阶程序员的习惯3、 本题特点这是“分治 二进制 奇偶性”的综合应用 十一、从五级考试层面看这道题 这题明显是一道限高题对于五级考生挑战很大它在考能力是否考到二进制✅奇偶性✅区间转前缀✅分治思想✅大数据优化✅十二、 记忆口诀数字太大别硬算二进制里看奇偶区间问题变前缀一刀一半分着走 ✨