CF EDU108 题解

[toc]

AC代码

A. Red and Blue Beans

B. The Cake Is a Lie

C. Berland Regional

有 $N$ 个人分别来自学校 $U_i$ ，能力值为 $S_i$ ，要求每个学校组成几支人数恰好为 $K$ 的队伍（不满 $K$ 不能组队）去参加比赛，所有参赛选手的能力值之和尽可能大，询问 $K$ 从 $1$ 到 $N$ 的所有最大能力值。

$\sum N\leq 2\times 10^5$ 。

拿STL暴力模拟一下就好了，先把每个学校的学生都丢到各自对应的vector里，然后从大到小排序后求前缀和，每个学校计算出对于所有 $K$ 的贡献即可。时间复杂度巨大，但是能过。

D. Maximum Sum of Products

给定长度为 $N$ 的数组 $A,B$ ，你可以翻转数组 $A$ 的一个连续子段，询问 $\sum_{i=1}^N A_iB_i$ 的最大值。

$N\leq 5000$ 。

枚举翻转中心，$O(N)$ 扫一遍，总复杂度 $O(N^2)$ 。