随机化
什么是随机化算法？
随机化做法，就是基于当前算法而言，通过正确算法求解会 TLE 或者 MLE，但是出于骗分的目的，我对可能答案中的一些序列或者值进行查找，在我随机瞎找的这些值中去找正确答案，最后，所得出的答案具有极大可能性为正确答案，甚至于百分之一百。
如果题目要求最优解，但难以按照某个规则贪心求出最优解，也无法使用动态规划等算法。可以考虑随机贪心，将输入数据随机打乱，然后从前到后按照某种方式贪心，多次随机求最优值。
还可以结合多种不同的贪心规则，每次使用不同的贪心方法，不断逼近最优值。
一般可以用在出题人无法轻易掌控某个输入时得到的输出类型的题目，随机情况下可以避免出题人的刻意卡。同时，随机化贪心也可以加入权重，例如为直观感受上更优的点提供更高的权重，更有几率排在序列的前面。
如何为更优的点提供更高的权值呢？如果某个点存在多个有关量，首先我们把有关量分类，类间的关联性较小，类间的权值用加法。同类的量用比值定义法，越重要的量就在上面加次方就可以了。
随机化解决例题
[POI2004] PRZ
正解是状压 dp
但我想玩随机化。
\(id\) 表示贪心的顺序，初始的时候让 \(id_i=i\)，之后每次都对 \(id\) 进行 random_shuffle，按这个新的顺序贪心，每次记录所得到的最小值，最后最小的那个就是答案。
signed main()
{
srand(time(0));
cin >> v >> n;
for (rint i = 1; i <= n; i++)
{
cin >> t[i] >> w[i];
id[i] = i;
}
int times = 3e5 + 5;
while (times--)
{
random_shuffle(id + 1, id + n + 1);
int sum = 0, cnt = 0;
int maxx = 0;
for (rint i = 1; i <= n; i++)
{
int x = id[i];
if (sum + w[x] > v)
{
cnt += maxx;
sum = w[x];
maxx = t[x];
}
else
{
sum += w[x];
maxx = max(maxx, t[x]);
}
}
minn = min(minn, cnt + maxx);
}
cout << minn << endl;
return 0;
}
[TJOI2015] 线性代数
正解是矩阵乘法 + 网络流
但我想玩随机化
每次随机一个位置，把这个位置取反，判断大小并更新答案。然后官方数据全能水过。luogu 上三个 hack 数据有一个过不了
void calc()
{
memset(d, 0, sizeof d);
int now = 0;
for (rint i = 1; i <= n; i++)
for (rint j = 1; j <= n; j++)
d[i] += a[j] * c[i][j];
for (rint i = 1; i <= n; i++)
now += (d[i] - b[i]) * a[i];
ans = max(ans, now);
}
signed main()
{
cin >> n;
for (rint i = 1; i <= n; i++)
for (rint j = 1; j <= n; j++)
cin >> c[i][j];
for (rint i = 1; i <= n; i++)
{
cin >> b[i];a[i] = 1;
}
calc();
int times = 1e3 + 5;
while(times--)
{
int x = rand() % n + 1;
a[x] ^= 1;
calc();
}
cout << ans << endl;
return 0;
}
[春季测试 2023] 密码锁
这个题我不会正解，连题解都看不懂。
但是我想玩随机化。
考虑贪心，有一个假的贪心为：从 \(1 \sim n\) 考虑，对于每个转圈枚举出转多少对总答案的影响最小。
虽然这个贪心是错的，但是我如果多随机几次，从随出来的这些数据找答案呢？？？
然后恭喜你，这道题你可以切了，一般来说交个七八次就过了。
signed main()
{
srand(time(0));
T = read();
k = read();
while (T--)
{
n = read();
for (rint i = 1; i <= k; i++)
for (rint j = 1; j <= n; j++)
a[j][i] = read();;
int times = 150;
while (times--)
{
random_shuffle(a + 1, a + n + 1);
memset(maxx, -0x3f, sizeof maxx);
memset(minn, 0x3f, sizeof minn);
for (rint i = 1; i <= n; i++)
{
int v = inf;
int p = 0;
for (rint x = 0; x ^ k; x++)
{
int w = 0;
for (rint j = 0; j <= k; j++)
{
int o = (j + x - 1) % k + 1;
w = max(w, max(maxx[j], a[i][o]) - min(minn[j], a[i][o]));
}
v = w < v ? (p = x, w) : v;
}
for (rint j = 1; j <= k; j++)
{
int o = (j + p - 1) % k + 1;
maxx[j] = max(maxx[j], a[i][o]);
minn[j] = min(minn[j], a[i][o]);
}
if (ans <= v)
{
break;
}
}
int res = 0;
for (rint i = 1; i <= k; i++)
{
int delta = maxx[i] - minn[i];
res = max(res, delta);
}
ans = min(ans, res);
}
cout << ans << endl;
}
return 0;
}
CF329C
这道题的正解好像就是随机化？？？
但是我想玩随机化
不断地随机生成一个链的形式，判断它是否在原图中出现过，如果没有，直接输出。然后如果随机了好几次都找不到，则输出 -1
signed main()
{
cin >> n >> m;
for (rint i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
d[a][b] = d[b][a] = 1;
}
for (rint i = 1; i <= n; i++) a[i] = i;
int times = 1e3 + 5;
while(times--)
{
random_shuffle(a + 1, a + n + 1);
if(!check())
{
int len = min(n, m + 1);
for (rint i = 2; i <= len; i++)
cout << a[i - 1] << " " << a[i] << endl;
if (n == m)
cout << a[n] << " " << a[1];
return 0;
}
}
cout << -1 << endl;
return 0;
}
CF798D
这个题的正解是一个非常复杂的分组贪心。
但是我想玩随机化
每次随机打乱原数列
然后按这个新的数列贪心地取前$ \frac{n}{2}+1$ 个数，一直到合法为止
bool check()
{
int a = 0, b = 0;
for (rint i = 1; i <= n / 2 + 1; i++)
a += f[i].a, b += f[i].b;
return a * 2 > s1 && b * 2 > s2;
}
signed main()
{
cin >> n;
for (rint i = 1; i <= n; i++)
{
cin >> f[i].a;
s1 += f[i].a;
f[i].id = i;
}
for (rint i = 1; i <= n; i++)
{
cin >> f[i].b;
s2 += f[i].b;
}
cout << n / 2 + 1 << endl;
while(1)
{
random_shuffle(f + 1, f + n + 1);
if(check())
{
for (rint i = 1; i <= n / 2 + 1; i++)
{
cout << f[i].id << " ";
}
return 0;
}
}
return 0;
}
[WC2018] 通道
这道题的正解是虚树分治
但是我想用随机化
对于一个节点跑 SPFA，查找在三棵树上和自己距离和最大的节点。
所以我们可以：不断寻找与自己在三棵树上总距离最大的节点，并跳到那个节点上。
然后随机选节点，走十次，找最大值记录答案。
随个五遍就过了
struct tree
{
int h[N], ne[N], e[N], w[N], idx = 0;
int dist[N];
bool v[N];
void add(int a, int b, int c)
{
ne[++idx] = h[a], e[idx] = b, w[idx] = c, h[a] = idx;
}
void SPFA(int s)
{
queue<int> q;
memset(v, 0, sizeof v);
memset(dist, 0x7f, sizeof dist);
q.push(s);
v[s] = 1;
dist[s] = 0;
while (!q.empty())
{
int x = q.front();
q.pop();
for(rint i = h[x]; i; i = ne[i])
{
int y = e[i];
int z = w[i];
if (v[y])
{
continue;
}
dist[y] = dist[x] + z;
q.push(y);
v[y] = 1;
}
}
}
} t[4];
signed main()
{
srand(time(0));
cin >> n;
int times = 3.7 * CLOCKS_PER_SEC;
for (rint k = 1; k <= 3; k++)
{
for (rint i = 1; i < n; i++)
{
int a, b, c;
cin >> a >> b >> c;
t[k].add(a, b, c);
t[k].add(b, a, c);
}
}
for (rint i = 1; i <= n; i++)
{
p[i] = i;
}
random_shuffle(p + 1, p + n + 1);
int idx = 1, ans = 0;
while (idx <= n && clock() <= times)
{
int u = p[idx];
for (rint k = 1; k <= 10; k++)
{
t[1].SPFA(u);
t[2].SPFA(u);
t[3].SPFA(u);
int maxx = 0;
for (rint i = 1; i <= n; i++)
{
int res = 0;
for (rint j = 1; j <= 3; j++)
{
res += t[j].dist[i];
}
if (res > maxx)
{
maxx = res;
u = i;
}
}
ans = max(ans, maxx);
//不断随机数列去找最大值
}
idx++;
}
cout << ans << endl;
return 0;
}
[NOIP2021] 方差
众人都说模拟退火过不了，但是吧，我用 mt19937 卡过去了。。。。
int calc()
{
int s = 0, w = 0;
int p = 0;
for (rint i = v1.size() - 1; i >= 0; i--)
{
p += v1[i];
s += p;
w += p * p;
}
for (auto i : v2)
{
p += i;
s += p;
w += p * p;
}
w = w * n - s * s;
ans = min(ans, w);
return w;
}
mt19937 neww(time(NULL));
double Rand()
{
return (double)(neww() % inf) / inf;
}
void solve()
{
double t = 5e5;
long long now = ans;
v1 = v3, v2 = v4;
int x, val;
while (t > eps)
{
if ((clock() - tim) * 1000 >= 980 * CLOCKS_PER_SEC)
{
cout << ans << endl;
exit(0);
}
x = neww() % (n - 1);
v5 = v1;
v6 = v2;
if (x < (int)v1.size())
{
val = v1[x];
v1.erase(v1.begin() + x);
v2.insert(lower_bound(v2.begin(), v2.end(), val), val);
}
else
{
x -= v1.size();
val = v2[x];
v2.erase(v2.begin() + x);
v1.insert(lower_bound(v1.begin(), v1.end(), val), val);
}
int delta = calc() - now;
if (delta < 0 || exp(-delta / t) > Rand())
{
now += delta;
}
else
{
v1 = v5;
v2 = v6;
}
t *= 0.999;
}
}
signed main()
{
tim = clock();
cin >> n;
for (rint i = 1; i <= n; i++)
{
cin >> a[i];
c[i] = a[i] - a[i - 1];
}
sort(c + 2, c + n + 1);
for (rint i = 2; i <= n; i += 2)
{
v1.push_back(c[i]);
}
for (rint i = 3; i <= n; i += 2)
{
v2.push_back(c[i]);
}
v3 = v1;
v4 = v2;
calc();
while (1)
{
solve();
}
return 0;
}
推荐例题
以下题目均可使用随机化润过
- CSP-S 2022 假期计划
- [HAOI2006] 均分数据
- [TJOI2010] 分金币
- Leaving the Bar
- [JSOI2016] 炸弹攻击
- Coloring
- RUNAWAY - Run Away
- Best Edge Weight