烤柿题,简单
zelensky 和 haochangjian 的
1.
AT_abc237_g [ABC237G] Range Sort Query
经典 trick ,考虑我们不关心其他数的位置
所以把 > x 的赋成 1,否则为 0
这样之后排序就变成区间覆盖
以及需要维护 0 的个数
线段树简单做,不要想根号
2.
AT_agc038_f [AGC038F] Two Permutations
题意转化很简单
每个置换环要么不动,要么一起动
将其缩点后,贡献变成类似两个环同时选可以获得 ... 贡献
显然网络流
然后这个很像文理分科,但不一样,为了处理不同环的贡献,不要想拆点
然后这个其实是可以直接连的
我懒得写了
我们发现情况分为 5 种:
- \(P_i=Q_i=i\),此时必然 \(A_i=B_i\)。
- \(P_i=i,Q_i!=i\),当且仅当 \(q_i\) 被拆分时 \(A_i=B_i\)。
- \(P_i!=i,Q_i=i\),当且仅当 \(p_i\) 被拆分时 \(A_i=B_i\)。
- \(P_i!=Q_i,P_i!=i,Q_i!=i\),当且仅当 \(p_i\) 和 \(q_i\) 都被拆分时 \(A_i=B_i\)。
- \(P_i=Q_i!=i\),当且仅当 \(p_i\) 和 \(q_i\) 都被拆分或都不被拆分时 \(A_i=B_i\)。
我们设 \(p_i\) 被拆分时在 \(S\) 集合中,\(q_i\) 被拆分时在 \(T\) 集合中,建出最小割模型。
- \(P_i=Q_i=i\),必定耗费 \(1\) 代价。
- \(P_i=i,Q_i!=i,q_i\) 在 \(T\) 集合中耗费 \(1\) 代价,\(S\) 向 \(q_i\) 连边权为 \(1\) 的边。
- \(P_i!=i,Q_i=i,p_i\) 在 \(S\) 集合中耗费 \(1\) 代价,\(p_i\) 向 \(T\) 连边权为 \(1\) 的边。
- \(P_i!=Q_i,P_i!=i,Q_i!=i,p_i\) 在 \(S\) 且 \(q_i\) 在 \(T\) 耗费 \(1\) 代价,\(p_i\) 向 \(q_i\) 连边权为 \(1\) 的边。
- \(P_i=Q_i!=i,p_i\) 和 \(q_i\) 在不同集合耗费 \(1\) 代价,\(p_i\) 和 \(q_i\) 互连边权为 \(1\) 的边。
然后跑最小割即可。
由于是二分图单位边权,时间复杂度 \(O(n \sqrt{n})\)。
3.
AT_abc305_g [ABC305G] Banned Substrings
一眼板纸
字符串长度很小,暴搜或 AC 自动机都行
然后写出 dp 矩阵优化即可
4.
AT_abc282_h [ABC282Ex] Min + Sum
柿子中有 min
考虑序列分治
然后板纸没了
刚开始觉得一个 log ,是双指针套双指针,但写着写着发现不单调
没事,用个 lower_bound 就行了
两个log , 但第二个 log 跟现在处理的长度有关,超级小