2200
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/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/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/628/problem/D 题目大意 给出 $m \ (1 \le m \le 2000)$ 和数字 $d \ (0 \le d \le 9)$，给出两个字符串表示的没有前导零的大整数 $a, b \ (1 \le a \le b \le 10^2000)$。 问在区间 $[a, b]$ 中有多少数字 $x$ 符合能被 $m$ 整除，且从高向低数的偶数位（$1-
…