分类： 思维

codeforces 1452E Two Editorials

题目链接：https://codeforces.com/problemset/problem/1452/E

题意：一次比赛中 2 个dalao来讲题，总共有 $m$ 个选手来听讲，题目总数为 $n$ ，编号从 $1$ 开始到 $n$ 。每个dalao都只会选择连续的 $k$ 个题目进行讲解，两个人可以交叉。而每一个听讲的人都只会选择听一个dalao的讲题，这是由哪个dalao讲的题目中覆盖的他感兴趣的题目数量较多决定的，第 $i$ 个人想听的题目范围是 $[l_i,r_i]$ . 问两个大佬怎么选可以使得两个人所获得的得分加一块最多，其中得分是他们讲的每个题目收听的人数。

数据范围：$1 \leq n, m \leq 2000,1 \leq k \leq n$， $1 \leq l_{i} \leq r_{i} \leq n$

输出：两个人采取某种讲题方案后加一块能获得的最大分数

题解：

把每个听讲的人看成一条线段，问题可以抽象成在数轴上找到两个长度为k的区间使得上述分数最大。从数据范围来看，可以 $O(n^2)$ 枚举两个人讲题的起点，之后如果能使用滑动窗口动态维护， $O(1)$ 更新答案这题就做完了。那么自然可以想到枚举第一个人讲题的范围之后，第二个人的范围在遍历的过程中动态维护。如果我们使用前缀和来做的话，是可以 O1 得到两个人各自的和的，但是题目要求两个人之间如果有均覆盖到的听讲者，那么只有覆盖的较多的讲题人才有得分。这是一个对每个听众来说取max的操作，但是我们要在数轴的维度来说要做到 O1 动态维护就是比较难的。我们假设第一个人对于自己内部的的得分和为sum1.第二个人的得分为sum2.先不考虑取max的情况，此时sum1和sum2都可以通过简单的积分前缀和得到。我们考虑把这个max操作转化成几个不同数组的差分和求和操作。简单的画一下第二个样例，就可以意识到当枚举到第一个人的讲课区间 [i,iend] 的时候，听众对应的线段可以分为三类：（1）在iend之前结束的；（2）在iend之后开始的；（3）在iend之前开始，在iend之后结束的。
继续阅读“[差分][前缀和][细节] codeforces 1452E Two Editorials”

题目链接

题意：

给定一个长度为 $n$ 的序列 $a$ ，$n \le 10^6$ ，每个数字 $a_i$ ，满足 $0 \le a_i \le 10^6$ .

可以对这个序列进行一种操作，把第 $i$ 个数字中的一份移动到 $i-1$ 或者 $i+1$ .即操作过后 $i$ 处变为 $a_i-1 , a_{i+1}$ 或者 $a_{i-1}$变为 原来的数字+1.

问最少需要多少次操作使得存在某个数字 $k>1$ 满足所有的 $a_i$ 都可以被k整除（$0$可以被任何数整除），操作过程要满足所有的 $0\le a_i$ 。

题解：

考虑操作完成之后的结果，如果每一个数字都能被 $k$ 整除，那么显然 $S = \sum_{i=1}^{n} a_i$ 也可以被k整除。所以 $k$ 一定是 $S$ 的一个因数。

然后显然 $k$ 为合数时的情况，要么被 $k=其质因子$ 的情况包括，要么就劣于这种情况。所以我们只需要考虑 $k$ 为质数的情况，也就是 $S$ 的所有质因子。

由 $S$ 最大为 $10^{12}$ 可知，其质因子最多应该只有$10-20$种，而且分解出质因子可以用时间复杂度 $O(\sqrt{n})$ 的算法，也就是约 $10^6$ 。

继续阅读“[思维][贪心][贡献拆分] codeforces 1255 E2 Send Boxes to Alice (Hard Version)”