Comet OJ - Contest #2 简要题解
Comet OJ - Contest #2 简要题解
A
模拟,复杂度是对数级的。
code
B
易知\(p\in[l,r]\),且最终的利润关于\(p\)的表达式为\(\frac{(p-l)(\frac{L+R}{2}-p)}{r-l}\),二次函数求最值即可。
code
C
枚举独立集点数即可。\(\sum_{i=0}^n\binom nip^{\binom i2}\)。
code
D
树上的任意一个满足\(|S|\ge2\)的点集\(S\)均有一个唯一的中心,即直径的中点(可能是一个点也可能是一条边),因此可以在该点集的中心处计算该点集的贡献。
枚举中心\(i\),枚举直径长度\(j\),要求在\(i\)点至少两棵不同子树里选与\(i\)距离恰好为\(j\)的点,距离小于\(j\)的点任选。复杂度\(O(n^2)\)。
code
E
原图是一片环套树森林。首先考虑把森林缩掉,对于一个叶子节点\(v\)与其父亲\(u\),可以令\(p_u\gets p_u+(1-p_u)p_vs_v\),并删除点\(v\)。如此操作后图中就只剩下若干个环了。
对于环上的任意一点计算答案,可以先把这个点的出边断掉,再视作一条链暴力计算,复杂度\(O(n^2)\)。考虑当前一个人以\(x\)的概率醒来的时候,后一个人醒来的概率可以表示成\(ax+b\)的形式,其中\(a,b\)均为只与当前这个人有关的常量。不难发现这种运算满足结合率,因此对环维护前后缀,每次\(O(1)\)合并答案即可,复杂度\(O(n)\)。
比赛的时候无脑上了棵线段树,做法上没有本质区别。code
F
orz suika
先求出\(F(x)=\prod_{i=1}^n(p_ix+1-p_i)\),然后对于每个\(i\),计算\(\frac{F(x)}{p_ix+1-p_i}\)与\(a_i\)数组点乘的结果。
为了方便处理,我们令\(w_i=\frac{1-p_i}{p_i}\)(题目保证\(p_i\in(0,1]\)),于是\(F(x)=\prod_{i=1}^np_i(x+w_i)\)。由于\(\prod_{i=1}^np_i\)是常数,故下文中均将其忽略。
不难发现问题大致是个退背包的模型,即先往背包里加入\(n\)个物品,然后每次删去一个。
假设当前求的是第\(k\)个物品的答案,考虑设\[F(x)=\prod_{i=1}^n(x+w_i)=\sum_{i=0}^nf_ix^i\\G(x)=\prod_{i=1,i\neq k}^n(x+w_i)=\sum_{i=0}^{n-1}g_ix^i\]
那么就有递推式
\[g_i=f_{i+1}-g_{i+1}w_k(0\le i<n,g_n=0)\]
将这个递推式暴力展开
\[g_i=\sum_{j=0}^{n-1-i}(-w_k)^jf_{i+j+1}\]
于是我们要求的东西就变成了
\[ans_k=\sum_{i=0}^{n-1}a_ig_i=\sum_{i=0}^{n-1}a_i\sum_{j=0}^{n-1-i}(-w_k)^jf_{i+j+1}\\=\sum_{j=0}^{n-1}(-w_k)^j\sum_{i=0}^{n-1-j}a_if_{i+j+1}\]
令\(coef_j=\sum_{i=0}^{n-1-j}a_if_{i+j+1}\),则\(ans_k=\sum_{j=0}^{n-1}coef_j(-w_k)^j\),多项式多点求值即可。求\(coef_j\)的过程只需要一个卷积,因此总复杂度\(O(n\log^2n)\)。
code
最新文章
- 【asp.net】Linux 部署 asp.net core 项目
- 超详细的Xcode代码格式化教程,可自定义样式
- 【转】oracle内存分配和调优总结
- Android自定义键盘
- linux笔记四-------用户和组的管理
- JetBrains WebStorm 安装破解问题
- 在jsp中常用的内置对象(5个)小总结和两种页面跳转方式(服务器端调转、客户端跳转)的区别
- SQLSERVER拯救某个时间点被误删除的数据
- stc89c52开发板遥控器解码 红外线发射 内置 eeprom 存储 串口显示编码
- 20150203一些移动端H5小bug解决
- Python编写一个Python脚本
- Jquery中index()问题
- 转义字符和ASCII
- 多线程并发 synchronized对象锁的控制与优化
- js 获取月份 格式yy-mm-dd
- C++基础-位运算
- pouchdb-all-dbs插件
- MySQL复制相关变量
- MiseringThread.java 解析页面线程
- vue项目中vux的使用