noip模拟19/20
这两场考试大部分的题都考过,然鹅有的 \(trick\) 忘了,有的当时咕了(虽然现在还咕着)
首先是 \(v\) 这道题需要加一个小优化,对于较小的状态应该直接用数组记录,较大的再用 map 记
然后就是这个神奇的 \(dp\) 题:
A. 玩具
考场上只会暴搜,胡了一个 hash 还给挂了
正解是神奇的 \(dp\)
首先核心是 \(f[i][j]\) 表示 \(i\) 个点的树深度为 \(j\) 的概率,那么期望即概率乘深度之和
考虑这个怎么转移:
如果想办法从 \(f[i-1][k]\) 转移,可以发现这个状态是不完备的,因为不知道 \(i-1\) 个点深度为 \(k\) 时各个深度的点各有多少个,那么加在每个深度的概率是不相同的
那么考虑这棵树最后加入的点是树顶那个点
因为树顶那个点加入前整个的深度是固定的为 \(j-1\)
那么问题又来了,如果加入的是树顶,那么原来所有的子树将形成一个森林,显然还需要一个变量维护森林的状态
那么设 \(g[i][j]\) 表示 \(i\) 个点的森林深度为 \(j\) 的概率,那么有
\]
接着考虑 \(g\) 的转移,可以想到从一部点形成的树外加另外的点形成森林来转移
假设树的大小为 \(k\),那么一部分是 \(f[i][k]\),发现另一部分的深度是不确定的,只要小于等于 \(j\) 即可
说明状态设计的有问题,那么设计成深度小于等于 \(j\) 就好了
\(f\) 的转移还是一样的
然后再看 \(g\) 的转移,发现还是有 \(bug\),因为总共有 \(j\) 个点,有 \(k\) 个点在第一棵树里,这是有概率的,那么继续打补丁——设 \(dp[i][j]\) 表示 \(i\) 个点的森林有 \(j\) 个点在第一棵树的概率
考虑转移,从 \(dp[i-1][]\) 转移而来,分为新加的点在不在第一棵树里两种情况,方程式为:
\]
这里需要注意看似上一种情况共可以向 \(i-1\) 个点连边,为什么分母上是 \(i\) 呢?
因为漏掉了一种情况就是新加的这个点其实是可以自成一棵树的,所以没有问题
这回终于可以转移 \(g\) 了:
\]
最后是统计答案,由于状态设计的是前缀和形式,那么答案需要减一下,即:
\]
最新文章
- oracleDBA-D3
- 从原生APK反编译,拿到界面,用于mono for android
- Hadoop 学习笔记(二) HDFS API
- Axis2(9):编写Axis2模块(Module)
- How to Create Dump File for Applications
- FaceBook页面加载技术
- Linux下undefined reference to ‘pthread_create’问题解决
- ajax中url赋json格式的值时发生中文乱码的相关问题
- mysql 查询正在执行的进程-亲试ok
- ----关于JS中迭代的三个“FOR”----
- Django 中的 model 继承
- Percona 数据库
- 借助python工具从word文件中抽取相关表的定义,最后组装建表语句-非常好
- flask 基本操作 模板语言 session
- (原)从mp4,flv文件中解析出h264和aac,送解码器解码失败
- bzoj1864 三色二叉树
- mysql/mariadb学习记录——创建删除数据库、表的基本命令
- CMD命令利用tasklist与taskkill关闭程序
- python文本挖掘模版
- InnoDB的三个关键特性
热门文章
- Couchdb 垂直权限绕过漏洞(CVE-2017-12635)
- noip模拟22[d·e·f]
- 【数据结构与算法】字符串匹配(Rabin-Karp 算法和KMP 算法)
- 表单验证插件jquery-validation以及案例
- Android Jetpack 架构组件最佳实践之“网抑云”APP
- 第一个Java文件
- Tomcat进程意外退出的问题分析
- pfx格式密钥库修改密码
- Java基础技术JVM面试【笔记】
- Ubuntu本地提权适配不同小版本内核(CVE-2017-16995)