ASC46
BZOJ1919: [Ctsc2010]性能优化

BestCoder#44

SkyDec posted @ 2015年6月14日 12:58 in 杂乱无章 , 1423 阅读

 

题目4月份就出好了,星期一时管理员突然通知要用这套题了,于是开始忙碌了

原本的A是C题的弱化版,即A数组和B数组完全一样,这个只要把A数组所有数xor起来再*2就好了,找了几个验题人好像没有在第一时间看出来,然后管理员说太难了,感觉无言以对,于是临时脑补了一道模拟题。

原本A的pretest想造的弱一点,不包含40%的,但是一失手好像还是造出了这种情况。

比赛一开始A题一堆人WA了,我看了看都是没判40%,其中有个大爷这样判

B是一道临时脑补出来的傻逼题,一血10min才出感觉还是慢了点

C题是做BZOJ4017时想到的,那题我是先分治,然后转化成了这道题,于是复杂度O(nlognlogA),后来与JSB讨论了一下发现直接按位搞再树状数组就好了。脑补了下二分和树状数组搞这次的C好像不能1个log,于是就出出来了

原本n的范围是100W来着,后来还是开小了一点。。。

D题是某天晚上突然脑补出来的,应该是比C简单的,在校内模拟赛测试时也过了将近一半的人


29min时LayCurse爷交了一发跟标算很相似的代码,但是他每次都sort了,是2个log的,遗憾的是他连pretest都WA了

33min时有个小哥交了一发n^2感觉意义不明

然后alpq654321jiry_2都交了一发,然后都TLE了,皮球好像是2个log有一个还是平衡树的log,劼劼劼的代码并没有看懂

36min时LayCurse拿下了一血,然而他还是2个log的,跑了2S+,然而pretest的n只造到了14W

然后去造了个大数据把2个log给卡T了

39min时uwi交了2个log,然而他是Java,时限太大根本卡不掉

44min时xing89qs交了2个log的,给他点个蜡烛

46min时,第一个写标算的人出现了:zld3794955。然而他上界只开到2^60,点个蜡烛

期间,C充裕的时限受到了选手们的一致好评:

 

35min时,开挂小哥jiangshibiao把D给过了

63min时,uwi爷交了个类似标算的做法,然而他写了个暴力卷积,换个FFT应该就能过了

79min时,zld3794955过掉了D,成为本场第一个AK了pretest的选手

83min时,uwi爷过了D,成了本场第一个AK的选手

然后比赛差不多就结束了

C题最后挂了一半的人,大多数都是写了2个log或者上限开到2^60的选手

于是比赛就结束了

其实这场比赛C最难,D主要难在要写FFT而已,不知道为什么就只有3位选手过了

Avatar_small
nbdhhzh 说:
2015年6月14日 16:01

膜敦。窝感觉D比C难多了QAQ

Avatar_small
SkyDec 说:
2015年6月15日 18:01

@nbdhhzh: 找了几个验题人都是D一眼秒C想了一会儿

Avatar_small
nbdhhzh 说:
2015年6月15日 18:52

@SkyDec: 好难过啊QAQ,C主要以前做某题的时候YY了很多。。尽管没有做出那题但貌似是这题的正解2333


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter