【2018.11.22】CTSC2018(模拟赛!)
太蠢了……$noip$ 后第一次模拟赛竟然是这样的……完全就是打击自信 / 降智……
1. 假面
一道神仙概率 $dp$!第一次写……
拿到题就发现血量 $m_i$ 的上限只有 $100$!
然后 $0$ 操作就可以用 $rate(i,j)$ 动态维护第 $i$ 个人血量为 $j$ 的概率啦。
$1$ 操作比较麻烦(但是它故意弄得很少)。
设 $live_i$ 和 $dead_i$ 分别为 $1$ 操作范围内的第 $i$ 个人活着和死了的概率,$g_{i,j}$ 是除 $i$ 以外有 $j$ 个人活着的概率。
第 $i$ 个人的答案就是 $live_i\times \sum_{j=0}^{k-1} \frac{1}{j+1}\times g_{i,j}$,其中 $\times \sum_{j=0}^{k-1}$ 是因为等概率攻击自己和其它 $j$ 个人(自己必定活着,因为自己的答案是命中自己的概率)。
但是 $g_{i,j}$ 怎么求?我们发现它的原型是这样一个 $dp$:设 $f_{i,j}$ 表示前 $i$ 个人有 $j$ 个活着的概率。
不难看出它是能递推出来的:$ f_{i,j} = f_{i-1,j-1} \times alive_i + f_{i-1,j} \times dead_i$
而且它最终转移出的总共 $k$ 个人的概率 与转移顺序无关,所以把当前求答案的这个人放到最后,然后不算他,推出的前 $k-1$ 个人的概率 $f_{k-1}$ 就是 $g_i$ 了。
每次最多有 $k$ 个人要求答案,套上述 $O(n^2)$ $dp$,时间复杂度是 $O(C\times n^3)$,能得 $70$ 分。
然后怎么优化?
$XJR$:我会 $FFT$!
不过他现场被卡成 $80$,事实证明 $200$ 个数的卷积算上常数 甚至比暴力还慢,$O(n^2\times log(n))$ 容易被卡成 $70$ 分。
$100$ 分就是(我)没弄过的一个操作了——倒推 $dp$。
什么意思?我们观察递推式 $ f_{i,j} = f_{i-1,j-1} \times alive_i + f_{i-1,j} \times dead_i$
它是可以简单反推的,即移项得到 $$f_{i-1, j} = \frac{f_{i, j} - f_{i -1, j - 1} \times live_i}{dead_i}$$
又因为答案与转移顺序无关,所以对于每个放到最后的要求答案的人,$f_{k-1}$ 可能会变,但 $f_k$ 一定不变。我们只需要从所有人的概率情况 $f_k$ 去掉当前求答案的人即可得到 $g_k$,而把这个人像上面一样放到第 $k$ 位时,由于上式可以从 $f_k$ 转移一次就得到 $f_{k-1}$,我们就可以一次求得 $g_i$。这样就不用像之前那样对于每个求答案的人重新从第 $1$ 到 $k-1$ 位递推一遍 $f$ 数组了(所以程序中的 $f$ 数组是一维的,最终存的是 $f_n$)。
$$f_{k-1, j} = \frac{f_{k, j} - f_{k -1, j - 1} \times live_k}{dead_k}$$
因为第 $k$ 个数是我们当前要求答案的第 $i$ 个人,所以 $live$ 和 $dead$ 的下标可以直接替换成 $i$,这样就省去了实际交换。
每次只是反推了一位,之前被各种博客无限误导为要整体反推一遍,然后无限瞎**理解,然后极其暴躁
2. 暴力写挂
我像是会边分治吗?
45pts:
$noip$ 难度,会写 欧拉序+RMQ 的 $O(1)$ 求 $lca$ 就行了。
100pts:
一个比较叼的线段树合并,作为一个初学者,别人的题解都好难看懂哦……杠了不少时间。
首先要知道这么一个不常用的计算链并长的方法:树上两点 $x,y$ 到根的链并长 = $[depth(x)+depth(y)+(depth(x)-depth(lca))+(depth(y)-depth(lca))] / 2$。
画个图就是
容易发现,四种颜色的边加起来之后,每条边都被算了两次,因此除以 $2$ 后每条边就只被算 $1$ 次了。
这里定义一个点 $x$ 的权值为 $depth(x)+(depth(x)-depth(lca))$。其中 $lca$ 会在之后枚举。
为什么要用这个?最后会提。
开始正题。
观察题目式子,发现前 $3$ 项是第一棵树上的,最后一项是第二棵树上的,好像不支持同时维护跨树的信息,所以我们枚举第二棵树的 $lca$。
也就是说,从第二棵树的根节点开始深搜遍历第二棵树。
那怎么解决第一棵子树?
我们注意到这样一个事情:一个点只对它的所有祖先节点有影响。
(这不是废话吗)
但正是这一点,让这个树上问题可以套个板子。
考虑一下不套板子的时候,直接做,怎么做?
如果我们固定了第一棵树的某个点为 $lca$,那我们只需要找这个点的所有子树中,子树中最大点权最大的两个,相加即可得到答案。
但我们只固定了第二棵树的 $lca$,所以我们可以反过来做,用第一个树中的点的权值更新其所有祖先节点。这样当之后祖先节点作为 $lca$ 时,只要取它被更新到的最大值和次大值,相加即可得到答案。
然而这样做复杂度并不对,因为树的深度一大,就有很多点有很多祖先节点,暴力更新的时间就炸了。
这时就可以套树分治板子了。我这用的是边分治(也可以用点分治做)。
众所周知,树分治就是通过重构树来让它尽量平衡一些,至少控制在 $log(n)$ 级别(二叉树)。然后我们就可以暴力枚举祖先什么的了。
而枚举第二棵树的 $lca$ 时,我们在之后对第一棵树做线段树合并时,只能枚举所有不能确定第一棵树的 $lca$
最新文章
- php 循环删除目录中的过期文件
- onclick事件与onserverclick事件
- Arrays类的十大用法
- SQL SERVER: 合并相关操作(Union,Except,Intersect) - 转载
- hdu 4961 Boring Sum
- 启动Memcache,出现memcached: error while loading shared libraries: libevent-1.4.so.1: cannot open shared
- iframe父子兄弟之间调用传值(contentWindow &;&; parent)
- iOS App上传中遇到的问题
- The method setOnClickListener(View.OnClickListener) in the type View is not applicable
- php 针对特殊字符进行转义
- VS2013中安装配置和使用Boost库
- 一个简单的Java集合范围过滤的多个方式对比
- python中星号的意义(**字典,*列表或元组)
- Hibernate学习笔记(5)---Query接口
- Jenkins+PowerShell持续集成环境搭建(四)常用PowerShell命令
- IDEA配置maven(配置阿里云中央仓库)
- Unity 3D UI Essentials 学习
- 【Java】 大话数据结构(8) 串的模式匹配算法(朴素、KMP、改进算法)
- LeetCode263——Ugly Number
- php打印负载函数、Linux awk打印负载
热门文章
- win10下vs2013为程序集新建强名称文件时“未能完成操作。拒绝访问”的解决方案
- jni ndk 入门
- 使用Google Colab训练神经网络(二)
- for..in...时,注意hasOwnProperty验证
- 两个input标签之间间隙问题的解决
- Mac电脑怎么显示隐藏文件、xcode清除缓存
- (49)zabbix事件是什么?事件来源有哪些分类
- GIMP用Path作画了解一下
- (三)Python3 循环语句——while
- Python-求解两个字符串的最长公共子序列