这是之前的博客。
鸽了一年的 ZYLOI终于举办了！讲完题的一刻，感觉心中的大石头终于落下来了！
265 P9150 邮箱题
很不错的题！！
分置换环考虑，我们将一个置换环上的结点重新编号为 \(1,2,\cdots,n\)，倍长后断环为链。
我们尝试维护若干条有序的链，每条链由一些点双连成。从后往前扫描每个点，我们检查其是否能与最靠前的链接上，若能合并我们就检查这条链哪些点会被合并成一个点双（容易发现一定是一个前缀），如果当前链被合并成一个点双了就继续做上面的步骤。
点双的合并可以使用并查集维护，有序链结构的维护可以直接用栈保存若干个区间，问题主要是如何找到合并成一个点双的一个前缀，事实上我们只需维护一个并查集最靠前的出边，这个在加边的过程中处理一下就好了。
复杂度 \(O(n\alpha(n))\)，代码实现依托答辩。
266 AGC024F Simple Subsequence Problem
比较简单？
直接使用子序列匹配的贪心模式，记 \(f_{S,T}\) 为已经匹配了子序列 \(S\)，还要匹配 \(T\) 的一个子序列，能匹配出多少个给定的子序列。
每次从 \(T\) 中选最前一个 \(0/1\) 加入 \(S\) 并将前面所有部分删除，注意到状态数为 \(\sum 2^ii=O(n2^n)\)，因此直接 dp 即可，复杂度 \(O(n2^n)\)。
267 AGC011F Train Service Planning
做这种题根本不想思考，好烦，直接看题解了！！
只要得到建模这题就比较简单，下面直接给出建模：
在模 \(k\) 意义下考虑本题，我们给每个站台赋正列车的等待时间 \(p_i\)，反列车的等待时间 \(q_i\)，那么一个铁路正列车的占用时间与反列车的占用时间是可以确定的：（设 \(st,sp,sq\) 为 \(t,p,q\) 的前缀和）
\[[st_{i-1}+sp_i,st_i+sp_i],[-st_i-sq_i,-st_{i-1}-st_i] \]我们的限制无非区间不交，将四个端点的值带入另一个区间列出不等式可以解出 \(p_i+q_i\ne\in[-2st_{i-1},-2st_i]\)。（注意是模意义下）
于是我们直接记 \(p_i+q_i\) 的值做 dp，线段树优化即可，复杂度 \(O(n\log n)\)。
268 AGC023D Go Home
无语题。
时光倒流，最后一个到达的要么是 \(1\) 要么是 \(n\)。如果 \(p_1\leqslant p_n\)，那么就算到达了 \(2\) 也得回到 \(n\)，所以 \(1\) 一定在 \(n\) 之后到达，那么其到达时间由 \(n\) 到达时间唯一确定，于是我们可以将 \(1\) 看作 \(n\) 一遍的，递归即可。复杂度 \(O(n)\)。
标签：列车,45,16,到达,复杂度,sp,合并,st,2023 From： https://www.cnblogs.com/xiaoziyao/p/17223957.html