资讯详情

Aug 3rd

P10837, P9750, P1076

Simulation. Somewhat easy, Beware of tiny details.

P17089, P1800

Interesting DP problem. Not easy to figure out.

Aug 4th

P1016, P1250, P4144, P1668

Greedy. It seems to be necessary to practice more.

P3382, P1883

Template of finding the extremum of a unimodal function via ternary search. Beware of precision errors.

P5931

Pure math problem. It is quite necessary to have a good command of Math Compulsory 1.
Somewhat interesting.

P1404, P1542

Binary search on answer.

P1717

DP. Practice more.

Aug 5th

P4712

Nice greedy problem.

P10389

Easy mathematical derivation & binary search on answer.

P3029

Easy problem of discretization and two-pointers. Merely a simple review.

P9025

Ternary search for the minimum of a unimodal function.

P2652

Discretization & binary search.
A greate example of leveraging reverse thinking.
Rather than focusing on replacements, it is better to consider the maximum number of cards currently forming a straight flush.
Enumerate each card as the end of the straight flush. This has a greedy flavor, and it ensures we obtain the maximum number. Then use binary search to find a valid card of the same suit.
Note that the input may contain duplicate cards (same suit and rank). Therefore, it is necessary to deduplicate the cards before binary search to ensure correctness.
In summary, the overall process is:

1. Discretize suits and store cards grouped by suit.
2. During enumeration: deduplicate, binary search, and update the maximum answer.
3. Finally output the difference between the total card number and this maximum value.

P7149

Discretize the values (since they are guaranteed to be distinct, so simply sorting them to obtain their ranks is sufficient), maintain a 2D prefix sum array, and enumerate to calculate the answer.
Remember \(+1\) to the final answer.

P5788, P2947, P2866, B3666

Template of monotonic stacks.
As yifusuyi points out in B3666 solution, "Essentially, a monotonic stack maintains the suffix extremum for all prefixes of a sequence."

P3467

Monotonic stack.
Obviously, the answer is independent of the width of the buildings.
Consider the case where all the buildings are of same height. One poster is enough.
但若整个建筑物链由两个高度不相同的等高建筑物子链拼接而成，那么显然需要两张海报。
如果是三个高度互不相等的，那么显然又需要三张。
但是！如果在一个较高的等高子链左右两侧的较矮的等高子链高度相同，这时这两个子链就可以用同一张海报覆盖，中间较高的子链高出来的部分再用一张即可。只需要两张。
此时我们就能想到用单调栈维护：初始海报数为建筑物数，枚举建筑物链的高度序列，当栈顶大于即将入栈元素时弹出，若最后栈顶元素与即将入栈元素等高，则将需要的海报数 \(-1\)。
最后得到的答案自然就是最少海报数了。

P1901

单调栈。
考虑当一个下标入栈时，弹栈操作中弹出的下标对应的发射站都相当于是以准备入栈的发射站作为右侧最近的更高发射站，所以对于每次弹栈，都将准备入栈的发射站接收的能量值加上弹出的发射站的能量值。
然后把这个发射站压入栈中。此时原本栈顶的发射站就是入栈的发射站左侧最近的更高发射站，所以入栈前给栈顶接收的能量值加上入栈的发射站的能量值。
这样对于每个发射站，都能够找到其左右两侧最近的更高发射站并向其发射能量。

P2032、P1886、B3667

单调队列模板。

P1714

令原数组前缀和为 \(\displaystyle s_i = \sum_{j = 1}^{i}{p_i}\)，则题意即最大化 \(s_r - s_{l - 1}\)。
考虑枚举 \(s_r\)，显然在 \(s_r\) 固定时，\(s_{l - 1}\) 应尽量小，并且应当满足 \(i - j \leq m\)。
这就转化成了求区间最值的问题，考虑用单调队列维护 \(s_{l - 1}\)。

另外，本题有两个需要注意的小细节：

• \(s_0 = 0\) 应当先加入单调队列中，否则无法覆盖到左端点为 \(1\) 的区间。
• 本题的子段长度应当大于 \(0\)，为避免在维护中出现自己减自己的情况，应当先统计答案再入队。

P2239、P1061

水题。

8.6

P3367、P1536、P1551、P2814

并查集板子。

P1455

并查集 + 0/1 背包。
在合并过程中记得先特判两元素已经在同一集合内的情况直接返回，防止代价和贡献重复计算。

P1661

并查集 + 二分答案。

P1892

拓展域并查集。
传统并查集只能够维护集合间的一种关系，而拓展域并查集能够处理集合间的多种不同关系，例如如相互排斥或相互独立的关系等。
此处是二倍拓展域。
设有 \(n\) 个元素。因为要维护二倍拓展域所以扩充到 \(2n\) 个，元素 \(x\) 对应的反元素为 \(n + x\)。
若其中两个元素 \(a, b\) 是朋友，很简单，合并 \(a\) 与 \(b\) 即可。
若其中两个元素 \(a, b\) 是敌人，这时我们需要做的是合并 \(a\) 与 \(n + b\)、再合并 \(n + a\) 与 \(b\)。
可以理解为因为 \(b\) 是 \(a\) 的敌人，所以 \(a\) 与反的 \(b\) 是朋友。对于 \(b\) 同理。
这时如果我们再有 \(c\) 是 \(b\) 的敌人，那合并之后，会发现 \(a\) 与 \(c\) 在同一个集合里。
这样我们就满足了题目中“敌人的敌人是朋友”的条件，接下来的部分就是朴素的并查集合并、连通块计数的过程了。

P1955

离散化 + 并查集。

P1525

与 P1892 类似，也要用到二倍拓展域并查集。

P10091

考虑对分数值进行二分答案。

先对序列 \(a, b\) 进行升序排序。
此时显然有 \(\displaystyle \frac{a_j}{b_i} < \frac{a_{j + 1}}{b_i}\) 与 \(\displaystyle \frac{a_j}{b_i} > \frac{a_j}{b_{i + 1}}\) 成立。
于是在 \(\texttt{check}\) 函数中可以依此求二分到的分数值在所有分数中的大致排名。
最后对于二分出来的答案，可以对每个分母枚举是否能找到对应的分子，最后约分、输出即可。

数据极卡精度，需要 \(\texttt{long double}\)。对应地，四舍五入应用 \(\texttt{roundl}\) 而非 \(\texttt{round}\)，求绝对值应用 \(\texttt{fabsl}\) 而非 \(\texttt{abs}\)。

P3865、P1816、P2880、P2251、P1890、P2412

ST 表板子题。

P14517

绝世好题！绝世好题！绝世好题！

考虑以下标 \(i\) 开始的数据如何合法。显然，这样的一组数据合法当且仅当：

\[\max_{j = i + 1}^{i + v_i} \max \{ u_j, v_j \} \le u_i. \]

发现上面这一坨区间最大值可以使用 ST 表维护。

接下来我们从后往前递推，令 \(f_i\)（取值为 \(0/1\)）表示以下标 \(i\) 开始的数据是否合法。很容易得到递推式：

\[f_i = [\max_{j = i + 1}^{i + v_i} \max \{ u_j, v_j \} \le u_i] \times f_{i + v_i + 1}. \]

注意需要初始值 \(f_{n + 1} = 1\)，其中 \(n\) 为题目所输入的数据行数。

因为题目中原题的第一组数据的 \(n, m\) 都尚未给出（其实也就是需要我们求方案数的核心部分），所以对于每个 \(f_i = 1\) 我们都钦定题目输入数据的 \(1 \sim i - 1\) 行为第一组数据给出的图边。
于是乎每当递推到一个 \(f_i = 1\)，我们都有 \(\text{ans} \gets (\text{ans} + 2 \cdot 10^5 - \max_{j = 1}^{i - 1} \max \{ u_j, v_j \} + 1) \bmod 998244353\)。
另外，注意 \(i = 1\) 的情况应当单独处理，考虑到在此之中为访问 ST 表而计算的 \(\log_2{(i - 1)}\) 不应当出现真数为 \(0\) 的情况。

P7809

• 询问 \(l\) 到 \(r\) 区间的最长上升子序列的长度。

显然答案只可能为 \(1/2\)，当且仅当 \([l, r]\) 中存在 \(\texttt{01}\) 子序列时答案为 \(2\)。
维护一个前缀 \(\texttt{01}\) 子序列计数数组 \(p\)，当 \(p_l = p_r\) 时说明 \([l, r]\) 中并不存在 \(\texttt{01}\) 子序列，反之则存在。

• 询问 \(l\) 到 \(r\) 区间的最长不下降子序列的长度。

显然是一个形如 \(\texttt{00...011...1}\) 的子序列。
维护一个前缀 \(0\) 计数数组 \(s\) 和后缀 \(1\) 计数数组 \(t\)，对于每个位置 \(i \in [l, r]\) 枚举其作为最长不下降子序列的转折点，故答案显然为：

\[\max_{i = l}^{r}(s_i + t_i) - s_{l - 1} - t_{r + 1}. \]

前面这个最大值显然可以使用 ST 表维护。

8.7

P3378

优先队列板子。

P1177

堆排序板子。
懒得打字的话用 \(\texttt{std::sort}\) 得了。

P2085

显然给出的任意 \(F_i(x)\) 在 \((0, +\infty)\) 内都单调递增。
故考虑维护一个大根堆，对每个函数 \(F_i\) 枚举正整数 \(x \in [1, m]\)，计算函数值，若其值小于当前堆顶则入队，若函数值大于当前堆顶，则由单调性得对任意 \(x_1 > x\) 均有 \(F_i(x_1) > F_i(x)\)，对前 \(m\) 小值均无贡献，此时直接 \(\texttt{break}\) 掉。
最后倒序输出堆中的值即可。

P1878

小根堆维护合法舞伴序列。当然要重载运算符，技术值相差小的优先。
现在有一个问题，就是当序列中间的一对舞伴出列之后剩下的部分怎么处理。
即在序列 \(\texttt{\{..., A, B, C, D, ...\}}\) 中，如果 \(\texttt{(B, C)}\) 出列，剩下的 \(\texttt{\{..., A\}}\) 与 \(\texttt{\{D, ...\}}\) 如何合并。
考虑使用双向链表，令 \(l[i], r[i]\) 分别表示下标 \(i\) 元素的前驱和后继。
当序列中连续的下标 \((x, y)\) 出列时，更新如下：

\[\begin{aligned} r[l[x]] \gets r[y], \\ l[r[y]] \gets l[x]. \end{aligned} \]

初始值自然是 \(l[i] = i - 1\)，\(r[i] = i + 1\)。

完整实现不难。

P1168

对顶堆。
建立一个大根堆、一个小根堆。
大根堆中的元素数 \(a\)、小根堆中的元素数 \(b\) 应当总满足：

\[\begin{cases} a = b & \text{if } 2 \mid (a + b) \\ a + 1 = b & \text{otherwise} \end{cases} . \]

同时，大根堆中的任意元素应当总不大于小根堆中的任意元素（等价于大根堆堆顶应当总不大于小根堆堆顶）。

说人话就是，对于前 \(n\) 个元素，小根堆维护这些数中前 \(\boldsymbol{\lceil n / 2 \rceil}\) 大的元素。
故当 \(2 \nmid n\) 时，小根堆堆顶是前 \(n\) 个数的中位数。

考虑如何维护这两个堆。
假设现在第 \(n\) 个数准备入队。

若 \(2 \nmid n\)，即前面已经入队的元素个数为偶数，那么我们需要使小根堆中的元素数量更多。同时考虑到「大根堆堆顶必须不大于小根堆堆顶」的限制，我们将准备入队的数与大根堆堆顶比较。
如果它大于大根堆堆顶，那么直接把它加入小根堆中是满足条件的；否则，如果将它加入小根堆就会破坏上述限制。
解决方式就是，先将大根堆堆顶弹出并加入小根堆中，再把准备入队的数加入大根堆，这时就会发现原来的限制依然能够满足。

同样地，若 \(2 \mid n\)，那么把准备入队的数与小根堆堆顶比较，若它小于小根堆堆顶则直接加入大根堆，否则把小根堆堆顶弹出加入大根堆，再把准备入队的数加入小根堆。

以上反映了对顶堆维护的基本思路模式。

P1801

也是对顶堆。

大根堆维护前 \(i\) 小值。

对于 \(\texttt{GET}\) 操作，因为是先 \(i \gets i + 1\) 再求第 \(i\) 小，所以相当于求当时的第 \(i + 1\) 小，故输出小根堆堆顶即可。
在此之后就把小根堆堆顶弹出，加入大根堆（因为 \(i\) 要 \(+1\)）。
对于 \(\texttt{ADD}\) 操作，将准备入队的数与大根堆堆顶比较，若大于大根堆堆顶则加入小根堆，否则将大根堆堆顶弹出加入小根堆，而准备入队的数则加入大根堆。

这里总结一下判断加入数时应当如何操作的思路：

• 首先一定要确定对顶堆维护的是什么（一般而言都是与区间第 \(\boldsymbol k\) 大相关的）。
• 接下来，要明确当下的操作是需要大根堆或小根堆中的哪一个增加元素（记 \(A\) 为需要加入数的堆，\(B\) 为另一个，需要加入的数为 \(x\)）。
• 明确之后，自然就是将 \(x\) 与 \(B\) 的堆顶相比较，如果直接把 \(x\) 加入 \(A\) 中并不会破坏对顶堆的限制，那么直接加入就行；否则需要把 \(B\) 的堆顶弹出加进 \(A\) 中，再把 \(x\) 加到 \(B\) 里。

做多了就能理解得更快了。

P1090

注意到一个贪心策略：每次选择最小的两堆合并。
这实际上的确是正确的，具体证明参见这篇题解。
拿小根堆维护即可，非常简单。

不过这题还有个更神的解法：先对原序列 \(a\) 排序，并另外维护一个序列 \(b\) 存放合并之后的果子堆，每次使用两序列中最小的两个数合并加入 \(b\) 中，同时上述贪心策略也使得 \(b\) 一定是升序的，故每次取数只需要在 \(a, b\) 的序列开头比较即可（也就是将 \(a, b\) 视作队列，队头取数相加添加到 \(b\) 队尾）。
排序只要用计数排序等算法就能够是整体的时间复杂度达到极低的 \(O(n)\)，非常快。

8.9

P16938

题目要求的是有且仅有一次转弯的路径。
注意要特判 \(n = 1 \lor m = 1\) 的情况！

P16392

没什么好说的，贪心 + 二分答案。
在答案的取值范围内，状态只要是连续且单调的，那么就可以考虑进行二分答案。
这题赛时没做出来明显是对贪心和二分答案的极其生疏啊。
多练。

P16939

更没啥好说的了。极其明显的反悔贪心 + 堆优化。
多练吧。

P16937

大模拟。细节有点多。

8.10

B3644

拓扑排序板子。

P1960

也是板子。
当优先队列中同时存在多个可选结点则代表有多种可选拓扑排序序列。

P1113、P4017、P6145

拓扑排序 + 递推。注意细节注意细节注意细节。

P4089

拓扑排序，之后统计入度仍不为 \(0\) 的结点数量即为答案。

P3366、P2121、P2847、P1194、P1396、P1991、P1265

MST 板子以及各种小变式。做多一点就很熟练了。

P1340

增量 MST（Incremental MST）。
题意比较明显。
考虑在已经生成了 MST 的情况下加边。
假设把这条边加进来，这时 MST 上会形成一个环。遍历这条环，把环上边权最大的边飞出，就能构出新的 MST。
大致是这样的思路。
当然这题做法还有很多，例如每次加边都把新 MST 取边集合更新为原 MST + 加边，跑 \(W\) 遍 Kruskal，复杂度也能较暴力 Kruskal 有所优化；或者从最后一次加边开始倒着做，每次进行删边；等等。

P3073

瓶颈生成树（Bottleneck Spanning Tree, BST）的小变式。
注意实现细节。
另外有个性质：BST 等价于 MST。

8.11

P4779

重温堆优化 Dijkstra 板子。

P6175

考虑使用 Floyd 求全源最短路。
此后我们考虑如何求最小环。

• 在 Floyd 后再 \(O(n^3)\) 遍历一遍，如果 \(i, j, k\) 三个点互不相同就记录答案。
  这种方法并不可行。考虑 \(k\) 恰好在 \(i\) 与 \(j\) 之间的最短路上的情况，此时这三个点无法形成环。

• 那在遍历的时候额外特判一个 \(\text{dis}_{i, k} + \text{dis}_{k, j} \neq \text{dis}_{i, j}\) 不就好了？
  也不可行。因为有可能虽然 \(k\) 不在所求出的 \(i\) 与 \(j\) 之间的最短路上，但 \(\text{dis}_{i, k} + \text{dis}_{k, j}\) 与 \(\text{dis}_{i, j}\) 也相等。说人话就是可能存在另外一条 \(i\) 到 \(j\) 的路径长度与求出的最短路长度相同。

所以正确的解法应该是，在 Floyd 的过程中顺带进行计算。
在 Floyd 的过程中所转移得到的最短路是只途径结点 \(\boldsymbol{1 \sim k - 1}\) 的最短路，所以这种情况下我们就能保证 \(k\) 不在当前的最短路上，这时我们当前的环总长就是 \(\text{dis}_{i, j} + e(i, k) + e(j, k)\)。其中 \(e(u, v)\) 表示边 \((u, v)\) 的长度。

P5764

跑六遍 Dijkstra，全排列求最小值。不难，注意细节。

P2296

当然要找出所有符合题目中条件 \(1\) 的点了。
从每个点开始都遍历一遍判断无疑是愚蠢的，等着 T 飞吧。
我们需要用仅一次遍历来找出所有可用点。
考虑建反图，从 \(t\) 点开始 DFS，每遍历到一个点就把它在反图中的入度（即原图中的出度）\(-1\)，若 DFS 后一个点的这入度被减到 \(0\) 了，就说明从 \(t\) 出发能够遍历到原图中该点的所有出边，也意味着原图中该点满足条件 \(1\)。
最后只使用原图中满足条件 \(1\) 的点来跑 BFS 求最短路就可以了。

P3371

SPFA 板子。

P3385

SPFA 求负环板子。
审题！审题！审题！
多测要清空！多测要清空！多测要清空！