codeforces吧 关注：2,004贴子：2,091
但是打div34基本都是掉分
先来三题。
——————
A：用时 03:51
（个人认为的）tag：几何
题目描述：给你矩形的四个端点坐标（不一定按顺序），求出矩形的面积。
思路：横坐标和纵坐标各有两种可能，不难发现矩形面积就等于 abs(两种横坐标之差) * abs(两种纵坐标之差)。
代码：
——————
B：用时 09:10
tag：贪心
题目描述：给你两个长度相同的 01 串 s,t ，每次操作你可以翻转 s 的某个位，或将某个 1 移动到某个 0 的位置上，问最少需要多少次操作才能将 s 变成 t。
思路：对于 s_i 和 t_i，只存在四种情况，1 - 0, 0 - 1, 1 - 1, 0 - 0。注意到，如果它们已经匹配，就没有必要修改或移动，否则会增加不必要的操作次数。对于 1 - 0 和 0 - 1 这两种不匹配的情况，一次移动操作可以抵消一对 1 - 0 和 0 - 1，剩余无法抵消的部分只能使用翻转来消除，因此答案就是 1 - 0 和 0 - 1 各自的出现次数中最大的那个。
代码：
——————
C：用时 11:37
tag：贪心
题目描述：给你一系列位于数轴正半轴上的点，初始位于 x = 0，能量为 f，现在你要从左到右依次访问这些点。假设你打算从 x = x0 走到 x = x1，此时有两种选择：1）消耗 a / 单位距离的能量，即 a * (x1 - x0)；2）消耗能量 b 直接传送到目的地。如果在某个时刻 f <= 0，则失败。问能否访问所有的点。
思路：贪心地选择能量消耗最少的方式进行移动。
代码：
——————
D：用时 N/A（想了 25 分钟无果，遂参考题解）
tag：贪心、构造
题目描述：给你两个数组 a 和 b，长度分别为 n 和 m，保证 n <= m。现在你需要从 b 中选出 n 个元素构成新的数组 c，使得 sigma |a_i - c_i| 最大，然后输出这个最大值。
思路：考虑暴力做法，首先选出 n 个数，有 C(m, n) 种可能，然后对这 n 个数进行随机重排，又有 n! 种可能，在这些可能性之中找最大值，时间复杂度为 O(nm!/(m-n)!)，对于 m = n = 2e5 的极限情况，如果从现在开始计算，那么算到银河系和仙女座星系碰撞的时候都不一定能算完。
因此，我们必须观察目标 sigma |a_i - c_i| 的性质，思考怎样构造 c 才能得到尽可能大的结果，排除大部分的无效构造方案，缩小搜索的范围，进而做到时间复杂度的优化。
这里需要一个关键的 observation：
然而，对于这么重要的东西，题解居然就用一句话带过了，仿佛在暗示这是个 trivial 的结论，一眼便知……但我看了 25 分钟都没看出来。。。
这里我将给出较为严格的证明。
假设我们现在构造了数组 c，那么我们可以将数组 c 的元素分为两类，A 类满足 c_i >= a_i， B 类满足 c_i < a_i。
以 A 类为例，此时 |a_i - c_i| 就等于 c_i - a_i，因此 A 类对于当前答案的贡献就是 sigma c_i - sigma a_i，和 a_i 与 c_i 的配对关系无关。
假设 A 类有 k 个元素，不妨将 A 类中所有的元素都替换为数组 b 中最大的元素，则 A 类对于答案的贡献必定是不减的。
同理，将 B 类中所有的元素都替换为数组 b 中最小的元素，则 B 类对于答案的贡献也必定是不减的。
所以，在所有的数组 c 的构造方案中，相对更优的方案是选择最大的 k 个数和最小的 n - k 个数，这里 k ∈ [0, n]。
还有一个问题没有解决，就是如何安排这 n 个数的顺序，使结果尽可能大。
结论是用这 n 个数中的最大的数来匹配数组 a 中最小的数，这可以用数学归纳法证明（好吧其实是暂时我证不出来，但可以说明 n = 2 时是对的。之后我一定把它证出来，否则这道题就不算完全解决，但目前需要先搁置一下，因为还有别的事情要做）
这就是为什么我们需要对数组 a 升序排序，而对数组 b 降序排序。
代码：
昨晚睡觉的时候一直在想 ① 的证明。最终得出的解法是：数学归纳法。
这里就不写规范的证明过程了，首先 n = 1 时不存在排序的问题，不妨以 n = 2 作为 base，简单的分类讨论就可以说明结论成立，然后假设 n = k 时结论成立，当 n = k + 1 时，我们可以从两个数组中任选一对元素 (x, y) 作为 “新增” 的元素，然后将剩下的 n 对元素分别升序、降序排序，两两配对，此时就是 n = k 的情况，结论成立。接下来，考虑将 (x, y) 插入到这 n 对元素中去，如果插入之后不满足两个数组分别升序、降序排序的条件，记 x 对应 x1，y 对应 y1，根据 n = 2 时的情况，我们一定可以通过交换 (x, y) 或者 (x1, y1），使它们重新满足条件，且此时答案是不减的。反过来，对于 n = k + 1 且两个数组分别升序、降序排序的情况，如果我们任取一对元素进行交换，则答案是不增的，因此待证明的结论成立。
综上，……，Q.E.D.
这里就不写规范的证明过程了，首先 n = 1 时不存在排序的问题，不妨以 n = 2 作为 base，简单的分类讨论就可以说明结论成立，然后假设 n = k 时结论成立，当 n = k + 1 时，我们可以从两个数组中任选一对元素 (x, y) 作为 “新增” 的元素，然后将剩下的 n 对元素分别升序、降序排序，两两配对，此时就是 n = k 的情况，结论成立。接下来，考虑将 (x, y) 插入到这 n 对元素中去，如果插入之后不满足两个数组分别升序、降序排序的条件，记 x 对应 x1，y 对应 y1，根据 n = 2 时的情况，我们一定可以通过交换 (x, y) 或者 (x1, y1），使它们重新满足条件，且此时答案是不减的。反过来，对于 n = k + 1 且两个数组分别升序、降序排序的情况，如果我们任取一对元素进行交换，则答案是不增的，因此待证明的结论成立。
综上，……，Q.E.D.
A：用时 3 分钟
tag: 暴力
题目描述：给你一个正整数 n，每次操作你可以将一个数变成两个相等的数，其值等于 n / 4 （向下取整），若某个数小于 4 则不可操作，问最多可以产生多少个数。
思路：想象一棵存储整数节点的树，根节点为 n，每次操作会产生两个相等节点。显然这棵树始终是完全二叉树，而当前数的个数就等于同一层所有节点的个数，因此我们只要不断地将 n 除以 4，同时维护节点个数，直到叶子节点为止。
代码：
——————
B：用时 22 分钟
tag: 数学（数论）
题目描述：给你一个数 dd...dddd (n! 个 d），判断它能否被 1、3、5、7 和 9 整除。
思路：
判断 1 - 任何数都可以被 1 整除。
判断 5 - 只有 d = 5 才可以被整除。
判断 3 - 一个数可以被 3 整除，当且仅当其数位之和可以被 3 整除，而这里数位之和等于 n! * d，所以等价于判断 n! 和 d 中的 3 的因子的个数，不难得到整除条件为 n >= 3 或者 3 | d。
这里有个小问题，如何证明 “一个数可以被 3 整除，当且仅当其数位之和可以被 3 整除”？
我们可以把任何整数写成 a_0 + 10a_1 + 100a_2 + ... + 10^na_n 的形式，并将其变换为 (a_0 + a_1 + a_2 + ... + a_n) + 3^2 * (a_1 + a_2 + ... + a_n)，因为右边的部分必定被 3 整除，所以任何整数模 3 的结果就等于其数位之和模 3 的结果，……，证毕。
判断 9 - 一个数可以被 9 整除，当且仅当其数位之和可以被 9 整除，证明方式同上，不难得到整除条件为 n >= 6 或者 3 <= n < 6 且 d % 3 == 0 或者 n < 3 且 d = 9
判断 7 - 这是本题的难点。首先，我们把 dd..ddd（n! 个 d） 写成 d * 111..11（n! 个 1），所以 d = 7 时可以被 7 整除。如果 d != 7 呢？需要判断 111..11（n! 个 1）是否能被 7 整除。
考虑构造 111..11 的过程：0 -> 1 -> 11 -> 111 -> ... -> 111111，递推方程为:
x <- (x * 10 + 1)
因为我们关注的是模 7 的结果，所以给两边加上取模：
x mod 7 <- (x * 10 + 1) mod 7
不妨设 x mod 7 = r，下一个余数为 r1，则上式等价于：
r1 <- ((r * 3) mod 7 + 1) mod 7
利用这个递推式，我们可以写出余数的前几项：
0 -> 1 -> 4 -> 6 -> 5 -> 2 -> 0 -> 1 -> 4 -> 6 -> ...
发现周期！可知整除条件为 6 | n!，也就是 n >= 3。
为什么会有周期？如何证明周期存在？如果存在，那么周期是多少？
这些问题的答案正是线性同余发生器（LCG）的原理，具体可参照 Hull & Dobell 的论文。
即便你不知道什么是 LCG，你也大概率用过它 —— C语言的 rand() 函数就是一个 LCG。
代码：
——————
C：用时 N/A （一个小时没做出来）
tag:（优雅的）暴力
题目描述：给你一个整数数组，其中最多只有一个元素不是 1 或 -1，按升序输出所有子数组求和的结果（重复的值只需要输出一次）。空数组也算子数组，其求和结果为 0.
思路：显然我们并不能暴力枚举所有的子数组再求和，因为这样做的时间复杂度是 O(n^2）。换句话说，这道题肯定存在某个特殊条件，让我们不需要暴力枚举这么多的子数组。这个特殊条件就是元素的值域。
因为最多只有一个元素不是 1 或 -1，不妨先考虑所有元素都是 1 或 -1 的情况。
然后我想，这样一来子数组的和的取值范围就在 -n 到 n 了，而 n ~ 2e5，因此可以直接枚举 -n 到 n，再检查这个值是否存在……但无论怎么想，我也找不到快速判断存在性的方法。整个算法最终还是会不可避免地变成 O(n^2)。于是就卡在了这里。
遂看题解，只看了第一段，就恍然大悟。
究竟该如何利用 “1”？
“1” 代表 “连续变化”。
对于一个只由 1、-1 组成的数组，如果我们固定左端点，枚举右端点，计算出所有的子数组和，记最小的和为 m，最大的和为 M，则所有的子数组和一定能取到 m, m+1, m+2, ..., M 的每一个数，形成了线段 [m, M]，且 0 一定位于线段内（空数组）。
想要计算出所有可能的子数组和，我们就需要枚举所有的左端点（或右端点），然后找到最小的子数组和以及最大的子数组和，得到 n 个线段，最后将这些线段合并，就得到了子数组和覆盖的范围。因为这些线段一定包含 0，所以它们都是相交的，只需要简单的 min max 就能处理合并的逻辑。
接下来考虑不是 1 或 -1 的 “特殊元素”。对于包含特殊元素的子数组，如果我们 “去掉” 这个特殊元素，则其子数组和的变化规律就如上述分析所述。现在加上这个特殊元素 x，可以理解为整体加上了 x 的偏移量，所以处理的方式和前面类似。
代码：
——————
B 和 C 都非常有趣，从中学到了很多。
tag: 暴力
题目描述：给你一个正整数 n，每次操作你可以将一个数变成两个相等的数，其值等于 n / 4 （向下取整），若某个数小于 4 则不可操作，问最多可以产生多少个数。
思路：想象一棵存储整数节点的树，根节点为 n，每次操作会产生两个相等节点。显然这棵树始终是完全二叉树，而当前数的个数就等于同一层所有节点的个数，因此我们只要不断地将 n 除以 4，同时维护节点个数，直到叶子节点为止。
代码：
——————
B：用时 22 分钟
tag: 数学（数论）
题目描述：给你一个数 dd...dddd (n! 个 d），判断它能否被 1、3、5、7 和 9 整除。
思路：
判断 1 - 任何数都可以被 1 整除。
判断 5 - 只有 d = 5 才可以被整除。
判断 3 - 一个数可以被 3 整除，当且仅当其数位之和可以被 3 整除，而这里数位之和等于 n! * d，所以等价于判断 n! 和 d 中的 3 的因子的个数，不难得到整除条件为 n >= 3 或者 3 | d。
这里有个小问题，如何证明 “一个数可以被 3 整除，当且仅当其数位之和可以被 3 整除”？
我们可以把任何整数写成 a_0 + 10a_1 + 100a_2 + ... + 10^na_n 的形式，并将其变换为 (a_0 + a_1 + a_2 + ... + a_n) + 3^2 * (a_1 + a_2 + ... + a_n)，因为右边的部分必定被 3 整除，所以任何整数模 3 的结果就等于其数位之和模 3 的结果，……，证毕。
判断 9 - 一个数可以被 9 整除，当且仅当其数位之和可以被 9 整除，证明方式同上，不难得到整除条件为 n >= 6 或者 3 <= n < 6 且 d % 3 == 0 或者 n < 3 且 d = 9
判断 7 - 这是本题的难点。首先，我们把 dd..ddd（n! 个 d） 写成 d * 111..11（n! 个 1），所以 d = 7 时可以被 7 整除。如果 d != 7 呢？需要判断 111..11（n! 个 1）是否能被 7 整除。
考虑构造 111..11 的过程：0 -> 1 -> 11 -> 111 -> ... -> 111111，递推方程为:
x <- (x * 10 + 1)
因为我们关注的是模 7 的结果，所以给两边加上取模：
x mod 7 <- (x * 10 + 1) mod 7
不妨设 x mod 7 = r，下一个余数为 r1，则上式等价于：
r1 <- ((r * 3) mod 7 + 1) mod 7
利用这个递推式，我们可以写出余数的前几项：
0 -> 1 -> 4 -> 6 -> 5 -> 2 -> 0 -> 1 -> 4 -> 6 -> ...
发现周期！可知整除条件为 6 | n!，也就是 n >= 3。
为什么会有周期？如何证明周期存在？如果存在，那么周期是多少？
这些问题的答案正是线性同余发生器（LCG）的原理，具体可参照 Hull & Dobell 的论文。
即便你不知道什么是 LCG，你也大概率用过它 —— C语言的 rand() 函数就是一个 LCG。
代码：
——————
C：用时 N/A （一个小时没做出来）
tag:（优雅的）暴力
题目描述：给你一个整数数组，其中最多只有一个元素不是 1 或 -1，按升序输出所有子数组求和的结果（重复的值只需要输出一次）。空数组也算子数组，其求和结果为 0.
思路：显然我们并不能暴力枚举所有的子数组再求和，因为这样做的时间复杂度是 O(n^2）。换句话说，这道题肯定存在某个特殊条件，让我们不需要暴力枚举这么多的子数组。这个特殊条件就是元素的值域。
因为最多只有一个元素不是 1 或 -1，不妨先考虑所有元素都是 1 或 -1 的情况。
然后我想，这样一来子数组的和的取值范围就在 -n 到 n 了，而 n ~ 2e5，因此可以直接枚举 -n 到 n，再检查这个值是否存在……但无论怎么想，我也找不到快速判断存在性的方法。整个算法最终还是会不可避免地变成 O(n^2)。于是就卡在了这里。
遂看题解，只看了第一段，就恍然大悟。
究竟该如何利用 “1”？
“1” 代表 “连续变化”。
对于一个只由 1、-1 组成的数组，如果我们固定左端点，枚举右端点，计算出所有的子数组和，记最小的和为 m，最大的和为 M，则所有的子数组和一定能取到 m, m+1, m+2, ..., M 的每一个数，形成了线段 [m, M]，且 0 一定位于线段内（空数组）。
想要计算出所有可能的子数组和，我们就需要枚举所有的左端点（或右端点），然后找到最小的子数组和以及最大的子数组和，得到 n 个线段，最后将这些线段合并，就得到了子数组和覆盖的范围。因为这些线段一定包含 0，所以它们都是相交的，只需要简单的 min max 就能处理合并的逻辑。
接下来考虑不是 1 或 -1 的 “特殊元素”。对于包含特殊元素的子数组，如果我们 “去掉” 这个特殊元素，则其子数组和的变化规律就如上述分析所述。现在加上这个特殊元素 x，可以理解为整体加上了 x 的偏移量，所以处理的方式和前面类似。
代码：
——————
B 和 C 都非常有趣，从中学到了很多。
