CTSC&APIO2017游记

CTSC

退役后第二次出来玩

大概和去年差不多

酒店的网前两天还可以 之后就慢成××了(不过没人的时候网速还行

和laofu一个房间。。于是每天晚上的睡觉时间都提前了若干小时

又和stonepage大爷面基了一发(重逢一周年?)

八十中的饭还是那么棒棒。。直奔铁板烧大法好。。不过这次的券似乎改成\(5\)块钱然后一张按钱给券了?

王选的世界还是不能不听然后没啥人听

答辩的内容貌似大多都是WC/ZJOI讲课内容

毛爷爷口语惊人!champion大法好!

YJQ大爷霸气的回答仍然没能让他翻盘。。心疼\(1s\),不过人家是有妹子的人

颁奖的时候YMD站在了WC时站在laofu旁边的那个[他/她]旁边23333333

[他/她]被杜子德赞为最强女选手!23333333

 

试机的题目是两道去年NOI的传统题。。果断预测今年没有提答

果真没有

Round 1

T1画风和谐 字符串?

T2题面眼熟

T3概率相关

 

T1好像直接送了\(30\)分?CTSC什么时候这么良心了

再分析一波。。A比B多那就是把A看成\(1\)然后B看成\(-1\)前缀和为正数的个数?

先倍长一发那么就是某个位置后面\(k\)个A的前缀和减去这个位置的前缀和

所以就是查询比这个位置大的个数。。树状数组搞一下?

\(50\)分get

然后\(0\)的部分似乎是个滑动窗口?\(65\)分get

先跑路写后面两题吧。。

T2好像很眼熟?貌似就是去年IOI改成树?CTSC果然鬼题多,肯定又是出题人想到什么别的算法加强了一波。。肯定不能求直径啥的用之前的做法。。暴力算了。。

可以是个基环外向树求直径?好像不是很好写。。先跳

T3大概可以dp一下?码码码。。诶后面好像对前面有影响来的?多记一维算了。。

于是写了个\(n^3\)。。\(20\)分到手

开写T2基环外向树求直径。。好像记不太清了呀。。先写个\(n^4\)再加点剪枝算了。。测了一下大样例里面有\(150\)的跑过了耶。。假设能过算了(然后的确过了

T1应该是可捉的。。带log肯定没戏。。要\(O(n)\)的话就不能用树状数组。。

等等这个树状数组的修改操作。。好像很诡异呀。。好像每次是修改相邻两个,一个\(+1\)一个\(-1\)

那直接数组维护前缀和就行了。。每次只要改一个位置。。

 

于是\(145\)分收场了

听说YMD250分。。T2还真求完直径变IOI原题。。艹什么时候CTSC还有原题来的还就是去年的IOI题

T3好像可以\(n^2\)dp,多记个期望而不是新增一维状态就行了。。是我蠢了。。

Round2

这T1。。怎么明摆着说要送\(100\)分的意思。。

直接dp就有\(70\)分嗯。。

然后发现并不会\(100\)分

T2没什么想法。。跳跳跳

T3什么鬼。。似乎要爆零了。。看看能不能骗个\(30\)分

等分再等分大法。。过了sb一样的样例。。看了看好像没有大样例装作能过。。(

回来瞄一眼T2好像可以费用流?码码码

\(n=1500\)的时候貌似就跑不动了。。因为边数是\(O(n^2)\)的

不过感觉还可以抢救一下

只往前连\(150\)条边!貌似随机数据基本不会错!

继续大力刚T1。。打表看了一下能够转移的数对。。没有看出来规律。。一步之遥啊gg

 

最后\(100\)分跪烂,T3爆零

发现其实是有大样例的。。第三个样例的第一组数据。。智障又没发现。。

刚才检查了一波好像投影的时候正负号出了偏差。。我™没学过数学。。

最后差\(10\)分金牌。。没爆零就好了 日哦

APIO

走了一部分人。。除此之外差别不大?

试机搞事情。。若干分钟后APIO网站就挂了,一直上不去

嗯然后这篇游记的前面一部分是我在试机的时候写的。。

最后半个小时好像好了。。然而交上去一直compiling并没有什么用

不过令人感动的是有\(21\)个人猜对了

 

开题。。第一题看起来好鬼啊

(也许是昨晚喝多了(?)的缘故)直接搞起

第一个sub随便搞

第二个线段树?好像要三个线段树 码码码

第三个只有一组询问的话就把边上一圈扣出来?码码码

拍了一下WA了 发现好像可能会被询问边界切开 所以还要加上边上一圈 码码码

拍了一下又WA了 发现如果全都不贴边界的话这样会多算一个连通块 特判一下 码码码

TLE了?map换hash 码码码

跑不出来了?模数搞大一点

又TLE了?模数再搞大一点

。。。

虽然我上面只写了\(6\)行然而代码量 其实可以想象一下

 

于是三个小时过去了

还是\(23\)分

我的内心是绝望的

用时\(1.3s\)

 

没办法了各花一个小时把剩下两个题暴力打了滚粗了

然后T2好像只会\(4\)分。。怎么玩啊(好像一直没有意识到数字是\(1\)到\(100\)

不会捉不会捉。。要死啦 不甘心地跑去优化T1常数

好像没什么地方好下手的。。

于是把hash的时候取模改成如果\(=MOD\)就置零。。

绝望地交了一发

诶变\(47\)分了?woc?还只要\(0.3s\)?

我可能。。还是需要学习一下。。常数优化的那一套理论?

T3似乎送了\(12\)分。。第三个sub似乎看上去还比较可做。。

好像就是分数规划?二分+SPFA判环?

码码码然后过了

正解应该不可捉。。跑去继续想T2(然而其实我写的已经和正解并没有什么区别了

死活还是想不出来任何一个点。。没有智商做不出智商题。。

于是\(96\)分滚粗了

一考完听说大佬们【都】切了T3。。【就我一个】写的\(45\)分

别人一道顶我三道啊。。没救

叶大佬\(130\)太厉害了%%%

G大佬\(144\)太厉害了%%%

他们怎么T2【都】有高分啊。。【就我一个】只有\(4\)分的。。我果然是弱智

 

银牌滚粗

G大佬和tmp大佬踩线金牌。。劲啊

 

说不定是最后一场比赛了呢?

GL

说点什么

3 评论 在 "CTSC&APIO2017游记"

提醒
排序:   最新 | 最旧 | 得票最多
成员

光光是坠强的!

成员

光光是坠强的!

wpDiscuz