[NOIP 2017]滚粗记

时间：2017-11-11（话说光棍节noip诶。）

Day 0

早早就去睡觉了，带来的结果是晚上入睡很难，脑子里总是蹦出来什么扩展gcd之类的不太熟悉的知识点。。。

Day 1

6：40 出发，前往吉大南校考试，路上很顺畅，并没有出现什么堵车之类的东西。到的时候发现还是有很多人已经到了。

7：30 开始抽签。 “离谱————！离谱到了吗？”感觉全场只有我反应过来那个老哥好像念错了(那个字是‘晋’啊！老哥你你该戴眼镜了。。。)，抽完签，二考场38号。

8：30 进入考场，等待下发解压密码的我发现其他人好像都可以看题了，原来解压包没有密码。
开始做题：

T1，好像是一道脑洞题？扩展gcd好像解不了。推了半面草纸式子发现没有什么太大的进展。继续往下看题。（讲真有点慌了。）

T2，这不是个大模拟吗？一会再码，不着急。

T3，分层图DP？？？-1的话判断一下是不是在1~n的一条可行路上存在0边构成的环就好了啊。感觉好像可写。

稳定了一下心情，重新推T1。
诶？？？可以用一些小聪明啊。。。假设x为答案，那么x+a一定可达，并且x+a=k1*b （k1< a） x+b=k2*a （k2< b） 。得到方程：(k1+1)*b=(k2+1)*a，a,b互质，只有一个解啊，不就是a*b-a-b么。。。检查了两个样例，发现没问题，又重新整理了一下思路，感觉稳了。（话说为什么不把最后的40%搞成多组数据啊。）此时考试时间已经过去了1h。

T2，码码码码。调大样例，找出了几处BUG。调过了就不管了。

看了一眼T3。纠结了一下拍T1还是写T3。最后还是拍了T1，过了。

看了下时间，还剩1h20min，上了一下厕所。

下面是噩梦的开始（我为什么开始慌啊。）：

T3，经过简单的思考后就开始码了（无限自责中。。。我好菜啊啊啊啊啊啊！！！），堆优化dij求最短路，然后spfa分层图DP（由于各种注意常数导致码了很长时间）。小样例没过，怎么调都调不出来了（重复更新）。看了一下时间（电脑上的），还剩30min。
果断放弃30分，直接分层图。改为枚举层，再枚举点更新。接着各种调，总感觉枚举点的顺序不对，改成了dij的最短路优化顺序。这应该对了啊。发现还是调不过。没事，我还有10min，一定能调出来的。

诶，怎么收卷了。瞬间出冷汗。电脑时间还有10min啊。啊啊啊啊啊啊！我的电脑的时间慢了10min！！！！
【后来发现，记录最短路顺序的计数器多组数据TMD没有清0，并且有些点可能都没有在这个出堆序中出现（从1节点不可达），dp的时候循环应该到计数器的位置，而不是n（可能有上一组的数据残留，影响结果）。哭死 QwQ 呜呜呜】

那一瞬间，怎么形容呢？？？感觉连破口大骂的愤怒都没有了，脑子一片空白，机械地离开考场，路过一些见过的面孔，耳朵里回响着讨论题解的一些声音，脑子却锈住了，一点都思考不了。
到楼下看到吉大机竞的战友们，好像都不错。
见到东东爸：“你考咋样啊？”“不咋样。”（突然感觉自己说话态度不对，然后脑子开始分析了起来）“前两题好像没有问题，T3没调出来，期望0分。总分期望200-”。
记得东东爸最后告诫我“千万不能因为今天的失误影响明天的考试”。（好像除了这种话也不能说什么了吧，考试的话，除了靠自己，别的，白扯）

和GXZlegend去吃了熟悉的旋转小火锅，强迫自己觉得在吃一顿大餐，实际上感觉从吃开始到最后都没有食欲，吃完，打车回家。
回到家之后，父母问道：“考得怎么样啊？”，“挺好的啊，感觉还不错。”，装出一副没什么事的样子，吃水果，和父母聊一会天，之后回到房间里睡觉，一觉睡到了晚上。
睡死过后终于活了过来，吃过晚饭。开始分析：“今天最高200,500+无望，明天得......”

老子可是lijinnn啊，怎么可能浑浑噩噩惨败啊？

调整心态2h+，终于有信心第二天好好考了，睡觉。
[day1分数：220]

Day 2

和第一天一样时间到，结果却没有几个人到，和CQzhangyu聊了第一天的考试。听说好像有很多人的表都慢。
进入考场，直接开始答题
昨天下午考普及用我电脑？？？昨天代码没删，删对拍代码？？？

T1，一眼并查集，判球相交开根精度好像不行，平方好像爆longlong（虽然并不是），开了longdouble。

T2，这不是状压？当前最深层数和可及情况为状态，预处理点到状态中任一点路径的最短长度，枚举子集算代价复杂度O(n^2*3^n)。
好像子集代价可以递推？研究了一下，真的可以。大概看了一眼T3，之后开始码T2。
调过了大样例之后巨开心（Jesus! paralysed and relieved）。

还剩1h40min，看了机房前面的表，确定真的是1h40min。

看T3，好像O(q^2)+平衡树可以80分。不会O(q^2)可以60。
想了一会O(q^2)，想不出来。打了30分裸暴力。剩下30分在犹豫写splay还是非旋转treap的过程中，选择了熟悉的splay。手玩了几组样例，过了，之后肉眼调试。

剩20min，各种检查。（突然反应过来好像昨天的失利并没有对今天产生影响，感觉自己棒棒的。）
不过话说我咋没检查出来T3需要开long long啊，好吧，我菜。

考完，期望分数260。[实际分数250]
成功讹到大师的顺风车，开心。
得知需要开long long后，总期望得分：450
[day2分数：250]

发分了

Day1 T3由于数据水得到了20分，感谢出题人。坐标弱省吉林，总分470。
宋爷和CQzhangyu由于DayT3大数据结构题不约而同地没开longlong，白丢50。
EdwardFrog，CQzhangyu，GXZlegend Day1 T3都被卡常了，70分。不过卡常什么的好像和我没关系啊（无力）。

完

mk703、Ciel退役了
Superbia_zyb说文化课学好了好像还是会回来的。
机房现在高二只剩下5人了。

总之还是可以的吧。坎坎坷坷什么的，如果没有的话，岂不是很无聊啊。