考察知识点：树上 DFS、倍增、LCA 设 为颜色 的两个直径端点（即距离最远的两个点）， 为颜色 中的一个点，则点 到颜色 中点的最大距离为 。 可以想象一个点到一条线段的最远距离必然出现在这个点到两个端点的距离中，在此不做严格证明。 进而我们有如下结论： 设 为颜色 的两个直径端点， 为颜色 的两个直径端点，则颜色 中的点到颜色 中点的最大距离为 。 特殊的，当某种颜色的点不足两个时，结论可以简化。 因此我们的任务就变成了查找每种颜色距离最远的两个点。 我们使用 LCA （最近公共祖先）来计算树中每两点间的距离： 其中， 表示点 的深度（即点 到根节点的距离）。 ...

考察知识点：树上 DFS、倍增 本题很容易想到模拟的方式，但时间复杂度为 ，会超时。 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<pii>...

考察知识点：树上 DFS 设节点 i 到根节点 1 的距离为节点 i 的长度，记为 dist[i]，则有以下结论： 长度为偶数的两个节点之间的路径长度一定为偶数 长度为奇数的两个节点之间的路径长度也一定为偶数 因此本题我们只需要遍历整棵树，记录每个节点的长度，然后统计长度为偶数的节点数量 和长度为奇数的节点数量 ，长度为偶数的路径的数量即为 。 时间复杂度： #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef p...

考察知识点：生成树 本题其实不用建树，对比两棵树的差异即可，当生成树 a 有而生成树 b 没有的边的数量不等于生成树 a 没有而生成树 b 有的边的数量时输出 -1（事实上，可以证明对于两棵节点相同的生成树，这两个值一定相等），否则输出相差边数之和的一半。 时间复杂度： #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll&...

考察知识点：贪心、优先队列、哈夫曼树 题目翻译一下就是 个节点构成一棵二叉树，求这棵树的最小带权路径长度。 哈夫曼树 是带权路径长度最小的树，所以本题只需要构造一棵哈夫曼树即可。 时间复杂度： #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi;...

考察知识点：贪心、优先队列 读入服务器的信息，按照 (l, r, v) 升序排序，遍历每一位用户，为每一位用户分配符合条件的服务器中 r 最小的服务器，对应的服务器的 v 值减一，若成功为用户分配服务器，则答案 ans 加一。 时间复杂度： #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typede...

考察知识点：贪心、优先队列 模拟操作系统 MIN/OPT 换页机制，每次换页优先选择未来不会再访问的页或者在最长一段时间不会再访问的页（即当前缓存页中下次最晚访问的页），具体实现请见代码。 理论上，MIN/OPT 换页机制 是最优的内存换页机制，但是由于需要预知未来的访问情况，所以在实际应用中无法使用，只能作为一种理论参考。 时间复杂度： #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, i...

考察知识点：贪心、优先队列 读入每个建筑的信息，按照每个建筑修理的截止时间 t2 升序排序，然后依次将建筑修理的时间 t1 加入优先队列（大根堆），同时维护当前建筑修理的时间之和 time，当当前建筑修理完成后的时间大于截止时间时，如果当前建筑所需的修理时间 t1 小于优先队列顶端的建筑所需的修理时间（即最长修理时间）时，则将当前建筑与优先队列顶端的建筑交换，同时更新 time 为 time - pq.top() + t1，最后的优先队列大小即为最多可修理的建筑数量。 时间复杂度： #include <bits/stdc++.h> using namespace std; typ...

考察知识点：贪心、优先队列 读入每个士兵的信息，按照士兵的 s[i] 值降序排序，然后依次将士兵战力加入优先队列（小根堆），同时维护当前士兵战力之和 cnt，当优先队列大小超过当前士兵的 s[i] 值时，将优先队列顶端的士兵战力（即最低战力）从 cnt 中减去，直到优先队列大小不超过当前士兵的 s[i] 值为止（由于已经进行了降序排序，所以当前的 s[i] 一定是已选择士兵中最低的 s 值），每次更新答案 ans 为 max(ans, cnt)。 时间复杂度： #include <bits/stdc++.h> using namespace std; typedef long l...

A. 开心的涂刷 题目链接：A. 开心的涂刷 考察知识点：数学、快速幂 nnn 个格子处于同一排，忽略限制最多有 mnm^nmn 种涂法。 考虑让小明不开心的涂法，易知这样的涂法有 m(m−1)n−1m(m-1)^{n-1}m(m−1)n−1 种，因为第一个格子可以从 mmm 种颜色中任选，后面的格子只能从与上一个格子不同的 m−1m-1m−1 种颜色中任选。 最终答案即为 mn−m(m−1)n−1m^n-m(m-1)^{n-1}mn−m(m−1)n−1，用快速幂优化即可。 时间复杂度：O(log⁡n)O(\log n)O(logn) #include <bits/stdc++.h&gt...

考察知识点：数学、逆元 11+22+⋯+nn=n(n+1)(2n+1)61^1+2^2+\dots+n^n = \frac{n(n+1)(2n+1)}{6}11+22+⋯+nn=6n(n+1)(2n+1)​ 证明方法有很多种，详情请见： 1²+2²+…+n²求和公式的推导有哪些方法? - 知乎 注意除 666 时要使用逆元。 时间复杂度：O(1)O(1)O(1) #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pa...

题目链接：G. 取手机 考察知识点：数学 事实上，问题相当于给定 aaa 台 iPhoneX 和 bbb 台 S8，然后随机排列，问你第 kkk 台是 S8 的概率。 很明显，答案与 kkk 无关，为 ba+b\frac{b}{a+b}a+bb​。 时间复杂度：O(1)O(1)O(1) #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair&lt...

考察知识点：数学、逆元 一个点到另一个点的曼哈顿距离可以分解为 xxx 与 yyy 方向上的分量，同一行的点到另一点的 xxx 分量相同，同一列的点到另一点的 yyy 分量相同。 因此，我们可以分别枚举每一行和每一列，统计对应的 xxx 分量和 yyy 分量。对于点 (i,j)(i,j)(i,j)，它的期望曼哈顿距离为第 iii 行的 xxx 分量与第 jjj 列的 yyy 分量之和。 然后枚举每个位置的点计算期望曼哈顿距离的异或和即可。 计算期望时注意使用逆元。 #include <bits/stdc++.h> using namespace std; typedef long...

考察知识点：数学 经典的约瑟夫环问题，模拟即可，下面的代码提供了一种思路。 时间复杂度：O(nk)O(nk)O(nk) #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vl; typedef ...