KickStart2018 RoundE

之前打的KickStart的E轮,是中午刚过的时候打的,但是做的时候不长,也只过了才3问,最后排名是585/2333。然后简单做个总结吧。

题目链接:https://codejam.withgoogle.com/codejam/contest/4394486/dashboard#s=p1&a=1

A

pass

B

题目的大意就是给你有m个人,每个人对奶茶的n个属性有0或1的喜爱,然后我们要买一份奶茶,使得大家的喜爱程度达到最高。在large数据下,n和m都<=100还有一个要求就是有p个方案是不能选的,这个p是min(100, 2^m)。

这个题的突破口就在于这个p的最大值是100,然后一个很重要的insight就是方案的选择可以每一位进行选择,也就是说我们可以对每一位进行从前往后的选择。然后既然最后是排除了p(100)个方案,那么我们每次找出p+1(101)个最大的就一定可以从这些最大的中找到最优解。然后至于怎么选择最大的,我们可以发现从第i个到第i+1个,只要暴力把之前的p+1(101)个加上0/1,也就是变成2p+2(202)个方案再从中找出101个就okay了。时间复杂度是O(plogm+m^2)。

我的代码如下:

C

待补充

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注