2026.2.28
Luogu P4039 [AHOI2014/JSOI2014] 拼图
\(\color{blue}{根号分治}\)
题目要求了 \(n\times m\le 10^5\)，容易想到根号分治
- \(n \le \sqrt {10^5}\)。枚举最终形成的举行的上下边界 \(l,r\)。遍历每个矩形，如果在第 \(l\) 行到第 \(r\) 行全部都是 \(0\)，那不要白不要，肯定会被选。对于不是全 \(0\) 的情况，计算他的最左边和最右边的全 \(0\) 长度。在所有不是全 \(0\) 的情况中，左边和右边会各自选择最大的一个矩形放置。同时记录一下次大的矩形，防止左边和右边选择同样的矩形。
- \(m \le \sqrt{10^5}\)，设 \(up_{i,j}\) 表示 \((i,j)\) 垂直向上第一个 \(1\)。那么就以 \(up_{i,j}+1,i\) 分别作为左端点和右端点跑上面的做法即可。
CF1523D Love-Hate
\(\color{blue}{随机化}\)
随机选择一个集合，那么最终答案不是他的子集的概率只有 \(\frac{1}{2}\)。设 \(f_i\) 表示状态为 \(i\) 的集合有多少集合是他的自己，使用 \(f_i\) 就可以回答问题。随机 50 次即可。
CF1310D Tourism
\(\color{blue}{随机化}\)
考虑先随机染色，强制不能走颜色不同的边。设 \(f_{i,j}\) 表示走了 \(i\) 步，现在在 \(j\) 的最小花费。使用 \(f_{i,j}\) 回答问题，随机 5000 次即可。