HackerRank糊做

NanoApe posted @ 2016年7月06日 17:08 in 蒟蒻不做题提前退役 with tags HackerRank , 4481 阅读

Update:16.07.06

没连边的点，假如值为0则方案*2，否则直接加入方案

剩余的直接搜索

扫一遍， $f[a,b]$ 表示有向线段 $a-b$ 的右侧满足要求的点数， $Ans=\sum f[a,b]*f[b,a]$

具体而言，维护两个指针，先转一圈，转第二圈的时候就可以求得 $f[a,?]$

转成前缀和询问，设 S 为其总乘积，我们可以把一个种类的某些看成一个砖（例如重量为 i 的每 S/i 个弄成个砖）然后枚举没弄成砖的个数，预处理搞个背包玩玩（先 $f[a]-=f[a-S]$ 后 $f[a]+=f[a-i]$ ）再乘上砖的放置，用个组合数公式就把组合数合成一个

贪心大法，枚举次大值之后的最大次数，根据前 $D-1$ 大的数的总和要小于 $N$ 的限制可以算出最大值的个数，取个最优值

[回复]

zhouzixuan 说:
9 年前

woc这是啥...

NanoApe's Blog