12
18
2014
0

IOI2015 THU Training

这酱油真难打


day -1

下午三点就到宾馆了,晚饭在吉野家解决,感觉还算不错。


day 0

报到日。竟然有发水果和水还有一件思考熊外套。下午试机清澄崩了感觉和无聊。


day 1

分到的电脑竟然是不能用的,这是什么运气。。

开题看了看,发现T3没什么意思,随手写掉了,很好奇为什么数据范围只开10w,感觉*60的算法也能低飞。

T1搞出了一个O(n*60+(64/k)k*2k)的容斥,写出来之后发现中间有一步是错的,想了想只会O((64/k)k*(n+2k))于是就只写了k<=2的。

T2感觉应该是怎么状压一下就好了(so naive),但是不会。

考完后身后的人在讨论他们调T1的辛(guang)酸(hui)历程,感觉自己暴力写写快垫底了吧。

成绩出来后发现暴力没写挂,还是比较开心的。J莫名掉了30分,后来发现是T3把操作数当序列长度了。很多人的T1貌似都挂了些分?

下午听讲题,T1高斯消元后暴力就行了,据说是常用技巧,想了很久才想通感觉自己还是太年轻了。。

T2的容斥感觉很优美啊,T3的标算竟然有O(220)的预处理,不知道出题人在想什么。。于是很多理论50分的代码都拿到了90~100。

全写暴力好像进前15了?有点开心的。


day 2

在机房门口等的时候看到有个管理人员(mato)很眼熟。

分到的电脑又是不能用的,位置在大哥后面,但是大哥因为电脑的问题被赶到xp机房去了。

T1是个一眼流的插头DP,但是我不会写,留了一年的梗了,这次终于出事了。果然在9:00看到了大哥和J都相继交上了一份3k左右的代码。

T3被10kb的标程吓退了(8kb以上是注释?),老老实实码了40分暴力。

于是这场我只能做T2了,那个解密弄了弄不会算,最后还是用二分解出来的,码出一个暴力验证了下题意后感觉这题也是挺sb的,感觉kdtree随便跑跑过好了。花了大概1h后写出来发现70分范围大概要跑6s,感觉要跪惨。只能使劲卡常数,后来mato增加了一组大样例,竟然跑wa了。。调了很久发现二分范围写错了。。经过一系列的优化,发现极限数据要跑6s。。看着版上3.8s的标程真的有一种想骂出题人的感觉。。(行内默规两倍时限?)

于是就只能跑70分,由于考试时的评测拥堵好像只有60了,最后因未知原因复评后还是70,有一个点4.935秒。

考后J和我说了一些优化,我好像都没加,kdtree好久不写了连小范围暴力都忘记了,中间运算好像也不用long double。

T1果然是插头DP,有7个人左右A掉了。

做T2的人好像不多了,于是和J拿了最高分和次高分。标解居然是用强制在线解方程(今天其实考了rho啊,不过几乎没人发现?),数据结构还是被人类智慧虐爆了囧233333333

T3是稳定婚姻问题。。在绍一某次NOIp模拟赛花老师出过。。由于我那时候还在读初中于是也就没什么后悔了。


day 3

T1是数学题 T2有正则表达式 T3是几何题   今天注定是爆蛋日?

刚看完题,发现版没封,点开看看杜教T1已经有60了。

T1做了很久,最后还是用打表混60分了

T2选择放弃,不过后来感觉这个决策好像很错误啊,30分还是很好写的啊

T3没想到把四维转三维,于是在尝试用已知向量拼出一个和目标向量平行的向量,用点积列方程,不过由于四维空间里似乎是不存在法向量这种概念的?还是失败了

然后J靠三维凸包又虐场了(去年J的集训队互测题是三维凸包),又一天rank2(为什么是rank2?我相信我不用解释了,大家都清楚)

T1好神奇,数学题被虐心服口服

T2似乎有库可以做正则表达式?不过由于编译器版本没人成功?

T3是用数据结构维护三维凸包的随机增量过程?没听懂,只感觉好厉害


day 4

T1是范爷的题,我终于在范爷的题上拿分了,感觉人生都圆满了

T2是主席的题,看到数据结构题就有一种亲切感,一点不怂写log方最后还是没过

T3列出了线性规划的式子,但是变量必须要是整数,又不能转网络流,就哔哔哔了,爆搜写了点优化还没有大哥直接搞快。。

吃饭时听说T2是黑技术,后来发现是J嫌麻烦没写的算法(没看到修改<=10w,其实我也没看到,还以为树套树空间开不下就没卡常数)

T2的标算好像被wys大爷艹翻了

T3的dp脑洞还是偏大的


写了4天暴力成功卡线15名,成功获得冬令营的50%生存概率


一段时间后。。。。。。。。

清华集训的题被放到BZOJ上了,玄学由于40*8s的时限直接就被和谐了?

然后交了一发mato的题,竟然过了。。。于是好奇地拿数据测了下,发现只有一个点5.1s。。。。。听说清澄很快?

把所有long double换成double后。。。。妥妥地进4s啊。。。。果然非标算的精度是很好的?


 

Category: My OI Life | Tags: My OI Life | Read Count: 1208

登录 *


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

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com