本文作者系IOI2017金牌获得者钟知闲，转自作者博客。

2017年7月29日

练习赛。

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

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

T2水题切了。

T3水题切了。

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

70+100+100+60=330

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

2017年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个点。然后就浪费了半个多小时（Agflag

已经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，成千古罪人。想想真是太后悔了。

2017年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+twopointers，只有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在我心目中一直是最稳的，可是……为什么会这样呢？

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

--end--

声明：本文章由网友投稿作为教育分享用途，如有侵权原作者可通过邮件及时和我们联系删除：freemanzk@qq.com