Organizing Colored Sheets
结论:如果每种型号的矩形无法完成覆盖,那么一定死于某些边界点
于是对各个方向枚举边界点,求矩形面积并一样的东西即可
Mission Impossible: Grand Theft Auto
首先有一个贪心的选法,按照dfs序,从中间向外匹配,但发现这个策略有时会出现覆盖不到的边
根据证明可以知道,至少存在一种策略使得只有一条覆盖不到的边,通过树形 \(DP\) 可以处理出,每个点对应的坏边数量,找到最少那个,用多余一次操作覆盖即可
Bulbasaur
容易想到网络流,转化为最小割模型,可以使用 \(DP\) 转移
设 \(dp_{i,j,S}\) 表示
流到 \(i\) 时,有 \(j\) 的流量,没割的点集为 \(S\) 时,左端点最远能在哪里,直接转移求和即可
Deja Vu*
貌似是吉司机套吉司机套吉司机
[ARC156F] Make Same Set
网络流,但发现直接流可能出现,两个集合都不选的情况,这时就寄了
仔细思考会发现,令这种点为待定点,如果每次都从最短路增广,待定点必然不会变回非待定点,于是在开始的时候,对这些点打标记就行了
[AGC045B] 01 Unbalanced
二分查找
\(check\) 的时候只要极差超过k就寄,可以用dp 维护连续段一样的东西