UOJ Logo WrongAnswer的博客

博客

退役之战——IOI2017

2017-07-25 08:19:10 By WrongAnswer

退役前的最后一战。

挺紧张的,毕竟我NOI只有#40+,就算把Day2挂掉的66分加上还是只有#20+。不止一题脑抽差一点想出来还是相当不爽的啊。

毕竟还是运气选手唉= =

以及我现在考场心态还是太糟糕。

不过作为国家队的最后一名,我也没有什么太多的梦想吧。保Ag争Au吧。

orz matthew99,xumingkuan,cy。


7月25日

入住酒店。

刷了CEOI2016D2T1。想了一个比较复杂的做法不知道有没更简单的做法。

NOI同步赛成绩单出来了,作为Day2挂成114分的国家队垫底选手,看着被一大堆人虐感觉也是很奇葩的。(然而同步赛FJ Day2最高分居然也就114?大家都考跪了?)

和xumingkuan住一间。

晚上宋老师带全队四人去McDonald吃了点零食,顺便和另外三人聊了些题目怎么做。深刻感觉我水平低得可怜。


7月26日

IOI前的ACM模拟赛。

把自己名称改成了orz_immortalCO,暴力膜锟。

A题找了好久的规律,才看出exgcd的做法。

B题只会一种很暴力的DP,过不去。jiaqiyang当场AC了。

C题完全不会。

D题看n<=17以为是傻逼题,然后想了1h还是不会,GG。

E题就是个辣鸡题,研究了好久发现细节很难处理,结果暴力都WA,最后干脆交了个不考虑四点共线,A//B//C时会退化成平方log的程序上去,正确性和复杂度都不对,居然能过。xumingkuan现场写了FFT过了。

最后2题滚粗。我并不能跟上国家队的平均水平。


7月27日

动员会。没什么好说的。


7月28日

在飞机上坐了大概10h,意识模糊。

下午Exhibition,没什么好说的。


7月29日

练习赛。

就是之前做过的题,不过只有2h,来不及AK。

T1用我论文里面的独立集搜索算法拿了70分。虽然说正解更好写但是懒得写了。

T2水题切了。

T3水题切了。

T4提答,暴搜搜出4个点,又搞了4,5两个特殊点,拿了60分。剩下的点没时间搞了。

70+100+100+60=330

明天就是day1了,为自己加油。


7月30日

Day1。

开场看了三个题,T1是个提答,而且数据点很大不能暴搜,感觉是神奇的构造或者随机化算法,应该要留到最后去争取;T2好像很套路;T3好像一脸不可做。

然后就开T2了。一开始想到费用流,然后思考了好一会儿如何优化这个费用流,发现增广路可能好几段,不太能优化。思考无果就去看T3了。

T3看完题再看数据范围,n<=5000,m<=20000,突然又觉得这题可能才是送分题。然后开始推DP,一开始想记f(i)为从i出发会不会绕道一个有充电点的环上,然后转移有环,搞不出来。又想了想,如果A必胜,那么最优路径就会一直经过充电点,反之n步以后再也不会经过充电点。

想到这里打了一个nm的DP:f(i,j)表示当前在i,走j步将经过多少个点,如果f(i,n)=f(i,2n)则i是0,否则1。虽然不会证但感觉没什么问题的样子,就写。

调到考试开始1:20时过了子任务1,2,3,5,另外两个子任务TLE,38分。看起来这个做法是对的,只是被卡常数了。然后优化常数,在1:40时过了子任务4,49分。继续优化常数终于不TLE了,然而WA在了子任务5的第96个点。

怀疑哪里写挂了,眼调了很久。

把怀疑挂的地方改改,怎么改都过不去,始终49分,WA第96个点。然后就浪费了半个多小时(Ag flag

已经2:20了,没什么救,弃疗去搞T2。

一开始打了个7分暴力。感觉这个题性质奥妙重重,一定有规律。于是拿7分暴力打表找规律,看看发现每段都是一段R一段B,两段最多有一个交点。这样就可以转移了,然而这样仍然是n^2的,在3:13时写了暴力过了子任务3,一共17分。

然后有一种自己这题到手了的感觉,开始想优化转移。看着式子发现是个斜率优化,然而看起来很复杂的样子。随后想想裸上决策单调性好像可以(Ag flag*2

然后以为决策单调性很好写,实际花了半个多小时,调不出来。好不容易调出来发现做法有问题,想fix这个做法又花了一会儿,还是错,惨啊。

这时候T1还没打,很慌,赶紧回去每个点随机输出一个极大的树拿了60分。

最后30min终于决定打T2的靠谱的斜率优化了,打了大概20min。

然而,没调出来(Ag flag*3

最后就悲惨得滚粗了。

60+30+49=139

考完第一个问xmk,他说他拿了274。我一听整个人都要吓软掉了,完了,真的没救了。lzz也拿了接近200分。myy和yjq好像也考跪了。

出来看榜,我#40,Ag分数,xmk#3,就要虐场。唉,这就是实力的差距。

听说T3只有4个人A,xmk就是其中一个。想想我这个做法自己都不会证是不是对的居然能拿49,却不知道骗分应该及时收手,导致浪费大量时间最后没时间做T2,70分没了,活该Ag。

下午回去,非常不甘心地继续调T2的斜率优化,花了大概半小时调出来了。早知道那个不靠谱的决策单调性就不要写了,省出这个时间完全足够A掉T2,70分没了,活该Ag。

在车上和myy,xmk讨论T2,他们说T2不用斜率优化,前缀最值就行。我说式子里不是有一个x吗,然后盯着式子又看了两眼,发现这个x是连续段的开头,是固定的!而不是x[i]会变。要是多思考下,前缀最值比斜率优化好写不知道多少倍。

调T3错误算法,搞T2决策单调性,写T2斜率优化,这三个错只要我任何一个不犯就是209分,但结局是139分。我连续这么多场比赛就没有正常发挥过,IOI又因为自己作死花大量时间在错误算法上而丢掉70分,丢掉Au,成千古罪人。想想真是太后悔了。

晚上去Exhibition到很迟才回宾馆。


7月31日

Exhibition。

本来很好看的,一想到D1T2就没心情了。

如果是实力Ag也不觉得遗憾,然而明明会做的题却因自己作死浪费时间最后来不及调出来导致Ag,就十分遗憾了。


8月1日

Day2。

还是花半小时看了三个题,T1、T2都是交互题,目测应该一道简单一道难,T3是传统题,看起来很可做。

然后猜了个T3贪心的结论,答案等于每个环的长度和加上s左边非自环最右和s右边非自换最左距离的2倍,交上去,爆0了。

发现写挂了,改了改交上去,又爆0了。

想了一会儿发现套在一起的环可以一起走,就fix了一下,交上去,50。

不错,起码s=0的对了。

60min过去了,我得了50分。(Ag flag

回去看T1。T1感觉i的个数大于i-1的个数的平方这个约束很奥妙重重,意味着可以用分治暴力搞出所有小于v的位置?然后随手打了个分治,交上去爆20。

然后发现递归到[l,r]时询问mid询问的不是[l,mid)而是[0,mid),接着想前缀和减减,发现mid和l,r不一定都是v类型。

接着想法就是先随便询问500个位置取个最大的,然后就能判断是不是v了,不是v的只有不到500个,暴力扔掉。

写完交上去,拿了97,把500调参调到480,并没有什么卵用。

100min过去了,我得了147分。(Ag flag*2

感觉为了剩下2分多折腾太浪费时间,就去看T2。

第一感觉是高斯消元解线性方程组,接着想想发现一点也不靠谱。既然是生成树,就一定有什么性质,无环?

随后我的想法是,每个环至少有一条边不属于生成树,这样就可以对每个环询问L(L为环长)次确定环上是边是否属于要求的生成树,这样就能m次询问搞定了。然而只有暴力分。

优化了一会儿拿到51分,继续想,怎么想都只会m次询问的做法。

180min过去了,我得了198分。(Ag flag*3

之后继续搞T3,想想我的做法s不等于0为什么会错,原来s和左右端点夹住s的环不能套在一起。然后加了个贪心,先走到最近的环。

交上去还是50。然后发现5,4,3,2,1,0这种情况没有两个环是嵌套的。接着推出从环A能进环B的条件是A的最左和最右点之间存在B中的点。

看样子是求一个最短的包含s的区间使其能到所有环?写了个bitset+floyd+two pointers,只有12。

和s=0的拍了一会儿拍出WA,手算了一下才意识到在任何位置加边使s能到所有环就行了。

接着写了个复杂度不满的n^2 DP:f(l,r)表示从区间[l,r]出发至少加多少边能到所有环,用hash表存状态,过了70,最后一个Subtask TLE在第66个点。

继续推发现是个最小树形图,然而这东西我只会n^2暴力,想试图观察出什么性质也没观察出来,一定是我太弱了。

T2也没什么好的思路,连完全图都不会做。

最后延长了半小时,然而T2、T3都做不出来,很绝望。

97+51+70=218

两天加起来139+218=357,Ag稳,Au不太行,好虚啊。

出来问了下,xmk 250,lzz 267,myy 219,都比我高分啊。要是我Day1没丢70分就稳Au了。要是大家都会T2,T3……

出来看到中间榜我貌似#23?然后不少人发祝贺?然而还不是最终榜,好虚啊。

最终榜出来了,我#25,好像又卡了一次Au线啊。xmk#2,lzz#3。然而myy还是挂了,惨啊,myy在我心目中一直是最稳的,可是……为什么会这样呢?

仔细想想,我现在的成就有:CTSC 0AC得到Au,NOI 0AC得到Au,IOI 0AC得到Au,感觉没有谁同时拿过这三个成就了。


8月2日

上午去water park,以为自己退役了无所畏惧了,还是被某大型水滑梯吓怕了。后来玩了几个小型的。

下午Exhibition。


8月3日

闭幕式。

颁奖按排名从后往前的,然后我是Au上去的第二个。

又开始后悔D1T2了。


8月4日

考挂滚粗回家。

退役了。


CJK猫,CJK强,CJK是FZYZ的红太阳

尽管immortalCO就要上大学了,但immortalCO永远是FZYZ的红太阳。

评论

vfleaking
前排围观WA大大虐场
r_64
前排围观WA大大虐场
AntiLeaf
原来NOI Day2还有这么多比我烂的…… 心里平衡多了(雾
C_SUNSHINE
前排围观WA大大虐场
SNKMODE
前排围观WA爷爷虐场
zcysky
前排围观WA爷爷虐场
bzoj
前排围观WA爷爷虐场
Anonym
5L2g5riF5qWa5Zyw55+l6YGT5L2g5Y+q5piv5L6d6Z2g6L+Q5r CUCuS9oOa4healmuWcsOefpemBk+S9oOeahOiDveWKmwrkvaDm uIXmpZrlnLDnn6XpgZPkvaDnmoTmipXlhaXlkozmiJDlsLHmmK /kuI3miJDmr5TkvovnmoQK5Lqr5Y+X5pyA5ZCO55qE6ZSZ6KeJ CuWvueS9oOeahOWIpOWGs++8jOeOsOWcqOadpeS6hgo=
liu_cheng_ao
中排围观WA爷爷虐场
immortalCO
所以最后T3是什么问题?算法不对? 为啥这么多Exhibition啊。。
zx2003
WA爷爷加油!祝WA爷爷抱得Au归!
kczno1
exhibition是干嘛啊
zhouyi
WA爷爷day2加油!
Anonym
SnVkZ2VtZW50IGhhcyBiZWVuIG92ZXIgaGFsZgo=
samzhang
WA爷爷帅气5连Au辣!
zx2003
您可是今年IOI唯一个一个0AC就得到Au的啊!
DenyTianly
为myy yjq 默哀 祝ACM顺利 祝xmk lzz zzxIOI Au
Trinkle
https://www.zhihu.com/question/59156172/answer/168224345
Steaunk
zzx也是FZYZ的红太阳了
cxh007
zzx也是FZYZ的红太阳了

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。