考点小记
-
等比数列求和公式
已知等比数列 \(\{a_n\}\) ，公比为 \(q\)，前 \(n\) 项和为 \(S_n\) 。
则有 \(S_n = \begin{cases} na_1, &q = 1 \\ \large \frac{a_1(1 - q ^ n)}{1 - q}, &q \neq 1 \end{cases}\)
证明：当 \(q \neq 1\) 时，\(\because S_n = a_1 + a_2 + a_3 + \cdots + a_n\)
\(\therefore S_n = a_1 + a_1q + a_1q ^ 2 + a_1q ^ 3 + \cdots + a_1q^{n - 1}\)
\(\therefore qS_n = a_1q + a_1q ^ 2 + a_1q ^ 3 + a_1q ^ 4 + \cdots + a_1q ^ n\)
\(\therefore (1 - q)S_n = a_1(1 - q ^ n)\)
\(\therefore S_n = \large \frac{a_1(1 - q ^ n)}{1 - q}\) -
对数化幂为积公式
例：若一个自然数在十进制下有 \(n\) 位，则它在二进制下的位数与哪个表达式最接近？
解：设该数在二进制下的位数为 \(x\) 位，则近似有
\(\begin{aligned} 2 ^ x &= 10 ^ n \\ x &= \log_2 10 ^ n \\ x &= n \log2_2 10 ^ n \end{aligned}\) -
对于边权为正的图执行 Dijkstra 算法，使用斐波那契堆数据结构效率最高。
斐波那契堆各操作的时间复杂度：插入、合并、查找最小节点均摊 \(O(1)\) ，删除最小节点平摊 \(O(\log n)\) 。
斐波那契堆的空间消耗较大，时间复杂度一般优于二叉堆。 -
二叉搜索树（二叉排序树）支持的操作
插入、删除、求第 \(k\) 大的元素、求元素 \(x\) 是第几大的元素。 -
巧用完全二叉树的编号性质
例：若一棵完全二叉树有 100 个结点，则其叶子结点的个数为？
解：由完全二叉树的编号性质得，若父结点的编号为 \(i\) ，则左儿子结点的编号为 \(2i\) ，右儿子结点的编号为 \(2i + 1\) 。
显然，编号为 50 的结点的左儿子结点的编号为 100 。所以编号为 51 ~ 100 的结点均为叶子结点。
故叶子结点的个数 \(n_0 = 100 - 51 + 1 = 50\) 。 -
用动态规划求解“最长公共子序列”（LCS）问题时，若两个字符串 \(s\) 和 \(t\) 的长度分别为 \(m\) 和 \(n\) ，则所需的存储空间为 \(O(mn)\) 。
\(f_{i, j}\) 表示字符串 \(s\) 前 \(i\) 位，字符串 \(t\) 前 \(j\) 位的最长公共子序列的长度。 -
DFS 和 BFS 的时间复杂度均为 \(O(n + e)\) ，DFS 不仅可以用递归实现，还可以用栈来模拟递归过程实现。
-
拓扑（pū）排序
拓扑排序可用于判断有向图是否存在环，对有向无环图（DAG）的所有结点排序，确定一个依赖关系集合中事物的发生顺序等。
以下是一个时间复杂度为 \(O(n + m)\) 的拓扑排序的代码。
int ind[MAXN], n, m;
vector<int> e[MAXN];
bool topo_sort() {queue<int> q;int cnt = 0;for (int i = 1; i <= n; i++) if (!ind[i]) q.push(i);while (!q.empty()) {int u = q.front(); q.pop();cnt++;for (int v : e[u])if (!--ind[v]) q.push(v);}return cnt == n;
}
- 快速排序
快速排序采用分治的策略，递归地执行。平均时间复杂度 \(O(\log n)\) ，最坏情况下可达到 \(O(n ^ 2)\) 。
基本思想：通过一趟排序将要排序的数据分割成独立的两部分：分割点左边都是比它小的数，右边都是比它大的数。
然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
void qsort(int a[], int l, int r) {int i = l, j = r, flag = a[l + r >> 1]; // flag 须保证是在 [l, r] 范围内的数据while (i <= j) {while (a[i] > flag) i++;while (a[j] > flag) j--;if (i <= j) swap(a[i], a[j]), i++, j--;}if (l < j) qsort(a, l, j);if (i < r) qsort(a, i, r);
}
- 计算机基础知识
- 内存储器通常可以分为随机存储器（RAM），只读存储器（ROM）和高速缓冲存储器（Cache）。内存（主存）和 CPU 构成了计算机的主机部分。
- 一般的个人计算机在同一时刻只能存取一个特定的内存单元。
- 分时系统让多个用户可以共享一台主机的运算能力，为保证每个用户都能得到及时的响应通常会采用时间片轮转调度的策略。
- 主定理计算时间复杂度
主定理用于解决形如以下形式的递归（分治）算法的时间复杂度。
\(T(n) = aT(n / b) + f(n)\)
其中 \(a(a \geq 1)\) 为子问题个数， \(b(b > 1)\) 为子问题规模。
则答案有以下三种情况。
- 若函数 \(n ^ {\log_b a}\) 更大，则 \(T(n) = O(n ^ {\log_b a})\) 。
- 若函数 \(f(n)\) 更大，且 \(af(n / b) < cf(n)\) ，则 \(T(n) = O(f(n))\) 。
- 若两函数相等，则 \(T(n) = O(n ^ {\log_b a} \log ^ {k + 1} n)\) 。
即比较 \(n ^ {\log_b a}\) 和 \(f(n)\) 的大小，取较大的。若相等则加上 \(\log n\) 的时间复杂度。
例1：设某算法的计算时间表示为递推关系式 \(T(n) = 2T(n / 2) + n (n \in N ^ +)\) ，且 \(T(0) = 1\) ，则该算法的时间复杂度为？
解：\(\because a = 2, b = 2, O(n ^ {\log_2 2}) = \Theta(n) = O(f(n))\)
\(\therefore T(n) = O(n \log n)\) 符合 Case 3 。
例2：设某算法的计算时间表示为递推关系式 \(T(n) = T(n - 1) + 2n (n \in N ^ +)\) ，且 \(T(0) = 0\) ，则该算法的时间复杂度为？
解：本题的递推方程属于线性递推（非分治型），不能使用主定理。考虑累加递推求解。
\(\begin{aligned}
T(n) &= T(n - 1) + 2n \\
&= [T(n - 2) + 2(n - 1)] + 2n \\
&\vdots \\
&= T(0) + 2 \times 1 + 2 \times 2 + \dots + 2n \\
&= 2(1 + 2 + \dots + n) \\
&= 2 \times \frac{n(n + 1)}{2} \\
&= n(n + 1) \\
&= O(n ^ 2)
\end{aligned}\)
-
插入排序的平均时间复杂度为 \(O(n ^ 2)\) 。
-
树一定可以进行黑白染色，使得相邻结点的颜色不同。基环树、连通图、欧拉图均不一定。
-
整数划分（EquationCount）问题
整数划分是将正整数 \(n\) 划分成多个不小于 1 的整数之和的组合形式。不同顺序的加数视为同一划分。
记 \(f(n, m)\) 为 \(n\) 的最大加数不超过 \(m\) 的划分个数。
有 \(f(n, m) = \begin{cases} 1, & n = 1 \lor m = 1 \\ f(n, n), & n < m \\ 1 + f(n, n - 1), & n = m \\ f(n - m, m) + f(n, m - 1), & n > m \end{cases}\)
对于正整数 \(n\) ，其划分数为 \(f(n, n)\) 。
以下代码的时间复杂度为 \(O(2 ^ n)\) 。
int equation_count(int n, int m) {if (n == 1 || m == 1) return 1;if (n < m) return equation_count(n, n);if (n == m) return 1 + equation_count(n, n - 1);return equation_count(n - m, m) + equation_count(n, m - 1);
}
- 最长上升子序列（LIS）问题
最长上升子序列是指元素按顺序递增且长度最大的子序列。这里考虑贪心和二分优化动态规划解法的 \(O(n ^ 2)\) 为 \(O(nlogn)\) 。
记 \(b_i\) 表示长度为 \(i + 1\) 的上升子序列的末尾元素的最小值。
int search(int lf, int rt, int x) {int mid;while (lf <= rt) {mid = lf + rt >> 1;if (x >= b[mid]) lf = mid + 1;else rt = mid - 1;}return lf;
} // search() 等价于 lower_bound()
b[1] = a[1];
int len = 1;
for (int i = 2; i <= n; i++) {if (a[i] > b[len]) b[++len] = a[i];else if (a[i] < b[len]) {int pos = lower_bound(a + 1, a + len + 1, a[i]) - a;// pos = search(1, len, a[i]);b[pos] = a[i];}
}
- 树的直径
树的直径是树上两点间距离的最大值，即树上最长的不重复经过一个点的路径长度。连接这两点之间的路径被称为树的最长链。
显然，一棵树可以有多条直径，其长度相等。
从树上任意一个点出发所到达的最远的点一定是树的两个端点之一。
考虑用反证法证明树的直径的这条性质。
证明：记两点 \(u\)， \(v\) 间的距离为 \(d(u,v)\) 。设树的最长链为 \((s, t)\) ，出发结点为 \(y\) ，搜索到达最远结点 \(z\) 不为 \(s\) 或 \(t\) ，则树的直径是 \(d(s, t)\) 。
- 若 \(y\) 在 \((s, t)\) 上，
则 \(d(y, z) > d(y, t) \Longrightarrow d(x, z) > d(x, t) \Longrightarrow d(s, z) > d(s, t)\) ，与 \(d(s, t)\) 为树的直径矛盾。
- 若 \(y\) 不在 \((s, t)\) 上，且 \((y, z)\) 与 \((s, t)\) 存在重合路径。
则 \(d(y, z) > d(y, t) \Longrightarrow d(x, z) > d(x, t)\Longrightarrow d(s, z) > d(s, t)\) ，与 \(d(s, t)\) 为树的直径矛盾。
- 若 \(y\) 不在 \((s, t)\) 上，且 \((y, z)\) 与 \((s, t)\) 不存在重合路径。
则 \(d(y, z) > d(y, t) \Longrightarrow d(x', z) > d(x', t) \Longrightarrow d(x, z) > d(x, t) \Longrightarrow d(s, z) > d(s, t)\) ，与 \(d(s, t)\) 为树的直径矛盾。
综上，三种情况下假设均会产生矛盾，故该性质得证。
不难发现，可以用两次 DFS 或 BFS 的方法在 \(O(n)\) 的时间复杂度求得树的直径。
具体地，首先从任意点 \(y\) 开始进行第一次搜索 ，到达距离其最远的点 \(z\) ，然后再从点 \(z\) 开始做第二次搜索 ，到达距离 \(z\) 最远的点 \(z'\) ，则 \(d(z, z')\) 即为树的直径。
vector<int> e[MAXN];
int d[MAXN], s, n;
int q[MAXN], f[MAXN], hd, tl, t;
void dfs(int u, int f) {for (int v : e[u]) {if (v == f) continue;d[v] = d[u] + 1;if (d[v] > d[s]) s = v;dfs(v, u);}
}
int bfs(int u) {memset(f, false, sizeof(f));hd = tl = 0, q[tl++] = u, d[u] = 0;while (hd < tl) {u = q[hd++];for (int v : e[u])if (!f[v])q[tl++] = v, d[v] = d[u] + 1, f[v] = true;}int c = 1;for (int i = 2; i <= n; i++)if (d[c] < d[i]) c = i;return c;
}
int main() {cin >> n;for (int i = 1, u, v; i < n; i++) {cin >> u >> v;e[u].push_back(v), e[v].push_back(u);}dfs(1, 0);d[s] = 0, dfs(s, 0);cout << d[s];
/*s = bfs(1);t = bfs(s);cout << d[t];
*/return 0;
}
-
完全二叉树的结点数量关系
设一完全二叉树有 \(N\) 个结点，$ n_0 $叶结点。
则 \(n_0 = \begin{cases} \large \frac{N + 1}{2}, & N \quad is \quad odd \\ \large \frac{N}{2}, & N \quad is \quad even \end{cases}\)
例：若一完全二叉树有 \(4n + 1\) 个结点，求叶结点的数量？
解：\(\because N = 4n + 1\) 是奇数 \(\therefore n_0 = \frac{4n + 1 + 1}{2} = 2n + 1\) -
按照字典序排序的下一个排列
- 从左往右找到第一个减小的数字 \(a\) 。
- 从 \(a\) 起往右找第一个比 \(a\) 大的最小数字 \(b\) 。
- 交换 \(a\) 与 \(b\) ，将交换后的的 \(b'\) 右边从小到大排序。
- 链式前向星存图
\(head[u]\) 表示以 \(u\) 为起点的第一条边的编号。
\(to[i]\) 表示第 \(i\) 条边所指向的点。
\(nxt[i]\) 表示第 \(i\) 条边下一条边的编号。
\(val[i]\) 表示第 \(i\) 条边的权值。
int nxt[MAXM], to[MAXM], val[MAXN], head[MAXN], cnt;
void add(int u, int v, int w) {nxt[++cnt] = head[u];to[cnt] = v;val[cnt] = w;head[u] = cnt;
}
- 由 \(n\) 个结点构成的形态不同的二叉树数量为对应的卡特兰数。
\(Catalan(n) = \large \frac{C_{2n}^n}{n+1} \small (n \in N)\) - Linux 系统的基本命令
ls：列出目录内容。cd：更改当前工作目录。pwd：显示当前工作目录的路径。mkdir：创建新目录。rmdir：删除空目录。rm：删除文件或目录。cp：复制文件或目录。mv：移动或重命名文件或目录。touch：创建空文件或更新文件的时间戳。find：在文件系统中查找文件和目录。
-r：目录； -f：强制。
- C++ 运算符优先级
关系运算符 \(>\) 位运算（移位除外）\(>\) 逻辑运算
例：以下 C++ 代码运行后 \(t\) 的值为？
解：auto 类型会自适应为 int 类型，答案为 \(0\) 。
int a = 1, b = 1, c = 4, d = 5, e = 1;
bool f = true;
auto t = ((a > b ^ c) && f) < d ^ e;
错题整理
J 组
-
一个 32 位无符号整数可以表示的最大值，最接近以下哪个选项？（A）
A \(4\times10^9\) B \(3\times10^{10}\) C \(2\times10^9\) D \(2\times10^{10}\) -
用 5 个权值 10,12,15,20,25 构造哈夫曼树，该树的带权路径长度是多少？（B）
A 176 B 186 C 196 D 206
构造哈夫曼树，带权路径长度为各个权值与对应的深度之和。即 \((10 + 12) \times 3 + (25 + 15 + 20) \times 2 = 186\) . -
已知 f[0] = 1, f[1] = 1, 并且对于所有 n≥2 有 f[n] = (f[n-1] + f[n-2]) % 7.那么 f[2025] 的值是多少？（D）
A 2 B 4 C 5 D 6
模拟前几项，{1, 1, 2, 3, 5, 1, 6, 0, 6, 6, 5, 4, 2, 6, 1, 0} 发现循环节为 16 。 则 \(f[2025] = f[2025 \mod 16] = f[9] = 6\) 。 -
下列关于 C++ string类的说法，正确的是？（B）
A string 对象的长度在创建后不能改变。 可以改变
B 可以使用 + 运算符直接连接一个 string 对象和一个 char 类型的字符。
C string 的 length() 和 size() 方法返回的值可能不同。 size() 等价于 length()
D string 对象必须以 '\0' 结尾, 且这个结尾符计入 length()。 '\0' 不计入 length() -
一个 8×8 的棋盘, 左上角坐标为 (1,1), 右下角为 (8,8)。一个机器人从 (1,1) 出发，每次只能向右或向下走一格。要到达 (4，5)，有多少种不同的路径？（B）
A 20 B 35 C 56 D 70
注意到，路径数为 \(C_{(4 - 1) + (5 - 1)}^{4 - 1} = C_7^3 = 35\) 。 -
一棵包含 1000 个结点的完全二叉树，其叶子结点的数量是多少？（C）
A 499 B 512 C 500 D 501
本题极其不应该失误。\(n_0 = \lceil \frac{1000}{2} \rceil = 500\) 。 -
将第 16 行中的“&&gcd(i,k)==1”删去不会影响程序运行结果。（F）
反例 \(\left\{ i = 2, j = 3, k = 4 \right\}\) 。 -
将第 7 行的“gcd(b,a%b)”改为“gcd(a,a%b)”后，程序可能出现的问题是？（B）
A 输出的答案大于原答案。
B 输出的答案小于原答案。
C 程序有可能陷入死循环。
D 可能发生整型溢出问题。
gcd 函数的返回值会变大，则满足 ans 增加的条件数会变少。 -
将第 14 行的“n=std::unique(a+1,a+n+1)-a-1;”删去后，有可能出现与原本代码不同的输出结果。（F）
阅读程序（2）解决的问题是：将 \(n\) 个数字分成尽可能少的组，要求每组中的极差小于 \(k\) 。
unique 函数去重前后，对分组的情况无影响。 -
假设输入的 a 数组和 k 均为正整数，执行第 18 行代码时，一定满足的条件不包括？（B）
A j<=i B a[i]-a[j]>k C j<=n D a[j]<a[i]
显然条件 A、C 一定满足，条件 D 满足的原因是：数组已经排序且去重，下标 j 总是小于 i 。
条件 B 不一定满足的原因是：由 a[i] - a[j + 1] <= k 结合上述推理得 a[i] - a[j] >= a[i] - a[j + 1] 。但不能据此判断 a[i] - a[j] 与 k 的关系。 -
假设输入的 a 数组和 k 均为正整数，但a 数组不一定有序，则若误删去第 13 行的“std:: sort(a+1,a+n+1);”, 程序有可能出现的问题有？（B）
A 输出的答案比原本答案更大
B 输出的答案比原本答案更小
C 出现死循环行为
D 以上均可能发生
若数组无序，则 a[i] - a[j + 1] 值可能为负数，指针 j 不满足移动条件，ans[j] 较小，ans[i] 较小，ans[n] 较小。 -
一个序列 b 与其升序排序后的序列 a 的最长公共子序列（LCS）为 b 的最长上升子序列（LIS）。
-
判断“挑战者与擂主”是否“意见不合”的语句？（D）
A query(candidate, i) == false
B query(i, candidate) == true
C query(candidate, i) == false && query(i, candidate) == false
D query(candidate, i) == false || query(i, candidate) == false
只要两人“意见不合”，就说明两人中至少有一人是糊涂人。所以是或者的关系。