CQOI2018 流水账

最近有幸参加了CQOI2018，觉得题目非常的难，就来更一发博客。

这么简单的题是哪个出题人出的，CQ有那么弱？好歹今去年noip一等分数线是全国并列第三啊

所以下面的部分绝大多数都是游记而不是题解。

Day 0

小机房整个上午都在口胡bzoj上的题，嘴巴AC感觉真爽啊。

花比较久的时间学习了一波最大最小容斥，即$max\{S\}=\sum_{T\subset S}min\{T\}(-1)^{|T|+1}$，然后发现除了过那一道题以外并没有什么用就是个把$O(n)$求最大值的算法优化为$O(n2^n)$的优秀算法啊。本来打算好好打一波板子，结果只打了一个Miller Rabin和Pollard Rho 。

临近饭点看代老板开炉石卡包，所有人都体验了一番。OBlack和Sparrow似乎体验到了快感于是第二天入了炉石的坑= =。

下午和OBlack、Sparrow坐老板的车去重邮看考场。老板让我们背板子，被我以在车上背板子会晕车为由水掉了。

今年重邮换了二维码大楼作为新的考场，不知道楼上的二维码扫了有何用。

新机房的环境还不错，电脑屏幕略小，键盘和学校的是同款，手感还行。

一开始的座位表真是劲啊，按照noip分数排座位，为了防止一堆dalao集体AK临时随机打乱了一波。

下午的试机心态爆炸，敲了个FFT的板和NTT的板，结果都炸了。顿时觉得第二天药丸。

晚上被代老板拐到一家比较普通的餐馆吃饭，价格和口感都是学校食堂水平。

回到宾馆开始临时抱佛脚。复习了一波很久没搞的虚树，打了一下Splay和treap的板。老板说CQ每年必考网络流，所以看了许多网络流的题目，复习了上下界网络流。

现在看来或成第二大flag

突然想起来有个BSGS算法，OBlack最近才讲过。觉得不怎么会考就看了一波原理，觉得理解之后连代码都不想抄就直接睡觉了。

现在看来或成最大flag

Day 1

早上八点到考场，老板把我们集中起来强调了一下注意事项：遇到不能AC的题，尽量把暴力分拿全，你做不起别人也做不起。之后发现好像没有做不起的题。

解压密码NOI2018-cq-cs，好像很劲的样子。

于是就开题辣：

T1一看：woc原根，难道要求原根吗？那岂不是GG？结果发现质数和对应的原根都是题目给好的，松了一口气。题目读完后心态爆炸：这岂不是裸的BSGS算法？感觉前一天好亏啊。于是本蒟蒻就在考场上花了2h推导+对拍。

T2一看：这好像是生成树计数的裸题啊？再次确认了数据范围和题面之后发现好像真是裸题。10min打完收工。

T3一眼看上去是一道矩乘，n的范围很大而a和b的范围很小，似乎可以二项式展开。然而发现乘积的形式根本没办法搞。想了半天之后发现n的范围好像也不是特别大——1e7的样子允许$O(n)$的做法。然后想到枚举0的个数发现最后答案是一个组合数乘上两个数的乘方再求和的形式，似乎很可做。然后智障的我始终放不下二项式展开的想法，以为展开之后就可以化简，最后发现并不能化简所以强行给自己乘上了45的常数打出GG。考后才发现不化简能拿更高的分，而且这种做法可能会T（从结果上来说真的T了）。

考完Day1，估分230+。觉得心头一凉：这种难度的题怎么拉出差距啊，我noip因为Day2T1挂了考得很惨啊。这样搞似乎要退役？

下午在宾馆看OBlack和Sparrow打炉石。第二次看到Sparrow大神打游戏——上一次是一个诡异的叫Lapse的游戏。

身为去年出题人的董神押了一下题。晚上复习了一波网络流，复习了一波很久没搞的虚树，打了一下Splay和treap的板，看了一下许久没写的CDQ分治。

按照CQ出题的尿性，第二天恐怕有一道数据结构、一道网络流、一道树DP吧？

结果最后都没有考

Day 2

早上八点到考场，老板把我们集中起来强调了一下注意事项：Day1的题目比较简单，Day2的题目可能会难一些之后发现还是一如既往的水。如果题目还是很简单就要求稳。

其实这时候是挺想要Day2的题目难一点的，感觉大家都可以很稳。如果还是很简单就可能会出现省选得分500+却因为noip得分低而退役的尴尬局面。

解压密码GotoCS-2018，和昨天没什么区别啊。2018赶快来玩CS,这是你没有碗过的船新版本

然后就开题辣：

通读了题目之后其实先做的T3：这不是某个讲莫队算法的ppt里面的例题吗？0.5h打完代码并开始对拍。顺便吐槽一波辣鸡出题人，出原题就算了，还混淆子序列和子串，差点就以为是一道难题了。

T1第一眼觉得很像noip前讲过的一道比较神的DP，所以做完了T3才仔细看题。结果观察数据范围之后发现是状压DP水题。加了一点优化之后试了下极限数据，稳。

最后看T2。这是什么我没有碗过的船新游戏啊，但是感觉可能和汉诺塔一样有一个递推/通项公式。写了爆搜打表一看果然发现了规律。此时才猛然发现这题求方案数却没有取模，原来是一道高精度。算了下裸递推复杂度感觉会被卡。写完之后发现极限数据果然要跑1s+。想到了一个很显然的似乎能减少一半时间的优化，写上去发现极限数据跑0.7s左右，觉得比较稳就没管了。这个时候比赛大概过去了2h+。

然后我就开了3个对拍开始玩扫雷了，感觉自己Day2的AK稳了

下午出成绩，发现Day2T2只有80。本机测了一下发现全都能过，于是去申诉。申诉之后发现还是只有80，觉得很玄学。

Day1得分235，Day2得分280。然而有两个AK的dalao，%%%。

然后就以最后一名的成绩侥幸进队了，心情有点复杂。目测了一下这次省选CQ大概有10个500+，在noip只考了460的成绩下勉强进队也算是运气吧。

出考场的时候，老板说：你是我见过的运气最好的选手。冬令营能够压线进，省队也能够压线进。

现在回想起来，要是当时noip做Day2的时候不那么马虎，现在根本不会无法进队的担心吧。

身边几个同学退役了，即使遇上了这样的幸运也高兴不起来。

不管怎么说，接下来又是新的开始了。接下来好好搞吧。

再一次到长沙后，希望不要带着遗憾离开。