2021牛客暑期多校训练营4 题解
2021/12/4 6:16:48
本文主要是介绍2021牛客暑期多校训练营4 题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
A
B
C
D
E
考虑设\(1\)号点的权值为\(x\)
那么其它所有点的权值则可以得到确定。
且每个点的区间限制都会为\(x\)添加一个形如\(l_i \ge x^w_i \le r_i\)的限制
这个限制容易发现是\(trie\)树上的\(logn\)个子树
维护一下即可。
F
G
这是一个类似背包的问题。
我们考虑写出每个物品的生成函数。
\[\begin{align*} f(x)&=\sum_{i=0}^{\infin} \frac{1}{(i+k)!}*x^i \\ &=\sum_{i=k}^{\infin} \frac{1}{i!}*x^i \\ &=e^x-\sum_{i=0}^{k-1} \frac{1}{i!}*x^i &=e^x+g(x) \end{align*} \]然后我们需要计算的便是\(f^n(x)\)
我们考虑对其进行二项式展开
我们考虑\(e^{kx}\)的\(i\)次项系数怎么计算
这个这个很显然就是\(\frac{i^k}{i!}\)
因此我们暴力做多项式卷积,然后求和即可。
H
I
签到题
J
推一下式子即可发现答案就是两个序列的均值最大子段和相加,分数规划即可。
这篇关于2021牛客暑期多校训练营4 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南