低分段：指 2700~2800
红色标题表示主要看了题解，绿色表示主要没有看题解。
\red{\textrm{1453F Even Harder}}
给定数组 a，a_i 表示从 i 能走到 [i+1, i+a_i]，问至少需要把几个 a_i 改成 0，才能使得 1 到 n 有且仅有一条路径。
***
[评测链接](https://codeforces.com/contest/1453/submission/107498741)
我们设 $f_{i, j}$ 表示考虑了前 $i$ 个 $a$，能走到的范围为 $[1, j]$，且只有一条路径至少需要修改几个。$g_{i, j}$ 表示 $f_i$ 的前缀最小值。
则有：
$$g_{i, j+a_j}=\min_j\{g_{j, i-1}+\textrm{cnt}_{i, j}\}$$
其中，$\textrm{cnt}_{i, j}$ 表示 $j+1$ 到 $i-1$，满足也能走到 $i$ 的位置数。这些位置都需要被修改。
时间复杂度：$O(n^2)$。
### [$\green{\textrm{1303G Sum of Prefix Sums}}$](http://codeforces.com/problemset/problem/1303/G)
有一颗 $n$ 个节点的树。树每个节点有一个权值。定义树上 $u \rightarrow v$ 的链的权值如下：
- 将 $u$ 到 $v$ 的路径上点的权值依次排列在数组中。
- 该数组的前缀和的和即这条路径的权值。
请求出权值最大的链，输出权值。
***
[评测链接](https://codeforces.com/contest/1303/submission/107677939)
点分治 + 李超树（凸包二分）大套路题。
非常不理解，2700 有的题又巧妙又长，有的又套路又好写。
### [$\green{\textrm{1338D Nested Rubber Bands}}$](https://codeforces.com/problemset/problem/1338/D)
给定一棵 $n$ 个点的树，第 $i$ 条边连接 $u_i$ 和 $v_i$。
你需要将每一个节点画成一个二维平面上闭合几何图形，当且仅当 $u$ 和 $v$ 之间有边相连，这两个点对应的几何图形边界相交（注意包含不算边界相交）。
我们定义一个序列 $a_1,a_2,\ldots,a_k$ 是好的，当且仅当对于任意的 $2\le i\le k$，$a_{i-1}$ 所对应的几何图形完全包含 $a_i$ 所对应的几何图形。
求好的序列最长可以是多少。
***
[评测链接](https://codeforces.com/contest/1338/submission/107734355)
我们考虑序列与链接序列的点的集合，当然，只能是一个连通子图。
考虑在序列上相邻的两者 $x, y$ 的必要条件。
1. $(x, y)$ 没有边。
2. 存在一条链使得 $(x, 链首), (y, 链尾)$ 有边。
发现满足条件 $2$ 的连通子图只能是毛毛虫（一条主链与链上和每个点相邻的点）。
而条件 $1$ 便是让我们求毛毛虫的最大独立集。这是一个简单的树 dp。
### [$\green{\textrm{1458C Latin Square}}$](https://codeforces.com/contest/1458/problem/C)
给定一个 $n\times n$ 的矩阵，每行每列都是个 $1\to n$ 的排列。有 $m$ 次操作，如果是 `UDLR` 就是要把整个矩阵每行/每列往一个方向循环移动一格。如果是 `IC`，就是把矩阵每行/每列变成原来的逆排列。求最后的矩阵。
$1\le n\le 1000$，$1\le m\le 10^5$。
***
[评测链接](https://codeforces.com/contest/1458/submission/107734599)
感谢这题让我上红。
我们独立地考虑每个位置 $(x, y)$，设其的值为 $z$。
我们把 $(x, y, z)$ 看作一个整体，则六个操作为：`x++`，`x--`，`y++`，`y--`，`swap(x, z)`，`swap(y, z)`。
记录 $x, y, z$ 的偏移值和 $x, y, z$ 最终的交换顺序即可。
### [$\red{\textrm{1279E New Year Permutations}}$](http://codeforces.com/problemset/problem/1279/E)
定义一个排列 $p$ 的分解如下：
将所有环（$i, p_i, p_{p_i}, \ldots$）划分成若干集合，每个集合按照在原序列中的出现位置从前向后排列，之后我们把这个排列循环移位直至最大的元素至排列首。我们再按照最大的元素的出现先后顺序把集合排序。
如 $p = [5, 4, 2, 3, 1, 7, 8, 6]$，划分为 $[[5, 1], [4, 2, 3], [8, 6, 7]]$。
求，长度为 $n$ 的，满足分解后与原序列顺序相同的排列 $p$ 中，字典序第 $k$ 大的。
$T\leq 1000$，$n \leq 50$，$k \leq 10^{18}$。
***
[评测链接](https://codeforces.com/contest/1279/submission/107776430)
满足条件的序列一定是这样的：每个环是一个区间，第一个位置 $i$ 为最大的元素，并且区间为 $[i, p_i]$。
我们逐位构造，有两种情况：
1. 我们确定了一个环的大小。
2. 我们确定环的连接顺序。
设 $g_i$ 表示大小为 $i$，已经确定环首的环有多少种。$f_i$ 表示大小为 $i$ 的环的集合有多少种。也即：
$$f_0=1,f_i = \sum_{j=0}^{i-1} f_jg_{i-j}$$
通过简单的分析可得：$g_0=1, g_i = (i-2)!$。
构造一个大小为 $s$ 的环，除了这个环还剩余 $t$ 位的方案数为 $g_{s}f_t$。
确定环的连接顺序时，若已经确定了 $i$ 位，则剩余元素的方案数为 $g_{s-i}$。这是因为我们可以把已经连成的链缩点。
### [$\green{\textrm{1366F Jog Around The Graph}}$](https://codeforces.com/problemset/problem/1366/F)
给定一个 $N$ 个点，$M$ 条边的无向图，边有长度。 对于每一个 $k \in [1, Q]$，求出从 $1$ 号点开始经过 $k$ 条边的路径的最大长度，输出它们的和。 $N,M\leq 2000, Q\leq 10^9$。
***
[评测链接](https://codeforces.com/contest/1366/submission/107894163)
显然 $\geq n$ 后会在一条边上循环走。
但是并不一定是最大的那条边，因为有可能从 $1$ 走到这条边经过路径太劣了，$Q$ 太小效果可能不佳。所以我们对所有边全部考虑当它是循环时的最大值。
由于要求和，我们维护所有边构成的一次函数的凸包。
### [$\red{\textrm{1422E Minlexes}}$](http://codeforces.com/problemset/problem/1422/E)
给定一只由小写字母组成的字符串 $s$，可以先删除任意相邻相同字符，再把剩下的部分拼接起来。
对于 $s$ 的每个后缀，求进行若干次上述操作后得到的字典序最小的字符串。 若输出超过 $10$ 位，则只用输出前 $5$ 位后 $2$ 位。
$1\le |s|\le 10^5$。
***
[评测链接](https://codeforces.com/contest/1422/submission/107899937)
一直以为这个输出有什么特殊性质，结果就走偏了。。。
我们考虑 $f_i$ 表示后缀 $i$ 得到的最小的字符串。
* 若 $s_i \neq s_{i+1}$，则 $f_i = s_i+f_{i+1}$。
* 否则，$f_i=\min(f_{i+2}, s_i+s_i+f_{i+2})$。
我们记录 $f_{i+2}$ 中第一个字符，和第一个字符不同的最靠前的字符，即可比较。
用指针或者 $\textrm{swap}$ 可以存下整个字符串的。
### [$\red{\textrm{1450E Capitalism}}$](http://codeforces.com/problemset/problem/1450/E)
$n$ 个点的图，每个点有一个权值 $a_i$。有 $m$ 条单向边或双向边。单向边 $(u, v)$ 表示 $a_v=a_u+1$，双向边表示 $|a_v-a_u|=1$，问是否存在合法的权值分配，若存在，最大化 $\max a - \min a$。
$n \leq 200$，$m \leq 2000$。
***
[评测链接](https://codeforces.com/contest/1450/submission/107986580)
差分约束板题，只不过因为太久没做了。
### [$\red{\textrm{1422F Boring Queries}}$](http://codeforces.com/problemset/problem/1422/F)
给定一个长度为 $n$ 的序列 $a$ 以及 $q$ 次询问 。
每次询问包含 $2$ 个整数 $l,r$ ，你需要求出区间 $[l,r]$ 的最小公倍数对 $10^9 + 7$ 取模的结果。
询问强制在线。
$n, q\leq 10^5$，$a\leq 2\times 10^5$。
***
[评测链接](https://codeforces.com/contest/1422/submission/107989540)
考虑将询问按右端点排序，线段树上维护每个质因子在每个位置的出现次数。用单调栈确定范围，区间乘即可。
由于强制在线，主席树即可。
这样的复杂度是 $O(\log n\sum \omega(a_i))$ 的，$\omega(x)$ 表示 $x$ 的质因子个数。
### [$\red{\textrm{1369F BareLee}}$](http://codeforces.com/problemset/problem/1369/F)
两人玩游戏。有两个数 $s, e$。两人轮流操作。
1. 将 $s$ 加 $1$。
2. 将 $s$ 乘 $2$。
操作使 $s$ 大于 $e$ 时，操作者输。
有 $T$ 次游戏。上一次输者先手。
整个游戏的胜负为最后一次游戏的胜负。
问第一次游戏先手者是否有必胜必败策略。
$T \leq 10^5$，$s, e \leq 10^{18}$。
***
[评测链接](https://codeforces.com/problemset/problem/1369/F)
我们考虑一小局游戏的必胜情况。（”手上拿的“指未操作时的状态）
* 若 $e$ 是奇数
* 若 $s$ 是奇数，先手无论如何手上都是奇数，后手胜。
* 若 $s$ 是偶数，可以让后手拿的都是奇数，先手胜。
* 若 $e$ 是偶数。
* 若 $s>\frac e2$，没有人会选择乘 $2$，胜者为手中 $s$ 为奇数的人。
* 若 $s > \frac e4$，先手可以先乘 $2$ 保证之后拿的都是奇数，先手胜。
* 否则，没有人会选择乘 $2$。答案为 $(s, \frac e4)$ 的答案。
再考虑必败情况。
* 若 $s> \frac e2$，先手败。
* 否则，没有人会选择乘 $2$。答案为 $(s, \frac e2)$ 的答案。
递推每个小局结束后，先手能否必胜必败即可。