260316 以前 x 天 / 谈笑间指银鞭

P4429 [BJOI2018] 染色

发现“日”是 NO，然后尝试推广到更长的环，发现更长的环其实限制更松，只是有一些包含四元环的东西需要特殊搞。

CF798E Mike and code of a permutation

发现根据给定的排列我们可以知道排列上一些位置的大小关系。根据经典结论 DAG 的后序遍历的逆序是拓扑序。但是边数特别多，于是使用线段树上二分优化 dfs 即可。

CF1466H Finding satisfactory solutions

发现唯一的方案可以如此构造：用每个人最想要的物品建出一个外向基环树森林，发现环是动不了的，于是将环固定，删掉和环相连的边，递归处理。注意到能生成给定排列的充要条件是排在前面的那些边不成环，于是是个 DAG 容斥。由于状态太大，注意到我们只关心每种环的数量不关心具体是哪个，这样状态只有 \(1440\) 种。

CF986F Oppa Funcan Style Remastered

AT_agc051_d [AGC051D] C4

需要用到 BEST 定理。

CF1129E Legendary Tree

CF1240F Football

CF1313D Happy New Year

简单 dp。

CF1007D Ants

若两条链相交，那么定有一条链中深度最浅的那条边被另一条链经过。于是这样拍到树上可以用线段树合并优化建图，拍到 dfn 序上可以用主席树优化建图。

主席树优化建图形如有一些横着的线段和竖着的线段，不存在两个横着的线段位于同一纵坐标，我们将会从每对相交的线段之间连接一条有向边。这显然可以做 3-side 矩形向点连边。