1 条题解
-
0
Guest
-
0
bitworld
@ 2025-8-27 20:41:58
- B
解释：
g(n)是实际代价，h(n)是启发式评估代价。为了保证A*算法能找到最优解，h(n)必须是“可接受的”（admissible），即它的值永远不能超过从n到终点的实际最小代价。 - B 解释： FFT及其在模算术下的变种NTT，可以将两个n次多项式的乘法运算从朴素的 O(n²) 优化到 O(n log n)，这等价于对系数表示的大整数进行乘法。
- B 解释： 根据Sprague-Grundy定理，Nim游戏的SG函数值等于各堆石子数量的异或和。如果异或和为0，则为先手必败状态（P-position）；如果不为0，则为先手必胜状态（N-position）。
- B 解释： Manacher算法是一个巧妙的在线算法，它通过利用回文串的对称性，可以在 O(n) 的时间内找出字符串中以每个字符为中心的最长回文子串，从而得到整个字符串的最长回文子串。
- C
解释：
std::move本身不执行任何移动操作。它是一个类型转换函数，将一个表达式（通常是左值）转换为右值引用类型，这使得对象可以被移动构造函数或移动赋值运算符接管，从而避免不必要的深拷贝。 - B
解释： 中国剩余定理提供了一个求解形如
x ≡ a_i (mod m_i)的一组线性同余方程组的系统性方法，前提是模数m_i两两互质。 - C 解释： 匈牙利算法是基于增广路思想的、用于求解二分图最大匹配问题的经典算法。
- B
解释：
constexpr变量要求其初始化表达式必须是编译器在编译阶段就能确定的常量表达式。这使得constexpr变量可以用在更多需要编译期常量的场景（如数组大小、模板参数等），而const变量不一定能做到。 - C 解释： 这是标准的三集合容斥原理公式：总数 = (所有单个集合大小之和) - (所有两两交集大小之和) + (三者交集大小)。
- C 解释： Treap是“Tree”和“Heap”的结合。它在满足二叉搜索树（BST）性质的同时，还为每个节点赋予一个随机的优先级，并使得这些优先级满足最小堆（或最大堆）的性质。堆性质通过旋转来维持，从而以很高的概率保证树的平衡。
- A
解释： 当问题的总搜索空间（如
2^N）过大，但将其对半分为2^(N/2)后可以接受时，可以使用折半搜索。分别搜索两半的所有可能状态，然后将两半的结果合并，从而找到最终解。 - B
解释：
[=]表示默认以值方式捕获所有在lambda外部使用的自动变量，而&x则是对变量x的一个例外，显式指定以引用方式捕获它。 - B
解释： 当DP问题中的某个状态维度代表了一系列“是/否”或有限的小范围选择时（例如棋盘上的棋子布局、集合的子集等），如果这个维度的大小
k不大（通常k <= 20左右），就可以用一个k位的二进制数来紧凑地表示这个状态，从而进行动态规划。 - B
解释： 卢卡斯定理给出了
C(n, m) mod p与C(n/p, m/p) * C(n%p, m%p) mod p之间的关系，可以将对大数n, m的组合数计算递归地转化为对小数的计算。 - B
解释：
std::bitset将比特位紧凑地存储，通常每个布尔值只占1位（bit），而bool数组每个元素至少占1字节（byte），因此空间效率高得多。同时，它重载了位运算符，可以方便地进行高效的整体位运算。 - C
解释： 在右手坐标系中，如果
a x b的结果为正，表示b在a的逆时针方向；为负，表示在顺时针方向；为零，表示两者共线。 - C
解释： 2-SAT问题可以通过构造一个“蕴含图”来解决。问题有解，当且仅当在这个图中，任何一个变量
x所对应的节点和它的否定¬x所对应的节点不位于同一个强连通分量（SCC）内。 - B
解释：
NULL在C++中通常被定义为整数0或者(void*)0。当用于函数重载时，f(NULL)可能会与f(int)而非f(char*)匹配，导致歧义和错误。nullptr是一个类型为std::nullptr_t的字面量，可以隐式转换到任何指针类型，但不能转换为整数类型，从而消除了这种歧义。 - B 解释： 莫队算法通过将所有查询分块，并对块内查询按右端点排序的方式，重新安排了查询的处理顺序。这保证了区间的两个端点在处理相邻查询时移动的总距离最小，从而优化了整体时间复杂度。
- B 解释： 高斯消元法是通过一系列的行变换，将线性方程组的增广矩阵转化为阶梯形矩阵，然后通过回代求解出方程组的解。
- C 解释： 树形DP通常利用树的递归结构。通过对树进行一次后序遍历（即深度优先搜索），可以先计算出所有子树的DP值，然后在回溯到父节点时，利用子节点的信息来计算父节点的DP值。
- B
解释：
std::unique会将所有不重复的元素移动到容器的前部，并返回一个指向这个新序列末尾（即第一个被覆盖的重复元素的位置）的迭代器。它并不会改变容器的大小。 - B
解释： 莫比乌斯反演提供了一种在“和函数”与“原函数”之间互相转换的方法。如果知道一个函数
g(n)是另一个函数f(d)在n的所有约数d上的和，就可以通过反演公式求出f(n)。 - B 解释： 可持久化的核心在于，每次修改操作都会创建一个“新”版本的数据结构，而旧版本保持不变且仍然可以访问。这通常通过巧妙地复用未改变的部分节点，只创建少量新节点来实现。
- C
解释： 一个n位无符号整数可以表示
2^n个数（从0到2^n - 1）。对于64位，最大值就是2^64 - 1。 - C
解释： 每个约束条件
x_j - x_i <= w_k都可以被看作是图中一条从节点i到节点j，权重为w_k的边。整个约束系统就构成了一个图，求解满足所有约束的一组解就等价于在这个图上求解单源最短路问题。 - B 解释： 拉斯维加斯算法的特点是其结果总是正确的，但完成计算所需的时间是随机的，存在期望运行时间。蒙特卡洛算法则相反，运行时间是确定的，但结果可能以一定概率出错。
- B 解释： 笛卡尔树的每个节点有两个值：一个键（key）和一个优先级（priority）。对于键，它满足二叉搜索树的性质（左子<根<右子）。对于优先级，它满足最小堆的性质（根<左子，根<右子）。
- C
解释： "插板法"是解决组合问题中“不定方程非负整数解个数”的经典模型。将k个相同物品放入n个不同盒子，等价于将k个球用n-1个隔板分成n份，总方案数为
C(k + n - 1, n - 1)或C(k + n - 1, k)。 - B
解释： SFINAE (Substitution Failure Is Not An Error) 是一种C++编译时技术。
std::enable_if是实现SFINAE的常用工具，它允许我们根据模板参数的特性（如是否为整数、是否有某个成员函数等）来“启用”或“禁用”一个模板，从而实现更精细的函数重载或模板特化。 - B
解释： Z数组
Z是Z算法的核心，其中Z[i]表示字符串S从下标i开始的后缀S[i...]与整个字符串S的最长公共前缀（LCP）的长度。 - C
解释： 这是C/C++中一个重要的优化规则，它允许编译器假设不同类型的指针指向不同的内存位置。如果你违反了这个规则（例如，将一个
int*强制转换为float*并解引用来访问同一个int对象），编译器的优化可能会导致程序行为不可预测，即未定义行为。 - C
解释： 欧拉定理指出，对于任何与
n互质的整数a，都有a^φ(n) ≡ 1 (mod n)，其中φ(n)是欧拉函数。当n是质数时，φ(n) = n-1，此时欧拉定理退化为费马小定理a^(n-1) ≡ 1 (mod n)。 - A 解释： 霍夫曼编码是一种贪心算法。它通过构造一棵特殊的二叉树（霍夫曼树），使得在文本中出现频率越高的字符，其在树中的深度越浅，从而对应的二进制编码长度越短，达到压缩数据的目的。
- A
解释： 一个二进制数
x减1，会使其最右边的1变为0，并且该位之后的所有0都变为1。再与原数x进行按位与运算，就会精确地将这个最右边的1清除，而其他位保持不变。这个操作常用于快速计算一个数二进制中1的个数。 - B 解释： 这是期望最基本也是最重要的性质之一：期望的可加性，即“和的期望等于期望的和”。这个性质对于任意随机变量都成立，无论它们是否独立。
- C 解释： 精确覆盖问题是指给定一个全集X和X的一系列子集，是否能从中找到一个子集集合，使得这些子集不相交且其并集恰好为全集X。DLX算法是高德纳（Donald Knuth）提出的，基于带双向十字循环链表的数据结构，是解决这类问题的事实标准算法。
- D
解释： 设
T(n)为移动n个盘子所需的步数。根据递归解法：将n-1个盘子从A移到B，将第n个盘子从A移到C，再将n-1个盘子从B移到C。可得递推式T(n) = 2*T(n-1) + 1。这是一个典型的指数增长，解得T(n) = 2^n - 1，因此时间复杂度为 O(2^n)。
- B
解释：
Guest