题解 洛谷 P5019 [NOIP2018 提高组] 铺设道路
2023-08-28 346 字 1 分钟

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

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

题解 洛谷 P7960 [NOIP2021] 报数

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

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

P5686 [CSP-S2019 江西] 和积和 简要题意 给定两个 个元素的序列 ，求下面这个式子对 取模的结果： 策略分析 如果直接模拟那么时间复杂度是爆炸级的 ，显然正常人都不会这么做，正常人会选择可爱的前缀和，所以最后一层括号复杂度变成 ，总复杂度 ，比刚刚好了很多，但依然是过不去的，所以我们考虑对前缀和进行优化。 设 的前缀数组为 ， 的前缀数组为 。那么上面的式子显然可以写成： 这样看我们求解还不是很方便，因为存在前面的求和符号，我们不便于对整体的式子进行观察，所以我们用一个 较小的式子看一下，比方说令 ，那么我们按照这个式子带进去展开化简得到：
题解 CF690F1 Tree of Life (easy)
2023-08-29 307 字 1 分钟

题解 CF690F1 Tree of Life (easy)

CF690F1 Tree of Life (easy) 简要题意 给你一棵树，求树上长度为 的路径条数 策略分析 我们看下面这张图： 我们发现对于点 ， 是与 相连的一个点，从 出发的长度为 的路径条数就等于 的度数减去 ，因为 本身也和 相连，所以要把自己减掉。比如说上面这张图中，与 距离为 的点有 这 个，而 的三个子节点的度数分别为 ，分别减去 再相加刚好是 。 我们对这整张图统计以后，其实对于每一个点我们都统计了与它距离为 的点，因为存图时是无向图，所以同一条路径一定计算了两次，累加的答案要减半。 时间复杂度 。 参考代码 123
题解 洛谷 P9118 [春季测试 2023] 幂次
2023-08-29 510 字 2 分钟

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

P9118 [春季测试 2023] 幂次 简要题意 给定两个参数 ，问在区间 中有多少正整数 满足 ，其中 。 策略分析 前置芝士：区间 中完全平方数有 个，这个结论用整除分块很容易就可以证出来。 有了这个结论，我们就已经处理完了这个题中 的情况了，我们来分析剩下的情况。 当 时，显然区间内每个数都可以表示为 ，所以答案就是 。 当 时，底数为 的情况就直接跳过，我们发现现在底数最小是 ，而我们单次计算最大的可能次数就是 ，本题中 ，所以单次最多计算次数为 。所以我们直接暴力枚举就可以了。平方不需要枚举直接用我们的结论，我们从 开始枚举即可，枚举到的
题解 CF1863C MEX Repetition
2023-08-31 770 字 3 分钟

题解 CF1863C MEX Repetition

CF1863C MEX Repetition 简要题意 给定一个 个元素的序列 ，其中的元素由小于等于 的自然数构成且元素之间两两不同。现在定义一种操作，该操作会将第 个位置的元素 替换为该序列中当前没有的最小自然 数。每一轮操作都会从 位置一直替换到 。给定整数 和序列 ，其中 表示要进行 轮操作，要求输出操作后的序列。 策略分析 题目中其实有一个诈骗条件。因为序列中的 个元素包含小于等于 的自然数且两两相同，所以我们可以发现，如果把原序列增加 个元素，那么这个序列就变成了 的一个排列。而我们要替换用的那个数其实就是原序列中没有出现的那个数。我们发现
题解 洛谷 P2376 [USACO09OCT] Allowance G
2023-09-02 483 字 2 分钟

题解 洛谷 P2376 [USACO09OCT] Allowance G

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

题解 CF1537E1 Erase and Extend (Easy Version)

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

题解 CF1537E2 Erase and Extend (Hard Version)

CF1537E2 Erase and Extend (Hard Version) 简要题意 给你一个字符串，找到该字符串的一个前缀并不断复制，可以删除末尾元素，最终要使得得到的字符串长度为 且字典序最小。 策略分析 对于此类构造题，我们一般需要运用逆向思维，也就是说我们要从前往后扫而不是从后往前删。为什么这样想呢？我们可以发现，字典序最小当且仅当我们要找的前缀的第 位比第 位的字典序小，这样拼接起来才能够使得字典序最小，这个结论是显然的，证明可以使用反证法。 参考代码 12345678910111213141516171819202122232425262728#in
题解 CF1204D1 Kirk and a Binary String (easy version)
2023-09-20 707 字 2 分钟

题解 CF1204D1 Kirk and a Binary String (easy version)

CF1204D1 Kirk and a Binary String (easy version) 形式化题意 给你一个长为 的仅包含 和 的串，要求尽可能多地将里面的 改成 使得在得到的新串中，对于 ，两个串的 区间内的最长不降子序列等长。 策略分析 题中给的数据范围完全可以 搜过，但这是 CF 的题，所以我们坚信这一定是一道人类智慧题。所以我们充分发扬人类智慧， 来构造这个题。 对于只有 的串来讲，一个序列想要不降其实只需要满足两个条件： 如果当前位为 ，那么后面无论 都是不降的； 如果当前位为 ，那么后面为 才是不降的。 那么我们