Posts

https://codeforces.com/contest/792/problem/B 题目大意 给出 $n \ (\le 100)$ 个点的环，顺时针标号 $1 \sim n$，以及 $k \ (\le n - 1)$ 次操作 $a_i \ (\le 10^9)$。最初位置为 $1$。每次操作顺时针数 $a_i$ 个位置，之后把这个点删掉，位置变为删掉的下一个。输出删掉标号的序列。 简

https://codeforces.com/contest/792/problem/C 题目大意 用字符串给出一个十进制大整数 $S \ (|S| \le 10^5)$。问最少删掉多少位可以得到一个没有前导零的能被 $3$ 整除的数。输出这个数。 简要题解 允许前导零的话这题非常水，直接 $dp[i][j]$ 表示到第 $i$ 位 $\mod 3$ 为 $j$ 的最多选数数

https://codeforces.com/contest/792/problem/D 题目大意 给出一棵 $n \ (\le 10^{18})$ 个节点的完全二叉树（$n + 1$ 保证为 $2^k$）。节点标号按照前序遍历顺序。给出 $q$ 个询问，每次询问为起点 $u_i$ 和操作序列 $s_i$，其中 $s_i$ 由 U, L, R 组成，分别表示走到父节点，走进左子

https://codeforces.com/contest/2005/problem/A 题目大意 使用 aeiou，构造 $n \ (\le 100)$ 的串，使得其回文子序列最少。（一样的回文下标不同要重复计算） 简要题解 容易发现，对于同一字母的所有组合，无论字母如何排布都会组成回文，那么需要不同字母组成的回文尽量

https://codeforces.com/contest/940/problem/A 题目大意 给定 $n \ (\le 100)$ 个点 $x_i \ (1 \le x_i \le 100)$ 和一个 $c \ (0 \le c\le 100)$。问至少删掉多少点使得剩余的任意 $i, j$ 满足 $|x_i - x_j| \le c$。 简要题解 范围很小所以可以直接 $n ^ 3$ 或者 $n^2$ 枚举。 当然，如果 $n \le 2 \times 10^5$，$x

https://codeforces.com/contest/940/problem/B 题目大意 给定数字 $n, k, a, b (1 \le n, k, a, b \le 2 \times 10^9)$，使用两种操作将 $n$ 变为 $1$， 花费 $a$ 使 $n$ 减 $1$。 花费 $b$ 使 $n$ 变为 $n / k$ （仅在 $k | n$ 时可用）。 简要题解 显然贪心即可，对于每次先将 $n$ 减到 $k$ 的某个倍数

https://codeforces.com/contest/940/problem/C 题目大意 给出字符串 $S$ 以及长度 $k$, $(|S|,k \le 10^5)$。要求用 $S$ 相同的字符集，构造字典序最小的且字典序大于 $S$ 的，长度为 $k$ 的串 $T$ 。题目保证有解。 简要题解 注意到这里是字符串，和数字的比较大小是不同的。 对于 $k > n$

https://codeforces.com/contest/940/problem/D 题目大意 给出序列 $n(\le 10^5)$ 长的序列 $a$ 和 $b$。 $b_1 = b_2 = b_3 = b_4 = 0$。对于 $i \ge 5$ $b_i = 0$，如果 $a_{i - 4}, a_{i - 3}, a_{i - 2},a_{i - 1}, a_{i} > r$ 且 $b_{i - 4} = b_{i - 3} = b_{i - 2} = b_{i - 1} = 1$。 $b_i = 1$，如果 $a_{i - 4}, a_{i - 3}, a_{i - 2},a_{i - 1}, a_{i} < l$ 且

https://codeforces.com/contest/940/problem/E 题目大意 给出 $n \le 10 ^ 5$ 长的数组 $a (1 \le a_i \le 10 ^ 9)$ 和常数 $c \le 10^5$ ，可以将数组分为一些连续的子数组。对于每个子数组，可以将其最小的 $\lfloor \frac{len}{c} \rfloor$ 个元素的权值减去。问剩余权值的和的最小值是多少。 简要题解 重要观察：最终

https://codeforces.com/contest/954/problem/E 题目大意 给出 $N (\le 2 \times 10 ^ 5)$ 个水龙头的水量 $a_i (\le 10 ^ 6)$ 和温度 $t_i (\le 10 ^ 6)$，每个水龙头可以取 $0 \sim a_i$ 的实数单位水量，问可以混合出 $T (\le 10 ^ 6)$ 温度的水最多多少。 若每个龙头取 $c_i$ 单位水，则混合水的温度为 $\frac{\sum c_i t_i)}{\sum c_i}$ 简

关于 2, 5, 4, 25 这一类比较显然。对于 $x = 2, 5$ 只需数字最后 $1$ 位能被被 $x$ 整除即可。 对于 $x = 4, 25$ 只需数字最后 $2$ 位能被整除即可。 之所以我们可以进行截断，是因为 $10 \equiv 0 \ (\bmod 2\ )$, $10 \equiv 0 \ (\bmod 5\ )$ 而 $100 \equiv 0 \ (\bmod 4\ )$, $100 \equiv 0 \ (\bmod

https://codeforces.com/contest/1993/problem/C 题目大意 给定 $n$ 盏灯和 $n$ 长数组 $a_i (1 \le a_i \le 10^9)$ 和 $k$，$1 \le k \le n \le 2 \cdot 10^5$。 起初 $n$ 盏灯都不亮。$i$ 位置的灯在 $a_i$ 时刻第一次点亮，之后每过 $k$ 单位时间点亮熄灭状态反转一次。问最早什么时刻，所有灯都亮

https://codeforces.com/contest/1993/problem/D 题目大意 给出一个 $n \ (le 5 \cdot 10^5)$ 长的数组 $a$ 其中 $a_i \le 10^9$。给定一个 $k \ (\le 5 \cdot 10^5)$。 不断地从数组中删去一些长为 $k$ 的子数组（删除后把数组接起来），使得最后的数组长度 $\le k$。 问此时剩余元素的中位数

https://codeforces.com/contest/1997/problem/E 题目大意 给定 $n\ (\le 2 \cdot 10^5)$ 长的数组和 $q\ (\le 2 \cdot 10^5)$ 个询问。数组中元素 $a_i\ (\le 2 \cdot 10^5)$。对于参数 $k$，我们依次在数组中标记 $k$ 个不小于 $1$ 的数，之后从最后标记的下标开始，再标记 $k$ 个不小于 $2$ 的数，以此类推。 每

https://codeforces.com/contest/1997/problem/D 题目大意 给以棵 $1$ 为根的有根树，节点数 $n \ (2 \le n \le 2 \times 10^5)$。每个节点上有权重 $a_i \ (1 \le a_i \le 10^9)$。每次操作可以选择给节点 $i$ 的权值 $+1$ 给其子树中所有其他节点权值 $-1$。任意时刻结点权值不能为

https://codeforces.com/contest/1996/problem/G 题目大意 给出 $n \le 2 \cdot 10^5$ 个点的一个简单环，给出 $m \le 2 \cdot 10^5$ 组点。要求选最少的边，使得 $m$ 组点之间，都可以通过选的边连通。给的每组点 $u < v$。 简要题解 一般环形问题先想直线问题，再想断开环。 直线问题非常好解决

https://codeforces.com/contest/1996/problem/F 题目大意 给定 $n \le 2 \cdot 10^5$ 的两个数组 $a$ 和 $b$。可以执行 $k \le 10^9$ 次操作，每次操作选择某个 $i$ 然后 $ans += a[i]$，之后 $a[i] = max(0, a[i] - b[i])$。问最大的 $ans$ 是多少。 简要题解 题目贪心的策略是显然的，只需要选当前最大

https://codeforces.com/contest/1996/problem/E 题目大意 给出 $01$ 串 $S$，长度 $\le 2 \cdot 10^5$。求其所有子串的 $01$ 个数相同的子串的个数。 简要题解 题目求 $\sum_l \sum_r \sum_x \sum_y [cnt0(x, y) == cnt1(x, y)] ,\ (1 \le l \le x \le y \le r \le n)$。 如果只有所有子串 $S(x, y)$ 的个数，那将非常好求。遇到 $0$ 就 $

https://codeforces.com/problemset/problem/724/D 题目大意 给定一个字符串 $S$ 串长 $\le 10^5$ 给定 $m \le |S|$。选择一些下标，使得所有长度为 $m$ 的子串都至少包含一个备选的下标。找出一组符合规定的下标，使其字符任意重排之后字典序最小，输出这个最小字典序的串。 简要题

https://codeforces.com/contest/713/problem/C 题目大意 给定 $n \le 3000$ 的数组 $a$。每次操作可以使数组中的某个位置的值 $+1$ 或 $-1$。 问最少得操作次数使得数组严格单调递增。 简要题解 重要的 trick： $a_i < a_{i + 1} \iff a_i + 1 \le a_{i + 1} \iff a_i + 1 - i \le a_{i + 1} - i \iff a_i