ASC46
BZOJ1919: [Ctsc2010]性能优化

BestCoder#44

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

 

题目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

Avatar_small
UK Board Question Pa 说:
2022年8月16日 18:09

Uttarakhand Board Model Paper 2023 Class 3 Pdf Download with Answers for English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer,

Avatar_small
Grade 8 Result Dhaka 说:
2022年8月31日 14:26

Bangladesh Education Board DPE has conducted the class 8th grade of Junior School Certificate Exam and Junior Dakhil Certificate Exam on 1st to 15th November 2022 at all centers in division wise under Ministry of Primary and Mass Education (MOPME), and the class 8th grade terminal examination tests are successfully conducted for all eligible JSC/JDC students for the academic year of 2022. Grade 8 Result Dhaka The Bangladesh government Minister of Secondary Education is going to announce the JSC Result 2022 in student wise for division students in education board wise, and the result documents will be submitted to the Prime Minister of the country after then the result with mark sheet will be announced to public to check the individual result.

Avatar_small
Uttarakhand 6th Cla 说:
2023年9月21日 18:10

Uttarakhand High School Students can Download the Textbooks for Academic Education Study Further uses, we have given more information about the Uttarakhand Board 6th Class Book, This Study Material Prepare by Uttarakhand Education Board Senior Experts,Uttarakhand Class Books Should be Followed as the Prime Resource Throughout the year to Clear All Doubts and Strengthen your knowledge. UBSE Uttarakhand 6th Class Books 2024 Class Textbook 2024 Provides an easy Explanation for Various Concepts in the Curriculum. Our Portal are Providing the Latest Verition of Uttarakhand Book 2024 which is Published by the Board Of School Education, Government of Uttarakhand. All the Chapters can be Downloaded in the form of PDFs.


登录 *


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