Bubble Cup 9 - Finals [Online Mirror] 题解

A. Festival Organization

很显然，设 fi 表示长度为 i 的满足条件的01串个数，那么有：

fi=fi−1+fi−2,f1=2,f2=3

这只是将传统的 fib 序列左移了一下，反正答案是形如 solve(r)−solve(l−1) 的，因此将 l,r 分别加 2 当作fib来做就可以了，以下的 fi 均表示下标从 1 开始的fib序列。

考虑我们现在要求的就是这样一个前缀和： ∑i=1n(fik)

看上去就好难的说，我们考虑一下 (xk) 其实就是变量为 x 的一个k次多项式，因此我们可以求出每项前面的系数 ai ，然后我们的任务就变成了求出：

∑i=0k⎛⎝ai⋅∑j=1nfij⎞⎠

所以我们现在的目的就是要求对于一个固定的 i ，∑nj=1fij的值。

这个东西的计算方法我们考虑 fib 的通项：

fn=15√⋅⎛⎝(1+5√2)n−(1−5√2)n⎞⎠

令 φ=1+5√2 ，那么原式就是：

fn=φn−(−φ)−n5√，因为1+5√2⋅1−5√2=−1

考虑 fij 怎么求，其实很简单，还记得复数是怎么表示的么，我们用 a+bi 来表示，那么这里我们可以用 a+b⋅5√ 来表示值，然后重定义加减乘除即可，这个就是很简单的了。

现在我们考虑怎么求 fij 的前缀和，根据二项式定理展开 fn 的分子，然后第 x 项形如：

(ix)φjx(−(−φ)−j)i−x

虽然有点小复杂， 但是可以看出 j 从1⋯n这个东西构成了一个等比数列，简单讨论一下正负号然后等比数列求和即可。

注意公比为 1 要特判。

B. R3D3’s Summer Adventure

很显然这是一棵树，而且01个数是相同的。

想一下如果要求 O(nlogn) 做法的话，我们有一个很好的贪心做法，就是最开始一棵空树，然后每次选权值最小的链，将其扩展出两个孩子。

仔细思考一下这个做法，我们发现假如我们给树上每个节点的权值定义为到根权值和，那么除去所有的叶子结点，其他的非叶子结点可以看成是权值从小到大依次出现的，因为根据前面的那个贪心做法，我们是从小到大扩展了所有的非叶子结点。

那么考虑非叶子结点权值和，假设根节点权值为 0 ，那么还要加上(n−1)⋅(c0+c1)才能满足要求（因为考虑以某个节点为根的子树，那么他自己的贡献被计算了子树大小次，然而叶子结点是=非叶子结点+1的，因为这个1的差距我们要加上这个东西）。

那么现在我们的问题就是求出权值从小到大的 n−1 个点的和即可，假设 c0<c1 。

考虑二分一下最大的权值，假设为 C ，求出所有≤C的结点个数，找到第一个 ≥n−1 的即可。

根据贪心原理，那么一条链上 c1 的个数 i 不会超过log2n，因此我们可以枚举 c1 的个数，然后求出 c0 个数的上界 j=⌊C−i⋅c1c0⌋ ，求出这个东西：

calc(C)=∑i=0log2n∑k=0j(i+ki)=∑i=0log2n(i+j+1i+1)

求出了最大权值 max 后，那么我们的答案就分成了两部分，一部分是等于 max 的，另一部分是小于 max 的。

等于的很好算，就是 (n−1−calc(max−1))⋅max 。

考虑小于的，可以写成：

∑i=0log2n∑k=0j(i⋅c1+k⋅c0)(i+ki)=c1⋅∑i=0log2ni⋅(i+j+1i+1)+c0⋅∑i=0log2n(i+1)⋅(i+j+1i+2)

嗯，就是这样了。

C. Potions Homework

排序即可。