【cf526X】ZeptoLab Code Rush 2015

2015年4月5日9853

懒得开多篇了,深夜口胡TAT 现在是凌晨4点。。。

A:King of Thieves

枚举起始点模拟

B:Om Nom and Dark Park

算出最大值,从最高层开始贪心,能加尽量加

C:Om Nom and Candies

设hb/wb为小于ha/wa即a的单位质量价值高

分类讨论

若wb很大,则可以枚举b取了多少个

否则a取的数量一定与c/wa相差不超过wb

分类暴力TAT

D: Om Nom and Necklace

我的做法是枚举A+B的长度,hash暴力

最后二分出A的最长长度T T,至于区间修改用差分前缀和就能完成

复杂度nlogn。。。FST

擦赛后加了个if(K*x>n)return;就卡过了T T。。。

正解kmpTAT详情请看官方题解。。。

E:Transmitting Levels

我的做法比较乱搞

先任意找个起始点划分一下。。。找最少个数的那段

最优解必然有一个断点在这一段中
枚举这一段的每个点作为起始点划分,根据该段的数量决定是每次二分下个断点还是暴力找

最后2.4s卡过

实际上只要预处理一下每个位置,最多能包含到向后什么地方,复杂度就可以变成On辣