算法基础1. 位运算1.1 常见二进制用法1.1.1 lowbit提取二进制的最后一位11.1.2 获取第k位1.1.3 判断奇偶1.1.4 无缓存交换1.1.5 位移实现乘除法1.2 位运算常见例题2. 离散化2.1 离散化知识点2.2 例题3. 区间合并3.1 区间合并模板3.2 例题1. 位运算在计算机中数字是以**二进制补码**形式存储的。常见的位运算符包括运算符名称规则二进制与 (AND)两个都为 1结果才为 11011 0110 0010或 (OR)只要有一个为 1结果就为 1^异或 (XOR)相同为 0不同为 1“不进位加法”1011 ^ 0110 1101~取反 (NOT)0 变 11 变 0~1011 0100(简略表示)左移所有位向左移动右侧补 0相当于乘 20011 1 0110右移所有位向右移动相当于除 20110 1 00111.1 常见二进制用法1.1.1 lowbit提取二进制的最后一位1i -i被称为lowbit操作。它的作用是返回 x 的二进制表示中最低位最右边的 1 及其后面的 0 所构成的数值。为什么x -x能得到最后一位 1这涉及到计算机如何表示负数——补码。原码假设 x 6二进制是0000 0110。反码~x是1111 1001。补码负数在计算机中-x等于反码加 1即-x ~x 1。-6的补码1111 1001 1 1111 1010。神奇的事情发生了x0000 0110-x1111 1010进行运算0000 0110 (6) 1111 1010 (-6) ----------- 0000 0010 (结果为 2即二进制中的最后那个 1)1.1.2 获取第k位n k 1这是处理二进制最基础的操作就像是在看数组的第k个元素。操作把想看的第 k位从右数从 0 开始移动到最右边然后把其他位全遮住。解释n k让整个数字向右移动k位。这时原来的第k位就站在了**个位第 0 位**上。 1数字1的二进制除了最后一位是 1前面全是 0。做运算时除了个位其他位都会被强制变成 0。结果如果第k位是 1结果就是 1如果是 0结果就是 0。1.1.3 判断奇偶x 1比x % 2 1更优雅、更快速。解释二进制中除了最后一位代表2^0 1其余位代表的都是 2 的幂2, 4, 8它们全是偶数。所以一个数是奇是偶全看最后一位。结果x 1 1为奇数x 1 0为偶数。十进制二进制拆解计算奇偶性100011奇数200102偶数300112 1奇数401004偶数501014 1奇数601104 2偶数发现规律了吗偶数的二进制最后一位永远是0。奇数的二进制最后一位永远是1。为什么因为二进制的位权分别是 …、8、4、2、1。前面的 …、8、4、2 全是偶数无论它们怎么相加结果还是偶数。唯一能决定这个数是奇还是偶的只有最后那个1 11即2 0 2^020位。1.1.4 无缓存交换**a ^ b; b ^ a; a ^ b;**这是一个不需要额外变量temp就能交换两个数的神奇魔法。原理异或的性质x ⊕ x 0 x \oplus x 0x⊕x0自己异或自己等于 0x ⊕ 0 x x \oplus 0 xx⊕0x任何数异或 0 等于本身异或运算满足交换律和结合律。推导第一步a a ⊕ b a a \oplus baa⊕b第二步b b ⊕ ( a ⊕ b ) ( b ⊕ b ) ⊕ a 0 ⊕ a a b b \oplus (a \oplus b) (b \oplus b) \oplus a 0 \oplus a abb⊕(a⊕b)(b⊕b)⊕a0⊕aa此时b bb拿到了原来的a aa第三步a ( a ⊕ b ) ⊕ a ( a ⊕ a ) ⊕ b 0 ⊕ b b a (a \oplus b) \oplus a (a \oplus a) \oplus b 0 \oplus b ba(a⊕b)⊕a(a⊕a)⊕b0⊕bb此时a aa拿到了原来的b bb注意虽然这个写法很酷但在现代编译器中使用std::swap通常更安全且一样快而且能避免a和b指向同一地址时把数值变 0 的风险。1.1.5 位移实现乘除法**与**这是算法优化中的常客。左移 n相当于乘以 2^n。每左移一位低位补 0数值翻倍。右移 n相当于除以 2^n。每右移一位相当于舍弃最右边的位数值减半。为什么快乘除法在 CPU 里是相对复杂的电路操作而位移只是简单的“排排坐往边挪”通常只需要一个指令周期。注意对于负数的右移C 通常执行的是算术右移高位补符号位这符合数学上的整除。1.2 位运算常见例题例题1给定一个长度为 n 的数列请你求出数列中每个数的二进制表示中 1 的个数。求二进制表示中 1 的个数#include iostream using namespace std; int main() { int n; scanf(%d, n); while (n -- ) { int x, s 0; scanf(%d, x);i ! 0 for (int i x; i; i - i -i) // 中间的 i 实际上等价于i ! 0 s ; printf(%d , s); } return 0; }例题2给定一个正整数 x请你将 x 的二进制表示中第 i 位和第 j 位的值互换并输出互换后的结果。二进制表示中第 i 位和第 j 位的值互换代码思路第一步拆解Extract利用“获取第k kk位”的知识点把整数x xx的每一位都取出来存入一个数组中。代码实现q[k] x k 1;原理把x xx右移k kk位让目标位落在最低位然后通过 1把它“抠”出来。第二步交换Swap直接在数组中交换下标为i ii和j jj的两个元素。代码实现swap(q[i], q[j]);原理此时位值已经变成了普通的数组元素0 或 1直接交换数值即可。第三步重组Reconstruct在前面的代码逻辑中你已经把整数x xx拆成了一个个的 0 和 1 放在数组q里并且完成了位置交换。现在你需要把这些“零件”按原位装回去重新变回一个十进制整数。利用“位移实现乘除法”的知识点将数组中的 0 和 1 重新放回对应的二进制权重位上。代码实现x q[k] k;原理q[k]是 0 或 1。如果q[k]是 1通过 k把它左移k kk位就得到了2 k 2^k2k的值累加进x xx即可。举个例子如果q[3] 1代表第 3 位是个 1那么1 3就是把1变成二进制的1000。 在十进制中1000二进制对应的数值就是2 3 8 2^3 8238。补充类型占用字节位数 (bits)近似范围精确公式int4 字节32 位± 2 × 10 9 \pm 2 \times 10^9±2×109− 2 31 -2^{31}−231~2 31 − 1 2^{31}-1231−1long long8 字节64 位± 9 × 10 18 \pm 9 \times 10^{18}±9×1018− 2 63 -2^{63}−263~2 63 − 1 2^{63}-1263−1#include iostream #include vector using namespace std; int main() { long long x; int i, j; cin x i j; vectorint q(40); // 默认40个0 for (int k 0; k 32; k) q[k] (x k) 1; swap(q[i], q[j]); // 4 - 100 // 复原为十进制数 long long res 0; for (int k 0; k 32; k) // q[k]只可能是0或1每次左移1位 然后转化为十进制数累加到res中 { if(q[k] 1) { res (q[k] k); // q[k]表示位于原本的第几位 即原本的2的k次方 } } cout res endl; return 0; }例题3判断其中一个的 16 位二进制表示形式是否能由另一个的 16 位二进制表示形式经过循环左移若干位而得到。判断其中一个的 16 位二进制表示形式是否能由另一个的 16 位二进制表示形式经过循环左移若干位而得到。核心思路双倍字符串技巧这是解决所有“循环移位”或“循环同构”问题的金钥匙。原理假设字符串A AA是1011。它循环移位可能产生的结果有1011,0111,1110,1101。技巧如果我们将A AA拼接在自己后面得到A A AAAA即10111011你会发现所有可能的循环移位结果都作为子串出现在了A A AAAA中。代码应用代码中通过y y;将b bb的二进制串加倍然后用y.find(x)检查a aa的二进制串是否在其中。字符串拼接与在 C 中如果的两边至少有一个是string对象它就代表拼接Concatenation即将后面的内容接到前面的内容末尾。代码应用x x to_string(...)会在原有的字符串x后面加上新生成的字符。代码应用y y是y y y的简写表示将y复制一份并拼接到自己后面使其长度翻倍。注意点拼接操作会产生新的字符串如果是在循环中频繁使用拼接长字符串性能会比使用.append()或直接操作char数组略低但对于处理 16 位二进制串来说性能差异可以忽略不计。to_string()函数将数值类型如int,long,float等转换为对应的字符串形式。在你的代码中a i 1的结果是一个整数0或1。转换结果如果结果是0to_string(0)会变成字符串0。如果结果是1to_string(1)会变成字符串1。目的这样做是为了能把这个二进制位“存”进string类型的变量x或y中方便后续进行全文匹配。y.find(x)函数C 字符串查找的核心函数用于在字符串y中搜索子串x。工作原理它会从y的开头开始往后找看看有没有一段内容和x完全一模一样。返回值找到了返回x在y中第一次出现的起始下标从 0 开始。没找到返回一个特殊常量string::npos。在大多数编译器和你的代码判断逻辑中这个值被转成了-1。代码逻辑if(y.find(x) ! -1)表示“只要在yy的大串里能找到x这个小串就说明匹配成功”。#include iostream #include string #include iostream using namespace std; int main() { int a, b; while (cin a b) { string s1, s2; for (int i 0; i 16; i){ s1 to_string((a i) 1); // 提取a的每一位并进行拼接 s2 to_string((b i) 1); } string s s2 s2; // 拼接在一块 这样 s2 s2 就包含了 s2 所有可能的循环移位结果 if (s.find(s1) ! -1) { printf(YES\n); } else { printf(NO\n); } } return 0; }2. 离散化2.1 离散化知识点什么是离散化离散化的核心思想是化大为小保持相对顺序。为什么要离散化比如坐标x xx的范围是[ − 10 9 , 10 9 ] [-10^9, 10^9][−109,109]。如果你想开一个数组a[2000000000]内存绝对会爆掉。但是我们实际用到的坐标点最多只有3 × 10 5 3 \times 10^53×105个n nn次增加坐标 m mm次询问的l ll和r rr。离散化就像是给这组稀疏的坐标点“排座位”比如有坐标{-100, 50, 1000000}我们把它们映射成-100→ \rightarrow→150→ \rightarrow→21000000→ \rightarrow→3这样原本巨大的坐标就变成了紧凑的下标1, 2, 3。2.2 例题区间和#include iostream #include vector #include algorithm using namespace std; // 定义 PII 方便存储坐标和加数的键值对 typedef pairint, int PII; // 为什么是 300010 // n 次插入用到 n 个坐标m 次询问用到 2m 个坐标 (l 和 r) // 总计 n 2m 300,000。开 300010 防止越界 const int N 300010; int n, m; int a[N]; // 存储离散化后的坐标对应的加数 即离散化压缩后的新数轴 int s[N]; // 存储前缀和 vectorint alls; // 存储所有“用到的”原始坐标用于排序去重 vectorPII add, query; // 存储所有的操作指令 // 二分查找输入原始坐标 x返回它在离散化数组中的“排名”下标 int find(int x) { // x是原始的坐标 非常大 int l 0, r alls.size() - 1; while (l r) { int mid l r 1; if (alls[mid] x) r mid; // 此时alls已经排序去重了存储的是所有的大坐标 else l mid 1; } return r 1; // 返回从 1 开始的下标方便前缀和计算 } int main() { // 1. 读入数据并收集坐标 cin n m; for (int i 0; i n; i) { int x, c; cin x c; add.push_back({x, c}); alls.push_back(x); // 记录插入操作的坐标 } for (int i 0; i m; i) { int l, r; cin l r; query.push_back({l, r}); alls.push_back(l); // 记录询问左边界 alls.push_back(r); // 记录询问右边界 } // 2. 离散化核心排序 去重 sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 3. 执行“加值”操作 for (auto item : add) { int x find(item.first); // 把大坐标转换成小下标 a[x] item.second; // 在映射后的位置加上 c /* 第一条指令在坐标100加3。第二条指令在坐标100再加5。映射过程假设通过 find 函数原始坐标100被映射成了离散化后的门牌号 1。执行结果第一次执行a[1] 变成3。第二次执行a[1] 变成358。 */ } // 4. 计算前缀和 - 可以直接算区间[l, r]的和 // 此时 a 数组里已经填好了值坐标已经变得非常紧凑 for (int i 1; i alls.size(); i) s[i] s[i - 1] a[i]; // 5. 处理询问 for (auto item : query) { int l find(item.first), r find(item.second); // 坐标映射 cout s[r] - s[l - 1] endl; // 利用前缀和 O(1) 算出区间和 } return 0; }离散化模板// 阶段一收集所有坐标读入数据 vectorint alls; // 存储所有待离散化的值 // 阶段二制作“坐标查找字典”核心步骤 sort(alls.begin(), alls.end()); // 将所有值排序 alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素 /* 去重unique 把重复的坐标删掉。 现在 alls 变成了一个从小到大排好序的字典。 比如 alls {10, 50, 100, 1000}。 坐标 10 就是字典里的第 1 个。 坐标 50 就是字典里的第 2 个。 */ // 二分求出x对应的离散化的值 int find(int x) // 找到第一个大于等于x的位置 { int l 0, r alls.size() - 1; while (l r) { int mid l r 1; if (alls[mid] x) r mid; else l mid 1; } return r 1; // 映射到1, 2, ...n } /* 这时候我们翻开加法备忘录 (add)。 备忘录说“在坐标 100 加 5。” 我们去查字典find 函数100 在字典里排第 3。 于是我们在缩小的数组里操作a[3] 5。 */unique()去重函数假设我们有一个排好序的数组alls{10, 10, 20, 30, 30}。当我们调用unique(alls.begin(), alls.end())时它会把数组改造成这样下标01234内容102030[10][30]状态有效有效有效垃圾数据垃圾数据unique返回的“分界线”就指向下标3。有效区域下标0, 1, 2共 3 个不重复元素。垃圾区域从下标3开始直到最后。返回值指向下标3的迭代器。auto it unique(alls.begin(), alls.end());int num it - alls.begin(); //这就是不重复元素的个数erase()删除函数C 的容器操作通常遵循“左闭右开”的原则即[开始位置, 结束位置)。当你执行alls.erase(unique(...), alls.end())时unique告诉erase“嘿从下标 3开始后面的全是没用的重复货了”erase接收到这个位置然后一路删到alls.end()。结果数组被切掉了后半截变成了真正的{10, 20, 30}长度也从 5 变成了 3。区间for循环for (auto item : add){}我们可以把它翻译成大白话“对于add容器里的每一个元素我都给它起个临时名字叫item然后拿着这个item进到大括号里干活。”add这是你定义的vectorPII。它就像一个“备忘录清单”里面存了一组组的{坐标 x, 加数 c}。item这是循环变量。在循环每执行一次时它都会自动代表add里的某一个pair一对数。第一圈item是第一条加数指令。第二圈item是第二条加数指令。auto这是 C 的自动类型推导关键字。编译器看到add里面存的是PII即pairint, int就会自动把item也设为PII类型。3. 区间合并3.1 区间合并模板核心思路贪心算法要合并区间最怕的是区间忽左忽右、乱七八糟。所以第一步永远是排序。第一步按左端点排序我们按照每个区间的左端点l从小到大排序。排序后我们处理区间的顺序就是从数轴左边往右边走的。这样我们只需要关注当前处理的区间和下一个区间是否有重叠即可。第二步扫描与合并我们维护一个“当前正在合并的区间”暂且叫它[st, ed]start 和 end。 当我们遇到一个新的区间[seg.l, seg.r]时只有两种情况无法合并断开了 下一个区间的开头seg.l比我们当前的结尾ed还要大。动作说明当前的[st, ed]已经到头了把它存入结果然后把[st, ed]更新为这个新的区间。可以合并有重叠 下一个区间的开头seg.l小于或等于当前的结尾ed。动作把当前区间的结尾ed延长。延长的长度取决于新区间能达到的最远距离即ed max(ed, seg.r)。// 将所有存在交集的区间合并 void merge(vectorPII segs) // PII - segs 存一个区间的 [左端点, 右端点] { vectorPII res; // 存储合并完成后的新区间。 sort(segs.begin(), segs.end()); /* sort: 排序前{[1, 3], [7, 9], [2, 6]} 排序后{[1, 3], [2, 6], [7, 9]} (按左端点排好了) */ int st -2e9, ed -2e9; /* 扫描第 1 个区间 seg [1, 3] 判断ed seg.first -2e9 1 成立 动作if (st ! -2e9) 不成立因为现在还是初始值。 更新当前维护区间st 1, ed 3。 当前活跃区间[1, 3] 扫描第 2 个区间 seg [2, 6] 判断ed seg.first 3 2 不成立 合并 更新 ed max(3, 6) 6。 当前活跃区间[1, 6] [st, ed]每次进行扫描变动 看是否能合并 */ for (auto seg : segs) // // 遍历排序后的每一个区间 if (ed seg.first) // 情况 1当前维护的区间与新区间“断开了” (无交集) { //说明当前区间 [st, ed] 的结尾够不着新区间 seg 的开头。 if (st ! -2e9) res.push_back({st, ed}); st seg.first, ed seg.second; } else ed max(ed, seg.second); // 情况 2有交集更新 ed 为更远的那个端点 if (st ! -2e9) res.push_back({st, ed}); segs res; }3.2 例题区间合并#include iostream #include vector #include algorithm using namespace std; typedef pairint, int PII; void merge(vectorPII segs) { vectorPII res; sort(segs.begin(), segs.end()); int st -2e9, ed -2e9; for (auto seg : segs) if (ed seg.first) { if (st ! -2e9) res.push_back({st, ed}); st seg.first, ed seg.second; } else ed max(ed, seg.second); if (st ! -2e9) res.push_back({st, ed}); segs res; /* 清空旧数据segs 会把原本存储的所有区间旧数据全部销毁掉。 拷贝新数据把 res 中的所有区间完整地复制一份到 segs 中。 同步长度segs 的大小size会自动变为和 res 一模一样。 */ } int main() { int n; scanf(%d, n); vectorPII segs; for (int i 0; i n; i ) { int l, r; scanf(%d%d, l, r); segs.push_back({l, r}); } merge(segs); cout segs.size() endl; return 0; }