Posts

https://codeforces.com/contest/1933/problem/E 题目大意 给出 $n$ 长的数组 $a$。 对于某个 $u$，如果连续训练 $k$ 次则获得收益为，后面的收益可以为负。 $u + (u - 1) + (u - 2) + \cdots + (u + 1 - k)$。 给出 $q$ 个询问，每次询问给出 $l$ 和 $u$。问最佳的 $r >= l$ 使得 $\sum_{i = l}^{r}

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/E 题目大意 给出 $n$ 长的排列 $p$。问其中有多少 $l, r$ 子段满足 $p_l + p_r = \max_{i = l}^{r} p_i$。 $3 \le n \le 2 \times 10^5$。$1 \le p_i \le n$ 且不重复。 简要题解 因为涉及到区间最值，想到笛卡尔树。建出最大值为根的笛卡尔树之后相当

https://codeforces.com/contest/1156/problem/B 题目大意 给出小写字母组成的字符串 $S$，要求重排字符串使得相邻位置，不能是字典序相邻的字符。（‘a’ 与 ‘z’ 不相邻）。有解时输出任意合法串，否则输出 ‘No answer’。

https://codeforces.com/contest/1156/problem/A 题目大意 给出 $n$ 个图形的序列 $a$。图形依次向里内接。 1 代表圆形 2 代表底和高相等的等腰三角形，并且底平行于 $x$ 轴，高位于底的 $y$ 轴正方向 3 代表正方形，四边平行于坐标轴 保证序列里相邻图形不会相同，问图形间的

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/903/problem/B 题目大意 一个回合制游戏，主角血量是 $h_1$ 攻击力 $a_1$ 有无限多的药，每次可以恢复 $c_1$ 的血量（恢复可以超出 $h_1$）。有怪物血量 $h_2$ 攻击力 $a_2$。每个回合： 主角选择攻击或恢复，攻击则 $h_2$ 减少 $a_1$ 否则 $h_1$ 增加 $c_1

https://codeforces.com/contest/632/problem/B 题目大意 给出 $n \ (\le 5 \times 10^5)$ 长的权重数组 $p$ 其中 $1 \le p_i \le 10^9$，以及 $n$ 长的只包含 AB 的字符串 $S$。可以最多一次，选择 $S$ 的前缀或后缀（题意这里不是特别清楚），将其中的 AB 互换。最大化 B 对应的权重的和。问最

https://codeforces.com/contest/1487/problem/B 题目大意 有 $n$ 个格子组成一个环，顺时针依次标号为 $1 \sim n$。猫 $A$ 最初在 $n$ 号格，它每单位时间后逆时针移动一个格，猫 $B$ 最初（$1$ 时刻）在 $1$ 号格，每单位时间后顺时针移动一个格。如果某时刻 $A$ 和 $B$ 移动到同一个格

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/903/problem/C 题目大意 给出 $n \ (\le 5000)$ 个数的数组 $a$ 其中 $1 \le a_i \le 10^9$。问最少可以把它分成多少个集合，使得每个集合都可以重排成一个严格单调递增的链。 简要题解 显然同样数值的数必然属于不同的链，因此最少不少于最大频率 $

https://codeforces.com/contest/1574/problem/C 题目大意 给出 $n \ (2 \le n \le 2 \times 10^5)$ 长的数组 $a$ 其中 $1 \le a_i \le 10^{12}$。 给出 $m \ (\le 2 \times 10^5)$ 个询问，每组询问给出 $x \ (1 \le x \le 10^{12}), y \ (1 \le y \le 10^{18})$，问至少需要多少次给某数 $+1$ 的操作才能使，数组选出

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$（保证一定在数组中）的元素的下标，询问后将其挪到数组最左侧。 简要题解 注意到其实每个数字只有最左侧