这次的题挺简单的,可惜了当时没做,错过一次好机会

A.Allocation

有 $N$ 个房子,每个房子单价为 $a_i$ 你共有 $B$ 块钱,求最多可以买多少个房子

分析

贪心

每个房子的收益都是 1,因此如果有两个房子 $A,B$, 一定是买价格低的最好

code

B.Plates

$N$ 堆盘子,每堆有 $K$ 个, 每个盘子的收益是 $a_{ij}$, 你可以取 $P$ 个盘子,不过限制是,如果你取了盘子 $A$, 必须要取走它上面的所有盘子,问最大收益,

分析

01背包的变种,相当于每堆盘子仅取一次,只需确定每堆盘子取的最大位置就好,

code

C.Workout

$N$ 个连续的数字,$a_{i+1}>ai$, 这个序列的收益是 $\max {a{i+1}-a_i}$, 你可以至多添加 $K$ 个新的数字,使得最小化这个序列的收益,问最小值

分析

二分

code

D.Bundling

$N$ 个字符串(仅包含大写),将他们分成 $N/K$ 个组,每个组 $K$ 个字符串,每个组的score是该组字符串的最长公共前缀

求最大化每个组的score的和

分析

这题很简单,建一棵trie 树 (前缀树), 每一个节点 记录这个节点的包含此节点的前缀个数(记为 $cnt$).

遍历这颗trie树,对每个节点($u->v$) 统计它的子树收益($ans$)以及需要使用的字符串个数($used$)

因此节点 $u$ 个收益为 $\sum v.ans +(u.cnt - v.used)/K*dep$. (dep 表示树的深度)

详细的计算公式可见代码(trie写的不好, :(, )

code

版权声明

本作品为作者原创文章,采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

作者: taotao

仅允许非商业转载,转载请保留此版权声明,并注明出处