2026.1.11
P4404 [JSOI2010] 缓存交换
\(\color{blue}{贪心}\)
替换以后最晚会用到的那个
Hailiang 网格
\(\color{blue}{构造}\)
因为 \(A\to B\to A\) 这样走，\(B\) 的值会取反，\(A\) 的值不变。
遍历 \(2\) 到 \(n-1\) 列，考虑当前在第 \(i\) 列，使用折返的方式把第 \(i-1\) 列填好。对于第 \(n\) 列，处理完前 \(n-1\) 列后，如果 \((i,n)\) 颜色不对，使用 \((i+1,n)\) 调整颜色，\((n,n)\) 使用 \((n-1,n)\) 调整。
P4214 [CERC2015] Juice Junctions
\(\color{blue}{强联通}\)
任意两点之间的最大流小于等于 \(3\)。如果最大流 \(\in \{1,2,3\}\)，两个点需要连通。如果最大流 \(\in \{2,3\}\)，两个点需要再同一个边双中。如果最大流 \(=3\)，需要删掉一条边还在同一个边双中。所以每次删除一条边跑边双，如果删除后每个点所在的边双编号不变就行。