题解 CF1537E1 Erase and Extend (Easy Version)
2023-09-13 296 字 2 分钟

题解 CF1537E1 Erase and Extend (Easy Version)

CF1537E1 Erase and Extend (Easy Version)简要题意给你一个字符串，找到该字符串的一个前缀并不断复制，可以删除末尾元素，最终要使得得到的字符串长度为 $k$ 且字典序最小。 策略分析对于此类构造题，我们一般需要运用逆向思维，也就是说我们要从前往后扫而不是从后往前删。为什么这样想呢？我们可以发现，字典序最小当且仅当我们要找的前缀的第 $i$ 位比第 $i \bmod len$ 位的字典序小 ，这样拼接起来才能够使得字典序最小，这个结论是显然的，证明可以使用反证法。 参考代码12345678910111213141516171819202122232425262
最短路径基础总结
2023-09-07 3.8k 字 17 分钟

最短路径基础总结

$\operatorname{Floyd}$（全源最短路）我们定义一个数组 $f_{k,x,y}$ 表示只经过节点 $1$ ~ $k$ 的情况下，$x$ 到 $y$ 的最短路长度，那么显然的，当一个图中节点个数为 $n$ 时，$f_{n,x,y}$ 就是我们所要求的答案。实现 $\operatorname{Floyd}$ 算法需要我们从 $k=0$ 时的情况逐渐递推到 $k=n$。$k=0$ 时，$x$ 和 $y$​ 不相等的情况下不可能通过任何情况联通，而一个点到自己的距离显然为 $0$，所以我们认为：$$\left {\begin{matrix}f_{0,x,
Tarjan 基础用法
2023-09-07 5.9k 字 29 分钟

Tarjan 基础用法

Tarjan⁡\operatorname{Tarjan}Tarjan 求最近公共祖先 前置芝士 最近公共祖先(Lowest Common Ancestor , LCA)：一棵树中两个结点的 公共祖先里面，离根最远的那个被称为最近公共祖先。我们记点集 S={v1,v2,…,vn}S=\{v_1,v_2,\dots,v_n\}S={v1​,v2​,…,vn​} 的最近公共祖先为 LCA⁡(v1,v2,…,vn)\operatorname{LCA}(v_1,v_2,\dots,v_n)LCA(v1​,v2​,…,vn​) 或 LCA⁡(S)\operatorname{LCA}(S)LCA(S)。
题解 洛谷 P2376 [USACO09OCT] Allowance G
2023-09-02 519 字 3 分钟

题解 洛谷 P2376 [USACO09OCT] Allowance G

P2376 [USACO09OCT] Allowance G简要题意给你 $n$ 种面值的货币，其中货币中面值小的货币的面值可以整除面值大的货币的面值，给你每种面值货币的数量。每周都要给贝茜发至少 $c$ 元的工资，问最多能发多少周。 策略分析首先对于面值大于 $c$ 的货币，显然我们每周给出一张就行了，没有其它办法，所以可以直接把它们的数量加在答案中。接下来是对于面值小于 $c$ 的货币，我们先对所有货币按照面值降序排序，每次选取能够选的最大的，然后再用最小的去填补剩下的那一点点价格缝隙，因为我们有小面值货币面值是大面值货币面值因数这个条件，所以最大配最小这种做法一定会产生最小的浪费，从而得
题解 CF1863C MEX Repetition
2023-08-31 838 字 4 分钟

题解 CF1863C MEX Repetition

CF1863C MEX Repetition简要题意给定一个 $n$ 个元素的序列 $a$，其中的元素由小于等于 $n$ 的自然数构成且元素之间两两不同。现在定义一种操作，该操作会将第 $i$ 个位置的元素 $a_i$ 替换为该序列中当前没有的最小自然 数。每一轮操作都会从 $1$ 位置一直替换到 $n$。给定整数 $n,k$ 和序列 $a$，其中 $k$ 表示要进行 $k$ 轮操作，要求输出操作后的序列。 策略分析题目中其实有一个诈骗条件。因为序列中的 $n$ 个元素包含小于等于 $n$ 的自然数且两两相同，所以我们可以发现，如果把原序列增加 $1$ 个元素，那么这个序列就变成了 $0 \s
题解 洛谷 P9118 [春季测试 2023] 幂次
2023-08-29 592 字 3 分钟

题解 洛谷 P9118 [春季测试 2023] 幂次

P9118 [春季测试 2023] 幂次简要题意给定两个参数 $n,k$，问在区间 $[1,n]$ 中有多少正整数 $x$ 满足 $x = a^p$，其中 $p \ge k$。 策略分析前置芝士：区间 $[1,n]$ 中完全平方数有 $\left \lfloor \sqrt{n} \right \rfloor $ 个，这个结论用整除分块很容易就可以证出来。 有了这个结论，我们就已经处理完了这个题中 $k=2$ 的情况了，我们来分析剩下的情况。 当 $k=1$ 时，显然区间内每个数都可以表示为 $a^1$，所以答案就是 $n$。 当 $k \ge 3$ 时，底数为
题解 CF690F1 Tree of Life (easy)
2023-08-29 350 字 2 分钟

题解 CF690F1 Tree of Life (easy)

CF690F1 Tree of Life (easy)简要题意给你一棵树，求树上长度为 $2$ 的路径条数 策略分析我们看下面这张图： 我们发现对于点 $u,v$，$v$ 是与 $u$ 相连的一个点，从 $u$ 出发的长度为 $2$ 的路径条数就等于 $v$ 的度数减去 $1$，因为 $u$ 本身也和 $v$ 相连，所以要把自己减掉。比如说上面这张图中，与 $1$ 距离为 $2$ 的点有 $6,7,8,9,5$ 这 $5$ 个，而 $1$ 的三个子节点的度数分别为 $3,3,2$，分别减去 $1$ 再相加刚好是 $5$。 我们对这整张图统计以后，其实对于每一个点我们都统计了与它距离为 $2$
题解 洛谷 P5686 [CSP-S2019 江西] 和积和
2023-08-28 953 字 5 分钟

题解 洛谷 P5686 [CSP-S2019 江西] 和积和

P5686 [CSP-S2019 江西] 和积和简要题意给定两个 $n$ 个元素的序列 $a,b$，求下面这个式子对 $10^9+7$ 取模的结果：$$\sum_{l=1}^{n}\sum_{r=l}^{n}(\sum_{i=l}^{r}a_i \times \sum_{i=l}^{r}b_i)$$ 策略分析如果直接模拟那么时间复杂度是爆炸级的 $O(n^3)$，显然正常人都不会这么做，正常人会选择可爱的前缀和，所以最后一层括号复杂度变成 $O(1)$，总复杂度 $O(n^2)$，比刚刚好了很多，但依然是过不去的，所以我们考虑对前缀和进行优化。 设 $a
题解 洛谷 P5019 [NOIP2018 提高组] 铺设道路
2023-08-28 391 字 2 分钟

题解 洛谷 P5019 [NOIP2018 提高组] 铺设道路

P5019 [NOIP2018 提高组] 铺设道路本题还有一道姐妹题，两题题意一样，代码也一模一样。 简要题意给你一个序列，每次选取一个区间对这个区间内所有数都减去 $1$，使得区间内至少一个数变成 $0$，重复执行这一过程直到整个序列都为 $0$，求最小操作次数。 策略分析本题可以用贪心在 $O(n)$ 复杂度完成。 操作方法我们可以从头往尾扫，设第 $i$ 个位置的值为 $v_i$，当第 $i$ 个位置的值大于第 $i-1$ 个位置的值时，我们就要给答案加上 $v_{i-1}-v_i$，否则不操作。为了后面能够正常操作，第一次必须将第一个位置的直接减到 $0$。 正确性证明考虑如果 $v_
题解 洛谷 P7960 [NOIP2021] 报数
2023-08-28 429 字 2 分钟

题解 洛谷 P7960 [NOIP2021] 报数

P7960 [NOIP2021] 报数简要题意报数游戏，凡是这个数字十进制表示含有 $7$的数和它的倍数都不能报，给定 $T$ 组询问，每次询问给定一个数 $x$，回答下一个要报的数，若 $x$ 是不能报的数，输出 -1。 策略分析经过良久的思考，我们发现找不到任何可行的 $O(1)$ 性质，所以我们本能的采用暴力。类似线性筛法求素数，我们线性筛求不能报的数的倍数。如果是可以报的数，我们就要记下它该报的下一个数，如果是不可以报的数，我们就要打标记。具体的解释见代码。 参考代码123456789101112131415161718192021222324252627282930313233343