noip2015

其实考前一点紧张的情绪都没有。。一副与我无关的样子。。

看着同学都在颓我极不情愿地点开了吉丽的《集训队作业题解》

完了感觉作业要变成抄吉丽的了怎么办

day1

。。我猜今天有人1.5h内AK

T1我见过。。初中的时候觉得这是个神题。。果真我的初中过得跟别人的小学一样么

【我的T1做法】维护两个变量$i,j$表示上一个数的位置，模拟就好。

然后看了看T3。。一副CTSC那个showhand的即视感。。老天不想让我AK?不管了。

算了好像T2是水题。。应该就是最短环的长度。。就写了个正解写了个暴力拍拍拍!

【我的T2做法】v1[i]表示i是否被访问，v2[i]表示i是否被上一次之前访问。对于每一个没被访问过(v1_i=0)的点访问它能够到的所有点，用v1数组判环，用v2数组走环。

然后开始写T3。。抽出所有可以一次打出的牌集合。。好像不会T。。是个精确覆盖问题。。

不过我并不会写蛋斯因另克斯DLX。。。前几天做了LPARTY，但是偷懒写的随机。。日。。

写了个dp当做暴力。。一遍过大样例。。就换成搜索加了几个剪枝，用链表优化了一下发现极限数据需要0.6~2.2s。。反正只有一个极限数据我就不管了。。

就开始拍。。。

后来仔细读题发现大小王好像可以出现在三带一中但是不能出现在三带二中(我猜的，要是错了。。我反正还有10分)，改了一下不管了。

(无论怎么理解题目好像都可以过大样例)

然后检查了一个小时的文件名→_→ 为什么不打游戏呢

【我的T3做法】首先求出所有的可以一次打出的牌的集合，转化为精确覆盖问题，怎么好玩怎么搜。不保证能过。

day2

早上下雨了。。反正不下雨也很冷。。在车上就开始流鼻涕。。突然记起来今天没带卫生纸。。一个多么大的铺垫。

除了流鼻涕以外想的就是“反正noip越变越水，看老子今天AK”（结果今天闷声滚大粗

到了考场先看T3。。题目名称给我的第一印象是“货车运输”类似物。D2T3考树一般都是blockade这种神题。。算了滚回去看T1。。

T1是原题。。如果我没有记错的话二分答案贪心检验可以过。。妈蛋说好的考“无线网络发射器选址”这种题呢?为什么搬一个有思维难度的题?

感觉自己心态不对。。就快速写了T1开始拍。

【我的T1做法】二分答案，检验是否可以让相邻石头的距离都大于等于答案。检验的时候贪心，能不拿走的石头就不拿走。

看了一下T2这是显然的dp模型。。转移的时候枚举$A$中下一个区间取谁就好。。不过复杂度不对，不管了。

T3可以枚举每条边变成虫洞，$O(m)$检验，好像有$50$分。不过我是要AK的男人

然后翻数据范围发现有一个点$n=m=300000$，其他点都不超过$100000$，还特意标明了

(upd：pyx神犇说正解是$O(n\alpha(n))$的。。给跪

。。然后开始头晕流鼻涕。。天哪我居然感冒了，昨天还好好的TAT，今天每隔10s就打一次喷嚏。。感受一下。。

脑子还被一首歌洗脑了。。虽然是很喜欢听的歌。。赶快脑补另一首歌

一搞就是一个小时。。T2写了个dp方程是$O(nmk)$的，觉得过不了就没管了。。T3感觉好复杂。。dfs序上的矩形数点问题，用主席树维护一下说不定可以做。。才不写呢。

妈的这一个小时我就搞出这点东西

本来原计划是1h内干掉两个题?如果题目有去年那么水的话1h两个题是可以的。。结果搞了一个半小时毛都没有搞出来。。

感觉鼻子好了就赶快去写了T2的dp。。发现可以1s跑出极限随机数据。。试了试全a串果然要2s。。就去卡了卡常数。。卡到1.2s就弃疗了，放个爆搜开始拍。

【我的T2做法】$f_{i,j,k,l}$表示从$A_{1\dots i}$中选$k$个子串拼成$B_{1\dots j}$，最后一个字符($l==0$?有:没有)被选的方案数，转移枚举下一个字符有没有被选所以是$O(1)$的。总复杂度$O(nmk)$。

然后不管T2了开始想T3。。

【我的T3做法】首先找出$m$个运输计划中耗时最长的，必须把这条路径上的某条边变成虫洞。用堆维护经过/不经过一条边的路径集合，每次取出最大值。由于备选边的形状是链所以直接搞过去。。可以维护这两个堆。

没有时间了。。我11:00的时候还在码代码。。无视最后一个点算了，STL大法好。。好像是11:20还是30码完的。。

最后总算是调出来了。。不记得怎么写堆了写了个平衡树结果wa了，实在没有力气调。。

感觉今年noip和noi画风好像。。d1两道送肉题。。d2（不知道哪里像，反正我day2都是码不停蹄

回来的车上比较爽。。wyh2000说他T1写了个贪心。。立马被人hack了。。虽然我并没有看懂他的算法和数据。。

wyh2000又说他T3写的二分答案。。然后变成树上点事件啥的。。听起来比较好写，常数也小一些。。

跪跪跪

noip结束 以后再也没有正常的比赛等着我了（大雾）。

upd11.14

搞到了民间数据和程序。transport由于使用了STL跪了几个点(老爷机)。

wyh2000写错了landlords，$n=2$就挂了→_→你个傻逼叫你天天开dota2遭报应了吧

ymdragon老司机神神神

upd11.17

滚粗啦