Codechef 14.9 QRECT CDQ分治+分治+线段树
任意模数的FFT

清华集训总结

shinbokuow posted @ Dec 14, 2015 02:55:34 PM in Something with tags 清华集训 , 2020 阅读
 
本月的5日至10日,我参加了在清华大学举办的IOI2016国家队集训。
期间举行了四场考试,考试均在UOJ的拷贝上进行,每场考试时长四个小时。
我自己的分数十分惨淡,在这里略过不谈,讨论一下题目吧。
在这些考试中出现过一些思路比较巧妙的传统题:例如第一天的第一题,是注意到互为反向边的两条单向边的权值互为相反数这个性质,随后就能够简单地将问题转化为维护每个连通块的所有环的权值和的最大公约数以及生成树上两个节点路径上的权值和即可,而这能够很简单的利用并查集维护,并没有用到一些复杂的数据结构如Link-Cut Tree以及Link-Cut Cactus等等。又如最后一天的第一题,题目很明显是一道数据结构题,但是从思路上却需要另辟蹊径,并非简单的维护每个时刻每个位置的值,而是维护每个时刻每个位置现在的值关于初始值的一个函数,而这个函数是一个一次分段函数,能够方便的进行打标记处理。但这个题目最终却还需要维护历史最大值,个人觉得这有些画蛇添足,因为思想并不深刻而细节繁多,但总的来说瑕不掩瑜。
今年清华集训中最大的变化就是非传统题比重的增大:这一点与比赛举办在UOJ上有很大的关系,在此感谢UOJ的开发者VFK以及ydc,Picks等一些维护人员,感谢他们无私的奉献。UOJ上举办的比赛如UR,UER的题目质量都非常高,算法十分有趣,而且不时会出现一些有趣的非传统题。今年清华集训中有一些非传统题只是借用了非传统题的外壳,本质上还是传统题;但也出现了一些有趣的斗智斗勇斗常数的非传统题,如VFK出的维护二次分段函数轮廓线的题,从朴素的分治算法入手,并更改算法得到优秀的复杂度;以及松爷的造计算机题也是各种理性愉悦,这些题目的质量还是很高的。
但是本次清华集训也出现了一些不是那么优美的题目,如特征根+行列式题,以及物理题。个人认为好的OI题应该有明确的切入点,而不应该让选手将过多的时间花费在OI之外的需要思考的地方,而不是算法本身。而像是这种题目不能说不是好题,但是出现在OI比赛中是不合适的,或许出现在ACM中会让人觉得比较正常。然而清华集训并不是OI到ACM的过渡,因此这种题目出现在这种比赛中就会让人很不舒服。比如这两道题,我自己就不知道什么是特征根,什么是“浮力势能”,那就只能暴力分草草收场,固然这些题总是有神犇会做的,但是在OI中只能被定义为“冷门”,我认为好的OI题应该不设“技术壁垒”,用尽人皆知、普及度高的算法及知识来检测选手解决问题的能力。
OI精神更应该像VFK的《UOJ精神之源流》中表达的一样。但是如果想要达到这样的境界并不是一朝一夕的,必然要经过长期的奋斗,国外质量高的OI竞赛如POI,USACO等都是经过了多年的沉淀才能够取其精华去其糟粕的,因此如今让名校的大学生(他们也很忙啊喂)负责系列赛事的出题也许只是一种对于现实的妥协,UOJ的诞生就是一个好的预兆,我们仍在进步当中,我们仍走在上升的路上。只要存在着算法竞赛的爱好者,OI精神就永不会断绝,OI总有一天会像我们期望的那样美丽而又简洁,让我们能够沐浴在它的光芒之下享受算法的美。
Avatar_small
Recursion 说:
Dec 16, 2015 09:12:06 PM

说真的,usaco的质量真的不咋样...

wyfcyx 说:
Dec 17, 2015 11:07:51 PM

@Recursion: 同意你的观点。但是有时候还是有一些思路巧妙的题目的。

Avatar_small
Recursion 说:
Dec 18, 2015 04:36:13 PM

@wyfcyx: 您不妨看看今年的题目,难度已经低于noip了...

ww140142 说:
Dec 20, 2015 10:00:32 PM

好像很厉害的样子呢![鼓掌熊]
我觉得OI里的非OI题确实很坑哦。。(NOIP)斗地主搜索谁写不出来最后大多挂在特判上。。。(实际上似乎只要顺子写对好像就差不多能A?)(不过曾经有一个人出的原题差点出到我们的模拟赛里然而被宋爷毙掉了233333)
去UOJ膜了一下物理题,然而差评并没有(清华)斗地主多。。。
说起来特征根啥的我现在还不会省选T1呢。。(虽然抄个式子AC了= =)

【然而左下那个水印什么情况。。。

Avatar_small
wyfcyx 说:
Dec 22, 2015 03:19:05 PM

@ww140142: 随便找了张图,不要在意。。。


登录 *


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