Round A 2020

3. Workout

用二分猜想法，每次猜想一个最小困难值，然后计算要达到这个值需要插入多少session，如果插入的session数不大于K则困难值合法猜想次数最多为 $log(10^9)\approx 30$，每次验证需要扫描一遍即 $10^5$，所以复杂度还好在网上看到另一种方法，就是用最大堆，每次弹出最需要划分的那个，划分数+1，然后塞回去，直到用完所有划分额度，这样的复杂度还低一点

4. Bunding

这题确实需要依赖一些特别的数学性质；我们先证明一个引理：最好的分组方法，就是每次取出当前相同前缀最长的一组；例如若将下面分为两组，则一定是先取234行，再取156行 ABCD ACDE ACDF ACDG ADEG BEFG 用归纳法证明，如果当前应该取出的那组贡献为 $G_0$，但它被拆开取出，拆开后每组贡献为 $G_1$, $G_2$, …, $G_k$，不妨设 $G_1\le G_2\le ...\le G_k\le G_0$，则未拆开前的总和 $\ge G_1+G_2+...+G_{k-1}+G_0\ge G_1+G_2+...+G_k$，故不拆开一定不比拆开差至于如何用这个引理计算我们的 $SUM$，还需要一个推论：若一个前缀出现的数量为 $CNT$，则它对 $SUM$ 的贡献为 $\lfloor CNT/K\rfloor$；证明为，由于每个前缀都会被尽可能连续地取出，所以它一定会填满 $\lfloor CNT/K\rfloor$ 组；剩下的填不满，贡献为0官方建议用Trie数来计算出现的前缀数量，我觉得也许先排序然后相邻的两两比较也行