1.CF1835F Good Graph
判定 Yes or No 等同于判是否存在最大匹配。
如果不存在，考虑找到一个不在匹配的左部点，在残量网络上 bfs 即可。
如果存在，考虑 tight 集合是怎么构成的。如果 \(S_i\) 表示包含左部点 \(i\) 的最小 tight 集合，发现每个 tight 集合都是一些 \(S_i\) 的并。
考虑怎么简化 \(S_i\) 的表示。
考虑如果存在边 \((i,j)\) 满足 \(i\in S\) 且 \(i\) 不与 \(j\) 匹配，我们就需要把与 \(j\) 匹配的点加进来。由此能连一张图出来，形式化的，若 \(m_j\ne i\) ，就把 \(i\) 连向 \(m_j\)。
\(S_i\) 就是 \(i\) 能到达的点集。现在问题转化成连尽量少的边使新图和原图的传递闭包相同。缩点后在每个 SCC 内连环，然后在 DAG 上存在 \((x,y)\) ，\((y,z)\) 就删掉 \((x,z)\) 。
可以 bitset 实现，总复杂度 \(O(n^{2.5}+\frac{n^3}{w})\) 。
2.CF1753E N Machines
由于答案不超过 \(2*10^{9}\) ，非 \(1\) 的乘法操作显然不超过 \(30\) 个。
我们会在其中选一些移到最后面。注意到对于乘数相同的操作，我们只会选一个前缀。所以可能的方案是不多的，具体的，不超过 \(5000\) 种。
此时可以得到加法操作次数的上界 \(K\) ，我们会选对答案贡献尽量大的到前面。二分第 \(K\) 大的值，对每一段 lower_bound 计算即可。
3. ARC163F Many Increasing Problems
咕。明天写。
4. P6256 [ICPC2019 WF] Directing Rainfall
其实是简单题。以前一直不敢写，今天写了发现很简单。首先通过扫描线可以得到线段间的拓扑序，我们从上往下 dp 。
维护 \(f_i\) 表示当前雨的坐标在 \(i\) 需要钻的洞数最小值。则我们需要支持区间加，区间取前缀最小，区间取后缀最小，最后查一遍区间最小。
考虑用线段树维护这个过程，比较难的是后两个操作。
如果一个区间不降/不增，我们就直接当成区间取 min 操作打 tag 。否则就递归做下去。为什么是对的？
考虑一次操作后 \([f_i<f_{i+1}]\ne [f_{i+1}<f{i+2}]\) 的位置只会增加 \(O(1)\) 个，而我们通过上面的方法保证了，如果位置减少量为 \(k\) ，则复杂度是 \(O(k\log n)\) 的。
总复杂度 \(O(n\log n)\) 。
5.P9158 「GLR-R4」小暑
直接做是非常难写的，但考虑这个往上合并的过程，我们实际上可以把这个树重构成二叉树！
考虑在新树上 \(p(v)\) 得到的结果为原树中 \(v\) 的子树得到的结果。现在我们要依次合并 \(x,p(v_1),p(v_2),...,p(v_m)\) 。
就是新建 \(m\) 个点 \(a_1,a_2,...,a_m\) ，\(a_i\) 左儿子为 \(a_{i-1}\) ，右儿子为 \(p(v_i)\) 。特别的，\(a_1\) 左儿子为 \(x\) 。最后 \(p(x)=a_m\) 。
这样就把图转成了二叉树，在上面用树剖简单维护即可。
6. AGC061E Increment or XOR
7.CF1446F Line Distance
8.P7712 [Ynoi2077] hlcpq
9.LOJ578. 「LibreOJ NOI Round #2」小球进洞
10.LOJ3652. 「2021 集训队互测」海胆
11.LOJ3695. 「JOISC 2022 Day4」鱼 2
12.LOJ3153. 「JOI Open 2019」三级跳
13.LOJ3631. 「2021 集训队互测」学姐买瓜
14.LOJ3661. 「2021 集训队互测」蜘蛛爬树
15.UOJ719. 【北大集训2021】经典游戏
16.P8497 [NOI2022] 移除石子
17.CF1599A Weights
明天再来写题解，现在睡了。
标签：集训队,tight,2021,区间,考虑,杂题,互测 From： https://www.cnblogs.com/cwhfy/p/17542653.html