分类 总结 下的文章

GDOI'2015 旁观记

5/28 Renew. 「真是抱歉一直拖到现在。」

做~大~死~啦~
嘛反正我这种人应该不能报什么希望才对。

Day -1

上完课回到家就一直在看算法。
本来想趁五一学一些黑科技的,但是AC自动机已经虐的我满地打滚了。
这间学校自然不会提供停课之类的服务,总之就是一切靠自己。
靠自己就靠自己咯,谁怕谁。

Day 0

早上本来想去学校颓废在机房的,但事先并没有告知的看病日程打乱了我的一切安排。
下午从GZ出发。地铁-》高铁-》的士-》到达酒店之类的。
队长什么的,完全不知所云。
总之就是没迟到。顺带一提就是不小心被车门夹到手了。还好没事。
晚上颓废地在自新,还立了几个flag。

Day 1

六点半起来真是一点都不人性。
早餐是自助餐。豆浆特别难喝,或者说,就是白色的白开水而已。其他一般。嘛毕竟不是省城。
看胸牌【///】说八点开始以为考四个半钟但结果是我们在门外站了半个钟。
走进去试机,Dev-C++4.9.9.2差点没把我恶心死。
边忍着恶心边把一些设置弄得我稍微能够接受一些。【比方说什么tab字符】以致于后来边码边吐槽这东西能进博物馆了吧。

从未如此想念我的sublime系列

真是不幸。
想打一个FFT结果没打出来。深深的滚粗感。
沉下心去看题。
T1莫非是sg?好像还是挺难的sg毕竟还有考虑转向边……D1T1没有这么难吧?!
不会的话……继续耐下心看……最后一句「现在小明并不关心他是否能获胜,他只想知道是……」出题人果然送()温()暖()。
想了一会儿发现自己完全不会。于是只能去看T2。
好熟悉的样子,以前@plm神犇好像做过一道类似的只不过只要考虑前两项的组合情况后面都能dfs的……
数据范围发现显然不对。那莫非是DP?
DP的话……看来我是推不出来了(仰天长叹
就这样看T3.woc概率论!果断弃疗。
T4其实没心情看了。但本已决定开考半个钟内不干其他事那就真不干其他事了。所以感觉直接弄棵树模拟模拟?
嗯,T2感觉dfs能拿一些(ge)点的样子那就先打。
回到T1发现也许对于存在一个格子他后面有连续六个格子跳转到他之前的好像就是Yes,好像真的没错,于是开打。
T3就只能随手造一个式子N*A&Q。O(1)的!
T4就真的弄了一棵树以及lca。其实一看树上操作+lca的就想到了什么树链剖分,但可惜那是什么能吃吗。
考完出来抱怨说好的T1可以排序水平呢?!
其它学校好像都弄的不错,呃,大弱校的众人只能膜了。
中午。感觉北江的食堂十分良心。令我十分感动。
然后到他们的阶梯教室。表示在众人面前看自新很那个啥的啊。后来还是盖上电脑睡觉了。
讲题,发现以自己的水平果然是来旁观的,这些思路不然就简单得觉得自己是弱智不然就是那是啥。
10+10+0+0.T3和T4全是WA,对于T4还是感到有点奇怪的,不过目测等差打残了。
晚上颓着轮流CS和MC。外加看了一眼最大流。十二点才睡。

Day 2

精神觉得很糟糕。
等待的时候听有人说会考高精度乘什么的,吓得我复习了一遍FFT。
试机时打了FFT跟SAM。希望SAM能用得上。
先看有没有字符串的题……T1不是,T2也不是,那T3还像是的。觉得还挺满足的仿佛能A题了。但其实就是个flag。
T1完全不会。弃疗。输出-1.
T2强连通分量?!tarjan好像不会打。那就打个BFS吧……
T3woc怎么在自动机节点维护这些值啊啊啊而且好像不可做啊。暴力也不会了。
-1大法好!打了分数保!
T4神级DP?不过$ \sum_{j=1}^{M} a_{ij}^2 = 1 $好像很熟悉……
结果就是都不会了跪了。
出来感觉要死。
讲题时发现其实都很简单(才怪)的。
0+10+10+0.D1的T1说是数据错了给我加了10pt。
T2和T4全是BIT打残。明明全暴力能拿多30pt。(哭瞎
复评时发现T1没编译就交了,丢了10pt。
嘛嘛算了咱是来围观的有胸牌就够了。
晚上颓CS。xx过来跟我们谈心谈到两点多快三点。

Day 3

好像说好四点起来打CS于是zbw谁在我们这里然后没人起的来……
早上说好的活动据说取消了的样子好的我们全员滚粗狗白等了好久。
回去继续颓CS。外加一边看自新。午餐晚餐懒得出去叫了两顿KFC。中午那顿好像还是由于天气原因我们值得三点才吃上?
自新的世界观已经完全明白了,的确是神作啊!也不得不佩服作者对人性的把握果然恰到好处啊!日本人难道都是心理学天才吗?
更加坚定了看小说的信念。
晚上出去拿座位安排,发现自己有个Cu满心欣喜。另外就是@plm是Au,@hzf是Cu。
后来打MC打到半夜。

Day 4

等讲话的时候我在补觉。
上去拿牌也没啥。
不过是郭嵩山教授亲自给我带上的!荣幸至极!荣幸至极!
还说了“考得不错”之类的话,已经感动得回不了感谢的话了……
聚餐什么的完全就被大乱了顺序。而且不好吃!

后记

也是终于看了几集自新。
而且这次有遗憾也有喜悦的地方。遗憾是因为有题其实差一点就能想出来/码出来了,喜悦时总算有了上面的这种遗憾而不是只能每次都只能做自己会做的。
【但是自己还有很多算法不会!!!!!】
接下来时间好像特别忙的样子。说好的OI滚粗也是真的快要滚了额。
就先这样。

GDKOI'2015被虐记

嘛……今年还是作了大死……总之考得比去年好就是了……

Day -1

在家赶作业。而且目测是无法及时交的。
幸好KOI占了回校日可以拖一点时间。
然后想着明天:会不会考网络流啊?我要再看一下啊……
可是最后发现是在不敢分散作业的注意力还是算了。
直到睡觉前才觉得有必要真的看一看一点东西,于是打开了Manacher跟FFT的代码。
实在太困了没仔细看就睡觉了。

Day 1

起晚了感觉有点怕。
集合时间我才到六中门口感觉有点怕。
中山楼下没看到其他人感觉有点怕。
找考室时发现同室没有认识的感到有点怕。
考号不知感到有点怕。
总之就是怕。

来到考场,6楼(?)的语音室……
进去发下书包就试机了,座位靠后还挺有安全感的。
放眼望去,呃,C++狗怎么这么多。
好像还都是同一所学校的,不像是广州的校服,纪中?
而且他们还把Dev-C++调成了黑底白字。woc第一眼还以为他们用了sublime。
打什么好呢。打了一段Hello world。发现还有时间想打SAM但是没打完就开考了。
比赛开始,等念密码。好像是奇奇怪怪的东西Orz。
然后看题。看了一众大神的参赛总结深知得看完全部题再分配做题顺序。
T1.嗯,想了想,这特么不就是回文串吗?
是应该三倍原串对吧,哦不对,两倍就行了。
然后就直接manacher了对吧!
等等,manacher到底怎么写?!<s>(哭晕</s>
T2.感觉像是动态规划,但没想到什么方程,先挂着。
T3.妥妥只会暴力。
T4.裸的数据结构?!LCA?!<s>这些都是只听过whj大神提到过的东西啊……</s>
呃,还有颜色。红黑树?!好像也不是……是的话反正我也不会。
看到有只有两种颜色的情况就直接普通树+lazytag吧Orz……
回过头来写T1,时间过了半个钟。
manacher怎么推都推不出来啊……只好打$ O(n^2) $暴力了……
再看T2.连暴力都想不出来感觉得跪……在草稿纸上试试画一画整理一下思路看看……
把所有无关节点去掉……
把字符跟次数写在一起,每次从G走到I都会消耗一次次数……
呃,等等。把字符看成点,把次数看成入入度流量不就是标准的最大流吗?!
标准的最大流?!
最大流?!
直接跳过不解释。
T3打完了暴力,发现大于50的好些点慢到爆。
好像偶数都挺快的,有一些数直接就无输出,目测递归爆栈了。
然后测多几组数据发现:除了2的质数都无解?!<s>考完出来被真·结论吓呆了</s>
然后用了ctime的clock卡0.95s。
然后就是暴力+调试过完了接下来愉快的一个半钟。
顺便说一句,右边的一个人好像一直都在挑战新姿势……没看他认真做过题,好像有一题还打了很长的表?

中午围餐,期间各种欢脱。

下午讲题,在中大<s>被whj带</s>迷路了。赶到信科院时就知道抢不到位了。
由于下了新世界就坐在那里补番。旁边whj和xx在讨论t4好像很有趣的样子。
T1几个人上去讲,第一个上去是一个纪中的A了的妹纸OrzOrzOrz。M字头算法不解释。
第二个H字头不解释。
接着重头戏来了。whj神犇充满强大的气场上去,用犀利的眼神以及蔑视众生的笑容令台下众人心中生畏。
“大家好,我是来自华南师范大学的whj。”
“卧槽大学狗。”——台下某人,相信那一天他人品已经掉光了。
接下来原本安静的会场因大神的自我介绍而热闹起来。
我们很容易就可以猜到其内心OS:「你们这些中学狗,不好好学文化课打什么OI,除了我之外都是把不到妹子的!」
再用压住其他人的声音说:我用的是N字结尾的算法!后面已经有人哇了起来。
S开头的!已经有人喊出了SA。
我的思路是……blabla……用「后缀自动机」乱搞一下就行了……
全场掌声雷动。
出题人:呃,我没想到居然用这么高级的东西做我这道题,还写错了,<s>大家不要学啊。</s>
膜拜膜拜。
然后一堆一堆的wen·wen·tao上去讲课并祝出题人身体健康。好像是WC·AU?

听完评讲发现我了个大treap居然时限不是全1s的……
目测T3玩完了……

其实就是T1判定回文串,可以manacher、hash、后缀做;
T2网络流,SAP会卡一个点;
T3考智商,要对图缩点并且从哈密顿回路变成欧拉回路;
T4树上操作Orz。

拿到成绩,好险有60'。T1&T3的暴力分各30'。T4的评测信息可称错误大全了。
whj:150';xbw:110';htc:120……
请叫我蒟蒻。

Day 2

状态感觉不是特别好。
左边的人还是一如既往的手速。
右边的人还是一如既往的在玩。
看了题发现全都不可做,感到颓废,觉得要爆0滚粗了。
T1&T2感觉还是动规,T3想了想昨天立的flag:D1T4和D2T3可以用同种方法做!
特么动态树……还是跳过了。
T4太长了……本来前面已经看慌了再看到这么长并且还有看不懂更是感到深深的不可做感。
没办法,只能迎着头皮写……
T1连暴力都不会,打算交个shutdown但想想还是算了……
T2打了爆搜。
此时2个半钟过去。
T3暴力+调试一直到了考试结束。
T4考完发现模拟是可!做!的!

啊啊,0分的感觉真好啊~

中午hbg来一起吃饭,一堆人提前走了……

下午早了很早去,在门口站了1个半钟。嗯,终于看完新世界第1集了。
快进去的时候拥挤了起来,感觉可能会有踩踏事故啊……
上到去,抢到位置感觉不错。
是在太困了睡着了Orz……

T1:动规+线段树。两种都想到了,但是动规没列出来就完了嘛……
T2:动规+智商。智商不够推不出动规Orz。
T3:树上操作again……
T4:变态模拟+数学。

听完深深的滚粗感。
已经不想拿成绩单了结果xbw说万一有分呢……
万一有分呢……
算了还是看一下吧……
刚刚好只过了一个点,10'.
whj:90';xbw:50';htc:10'……
看看错误全是TLE。
说好的$ O(n^4) $只跑0.05s的呢?
哦不对,我写的好像是指数级别的……

总结

70'滚粗。
感觉暴力分有些还没拿到……
各种树上查询感觉特别厉害啊……
品是基础十分重要啊比方说网络流和动规……
市选·省选加油!