B 解释：

• A/D (冒泡/插入排序): 平均和最坏情况时间复杂度均为 O(n²)，效率较低。
• B (快速排序): 期望（平均）时间复杂度为 O(n log n)，是基于比较的排序算法中非常高效的一种。但其最坏情况（例如，对一个已经排好序的数组进行排序）下时间复杂度会退化到 O(n²)。
• C (计数排序): 是一种非比较排序，时间复杂度为 O(n+k)（其中 k 为整数范围），当 k 远小于 n² 时，效率很高，但不属于 O(n log n) 类别。
• 因此，快速排序的期望时间复杂度符合 O(n log n)。归并排序和堆排序也属于此类，且它们的最坏时间复杂度也是 O(n log n)。

D 解释： 排序算法的稳定性指，对于数组中两个值相等的元素，在排序后它们的相对位置不发生改变。

• A (选择排序): 不稳定。在每一轮选择最小元素时，将其与当前位置元素交换，这个交换操作可能会打乱其他相等元素的相对顺序。
• B (堆排序): 不稳定。建堆和调整堆的过程都会涉及元素交换，可能打乱相等元素的顺序。
• C (快速排序): 不稳定。Partition 操作中，基准值（pivot）的交换可能导致相等元素的顺序改变。
• D (归并排序): 稳定。在合并两个有序子数组时，如果遇到相等的元素，我们可以规定总是先取左边子数组的元素，这样就能保证它们的相对顺序不变。

B 解释： 二分查找的核心思想是每次将搜索范围缩小一半。这依赖于数据的单调性。即数据必须是升序或降序排列的。只有这样，我们才能通过比较中间值与目标值的大小，来确定目标值在哪一半区间，从而舍弃另一半。数组中可以有重复值，元素也可以是浮点数或其他可比较类型，长度也无特殊要求。

B 解释： 广度优先搜索（BFS）按照“逐层”的顺序进行遍历，即先访问所有距离起点为1的节点，再访问所有距离为2的节点，以此类推。这正好符合队列**“先进先出”（FIFO）**的特性。我们将起点入队，然后不断从队头取出节点，并将其所有未访问过的邻居节点加入队尾。

• 栈（先进后出 LIFO）通常用于实现深度优先搜索（DFS）。

C 解释：

• 首先，1 << k 会生成一个掩码（mask），这个掩码只有第 k 位是 1，其他位都是 0。
• 然后，~(1 << k) 对这个掩码进行按位取反，得到一个新掩码，它的第 k 位是 0，而其他所有位都是 1。
• 最后，将原始变量 x 与这个新掩码进行按位与 & 运算。由于任何位与 1 相与都保持不变，与 0 相与都会变为 0，因此这个操作能精确地将 x 的第 k 位清零，同时保持其他位不变。
• 其他选项：A 是将第 k 位置1；B 是检查第 k 位是否为1；D 是将第 k 位翻转（0变1，1变0）。

B 解释： 当 n 较大时（例如 int 类型的 n 接近其上限），n * (n + 1) 的结果很可能会超出 int 的表示范围，导致整数溢出，得到一个错误的负数或小数值。

• 写法 B 通过 (long long)n 将变量 n 强制类型转换为 64 位的 long long 类型。这样一来，整个表达式 (long long)n * (n + 1) 都会在 64 位下进行计算，其结果的范围远大于 int，从而极大地降低了溢出风险。
• A 和 C 的问题是相同的，乘法发生在 int 类型下。D 循环相加虽然不会因乘法溢出，但效率远低于公式法，且累加过程也可能溢出。

C 解释：

• C (Dijkstra): 是解决非负权图单源最短路问题的标准算法。通过使用优先队列（通常是二叉堆）进行优化后，其时间复杂度可以达到 O(E log V) 或 O(E + V log V)，非常高效。
• A (Floyd-Warshall): 用于计算图中任意两点间的最短路（所有源），时间复杂度为 O(V³)，对于单源问题来说过于耗时。
• B/D (Bellman-Ford/SPFA): 这两种算法可以处理带负权边的图（但不能有负权环）。在没有负权边的情况下，它们的效率通常低于堆优化的 Dijkstra 算法。

A 解释： 哈希表通过哈希函数将键（key）映射到数组的索引上，理想情况下可以直接定位到元素。虽然存在哈希冲突（多个键映射到同一索引）的可能性，但在一个设计良好的哈希表中（哈希函数均匀、负载因子合适），解决冲突的开销很小。因此，其平均和摊还时间复杂度为O(1)。但在最坏情况下（所有键都冲突），查找时间会退化到 O(n)。

B 解释： 闰年的规则是：

1. 能被4整除的年份是闰年（例如 2024）。
2. 但是，如果该年份能被100整除，它就不是闰年（例如 1900）。
3. 有一个例外：如果该年份能被400整除，它仍然是闰年（例如 2000）。 将这三条规则合并，就得到了 B 选项的逻辑表达式：(year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)。

C 解释： C/C++ 为了性能，默认不进行数组边界检查。访问越界是一种未定义行为（Undefined Behavior, UB）。这意味着标准没有规定此时程序必须做什么。可能的结果包括：

• 程序崩溃（段错误）。
• 读取或修改了不相关的内存数据，导致程序逻辑错误且难以调试。
• 在某些情况下，程序可能看起来“正常”运行，但存在潜在的巨大风险。 它不会在编译或链接阶段报错，因为这是一个运行时问题。

B 解释： 当并查集同时使用路径压缩（在 find 操作时，将路径上所有节点直接指向根节点）和按秩合并（按大小或深度合并，将小的集合合并到大的集合上）这两种优化时，其操作的均摊时间复杂度可以达到 O(α(n))。

• α(n) 是反阿克曼函数，它增长得极其缓慢。对于任何现实世界中可能遇到的 n（例如宇宙中所有原子的数量），α(n) 的值都不会超过 5。因此，这个复杂度可以认为是近似常数时间，但理论上它并非严格的 O(1)。

C 解释： a 在模 m 意义下的乘法逆元是指一个整数 x，满足 (a * x) ≡ 1 (mod m)。 这个逆元存在的充要条件是 a 和 m 互质，即它们的最大公约数 gcd(a, m) = 1。

• 如果满足此条件，可以使用扩展欧几里得算法求出逆元。
• 一个特殊情况是，当 m 为质数且 a 不是 m 的倍数时，gcd(a, m) 必然为 1，此时也可以用费马小定理 (a^(m-2) mod m) 来求逆元。

A 解释： 快速幂算法利用了指数 n 的二进制表示。它通过不断地将底数 a 平方 (a -> a² -> a⁴ -> ...)，并根据 n 的二进制位来决定是否将当前结果乘上对应的 a 的幂。由于 n 的二进制表示大约有 log₂n 位，算法的循环次数与 log n 成正比，因此时间复杂度为 O(log n)，远快于 O(n) 的朴素乘法。

D 解释： A、B、C 都是比较排序，它们通过比较元素间的大小关系来确定元素的顺序，其时间复杂度的理论下界是 O(n log n)。

• D (计数排序): 是一种非比较排序（或称线性时间排序）。它不比较元素，而是通过统计每个元素出现的次数，然后根据这个统计信息直接计算出每个元素在排序后数组中的位置。它适用于整数范围不大（k 较小）的场景，时间复杂度为 O(n+k)。

B 解释： 在无权图中，任意一条边的权重都可以看作是 1。因此，两点间的最短路径就是包含边数最少的路径。

• B (BFS): 广度优先搜索（BFS）从源点开始，逐层向外扩展。它访问节点的顺序恰好是按照离源点的距离（即边数）从小到大进行的。因此，当 BFS 第一次到达目标节点时，所经过的路径必然是边数最少的，即最短路径。BFS 是解决无权图最短路问题最直接、最高效的方法，时间复杂度为 O(V+E)。

C 解释： 二分答案是一种将最优化问题（例如求最大值的最小值）转化为一系列判定性问题（“某个答案 x 是否可行？”）的技巧。 能够使用该技术的前提是，这个判定函数 check(x) 必须具有单调性。例如，如果答案 x 是可行的，那么所有比 x “更优”或“更容易”的答案（如比 x 小的值）也都是可行的。这种单调性使得我们可以在答案的定义域上进行二分搜索，从而快速逼近最优解。

D 解释： 由于计算机使用二进制表示浮点数，会存在精度误差。两个在数学上相等的数，在计算机中存储时可能存在微小的差异。

• A (直接使用 ==): 非常不可靠，很可能因为微小的精度差而判断错误。
• D (使用 eps): 是标准做法。我们不直接判断 a == b，而是判断它们差的绝对值是否足够小，即 abs(a - b) < eps。其中 eps 是一个预先设定的非常小的正数（如 1e-8 或 1e-9），称为精度或容差。

A 解释： 根据 C++ 标准，有符号整数的溢出是未定义行为（Undefined Behavior, UB）。

• B (回绕): 这是无符号整数（如 unsigned int）溢出时的行为，它们会进行模运算。
• 有符号整数溢出则没有任何保证。编译器可能会做任何事情：产生一个看似随机的值、程序崩溃、或者基于“溢出不会发生”的假设进行代码优化，导致难以预料的逻辑错误。因此，必须极力避免有符号整数溢出。

C 解释： std::lower_bound(first, last, key) 返回一个迭代器，指向有序区间 [first, last) 中第一个不小于（not less than）key 的元素。在升序数组中，“不小于”就等价于**“大于或等于（>=）”**。

• 与之对应的是 std::upper_bound，它查找第一个大于 key 的元素。

D 解释： LCA 的倍增算法分为两个阶段：

1. 预处理 (O(n log n)): 对树进行一次 DFS/BFS，计算每个节点的深度和父节点。然后通过动态规划（或递推）填充一个 up[i][j] 数组，表示节点 i 向上跳 2^j 步所到达的祖先。这个过程需要 O(n log n) 的时间和空间。
2. 查询 (O(log n)): 对于每次查询 LCA(u, v)，先将较深的节点跳到与较浅节点相同的深度，然后再将两个节点同时向上跳（利用 up 数组），直到它们的父节点相同。这个跳跃过程的复杂度是 O(log n)。

B 解释：

• A/C: 当 l 和 r 都很大时（例如接近 INT_MAX），l + r 的和可能会超出 int 的表示范围，导致溢出，得到一个错误的结果。>> 1 本质上和 / 2 一样，有相同的风险。
• B: 这种写法是最优的。它首先计算 r 和 l 的距离 (r - l)，这个差值一定不会溢出（因为 r >= l）。然后将距离的一半加到 l 上，数学上等价于 (l+r)/2，但计算过程避免了两个大数直接相加，从而防止了溢出。
• D: 将 l+r 转换为 unsigned 可能会避免溢出（无符号数会回绕），但如果结果超出了有符号数的正数范围，再转回 int 时可能会得到负数，同样是错误的。

B 解释： 在 C++ 中，当除法的两个操作数都是整数时，执行的是整数除法。整数除法的结果会向零取整（truncate towards zero），即直接舍弃小数部分。

• 3 / 2 的数学结果是 1.5。舍弃小数部分后，得到 1。
• 同理，-3 / 2 的结果会是 -1。

B 解释： cin >> var; 在读取数据后，会将我们输入时敲下的回车符（换行符 \n）留在输入缓冲区中。getline 函数会读取这一行直到遇到换行符，因此它会立即读到这个残留的换行符并结束，导致读入一个空字符串。

• B (cin.ignore()): 是标准且正确的做法。cin.ignore(numeric_limits<streamsize>::max(), '\n'); 会丢弃输入缓冲区中当前位置到下一个换行符（包括换行符）之间的所有字符，从而清空这一行，确保 getline 能正确读取下一行输入。
• A (fflush(stdin)): 在 C++ 标准中是未定义行为，不保证有效且不应使用。

C 解释： memset 函数是按**字节（byte）**来对内存进行赋值的。

• 一个 int 通常占 4 个字节。-1 的二进制补码表示中，所有位都是 1（即 0xFFFFFFFF），所以它的每个字节都是 0xFF。因此 memset(a, -1, sizeof a) 恰好能将每个 int 都正确设置为 -1。
• 然而，memset(a, 1, sizeof a) 会将每个字节都设为 1（0x01），这会导致每个 int 的值变为 0x01010101，而不是 1。
• C (std::fill): 是 C++ 中推荐的方式。fill 是一个模板函数，它会正确地按元素类型进行赋值，无论初始化的值是多少，也无论数组是什么类型（int, double 等），都安全可靠。

B 解释：

• A: for (auto x : v) 默认会复制容器中的每个元素到变量 x。修改 x 只是在修改这个副本，容器 v 本身的元素不会改变。
• B: for (auto& x : v) 使用了引用 &。此时 x 成为容器中元素的别名（或引用），而不是副本。对 x 的任何修改都会直接作用于容器 v 中对应的原始元素。这是修改元素的正确方式。
• C: const 表示 x 是一个只读的副本，尝试修改它会导致编译错误。

C 解释： 不同的整型需要不同的格式化占位符来保证正确解析和输出：

• %d: 用于 int。
• %u: 用于 unsigned int。
• %ld: 用于 long int。
• %lld: 用于 long long int。
• %llu: 用于 unsigned long long int。 使用错误的占位符会导致输出错误的值，甚至程序崩溃。

D 解释：

• A (x % 2 == 1): 对于负奇数是错误的。在 C++ 中，-5 % 2 的结果是 -1，所以 -1 == 1 为假。
• D (x % 2 != 0): 这是最稳健的写法。对于任何奇数（正或负），模 2 的结果都是非零的（1 或 -1）；对于任何偶数，结果都是 0。此判断完全正确。
• B (x & 1): 利用位运算，判断 x 的最低二进制位是否为 1。奇数的最低位总是 1，偶数总是 0。这种方法正确且通常效率最高。在题目选项中，B 和 D 都正确，但考虑到对 % 运算符的兼容性，D 更具普适性。

A 解释： unordered_map 是基于哈希表实现的。

• 平均情况 (O(1)): 在哈希函数良好、没有大量冲突的情况下，查找、插入和删除操作的平均时间复杂度是常数时间 O(1)。
• 最坏情况 (O(n)): 如果发生严重的哈希冲突，导致大量元素被映射到同一个桶（bucket）中，哈希表会退化成一个链表（或红黑树，在较新标准中）。此时，查找操作需要遍历这个长链表，时间复杂度退化为线性时间 O(n)。

B 解释： C/C++ 标准严格规定了位移操作的限制：

1. 对负数进行左移是未定义行为 (UB)。
2. 位移的位数是负数，或大于等于操作数类型的总位数（例如，对 32 位 int 左移 32 位或更多），也是未定义行为 (UB)。 这意味着结果完全不可预测，程序可能崩溃或产生任何奇怪的结果，应绝对避免。

B 解释：

• 默认情况下，C++ 的 iostream（cin, cout）与 C 的 stdio（scanf, printf）是同步的，以保证混合使用时输入输出顺序符合预期。但这会带来性能开销。
• ios::sync_with_stdio(false); 关闭同步，可以大幅提升 cin/cout 的性能。但关闭后，就不应再混用 C 和 C++ 的 IO 流，否则可能导致输入输出顺序错乱。
• cin.tie(nullptr); 解绑 cin 和 cout。默认 cin 绑定了 cout，意味着每次执行输入操作 (cin) 之前，都会强制刷新输出缓冲区 (cout)。解绑可以避免这种不必要的刷新，进一步提速。
• 在竞赛编程中，为追求极致性能，通常会同时执行这两项操作，并且之后只使用 cin/cout。

C 解释： 这个问题是差分数组的经典应用。

• 差分数组 d[i] = a[i] - a[i-1] 记录了原数组 a 相邻元素的差。
• 区间增加： 对原数组 a 的 [l, r] 区间统一加上 v，等价于在差分数组上执行两次单点修改：d[l] += v 和 d[r+1] -= v。操作复杂度为 O(1)。
• 单点查询： 查询原数组 a[i] 的值，等于计算差分数组的前缀和 sum(d[1]...d[i])。操作复杂度为 O(i)。
• 对于这个问题，差分数组实现简单，效率极高。而线段树等结构虽然也能实现，但代码更复杂，属于“杀鸡用牛刀”。

C 解释： 这个问题同时涉及区间查询（最小值）和区间修改（批量增加），是线段树的典型应用场景。

• C (线段树): 线段树可以将区间信息（如最小值、和）存储在树节点上。对于区间修改，使用**懒标记（Lazy Propagation）**可以避免遍历整个区间，将修改操作的复杂度从 O(n) 降低到 O(log n)。区间查询的复杂度也是 O(log n)。
• D (稀疏表): 支持快速的区间查询（RMQ问题可达 O(1)），但不支持修改。

B 解释： 一个图是二分图，当且仅当它的所有顶点可以被分成两个不相交的集合 U 和 V，使得所有边都连接 U 和 V 中的顶点（集合内部没有边）。这等价于图中不存在奇数长度的环。

• B (染色法): 是判断二分图的标准方法。从任意一个未访问的顶点开始，用 DFS 或 BFS 遍历图。将起点染成颜色1，其所有邻居染成颜色2，邻居的邻居再染回颜色1，以此类推。如果在遍历过程中发现一个顶点和它的邻居颜色相同，说明存在奇数环，该图就不是二分图。

B 解释：

• B (Trie 树): 是为处理字符串前缀问题而生的数据结构。它将字符串按字符存入一棵树中，从根节点到任意节点的路径都代表一个前缀。要查找以 "pre" 为前缀的所有字符串，只需沿着 "pre" 的路径走到对应节点，该节点下的整个子树就代表了所有符合条件的字符串。效率极高。
• A/C (KMP/Z算法): 主要用于在一个文本串中查找一个模式串，不适合处理大量字符串的前缀匹配问题。

A 解释：

• A (双栈队列): 可以实现均摊 O(1) 的复杂度。一个栈（inStack）用于入队，另一个栈（outStack）用于出队。入队操作直接 push 到 inStack (O(1))。出队时，若 outStack 为空，则将 inStack 的所有元素依次弹出并压入 outStack，这个过程耗时 O(k)，k 为当时 inStack 的大小。然后从 outStack 弹出栈顶。虽然单次出队最坏是 O(n)，但每个元素一生最多只会被移动一次（inStack -> outStack），所以 n 次操作的总时间是 O(n)，均摊到每次操作就是 O(1)。
• B 和 C 实现的队列，单次操作的最坏时间复杂度本身就是严格的 O(1)。

C 解释： 对于 10⁹ 级别的数据，暴力枚举和分解质因数都太慢了。

• C (欧几里得算法): 也叫辗转相除法，基于 gcd(a, b) = gcd(b, a % b) 的原理。它的时间复杂度大约是 O(log min(a, b))，对于大整数计算非常快，是求最大公约数的标准算法。
• D (扩展欧几里得算法): 用于求解 ax + by = gcd(a, b) 的一组解 (x, y)，虽然也能求出 gcd，但比单纯的欧几里得算法要复杂。

B 解释：

• A (Dijkstra): 其贪心策略（每次选择当前最近的点）在有负权边时会失效，可能得到错误答案。
• B (Bellman-Ford): 能够正确处理带有负权边的图，只要图中不存在从源点可达的负权环。其时间复杂度为 O(V * E)，是这类问题的标准解法。
• D (SPFA): 是 Bellman-Ford 的队列优化版本，在大多数情况下比 Bellman-Ford 快，但其最坏时间复杂度仍然是 O(V * E)，并且在一些特殊构造的图上性能会退化，不如 Bellman-Ford 稳定。

B 解释：

• B (std::fill): 是最清晰、最安全、最符合 C++ 风格的做法。它按元素类型进行赋值，你可以精确地将数组设置为你定义的任何极大值常量 INF。
• A (memset): memset(dist, 0x3f, sizeof(dist)) 是一个常用技巧。它将每个字节都设置为 0x3f，使得每个 4 字节的 int 值为 0x3f3f3f3f。这个数大约是 10^9，足够大，且两个这样的数相加不会溢出 int，方便用于最短路等算法。但它是一种技巧，可读性不如 fill。
• C (memset): 除非 INF 恰好是 0 或 -1，否则这种写法是错误的，因为它按字节赋值。

B 解释： 乘法逆元存在的充要条件是 gcd(a, p) = 1。

• a ≡ 0 (mod p) 意味着 a 是 p 的倍数。
• 由于 p 是质数，a 作为 p 的倍数（且 a 不为0时），它们的最大公约数 gcd(a, p) = p。
• 因为 p 是质数，所以 p > 1。因此 gcd(a, p) ≠ 1，故 a 在模 p 意义下不存在乘法逆元。

B 解释：

• A (0/1 背包): 每种物品只有一件，要么选，要么不选。
• B (完全背包): 每种物品有无限件，可以选任意多件。
• C (多重背包): 每种物品有有限的 k 件。
• D (分组背包): 物品被分成若干组，每组中最多只能选一件。