Med-
https://codeforces.com/contest/2064/problem/C 题目大意 给出 $n$ 长的不含 $0$ 的数组 $a$。每次可以选择当前一个正数 $a_i$ 将其加到答案，并将数组的 $i$ 结束的前缀删掉，或者选择某个负数 $a_i$ 将 $- a_i$ 加到答案，并将 $i$ 开始的后缀删掉。问可以得到的最大答案是多少。 $1 \le n \le
…
https://codeforces.com/contest/2064/problem/D 题目大意 给出一个 $n$ 长的数组 $a$，和 $q$ 个独立询问（每次询问结束恢复 $a$）。对于某个询问，给出 $x$，然后如果 $x$ 不小于 $a$ 最后的元素 $a_{last}$ 则把 $x$ 变为 $x \ xor a_{last}$ 并删掉 $a_{last}$，问这个操作能进行几次
…
https://codeforces.com/contest/1107/problem/C 题目大意 给出 $n$ 长的小写字符的串 $S$ 和数组 $a$。给出某个 $k$，需要删掉字符串中的某些字符，使得最终串连续的相同字符个数不会超过 $k$。问最后保留下的字符的下标对应的 $a_i$ 的和最大是多少。 $1 \le k \le n \le 2 \times
…
https://codeforces.com/contest/1107/problem/D 题目大意 给出一个 $n \times n$ 的 $01$ 矩阵 $A$。规定 $B$ 为 $A$ 的一个 $x$ 压缩矩阵，如果 $x | n$ 以及 $A[i][j] = B[\lceil \frac{i}{x} \rceil][\lceil \frac{j}{x} \rceil]$（$1$-indexed）。 $4 \le n \le 5200$，且 $4 | n$。 $A$ 按照每行每 $4$ 位压缩成一个十六
…
https://codeforces.com/contest/571/problem/B 题目大意 给出 $n$ 长的数组 $a$，及某数 $k$，可以任意调整 $a$ 中元素位置，需要最小化 $$ \sum_{i = 1}^{n - k} |a[i] - a[i + k]| $$ 。 问这个最小值是多少。 $2 \le n \le 3 \times 10^5$。$1 \le \min(5000, n - 1)$。$-10^9 \le a[i] \le 10^9$
…
https://codeforces.com/contest/520/problem/D 题目大意 给出 $n$ 个立方体（其实可能叫正方形更好，因为其实只需要考虑 $2$ 维），考虑 $OX$ 是地面，$OY$ 是向上的方向。每个立方体用 $(x, y)$ 表示其位置。定义某个立方体是稳定的当且仅当： 立方体在地面上（$x = 0$） 其
…
https://codeforces.com/contest/2065/problem/H 题目大意 给出一个 $01$ 字符串 $s$ 和 $q$ 次询问，每次询问将 $v_i$ 位置的字符翻转（询问不独立），之后询问这个串由下述函数算出的值是多少。 $f(S)$ 表示 $S$ 由多少个连续的相同字符的段，比如 $00110001$ 有 $00, 11, 000, 1$ 这样的 $4$ 段。 $g(S)$ 表示对于 $S$ 的
…
https://codeforces.com/contest/1389/problem/C 题目大意 给出字符串 $S$ 问最少删掉其中多少个字符，可以使得它向左循环移动一位和向右循环移动一位的串相同。 $2 \le |S| \le 2 \times 10^5$ 简要题解 观察： $2$ 长的串一定行 同一个字符的串一定行 两种字符交替的偶数长的串一定行 其实这
…
https://codeforces.com/contest/1389/problem/B 题目大意 给出 $n$ 长的数组 $a$，可以用下述操作走 $k$ 步，其中最多 $z$ 步向左，问最大可以取到的权值。 每次操作可以进行两种中的一种： 向右走。现在在 $x$ 且 $x < n$，权值增加 $a[x + 1]$ 之后走到 $x + 1$。 向左走。现在在 $x$
…
https://codeforces.com/contest/1238/problem/D 题目大意 给出 $n$ 长的只包含 ‘AB’ 的字符串 $S$。 定义一个字符串是好的：字符串中所有字符都可以是某个（不同字符不用是同一个）长度至少为 $2$ 的回文串的一部分。 问 $S$ 有多少个好的子串。 $|S| \le 3 \times 10^5$。 简要题解 观
…
https://codeforces.com/contest/2059/problem/C 题目大意 给出 $n$ 个 $n$ 长的数组 $a_i$。进行如下操作 $n$ 轮，在第 $i$ 轮，选择某个 $j$，使得 $a_{j,k} = 0 \ (k \le i)$。即把某选择的行的开始一段小于 $i$ 的元素刷成 $0$。 $n$ 轮进行完之后设 $b_i = \sum a_{i, j}$，则问可以任选
…
https://codeforces.com/contest/1156/problem/C 题目大意 给出 $n$ 个数的数组 $x$ 以及一个数字 $z$，要求找出 $x$ 中尽量多的不相交的对子，使得每对满足 $|x_i - x_j| \ge z$。 $2 \le n \le 2 \times 10^5$。$1 \le z, x_i \le 10^9$。 简要题解 显然答案是可以二分的。下面就来思考如
…
https://codeforces.com/contest/1156/problem/D 题目大意 给出一棵 $n$ 个点的树，边上有 $0$ 或 $1$ 的权值。问有多少个 $u$ 到 $v$ 的简单路径（$u \neq v$）满足该路径通过任何边权为 $1$ 的边后不再经过边权为 $0$ 的边。 $2 \le n \le 2 \times 10^5$。 简要题解 如果我们固定了某个根，让
…
https://codeforces.com/contest/1156/problem/B 题目大意 给出小写字母组成的字符串 $S$，要求重排字符串使得相邻位置，不能是字典序相邻的字符。（‘a’ 与 ‘z’ 不相邻）。有解时输出任意合法串，否则输出 ‘No answer’。
…
https://codeforces.com/contest/903/problem/F 题目大意 给出 $4 \times n$ 的矩阵 $f$，其中有 ‘.’ 和 ‘*'。可以用 $a_i$ 点花费将 $i \times i$ 的某个子矩阵中的 ‘*’ 全部变为 ‘.'，问将整个矩阵都变为 ‘.’ 的最小花费。 $4 \le n \le 1000$。 $1 \le a_i \le 1000$ 固定给
…
https://codeforces.com/contest/1487/problem/E 题目大意 给出 $4$ 个数组分别长 $n_i$。要求各从中选取一个元素，使得选出的和最小，问这个最小和是多少。有一些第 $1, 2$ 数组之间，$2, 3$ 数组 $3, 4$ 数组之间的下标的组是互斥的，各有 $m_i$ 个，互斥的下标不能同时选。
…
https://codeforces.com/contest/903/problem/E 题目大意 有某未知长为 $n$ 的串 $s$ 和 $k$ 个由串 $s$ 通过交换两个不同下标字符构成的串 $s_i$。其中 $k \le 2500, nk \le 5000$。输入未必合法。问是否有这样的串 $s$，如果没有输出 $-1$，否则给出任意合法的串。 简要题
…
https://codeforces.com/contest/903/problem/D 题目大意 给出 $n \ (\le 2 \times 10^5)$ 长的数组 $a$ 其中 $1 \le a_i \le 10^9$。定义函数 $d$ 如下 $$ d(x, y) = \left\{ \begin{align} y - x, \quad & |x - y| > 1, \\ 0, \quad & |x - y| \le 1 \end{align} \right. $$ 求 $$ \sum_i \sum_{j = i}^{n} d(a[i], a[j]) $$ 简要题解 注意到其实特殊的只有 $a[i] = a[j] \pm 1$ （等于虽然是 case
…
https://codeforces.com/contest/985/problem/D 题目大意 输出最小的序列 $h$ 的长度 $l$，满足 $h_i \ge 0$ $h_0 \le H$ $h_{l - 1} = 1$ $\sum h = n$ $|h_i - h_{i - 1}| \le 1$ 其中 $1 \le n, H \le 10^{18}$。 简要题解 因为我们想要序列尽量短，因此我们想每个 $h_i$ 尽量大。如果没有 $h$ 的限制，会是这
…
https://codeforces.com/contest/985/problem/E 题目大意 给出 $n \ (\le 5 \times 10^5)$ 根铅笔，要求放入 $k \ (1 \le k \le n)$ 个盒子。每只铅笔有一个属性 $a_i \ (1 \le a_i \le 10^9)$。 要求盒子要么为空，要么有至少 $k$ 只铅笔，且在同一盒子中的任意一对 $a_i, a_j$ 满足 $|a_i - a_j| \le d$ 其中 $0 \le d \le
…