Imy feat. 棗いつき —— Not Falling

懒得找歌了,用一首比较喜欢的。

51 [qoj9774] Same Sum

相对最小最大值去做集合哈希,两边的集合要一样。代码。


下午出去玩。

晚上打 CF1134(Div. 4),发现自己秒不掉后面的题,而且打着打着就困了,上了大学之后作息还是太健康了熬不动夜了。

一开始想去外面住酒店打,但这样一天就要 -300,我很久没讲过课了所以不太赚的到钱,再说吧。

确实能说明水平不足。记录后面两个做得奇异搞笑的题。

H. Extra Road

一开始得出了错误的观察:一定是根节点连向某个节点,这个观察基于根节点只有一个儿子。

那么发现它一定会连向树的叶子节点。

然后顺着这个做下去了!设 fif_i 考虑子树内要丢失的最小是多少(即断掉子树一条边),只有一个儿子是 ff,剩下的是 sizsiz,然后取最大值。

也就是说,将边连进去则可以“保住”,此时断这里的边的损失最大是 ff,否则是 sizsiz。

如果根节点真的只有一个儿子那么答案就是 n−f1n-f_1。然后样例 4 就错了。

否则我们对于两个儿子则可以通过连接这两个子树的某两个叶子来保住这两个儿子,那么挑 sizsiz 最大的两个保住就可以了。代码。

G2. Lakeside Trail

肯定是二分,当然,不要像我第一眼把 max⁡\max 看成求和。

梦碎 ICPC 2026 武汉,三个人没人会二分的,唉。

由于只能变高,因此高度至少需要是 yi=max⁡j(hj−D⋅dist⁡(i,j))y_i=\max_j\left(h_j-D\cdot \operatorname{dist}(i,j)\right)。直接枚举 G1 就做完了。

把距离的绝对值拆了,分成左边右边去维护。让左右都直接取 nn 个,这样比较方便,而且多取的一定不会使得答案变劣。两边都直接用滑动窗口做掉即可。

然后好久之后的第一次打 CF,在此期间代码习惯把 long long 都写成了 long,Linux 下 long 确实是 64 位,但是 CF 是 Windows,然后吃了一发。代码。


学习了拟阵。还没学完,剩下的才是大头。先做点别的。

52 [CF2258E] DivMEX

每个区间的答案形如 pkp^k。

我们直接枚举答案。一个答案合法,当且仅当能选择一个区间,这个区间里没有 xx 的倍数,并且 [1,x−1][1,x-1] 中的每个数都在这个区间存在倍数。对右端点扫描线,其出现位置都 ≥l\ge l 即可。

我们只针对形如 pkp^k 的东西去维护。nn 中这样的数只有 18120 个。

但是要注意答案的范围是可能大于 nn 的。代码。

53 [qoj3089] Harsh Comments

答案答案是 NN + B 在至少一个 A 前的期望个数,后者由线性性质可以对每个 B 单独统计,那么就是算每个 B 在所有 A 后的概率。

套路地,将这个分布转化成转化成指数分布,即 TT 的概率密度函数为 f(t)=xe−txf(t)=xe^{-tx},TT 越小的越先删除。

我们考虑 BjB_j:

Pj=P(TBj>max⁡i=1NTAi)=∫0∞P(t>max⁡i=1NTAi)⋅fTBj(t)dt=∫0∞(∏i=1n(1−e−Ait))Bje−Bjtdt=∫01BjxBj−1∏i=1N(1−xAi)dx\begin{aligned} P_j&=P(T_{B_j}>\max_{i=1}^N T_{A_i})\\ &=\int_{0}^{\infty} P(t>\max_{i=1}^N T_{A_i})\cdot f_{T_{B_j}}(t)\d t\\ &=\int_{0}^{\infty} \left(\prod_{i=1}^n(1-e^{-A_it})\right)B_je^{-B_j t}\d t\\ &=\int_{0}^{1} B_j x^{B_j - 1} \prod_{i=1}^N (1 - x^{A_i}) dx \end{aligned}

那个乘积是背包的形式,做成:

Pj=∫01BjxBj−1∑k=0Sckxkdx=∑k=0Sck∫01BjxBj+k−1dx=∑k=0SckBjBj+k\begin{aligned} P_j &= \int_{0}^{1} B_j x^{B_j - 1} \sum_{k=0}^S c_k x^k \d x \\ &= \sum_{k=0}^S c_k \int_{0}^{1} B_j x^{B_j + k - 1} \d x \\ &=\sum_{k=0}^{S} c_k \frac{B_j}{B_j+k} \end{aligned}

暴力跑背包把 ckc_k 求出来即可。


因此,需要重学概率论和母函数。

晚上打 ABC。虽然因为要讲训练赛只能打一半。

https://atcoder.jp/contests/abc484


Nothing built can last forever.
本站由 iznomia 使用 Stellar 1.30.4 主题创建。
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。