【Comet OJ - Contest #2】题解

## 【Comet OJ - Contest #2】A. 因自过去而至的残响起舞 ### 题目描述 设 $f_1=f_2=1$，且对于 $i \ge 3$，有 $f_i=\left\lfloor \frac{\sum_{j=1}^{i-1}f_j}{2} \right\rfloor$ 求一个最小的 $n$，使得 $\sum_{i=1}^{n}f_i>x$ 其中 $1 \le x \le 10^{18}$ ### 题解 设 $S$ 是 $f$ 的前缀和，则 $S_i=S_{i-1}+\left\lfloor \frac{S_{i-1}}{2} \right\rfloor$ 大体上是每次乘以 $\frac{3}{2}$，因此 $S_i$ 可以近似为 $\left(\frac{3}{2}\right)^i$ 指数函数的增长十分快，于是 $n$ 的级别是 $O(\log x)$ 级别的 ## 【Comet OJ - Contest #2】B. 她的想法、他的战斗 ### 题目描述 $Takuru$ 是一名情报强者，所以他想利用他强大的情报搜集能力来当中间商赚差价 $Takuru$ 的计划是让 $Hinae$ 帮他去市场上买一个商品，然后再以另一个价格卖掉它 $Takuru$ 会给 $Hinae$ 一定的钱 $p$，其中 $p$ 是一个非负的实数 这个商品的市场价是一个在 $[l, r]$ 内均匀随机的实数 如果 $p \geqslant \text{市场价}$，那么 $Hinae$ 会买下这个商品，然后私吞剩下的钱 也就是说，$Takuru$ 以 $p$ 的代价买来了这个商品 如果 $p <\text{市场价}$，那么 $Hinae$ 既不会买下商品，又不会私吞任何钱 也就是说，$Takuru$ 的利润为 $0$ 当 $Hinae$ 买下了商品后，$Takuru$ 会生成一个在 $[L, R]$ 内均匀随机的实数 $q$，并把商品以 $q$ 的价格卖掉 那么 $Takuru$ 的利润就是 $q - p$ $Takuru$ 想要获得最多的利润，所以你要帮 $Takuru$ 确定给 $Hiane$ 的钱 $p$，使得 $Takuru$ 的期望利润最大 请求出最大的期望利润 其中 $1 \le l < r \le 2000, 1 \le L < R \le 2000$ ### 题解 首先一定有 $p \in [l,r]$，因为如果 $p<l$ 那么答案是 $0$，如果 $p > r$ 那么不如 $p=r$ 更优（超过 $r$ 的钱被吞了） 答案就是： $$ \begin{aligned} &\max_{l \le p \le r} \left( \frac{\int_{l}^{r} [x \le p] \left( \frac{\int_{L}^{R}x \mathbb{d}{y}}{\int_{L}^{R}1 \mathbb{d}y} -p \right) \mathbb{d}x}{\int_{l}^{r}1 \mathbb{d}z} \right) \\ =&\max_{l \le p \le r} \frac{p-l}{r-l} \left( \frac{L+R}{2}-p \right) \end{aligned} $$ 也就是答案是一个关于 $p$ 的二次函数，不妨写成 $ap^2+bp+c$ 的形式，其中： $$ \begin{cases} a= \frac{1}{l-r}\\ b= \frac{(L+R+2l)}{2(r-l)}\\ c= \frac{l(L+R)}{2(l-r)}\\ \end{cases} $$ 那么最大值只会在端点处或者 $-\frac{b}{2a}$ 取到（如果在定义域内的话） ## 【Comet OJ - Contest #2】C. 言论的阴影里妄想初萌 ### 题目描述 $Takuru$ 是一名能力者，他在地震时获得了念力致动的能力 所以他经常用自己的能力去干一些奇奇怪怪的事情 有一天他获得了一张 $n$ 个点的无向完全图，之后他使用了能力，导致这张图的 $\frac{n(n-1)}{2}$ 条边中的每一条都有 $\frac{x}{y}$ 的概率遭到破坏而消失 现在 $Takuru$ 想知道这张无向图点集的全部 $2^n$ 个的子集中，是独立集的子集数量的期望值 一张无向图 $G$ 的一个子集是独立集的定义如下：此点集 $S$，满足对于任意的 $x, y \in S$，图 $G$ 中不存在连接 $x$ 和 $y$ 的边（空集也是一个合法的独立集） 其中 $1 \le n \le 10^5, 1 \le x \le y < 998244353$ ### 题解 考虑每个点集的概率，加起来就是总的期望 那么答案就是： $$\sum_{i=0}^{n}{n \choose i} \left(\frac{x}{y}\right)^{{i \choose 2}}$$