OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

〖CTSC2015〗Hello,world!

【前言】

本来是打算APIO结束后一起写总结的,不过这短短几天的感触远远超过了自己的想象,所以就单独写一篇总结啦~

然而我写完这篇总结时APIO都结束了,这句话是临时加的,我也不想单独写APIO的总结了。

很遗憾,这是我第一次参加CTSC,真的很希望不是最后一次QAQ

为什么以“Hello,world!”为题?因为我觉得这次的比赛让我对OI的认识提升了一个新台阶(其实就是被教做人了sad),也让自己的目标更明确,为自己接下来的路增添了动力。感觉是一个新的开始,所以就用“Hello,world!”啦~

现在,记录下我的CTSC2015经历吧~

【Day0】

初到北京,来报到的时候就发生意外了……

非常sad,不想回忆了……就当什么都没发生好了……

报到,领胸牌和T-shirt,还拿了一大堆花花绿绿的册子,看来是人大的招生册什么的。由于提前一天就来了,所以算是最早报到的一批次了,房间很迷醉,三人间强行加床变四人间,一个人先来,所以默默选了那个小房间。

去人大找了找地方,然后去吃饭,餐厅挺不错的。见到了iwtwiioi,感觉好神啊~似乎WC的时候和他交谈过的,可惜当时没认出来,真是sad,这次可以近距离膜一膜了~

下午去面基dx,顺便膜了所有到CTSC来的CQ神犇,中途还有FJ神犇到访。CQ省队胡策题感觉很nice,题面令人狂死乱舞,但很有意思的样子,至少胡策这件事就让人觉得很有意思QwQ给大家分享了几道被封印的SCOI2015题(题面都不公开简直差评),大家觉得非常沙茶,然而我就是跪在了这些题上TAT

跟着巴蜀中学某学长参观了人大,感觉人大校园挺好的,不过似乎稍微偏文科了一点不太适合我的风格啊0.0去试机的时候已经比较晚了,好在试机题非常和谐w

晚上叶老师带我见了cxm和GFS,顺便一起吃晚饭。听cxm摆谈了许多事,感觉挺长见识的,对未来的规划需要在大学时决定好,不过在进入大学之前还要让自己不断地变强啊,进入大学之后发展方向就和现在大不一样了啊,但愿能有一个丰富的大学生活吧~感觉GFS高三就实习很不错的样子,只是因为之前不认识所以没有交流太多╮(╯▽╰)╭听说cxm要来负责一些CTSC的工作?感觉有大腿可以抱了~

稍微聊了一些国家队的情况,去年直接浙江队简直无敌,可惜我们学校这几年除了cxm似乎都在NOI以后默认退役了sad如果能有机会的话,我还是很愿意继续冲下去的,结果倒无所谓,我喜欢的只是学的这些内容和学习的过程。晚上回宾馆,室友已经来了,另外三人都是成都七中的,大家以前基本上都见过,所以交流起来并没有什么隔阂,互相交流了一下情况,感觉挺开心。明天就要Day1了,早早睡觉,愿不滚粗TAT

【Day1】

北京的太阳真刺眼,而且四五点的时候天就大亮了,好多人都以为起晚了……

要开始了好激动啊,看了看文件夹,发现有提答,感觉人生有了奋斗的方向~

先说说题意啦~

T1好朋友:给出一张n个点m条边的无向连通图,每个点有一个点权,每条边有一个长度和宽度,定义一条路径的长度为路径上的边长度之和,一条路径的宽度为路径上的边宽度之积,一个三元组(s,t,u)对u这个点的值的贡献为s到t路径的最短路中经过u的路径的宽度之和,乘上s和t的点权后再除以s到t所有的最短路的宽度之和,求每个点的值。

这个题我不会做,但n^3大暴力还是会写的,20pt到手~有部分数据m=n-1?又有20pt到手~感觉可以优化一下rush一下n<=1000的数据?不太科学的样子,一定是我想多了TAT

然后就被毕姥爷感动了,常数小的n^3直接怒切95pt下来……

正解是O(nmlogn)的DP,不知道和n^3哪个快……

怪自己不敢大胆暴力吧……不过不知道数据强弱的话其实写40pt是比较稳的?

T2葱:给出二维平面上的n个点,相邻两点间有一条线段,支持加入一个点,每次询问给出一条直线,询问这条直线与多少条线段相交,要求在线并支持询问历史版本。

Orz如此神的计算几何+数据结构我当然不会做……读完题后斟酌一下,决定去做提答比较合适。正解似乎是可持久化平衡树套可持久化平衡树来着?总之吉丽爷似乎用kd-tree怒切此题Orz

T3尺规作图:给出单位线段,有三种可行操作:连接两点并得到一条直线,以一个点为圆心、两个点之间的距离为半径画圆,标记两个已有图形的交点。要求作出点(L0,0),并尽量最小化操作次数,其中L0的鬼畜程度请自行脑补=.=

这个题我不太会做,但由于是提答题,所以开场就一通乱搞,一开始题面上描述的评分参数写反了,当我觉得第一个点很沙茶秒掉时,checker返回一个0分sad

然后有人来改题,瞬间就感觉不太可做了sad

强上每个点,无视次数直接乱搞,基本上都能混到1pt~2pt的样子,加起来大概有15pt的样子,感觉不能坑在提答上了,所以先去做了一波前两题。再回来看这题,静下来推了推,解决了第四个点,10pt到手~然后YY出了用相似来平方的办法,于是前三个点得分都拉高了一点,大概又有10pt到手~发现第一个点和第十个点答案很相似,直接复制过去,稍微改了改,又是4pt到手~现在提答大概有30pt的样子,本来想rush一下倒数和平方根的求法,但时间不太够的样子,最后提答题一共到手了34pt,对这题来说算是一个挺不错的分数了QwQ

出了考场没去吃饭,直接回宾馆倒头就睡……

然后下午就差点迟到了……得分74pt,感觉还行,给cxm说了自己的分数,他马上问我找到自己哪里写挂了没有……maya听这意思看来这分太低了,多半连Cu线都够不着……看来要滚粗了,我对不起大家……

去听讲评,各种跪跪跪sad吉丽爷221怒屠全场,然后国家队标准分166,非队爷第二136……跪吉丽,添动力啊。按毕姥爷给的那分数,估计有50~60人100+,看来我要排到三位数sad

晚上稍微做了会儿题就去睡了,明天还要听答辩,本来就没抱太大希望听懂,再不早睡就只有补觉了……

【Day1.5】

六点就起来了,感觉没什么事儿做就直接去教室了。选了个很靠前的位置,准备近距离膜一下各位候选队爷。前面坐着iwtwiioi和laekov,感觉各种跪跪跪,连王教授都差点以为他们是准备答辩的ovo

然后就是答辩了,没预习感觉简直飞起来了……

有三篇是关于字符串的,其中两篇都是SAM相关,感觉不好好掌握SAM就要滚粗了啊。命题报告是什么神奇的东西0.0以前没听说过怎么破TAT其他比较有印象的,就是鏼爷的生成函数,令有公式恐惧症的窝狂死乱舞;松爷的仙人掌,松爷还被问到仙人掌在生活中有什么用处,似乎并没有什么卵用;vfk的集合幂级数,感觉好神奇啊指数还可以是一个集合ovo然后就没有然后了,各种不明觉厉sad

cxm和GFS也在答辩现场,所以抱他们大腿去吃午饭,竟有幸在路上遇到了vfk,然后就听cxm和yly介绍各种五道口技术学院相关,cxm还传授了如何使用内嵌汇编强行氧气优化,感觉非常神奇。跟在vfk后面走回宾馆,好激动啊可惜没怎么交流sad

下午去国家博物馆社会参观,感觉好厉害啊。往返路上共花费2.5小时,参观共花费0.5小时,没看什么就要回去了。卓神在车上讲自动机感觉好神啊,Idy问我ScapegoatTree的删除,发现自己都忘了怎么写了sad晚上也没干什么有意义的事儿,随便复习了一下就准备去睡了,忽然有一种要胸牌回家的感觉,赶紧上QQ去膜(shui)了一圈,然后碎觉。

【Day2】

今天还有提答题?感觉又可以提答+暴力了,感觉昨天做得还不错,今天爆发一波说不定能争银保铜,然后就以这样的策略跪烂了sad

老规矩,说题意~

T1性别改造计划:已经无法用简单的语言描述题意了sad总之要求最小化的式子形如[10*ln(A)]*S-C,题目鬼畜程度请自行脑补=.=

所以这个题其实我比较会做TAT大概思路是分层最小割预处理之后状压DP来着?应该是我能在考场上做出来的吧,可惜当时只做了10pt的暴力,大部分时间耗在了T3上。果然考场上合理投资非常重要,这次算是吃了大亏了sad

T2日程管理:给出一个天数限制T和多个任务,每个任务i必须在Ti天之前完成,且有一个价值Pi,每一个任务恰好需要1天时间,求最大能得到的价值,支持插入和删除一个任务。

这个题我不会做……陈老师又来出数据结构题了?总之5pt大暴力滚粗……正解是贪心,线段树维护一下即可,听说这道题一波带走集训队内的ZJ选手-.-

T3诡异的文本处理:按要求构造一个DFA(也许更类似于图灵机?),使得对于给出的文本都能输出给出的对应的文本,每个转移都有一个权值,要求权值之和最小。

这道题我根本不会做。构造一个可行解已经很不容易了,我在第一个点上耗了很久,得到可行解后再枚举+搜索+手算各种优化,把最开始的权值缩小到了1/3,感觉5pt总该有吧,但后面几个点连可行解都玩不出sad截止到此已经在此题上耗费了将近3h,另外两题读题+暴力后就只有不到0.5h了。

出考场时和佣神聊了一会儿,感觉大家情况都不是很好。水群的时候发现毛爷爷又A题了简直不能更跪……似乎ZJ情况都不太乐观?

滚去看成绩,路上遇到了黄学长Orz听说FJ神犇都把T1给切了,听说HN神犇都把T2给切了,听说某四川蒟蒻Kiana胸牌滚粗了……一看成绩只有16pt,第三题玩了两个多小时就给1pt,简直狂死乱舞,出题人是谁?我要和你谈笑风生……

滚去听评讲,陈老师题不是数据结构sad提答是Mato的题,可行解一律1pt,正解各种搜索+贪心+剪枝,跪人类智慧,我的智慧已欠费,无法修复……T1是wm的题,cxm来讲的解法,听说有人和陈老师打赌,陈老师说集训队至少5人A掉这题,然而并没有5人,所以陈老师并没有分辨题目难度的能力吗(当然……)?后来vfk把正解hack了,网络流的复杂度向来意识流,听vfk说维护一个三维凸包可做?总之我想都没怎么想过……

滚去膜laekov,听说他140+,看来也没发挥好,iwiwiioi说没看第一天分数,第二天分数和我差不多,总分应该比我高吧。反正我是两位数选手,多半要滚粗了sad

六人名单公布辣~Rank1是雅礼中学的lyy,接下来是约大爷和杜教,第四名是绍一zhj,第五名是ljcc,第六名是“集训队”的zxy,赶快跪!等等,maya策爷、松爷、vfk、saffah都没进sad不过能进十五人队已经非常厉害了,虽然会有遗憾,不过我相信他们是不会后悔曾为此拼搏的吧~看起来今年国家队不会是浙江队了XD

六人口试挺有意思的,lyy完成得挺nice,看来应该没问题了。约大爷被问道蛟川书院和镇海中学的关系时似乎有些答非所问,maya这俩真不是一个学校?杜教当然自信满满,OI数竞文化课三手抓Orz

到zhj的时候是最有意思的:

Q:“听说你去年也进了15人队?”

A:“是啊,那次第七名,不甘心啊!”

Q:“听说你是胡策Rank1,你觉得胡策能够体现选手实力吗?”

A:“不能。”

Q:“你为什么想进国家队?”

A:“对出国有帮助。”

以上仅凭当时记忆,可能不准确,总之全场掌声+笑声交错~

ljcc有点失误了,主要是忘词太伤了sad感觉zxy讲得一般吧,毕竟Rank6,不是特别出彩就没办法了TAT

口试之后就要公布获奖名单辣~按照惯例,应该是以Cu、Ag、Au、国家队的顺序公布。公布名单前休息的时候去听vfk直播hackT1,见到了zky,谈到了AIcraft,我这个小蒟蒻竟被误认成A7,曾哥果然大名远扬~公布之前卓神和黄学长他们搞到了分数线,大概是Cu35,Ag74,Cu135,maya我这么跪还能混Ag?带着不相信的态度再去膜了一次Au爷laekov,或许大家都多多少少挂了一点然后我趁机捡了个AgQwQ

所以FJ神犇的名单是真实的,然后我就Ag滚粗辣~国家队名单毫无疑问就是前四名,虽然据说前六名选手机会均等,不过前面的成绩果然占的分量太足了啊。

laekov神犇Au无疑,还有khb有一枚Au,所以SC一共有两人夺金。FJ八人金牌不能更跪,CQ情况似乎不太理想,而ZJ和HN则依然延续辉煌。吉丽爷虽然Day2也不太好,但毫无疑问拿下了非集训队第一名,毛爷爷状态似乎也转好了,拿下了第三名,看来以后状态会好上加好吧~

晚上去参加UOJ群聚+vfk退役宴,跟着cxm就是能抱大腿,我那桌坐着cxm、吉丽、dzy、fullpower、Mato、毛爷爷、松爷、vfk,然后就是我这只蒟蒻了TAT聚会时玩谁是卧底被各种碾压QAQ虽然有一点点小意外,不过大家都还是很开心的~聚会后随机送抱枕,得主还友情献唱一首~最后大家一起合影不能更赞,有这样一些朋友真好~


或许大家以后关系会更近,或许今天之后就不会再见,但能够有机会相遇,就是上帝所给的最佳的礼物~

【Day?】

CTSC结束后的第一天,ZGY和ycd来了北京准备APIO,简直不能更浪了。

去找CQ神犇膜拜,结果诸神犇在愉快地玩耍,听说吉丽爷带了麻将?dx中途离开说是去找吉丽爷打麻将XD

然后去膜拜佣神,JS神犇正在怒切APIO试机题,TKD也在那里,感觉萌萌哒~然后不知用什么神奇的方法召唤来了vfk,大家一起做一道不太可做题。然后不知道用什么神奇的方法召唤来了杜教,和我们一起做那道不太可做题。后来发现似乎是把题读错了,然后瞬间变水题(╯‵□′)╯︵┻━┻佣神和TKD准备开颓osu,杜教继续切题,感觉要没题做了sad

所以接下来的几天大部分时间在和七中同学一起玩耍,简直不能更浪了。

【APIO?】

真的不太愿意承认参加了APIO2015……

两位数Cu滚,真的很丢脸……

没什么可以记的,反正水过去了,也没太大收益……

【总结】

CTSC2015:40+0+34+10+5+1=90,Ag滚粗。

APIO2015:0+57+17=74,Cu滚粗。

CTSC的题难度较大,但也不是不可做,至少Day2T1我应该有能力在考场上AC的,不过错误的估计题目难度和时间分配的不合理是一块硬伤,在这类比赛中花费的时间和得分往往可能不成正比,一直攻克一道题或者分配时间给所有题都不失为一种好策略,所以我觉得自己在这方面还很不足。当然领袖曾经说过,如果有强得离谱的实力,就不用考虑这些问题了TAT

至于APIO,我不多说了,考前还有人D我说我乱考都能Au,这样的结果真的很难堪。

不过这一次来CTSC&APIO,收益真的非常大~

在CTSC时看到各位国家队候选队员精心准备的论文和答辩,每一年都给后人留下一大笔宝贵的财富,从中看到他们对OI的热诚,真的很感动,在这个1=已经不能保送的年代,能够冲刺到这一步,除了雄厚的实力,最少不了的,大概还是心中那份对OI的喜爱吧。

膜拜了各位神犇,相互交流之后发现了自己很多的不足。很高兴能够认识大家,与大家的交流是此行最大的收获~

嘛,最后有一些单独的话想说~

lqybzx,祝你JSOI三试翻盘,咱们七月见~

laekov,希望能和你成为很好的朋友,虽然现在的我实力还不足以和你较量,但我会继续努力的,一起加油吧~

给南山的同学们,这次好多人都没来真的很可惜啊sad大家要好好抓住机会~

给所有的朋友们,认识大家很开心,咱们七月杭州见~

给你,希望你能看到,身无彩凤双飞翼,心有灵犀一点通~

Hello,world!Bless All~

评论(1)

© OI技术宅 | Powered by LOFTER