笔记 2023.12.19:题目选讲
不会的题目没在这里展现。一共 14 道题。
gym103371I Organizing Colored Sheets
猜结论:两个同一行的 sharp 的间隙的 \(\min\) 是 \(W\) 上界,同一列的 sharp 的间隙的 \(\min\) 是 \(H\) 上界,然后相乘。
这是假的,是答案上界,过不去样例二。每个 \(H\) 对应的 \(W\) 上界不一定相同。
结论:不合法的尺寸,不能被覆盖的网格一定有至少一个与边界或有色网格相邻。
如果 \((x, y)\) 无色,\((x+1, y)\) 有色,尝试计算 \((x, y)\) 的限制,发现只需要记 \(L, R, U\) 表示向左、向右、向上走多少格到有色网格,那么暴力枚举 \(1\sim U_{xy}\) 的高度,用 \(L, R\) 取一点 \(\min\) 加以限制,发现复杂度是对的。
QOJ1884 Mission Impossible: Grand Theft Auto
考虑到缩链后有最多 \(2m-2\) 个点(\(m+x\) 个点,\(x\) 个点至少三度,\(m+3x=2(m+x-1), m-x=2\)),\(2m-3\) 条边,每条边对应了至多一个叶子。而共有 \(m\) 个叶子,根据鸽巢原理,存在一个叶子使得它有至多一条坏边。用这个叶子开始操作,直到最后一次操作覆盖掉坏边即可。
*gym102341B Bulbasaur
考虑固定左端点之后暴力向后流,例如 \(F(1, n)\),流满了以后把最后的一些点删掉,删到增广最远的地方,然后继续流。移动左端点只需要把左端点删掉。\(O(nk^3)\)?
*QOJ4214 Deja Vu
设 \(a, b, c\) 表示长度为 \(1, 2, 3\) 的子序列,初始 \(\infty\),从左往右扫描到 \(x\):
- 如果 \(x\leq a\),\(a=x\)。
- 否则如果 \(x\leq b\),\(b=x\)。
- 否则如果 \(x\leq c\),\(c=x\)。
- 否则我们得到了答案。
就很像二分求 LIS 的过程。注意时刻有 \(a<b<c\)。然后他说势能线段树,不知道是啥。
ARC156F Make Same Set
直接网络流,但是会不会有问题呢,不会。
你考虑那些没有流量的点。称一个点为空点,当且仅当它连出去的两条边都没有匹配,它是严重不合法的。实点就是相反。考虑一个空点变为实点以后不会再变回去?因为变回去的时候反悔到那里就不是最短路了,有个更近的从实点过来走两步的流,它是个假的流。所以一开始强制所有 \(A_i\) 流掉再进行 dinic,因为这样全是实点,且 dinic 每次增广都是最短路,就对了。\(O(n\sqrt n)\)。
标签:个点,min,19,2023.12,选讲,leq From: https://www.cnblogs.com/caijianhong/p/17914312.html