LOJ2229. 「BJOI2014」想法(随机化)
题目链接
题解
评分标准提示我们可以使用随机化算法。
首先,我们为每一道编号在 \([1, m]\) 以内的题目(这些题目也对应了 \(m\) 个初始的想法)赋一个 \([0, d]\) 以内的随机权值。接下来,我们可以通过 \(O(n)\) 的递推来求出每一道编号在 \((m, n]\) 以内的题目所包含的所有想法对应权值的最小值。记第 \(i(i > m)\) 道题目包含 \(x_i\) 个不同的想法,且这些想法对应权值的最小值为 \(w_i\),那么有 \(w_i\) 的期望值为 \(\frac{d}{x_i + 1}\)。
我们试着证明一下上述结论。在此之前,我们先思考一个值域较小但更为普遍的问题:在 \([0, 1]\) 内选择 \(x\) 个随机变量(变量之间互相独立,且在 \([0, 1]\) 内均匀随机),求选出的这 \(x\) 个变量中第 \(k\) 小值的期望。
我们将该问题做一个转化:求选出的这 \(x\) 个变量中第 \(k\) 小值的期望,等价于求再在 \([0, 1]\) 内选择一个随机变量,求选出的这个变量小于之前选出的 \(x\) 个变量中第 \(k\) 小值的概率。
经过转化之后的问题显然就很好做了。我们考虑按照数值从小到大给这 \(x + 1\) 个变量赋上排名。忽略变量相等的情况,那么这 \(x + 1\) 个变量的排名构成了一个 \(x + 1\) 的排列,且显然,产生各个排列的概率是相同的。\(x + 1\) 的全排列数为 \((x + 1)!\),我们考虑用合法的排列数除以全排列数来求概率,这样,问题转化为了求共有多少种 \(x + 1\) 的排列满足排列的最后一个位置的值不超过 \(k\)。显然合法的排列总数为 \(k \times x!\)。因此概率即为 \(\frac{k \times x!}{(x + 1)!} = \frac{k}{x + 1}\),那么可以得到在 \([0, 1]\) 内选出的 \(x\) 个随机变量中第 \(k\) 小值的期望也为 \(\frac{k}{x + 1}\)。
这个结论其实被直接放在了[ZJOI2015]地震后的幻想乡一题的提示中。
这样,当随机权值的值域为 \([0, d]\) 时,选出 \(x\) 个随机权值的最小值 \(w\) 的期望即为 \(\frac{1}{x + 1} \times d\)。若求得 \(w\) 的期望 \(E\),那么可得 \(x = \frac{d}{E} - 1\)。
对于第 \(i\) 个想法,我们可以通过多次随机化求平均数来得到 \(w_i\) 的期望的近似值。设随机化的次数为 \(T\),那么总时间复杂度为 \(O(Tn)\)。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m, from[N][2], a[N];
double answer[N];
int main() {
scanf("%d%d", &n, &m);
int M = 100000000 / n;
for (int i = m + 1; i <= n; ++i) {
scanf("%d%d", &from[i][0], &from[i][1]);
}
for (int tt = 1; tt <= M; ++tt) {
for (int i = 1; i <= m; ++i) {
a[i] = rand();
}
for (int i = m + 1; i <= n; ++i) {
a[i] = min(a[from[i][0]], a[from[i][1]]);
answer[i] += (double) a[i] / M;
}
}
for (int i = m + 1; i <= n; ++i) {
answer[i] = RAND_MAX / answer[i] - 1;
printf("%.0lf\n", answer[i]);
}
return 0;
}
最新文章
- Lua手动编译姿势
- iSight集成Adams/View:Simcode
- git SSH keys
- MVC2 Area实现网站多级目录
- HDU 2594 Simpsons’ Hidden Talents(辛普森一家的潜在天赋)
- Apache配置多个监听端口
- MonkeyRunner 连续两次点击报“Error sending touch event”
- MYSQL数据备份与还原学习笔记
- IO-03. 求整数均值
- 《R实战》读书笔记三
- [Linux]当一个棘手问题需要即可定位,如何协助开发,缩小定位范围
- Ubuntu16.04安装搜狗输入法后有黑边问题的解决方法
- 为神马精确Sprite的碰撞形状不通过简单的放大Sprite的尺寸来解决?
- java发送soapui格式的报文
- MyBatis 的动态 SQL 使用说明
- Android 弹性布局 FlexboxLayout了解一下
- python模块:xlsxwriter和xlrd相结合读取、写入excel文件
- hive学习02-累加
- git reflog
- JPEG
热门文章
- MySQL 系列(二)Jdbc
- Spring boot——logback.xml 配置详解(二)
- cucumber安装步骤
- 利用BeanUtils.copyProperties 克隆出新对象,避免对象重复问题
- user_mongo_in_a_docker_and_dump_database
- [leetcode] 11. Same Tree
- SQL Server创建表超出行最大限制解决方法
- TFS 2015新功能之一,当前迭代查询标记
- Centos7下修复 视频播放器(先 安装VLC视频播放器)
- VUE 学习笔记 三 模板语法