2025-01
https://codeforces.com/contest/985/problem/A 题目大意 给出 $1 \times n$ 的棋盘且 $n \ (\le 100)$ 为偶数。棋盘格为黑白相间的。给出 $n / 2$ 个棋子的位置，问最小的移动步数使得棋子都在同色格子中。棋子不能占据同样的格或相互跨越，给出最小的移动步数。 简要题解 因为无论移动
…
https://codeforces.com/contest/985/problem/B 题目大意 给出 $n$ 个开关和 $m$ 盏灯，和每个开关可以点亮哪些灯的 $n \times m$ 的矩阵。其中 $1 \le n, m \le 2000$。灯被多个开关操作时，如果任意开关可以点亮它，则点亮它。 最初所有灯都是熄灭的。问是否可以去掉某一个开关，
…
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
…
https://codeforces.com/contest/1511/problem/C 题目大意 给出 $n \ (2 \le n \le 3 \times 10^5)$ 长的数组 $a$ 其中 $1 \le a_i \le 50$。给出 $q$ 个询问，每次问最左侧的值为 $v_i$（保证一定在数组中）的元素的下标，询问后将其挪到数组最左侧。 简要题解 注意到其实每个数字只有最左侧
…
https://codeforces.com/contest/1511/problem/D 题目大意 用少于 $k \ (1 \le k \le 26)$ 的字符集，构造一个 $n \ (\le 2 \times 10^5)$ 长的串。使得 $$ \sum_i \sum_{j = i + 1}^{n - 1} [s[i, i + 1] = s[j, j + 1]] $$ 尽量小。 简要题解 假设原串中每种 $2$ 长字符串 $ab$ 出现频率为 $c_{ab}$ 则题目实际上就是要求 $$ \sum c_{ab} * (c_{ab} - 1) /
…
https://codeforces.com/contest/1076/problem/D 题目大意 给出 $n \ (2 \le n \le 3 \times 10 ^ 5)$ 个点 $m \ (n - 1 \le m \le 3 \times 10^5)$ 条边的无向连通图。问最多保留 $k \ (0 \le k \le m)$ 条边时，最多可以使多少点的从 $1$ 点出发的最短路长度不变，输出任意最好方案下保留边的集合。 简要题解 显
…
https://codeforces.com/contest/962/problem/D 题目大意 给出 $n \ (\le 150,000)$ 长的数组 $a$，其中 $1 \le a_i \le 10^9$。执行如下操作，直到不能进行为止： 找到出现两次以上的所有数中最小的数，然后在这个数当前的所有下标里选择最小的两个 $i$ 和 $j$。将 $a[i]$ 删去 $a[j] \gets a[i] +
…
https://codeforces.com/contest/962/problem/C 题目大意 给出数字 $n \ (1 \le n \le 2 \times 10^9)$。问能否从 $n$ 中删掉一些数字得到另一个不含前导零的数字（循序不变），使得新数字是一个平方数。不能输出 $-1$，能则输出最少需要删除的数。 简要题解 这里注意到一
…
https://codeforces.com/contest/962/problem/B 题目大意 给出 $n$ 个座位，以及一个 $n$ 长的序列给出每个座位是否可用。有 $a$ 个程序员，$b$ 个运动员。程序员不能相邻，运动员不能相邻，问最多可以让多少个人坐下。其中 $n, a, b \le 2 \times 10^5, a + b > 0$。 简要题解 首先对于
…
https://codeforces.com/contest/1487/problem/D 题目大意 给出一个上界 $n \ (\le 10^9)$，问有多少正整数三元组 $(a, b, c)$ 满足 $(1 \le a \le b \le c \le n)$， $a^2 + b^2 = c^2$ 且满足 $c = a^2 - b$。 简要题解 由 $a^2 + b^2 = c^2$ 和 $c = a^2 - b$ 都包含 $a^2$ 则我们可以将其约去，易得 $c = b + 1
…
https://codeforces.com/contest/1487/problem/C 题目大意 给出 $n \ (\le 100)$ 只球队，两两各打一场比赛，输记 $0$ 分，平局记 $1$ 分，赢记 $3$ 分。已知在 $n (n - 1) / 2$ 场比赛后，所有球队比分相同，请构造出一个方案，使得平局尽量少。 简要题解 假设有 $w$ 个非平局和 $t$ 个平局则。$
…
https://codeforces.com/contest/2063/problem/E 题目大意 给出一棵 $n \ (\le 3 \times 10^5)$ 个点的树，根为 $1$，边长全部为 $1$。设 $l = lca(u, v)$，定义 $f(u, v)$ 代表，能和 $dist(u, l)$ 与 $dist(v, l)$ 组成非退化的三角形的第三边的整数值个数。求 $$ \sum_{i = 1}^{n - 1}\sum_{j = i + 1}^{n} f(i, j) $$ 简要题解 首先我们考
…
https://codeforces.com/contest/985/problem/F 题目大意 给出字符串 $n \ (n \le 2 \times 10^5)$ 长的字符串 $S$，和 $m \ *(m \le 2 \times 10^5)$ 个询问。 定义串 $S$ 和 $T$ 是 isomorphic 的，当且仅当，$S$ 和 $T$ 的字符集之间能建立一一映射，使得 $S$ 和 $T$ 可以通过这组一一映射互相转化。 每组询问给出 $i, j,
…
https://codeforces.com/contest/1933/problem/D 题目大意 给出 $n \ (2 \le n \le 10^5)$ 长的数组 $a$ 其中 $1 \le a_i \le 10^9$。 问是否存在某种排列使得 $a_1 \mod a_2 \mod a_3 \cdots \mod a_n \neq 0$。 简要题解 假设 $m = \min(a)$ 容易想到 $x < y$ 时 $x \mod y = x$，则如果数组中的最小数 $m$ 唯一，那么我们按顺序排
…
https://codeforces.com/contest/2060/problem/D 题目大意 给出 $n \ (2 \le n \le 2 \times 10^5)$ 长的数组 $a$ 其中 $1 \le a_i \le 10^9$。问数组是否可以靠以下操作完成排序。 任选 $i \in [1, n - 1]$，$a_i, a_{i + 1}$ 都减去 $\min(a_i, a_{i + 1})$。 简要题解 这题分不高大概是结论很好猜，但其
…
https://codeforces.com/contest/1902/problem/B 题目大意 有 $n \le 10^{9}$ 天，在第 $1, 8, 15, \cdots$ 天会放出任务，在当天或之后任何天都可以完成这个任务，每天都会有课程。每天可以选择休息，或上课并完成 $0 \sim 2$ 个还未完成的任务。上课获得 $pl \ (\le 10^9)$ 点，完成一个任务获得 $pt \ (\le 10^9)$
…
https://codeforces.com/contest/1902/problem/C 题目大意 给出 $n \ (\le 2 \times 10^5)$ 长的数组 $a$ 其中 $-10^9 \le a_i \le 10^9$，且元素不重复。给 $a$ 添加任意其中未出现的元素 $a_{n + 1}$ 后，对于新数组，可以选定某固定 $x$ 后，对数组执行若干次，选定某 $a_i$ 然后 $a_i \gets a_i + x$。问选取最佳的
…
https://codeforces.com/contest/1902/problem/D 题目大意 给出某 LRUD 组成的 $n \ (\le 2 \times 10^5)$ 的操作序列 $S$ 以及 $q \ (\le 2 \times 10^5)$ 个询问。询问之间彼此独立。每次问，将原始操作序列 $[l, r]$ 的这一段反转后，整个操作序列以 $(0, 0)$ 为起点会不会通过 $(x, y)$。（$S$ 翻转 $[l, r]$ 之后的序
…
https://codeforces.com/contest/1902/problem/E 题目大意 给出 $n \ (\le 10^6)$ 个字符串，且 $\sum |S_i| \le 10^6$。两个串的运算 $C(a, b)$ 规则如下： $a$ 为空则 $C(a, b) = b$ $b$ 为空则 $C(a, b) = a$ 若 $a[|a| - 1] = b[0]$ 即 $a$ 的末尾字符与 $b$ 的开头字符相同则 $C(a, b) = C(a', b')$，$a'$ 为 $a$ 去掉尾字符的串
…