题解

A.Bunny的平均数

对于50%的数据

自由发挥

对于100%的数据

根据平均数的定义，平均数M=∑i=1NaiNM=\frac{\sum\limits_{i=1}^{N}a_i}{N}M=Ni=1∑Nai。现在已经给出了N−1N-1N−1个数和平均数，把式子左右两边同乘NNN，得M⋅N=an+∑i=1N−1aiM\cdot N=a_n+\sum\limits_{i=1}^{N-1}a_iM⋅N=an+i=1∑N−1ai，即M⋅N−∑i=1N−1ai=anM\cdot N-\sum\limits_{i=1}^{N-1}a_i=a_nM⋅N−i=1∑N−1ai=an。所以对给出的N−1N-1N−1个数求和，将N⋅MN\cdot MN⋅M减去这个和即为答案。
std：
https://paste.ubuntu.com/p/zdyWFKTjtG/

B.Bunny的任务

对于50%的数据

直接深搜即可。搜索所有做任务的可能，在所有合法的任务顺序下取最大的答案。

对于100%的数据

贪心地想，要在有限的时间内做尽可能多的任务，就必须从耗时小的任务做起。所以对aaa从大到小排序，O(n)O(n)O(n)统计前缀和小于等于TTT的地方最大在哪里，输出答案。
std：
https://paste.ubuntu.com/p/NHZmN4xgmV/

C.Bunny的修路工程

对于30%的数据

nnn 很小，直接暴力搜索边是否选择。

对于50%的数据

给 O(n2)O(n^2)O(n2) 的做法通过，自由发挥。

对于100%的数据

我们可以贪心的思考，每一个城市都往最近的一个大商场前进。
那么就将所有有大商场的城市都加入队列，并向外一层层拓展，如果拓展到的点是遍历过的则不加入队列并删除拓展所走的边，否则加入队列。
我们来证明这样的贪心是正确的。
由于题目中说“原来的兔子王国已经满足了兔子们的要求”，那么可以保证每一个点都是可以往最近的大商场走的，不会不满足最多走 ddd 条路的限制。
设 kkk 为有(一个或多个)大商场的城市数。
想象一下，将有大商场的城市与离他最近的其他城市看成一个点，那么缩点完后有 kkk 个点。因为原先是树，缩点后也依旧会是树。
那么多余的边数就是 k−1k-1k−1，用来连接这 kkk 个点的边。
以上证明了答案的可行性，接下来我们证明 k−1k-1k−1 是最大能删的边数。
我们假设能删除 k+t(t>=0)k+t(t>=0)k+t(t>=0) 条边，那么就说明缩点后的树有 k+1+tk+1+tk+1+t 个点(缩点意义上)，而我们只有 kkk 个城市有大商场，那么至少有一个点是没有大商场的，因此不可能删除这么多边。
至此，我们证明了 k−1k-1k−1 是最大的答案。
那么就不需要实现bfs了，直接去重得到 kkk 就好了。
std：
https://paste.ubuntu.com/p/BpRjWBxcFd/

D.Bunny的聚会

D Bunny的聚会

10%的数据

显然可以直接爆搜，爆搜每一步让哪一只兔子往哪里走。

复杂度O((2n)k)O((2n)^k)O((2n)k)。

20%的数据

这里保证兔子的位置单调递增，显然最终的答案是把一段连续区间里的兔子全部聚在一起，那么我们可以枚举这段区间的左右端点，枚举把兔子聚集到的位置，判断是否能让这段区间内的所有兔子都到达那里。

用最暴力的方法实现，复杂度O(n3max⁡{ai})O(n^3\max\{a_i\})O(n3max{ai})。

35%的数据

我们可以证明对于一群兔子，设他们的位置为aia_iai，使它们聚集到同一个点时总路程长度最小的位置，是它们的中位数。

考虑若当前把兔子聚集到位置ppp，若ppp不是中位数，则有∑[aip]\sum[a_ip]∑[aip]。

若∑[ai∑[ai>p]\sum[a_i \sum[a_i>p]∑[ai∑[ai>p]，则若它们聚集在p−1p-1p−1，总路程减少∑[aip]\sum[a_ip]∑[aip]。
若∑[ai∑[ai>p]\sum[a_i \sum[a_i>p]∑[ai∑[ai>p]，则若它们聚集在p+1p+1p+1，总路程减少∑[ai>p]−∑[ai<p]\sum[a_i>p] - \sum[a_i<p]∑[ai>p]−∑[ai<p]。