Sols
count:
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$ 去掉尾字符的串
…
https://codeforces.com/contest/2063/problem/B 题目大意 给定某 $n \ (\le 10^5)$ 长的数组 $a \ (1 \le a_i \le 10^9)$ 以及某一个区间 $1 \le l \le r \le n$。进行如下操作一次： 选择 $a$ 的某个子序列，将其拿出来反转之后再放回原位。 问 $sum(l, r)$ 最小是多少。 简要题解 注意到如果 $k$ 长的操作序列最小
…
https://codeforces.com/contest/2063/problem/C 题目大意 给出一棵 $n \ (2 \le n \le 2 \times 10^5)$ 个点的树，从中删掉 $2$ 个不同的点，问删完之后最多有多少个联通分量。 简要题解 首先 $n = 2, 3$ 是平凡的，单独处理就好。 其他情况，我们应该尽量删掉两个度最大的节点。但注意要处理
…
https://codeforces.com/contest/2063/problem/D 题目大意 给出 $n \ (\le 2 \times 10^5)$ 个点坐标为 $(a_i, 0)$ 以及 $m \ (\le 2 \times 10^5)$ 个点坐标为 $(b_i, 2)$。（$a_i, b_i$ 各自没有重复点） 问从这些点中选出非退化的三角形最多多少个（点不能重复选）。记最大数量为 $mx$，对于所有 $i \in [1,
…
https://codeforces.com/contest/2061/problem/E 题目大意 给出 $n \ (1 \le n \le 10^5)$ 长的数组 $a$ 和 $m \ (1 \le m \le 10)$ 长的数组 $b$。满足 $0 \le a_i, b_i < 2^{30}$。 可以执行以下操作 $k \ (0 \le k \le nm)$ 次： 选取 $a_i$ 和 $b_j$ 将 $a_i$ 变为 $a_i \ \text{&} \ b_j$。 问执行完这些操作最小的数组和是
…
https://codeforces.com/contest/2061/problem/D 题目大意 给出 $n$ 长的数组 $a$ 和 $m$ 长的数组 $b$。满足 $1 \le m \le n \le 2 \times 10^5$ 和 $1 \le a_i, b_i \le 10^9$。 可以执行下述操作若干次： 从 $a$ 中选出 $x, y$ 满足 $|x - y| \le 1$。将其从 $a$ 中删掉，再将 $x + y$ 加入。 问是否可以将 $a$ 转化为
…