有一个挺不错的 随机化blog
平面上有 (n) 个点 ((x_i, y_i)) ，保证这 (n) 个点可以用 (7) 条直线覆盖。找出一条直线使得它覆盖的点最多
(30) 组 Test
(nleq10^4; |x_i|, |y_i|leq1.5 imes10^4)
每次随机找两个点 (A, B) ，判断它们所在的直线所覆盖的点数，找到答案的概率为 (frac{1}{k^2}(k=7)) ，时间复杂度 (O(Tnk^2))
也有一个确定性算法：当 (n<k^2) 时暴力，当 (nge k^2) 时可以发现题目给定的 (k) 条直线点数一定大于等于 (k) ，故可以固定一个点，找到覆盖它的直线的点数最大值（可以按斜率考虑），若大于等于 (k) 则删掉这些点递归，时间复杂度 (O(Tknlog n))
杂题
给定一个 (n imes m) 的矩形，每个点有一种颜色 (a_{i, j}) ，你可以从 ((1, 1)) 出发，每次走到与它四连通的格子上，问至少经过 (k) 种颜色最少需要走多少步
(n, mleq30; kleq7; a_{i, j}in[1, 1000])
每次给每种颜色赋一个 ([1, k]) 的权值，将原矩形看做只有 (k) 种颜色，然后状压bfs，每次结果为正确答案的概率为 (frac{k!}{k^k})
时间复杂度 (O(Tnm2^k))
杂题
给定一个 (n imes m) 的矩形，每个位置有一个权值 (a_{i, j}) 和一个颜色 (c_{i, j}) ，找一个四连通块使得包含了至少 (k) 种颜色并且权值和最小
(n, mleq15; kleq7; a_{i, j}in[1, 10^5])
如上随机化赋值，问题转化为了求斯坦纳树，时间复杂度 (O(T(nm3^k+operatorname{spfa}(nm, nm)2^k)))