AC. 梦想

frank_c1

Codeforces.初体验

发布于2015年11月28日 | 暂无评论 | 1,271阅读 | 比赛经历

昨天终于上了Codeforces,真是有点小激动~~~

之前因为一些奇怪的原因一直登不上去(CAPTCHA君~),昨天弄好后终于可以上去了。一登上去就看到晚上刚好有一场比赛:Educational Codeforces Round 2,一冲动就点了Register。看了下时间,蛮好18:00,然而我忘了Codeforces并不是中国的,所以时区并不是UTC+8……换算一下是北京时间23:00开始,凌晨1:00结束。为了体验一把CF的快感,我也豁出去了,就姑且熬夜一晚吧。

比赛前查了点资料,了解到这场比赛Div. 2难度(普及+/提高),2小时6道题,语言当然是英文啦。想想平时3个半小时才做3道题还是中文题目,顿感压力山大。找了道Round#333的A来做,倒还是蛮简单的,然而B一眼觉得简单,就是打不对,感觉要弃疗了。

晚上回到家大概10点,洗漱一下准备一下就快到11点了。人生中的第一次CF哦~! 比赛页面

A. Extract Numbers

给定一些字符串,不同字符串用','或';'隔开,把所有数字串找出来。

蛮简单的一道题,10来分钟就打完了。打完一看不对,没有规定一定是整数,赶快改。改完上交,WA。回来一看,咦什么时候题目改成限定为整数了,都不早点跟我说一声。接着改完又WA了。冥思苦想到0:04左右突然发现有一个特别SB的BUG,当时都不知道该说什么好了……一共WA了6次,改完终于AC,马上转战B。

B. Queries about less or equal elements

给定数组A,B,对于B中每个位置j,输出A中有多少元素小于等于Bj

特简单的一道题,脑子不用动就能做出来。然而熬夜打CF时估计神智不太清醒,这么简单的一道题也WA了一次。

C. Make Palindrome

给定一个字符串S,可以改变其中若干个字符,使之重排后可以变成一个回文串,要求改变次数最少(重排不计改变次数),输出最终的回文串,如果有多个则输出字典序最小的。|S|<=2*10^5

一开始以为是DP。但是一看数据量笑了,80%可以贪心直接搞。注意到变成回文串时不需要考虑顺序的,那么就好办了。我们考虑回文串的特点,如果长度为偶数那么每个字符一定出现偶数次,如果长度为奇数次那么有且仅有一个字符出现奇数次,其余字符均出现偶数次。那么有一个显而易见的贪心:如果已有两个相同的字符,一定不会改变其中任何一个。于是我们求每个字符出现次数模2的结果,如果是0就不需要考虑了,剩下的字符是最主要的部分。

先把留下来的字符排序。可以看出这些字符仅出现1次,根据上述结论,我们需要把这些字符的出现次数改成要么是2,要么是0。因为最优策略中1次修改可以让一个字符次数加1,另一个字符次数减1,想要字典序最小,把后一半改成前一半不就好了嘛。如果长度为奇数,那我就留下最中间的字符。

至此,基本上所有的字符都成双成对了。剩下输出就很简单了,从小到大输出,特判奇数即可。

D. Area of Two Circles' Intersection

题意就是题目,求两圆相交部分的面积。每个圆用整数x,y,r描述,表示坐标和半径。-10^9<=x,y,r<=10^9。输出结果和答案相差不能超过1e-9。

做这题时只剩15分钟,要不是实在裸的可爱我也就不做了。分情况讨论即可,需要用上一点几何知识。

其实打完后我虚的很,因为是10^9数据量,最坏情况下要20多位有效数字,计算过程一不小心double就会爆。又不会神奇的搞法,没办法只能交了,然而竟然过了Pretest,数据蛮水的嘛。
 
(E,F没时间看了,以后有空补上。)

 

2小时的Coding转瞬即逝,凭借4题成功挤到Rank170。然后发现了一个神奇的现象,我的排名在唰唰的上升。嗯,肯定是都知道D题有精度问题了,都在疯狂cha人呢。终于上升到140时,我的D也荣幸地被cha掉了。然后排名瞬间爆炸,变成450啦。哎,洗洗睡。

早上起来一看,咦,Rank345啦,D题基本被cha光啦(看来志同道合的人不少)。蛮好~

刚刚才知道,鉴于这是Educational Round,貌似Hacking开放24小时,而且System Test结束以后还不算总分,不计rating。让我这么辛苦地打到凌晨1点,真是不知道说什么好了,权当熟悉比赛环境吧……

无论如何,这次体验让我发现了Codeforces的好玩和有趣之处。下面两次比赛都在工作日的凌晨,真巧,貌似都没法打。那么,期待下一次在双休日的Round哦!

[upd] Final Standing:Rank 331