近一个月来第一次赛时通过一道题。真是可喜可贺。
一开始以为与网络流相关；后来考虑 DP；结果是个贪心或者乱搞。
给定长为 $\newcommand\bigO{\operatorname{O}}n\ \ (n\leq 10^5)$ 的序列 $\langle a_i\rangle,a_i\in\{1,2,3\}$。匹配尽可能多的子序列，每个子序列均为 $\langle 1,2,3\rangle$ 或 $\langle 3,2,1\rangle$，且一个位置最多被一个子序列占用。求最大匹配数。 （更多…）
仍然是中规中矩的一场模拟赛。前两题正解，第三题暴力，第四题不会。
考虑是否有两条及以上双向连边，若是则无解，若有一条则枚举要将哪一侧的发射器旋转到哪一方向。简单模拟即可。
这类数轴上带标号小球相撞的题目都有一个经典套路：两球相撞调转方向时，我们不认为是球本身转向，而认为两球仍然保持原方向运动，而其编号交换。 （更多…）
或许是人品不错，最近两天接连刷到三道排列组合相关的题。在此作简单整理。
题意参见原题面。
很自然地想到，对于一个排列$P = (p_1, p_2, \dots, p_n)$，有$n$条$i \rightarrow p_i$的连边。因为排列中正整数$1, 2, \dots, n$恰好出现仅有一次，所以等价于每个点有且仅有一条出边、一条入边的图。容易发现这个图由若干个有向环构成（包括自环——即$p_i = i$的情况）。例如排列$P = (1, 3, 4, 2)$代表由$1 \rightarrow 1$和$2 \rightarrow 3 \rightarrow 4 \rightarrow 2$两个环组成的图。
我仍然坚持认为这道题不应该放在LCA的专题里面
一拿到题我毫无头绪……这看起来跟最近公共祖先没有半毛钱关系啊？我的第一反应是“递推出从某个状态开始能达到的所有状态”，时间复杂度大约是$\mathbf{O}(2^{|N|})$（至于为什么底数为$2$，请看完下一节后思考）。但很明显，坐标在$\pm 10^9$范围内的数据可容不下这般折腾。
但鉴于它被放在这个专题中，我们就尝试从树的角度来考虑。