Java教程

2021牛客暑期多校训练营4 题解

本文主要是介绍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)\)
我们考虑对其进行二项式展开

\[\begin{align*} (e^x+g(x))^n$=\sum_{i=0}^n C(n,i)*g^i(x)*e^{(n-i)*x} \end{align*} \]

我们考虑\(e^{kx}\)的\(i\)次项系数怎么计算
这个这个很显然就是\(\frac{i^k}{i!}\)
因此我们暴力做多项式卷积，然后求和即可。

H

I

签到题

J

推一下式子即可发现答案就是两个序列的均值最大子段和相加，分数规划即可。

这篇关于2021牛客暑期多校训练营4 题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航