2025.08.30打卡Day289

健康

• 1 点睡，7 点起床，最近睡前总是辗转反侧，连续两天没有做到 12 点前睡着了，怀疑是不够累或者午觉睡多了。
• 午睡 1.5 小时。
• 俯卧撑 100 + 仰卧起坐 100 + 深蹲 100。
• 跑步 3km，稍稍跑一点看看膝盖明天感受如何。

娱乐

• xin 计划，练好了光母鸡，狂刷青龙守护兽。

算法

强度有点高，主要是 2300 那道组合数学题有点麻烦。

Codeforces：

• https://codeforces.com/contest/1469/problem/D ，1700 分，先考虑用最大的数作为分母，可以轻易把其他除了 2 的数都变成 1。之后考虑 n 怎么变成 1，发现仅靠除以 2 有点太慢了，这说明我们可能还要留一个别的数，先除几次这个数，然后在恰好比这个数大时再把这个数给变成 1，之后再用 2 去变。由于 n = 2e5，通过尝试发现根号 n 还不够，但是三次根号 n 就可以了。
• https://codeforces.com/contest/332/problem/D ，2400 分，很容易想到考虑每条边贡献到答案中几次。枚举每条边 (u, v)，先钦定 u 是题目中说的能和 k 个点的集合相邻的点，那么看下 u 的度数是否真的不小于 k，是的话则强制选 (u, v) 这条边，再任选 k - 1 条，就是这条边在 u 为关键点时的贡献次数，类似的可以算 v 的。最后加起来除以 C(n, k) 就是答案了。这道题神奇的地方在于题给范围 C(n, k) 远远地爆 long long 了，但最后的结果居然不要求取模，事实上分析性质之后发现要满足题目的性质，k 远远取不了这么大，所以组合数不会很大。
• https://codeforces.com/contest/2077/problem/C ，2300 分，首先要发现实际上那个式子就是 0 的个数减去 1 的个数，然后发现前后缀的这个值是连续变化的，和是定值，所以想到使用均值不等式，可以发现一个序列的价值是多少仅取决于其包含多少 0 和 1，与他们具体怎么排布的无关。知道了这个，就可以考虑进一步的计算了。算总代价一个朴素的思路是枚举 0 的个数和 1 的个数，算有多少种这种序列，然后乘以价值，大概就是对 C(cnt0, c0) * C(cnt1, c1) * (c0 - c1)^2 进行求和，但这样会有一个 O(n^2) 的枚举，并且那个差的平方不太好处理，不太容易优化。另一个思路是我们从直接计算所有 (c0 - c1)^2 的和入手，这个可以拆分为 c0^2 + c1^2 - 2 * c0 * c1，平方项的快速计算甚为容易，例如只需要枚举 c0，即可得出满足序列中出现 c0 个 0 的序列个数。对于交叉项，我们枚举 c0 和 c1，发现是两个非常典的组合数相乘，这两个组合数可以用二项式定理的系数去理解，求个导带入值即可得到封闭形式，即可以 O(1) 计算。至此，我们发现我们可以 O(1) 计算这三个项分别的和，计算时只需要知道当前整个串有几个 0 和 1，所以题目单点修改后查询就很好搞了，即使是区间查询也是容易做的，只不过需要使用数据结构去维护 0 和 1 的个数。