由于我太狭隘了并不知道别的东西有哪些值得写，我就讲下自己这次参加WC比赛的状态吧。

考前几天刷了一波题：http://wronganswer.blog.uoj.ac/blog/2314 ，尽管改变不了我是无实力选手的事实。

8:35，终于开考了。

首先开场的时候看了下三道题。第一题看起来是个要推性质的题，我这种辣鸡水平就别想做出来了。第二题是个卡常数题，感觉很丧病。第三题是个构造类提交答案题，不太确定自己能搞多少分。

于是开场看第1题，发现有 10 分 $n\le 8$，开个 $8^7$ 的数组暴力 DFS 就过了，再看下面 $m=n-1$ 有 10 分，树上以 $0$ 为起点的路径只有 $n$ 条，DFS 枚举路径然后更新答案。后面还有 20 分 $m=n$，基环外向树，那么路径肯定是从起点往环上走，绕几圈，再往下走到终点，那么把起点和终点都移到根，去掉 $0$，看下环是不是循环同构的。

这样分三个 namespace 写就有 $40$ 分了，写完以后把树和暴力拍，过了，很开心，然后把基环外向树和暴力拍，WA 了，调了好久发现我只判了环是循环同构的，没判剩下树的部分相同，改完就过了。

接着再想有没别的部分分拿，想想网格图感觉就是个八数码，这不是 NP-Hard 的？又想了想每条边最多属于一个环的，发现两个环相接的不会处理，就放弃了。

这样第1题正常情况下就有 $40$ 了，接着看第2题。

第2题是个三合一，第一个Subtask是把 $n$ 个小于 $2^{32}$ 的非负整数排序，我会Radix Sort，不知效率如何。然后我就用链表写了个Radix Sort，写的时候发现指针数组 next 和存答案的数组 b 开了以后就爆内存了，就把输出答案的函数拷到了主程序里面一边遍历一边输出。写完过了测试点1，运行下测试点2，结果……

跑了10+s。

怎么办？我想一定是数组访问不连续导致这么慢。那就在Radix Sort之前先求出每个radix的出现次数，然后开一个连续的数组，算出每个radix对应的区间实现类似不定长数组来替代链表，改完以后WA了。调了好久才发现我原本是倒着 for，改写法以后要正着 for。这样测试点2跑进2s，测试点3……跑不过去。

觉得自己很没救就看子任务2，看起来像卷积，想FFT发现不会处理区间询问，如果再怎么处理一下复杂度就炸。这个点做法应该是压位？于是写了很久的压位，还调了很久，终于调出各种诸如 << 和 >> 打反之类的错误，终于过了测试点4，却过不了测试点5。想加优化，结果不管怎么优化都要跑十几秒。暴力分即视感。

感觉我真是逗比得不行，明明分没多，我干嘛去写细节巨狗的压位啊= =b

最后看子任务3，好像是Sereja的一道Codeforces题，那题正解好像就是 $O(n^2)$ 的，因此并没有犹豫就开始写暴力DP，开了滚动数组并且限制了有效的转移区间，常数挺小吧？然后样例WA了，就和不滚动的拍，意识到遇到 ( 的时候直接右移指针是错的，要把边界设成 $0$。这样就过了测试点6,7,8，然而9还是超时了一点。也懒得去卡这个常数了。

好像这样一共就有52分了。

比赛剩2h我才去看第3题，提交答案题。

由于时间不够，第3题我在做的时候完全处于一种手忙脚乱的状态。回想我去年CTSC二试的前半场也是这样，提交答案题一直刚不出多少分，但随着我搞出第二个点，以及用DAG骗到后面的点很高分以后就不虚了。然而今天……

先观察测试点1，直接把 $i$ 和 $P_i$ 连就能满足条件了，搞到6分。测试点2好像可以搜索，果断写暴搜，结果花了半小时一直调不出来，真是虚炸了。

由于之前吸取过经验教训，这种题应该写个通用贪心给每个点跑个部分分，然后想到了三天前杜教讲的一种 $O(n)$ 层排序网络，用这个给每个点骗了一些分，好像有19分了。可是只剩1h了……怎么办？

继续调第2个点，总之细节折腾了很久，好在最后终于调对了，然而也只跑出5分……汗。$n=9$ 就跑不出了，严重怀疑自己姿势有问题。

我浏览了一遍每个点，有的点明明知道性质却不会构造，深刻感受到自己是多么菜鸡。用暴搜似乎还能多跑过一两分。最后我还是专攻最后一个点。这个点的性质是每个排列都是把 $1,2,...,n$ 的 $n$ 和任意一个 $i$ 交换得到的排列。直接构造的 $num$ 和时间都是 $n-1$，第二组数据都过不了，那么我要把每个排列的 $n$ 聚集在一起，如果先连 $(1,2)(3,4)...$ 就能把时间差不多减半了，好像第二组数据能过了，于是写完 checker 一下，居然WA了。

百思不得其解，对着数据和方案看了很久，没发现问题，无奈手写了个 checker 输出方案发现跪了，原因是 $n-1$ 和 $n$ 交换导致非 $n$ 的数交换了。因此fix了一下构造，一开始不交换 $n-1,n$，后面再交换。终于正确了，然而仅仅多搞了1分。

再想想发现这其实可以做到 $O(\log n)$，就是类似BIT的构造。最后10min写出这个做法，然后，由于常数太大，这个点只有4分。

看了看我第3题才搞了28分，完了，滚粗了。

最后检查了下前2题，就这么遗憾地离开了考场。

我这一整场，根本没有搞出什么有意义的分数。

第一题，不过写了三个暴力罢了。

第二题，并没有卡过哪个难卡过的点。

第三题，只有28的低分。

而且还不知道会写挂哪个题，第三题不太可能写挂，如果第一题和第二题有一个挂了，那么100分都上不了。

被提交答案题虐惨。

GG。

出了考场，听说了一些事情。

听说matthew99第1题得到60+高分。

听说GD神犇第2题得到70-80的高分。

听说fateice第3题得了高分。

这么一来，我就算一题都没挂，40+52+28也会被虐得好惨。

最后去看成绩，一分没挂，40+52+28=120。也是挺幸运的吧。

xumingkuan第1题70分，而且改一改就能AC了。cy第2题79分，过了子任务2，好劲啊。fateice第3题38分，还有好多人第3题得了30以上。matthew99 130+，yyt16384 140+。讲题的时候matthew99表示自己开考半个小时就想到了第1题 $O(n^5)$ 的做法，然而我第1题啥思路都没有，还以为是 NP-Hard 的。果然实力差距太大根本比不上啊。

都高二了还是只会打暴力，提交答案题完全做不动。深刻感受到我的实力还有待加强。

这个猫老师immortalCO。。。强行把我也变成猫，感觉都有人误认为我和immortalCO一样都是猫了。。。我很不开心呐。。。

暴力%猫

#include<cstdio>
int main(){
    char*Solve_NP_Hard_Problem="#~_!vk%NP";
    for(int i=0;i<9;i++)putchar(10-Solve_NP_Hard_Problem[i]);
}

以下是闭幕式以后的更新部分。

看了颁奖，最后我们学校的结果是：immortalCO和我进了候选队，非集训队1金1银4铜。dick32165401确实挺稳，Au了。wzt有点惨，由于第1题没打满暴力只得了10分，离Au线差了10分。ziqian、Paladin、3A17K、chentong都没有拿到基本分，Cu。

首先感觉这场的基本分还是有的。第1题暴力有40分，即使没有immortalCO这么强的实力5min写一个程序解决40分，也可以像我这种SB一样写三个程序做三档部分分同样得到40分。第2题就算没听课的话21分也很好搞，如果加一些优化就能得到40以上的分数。第3题的第1个点规律很容易看出，6分应该是很基本的了，如果有听课会 $O(n)$ 深度的排序网络的话能得到更高的分数。

如果40+21+6=67就有Ag了，如果再多得一些分就有Au了。WC这种比赛就是暴力之战，暴力打挂是没什么希望的。（其实也只是我运气比较好罢了，WC前几天一直写挂题一直写挂题，然后到了WC就莫名其妙不挂了……不过这样的运气肯定不会持久下去）

其次关于比赛的不确定性，这个我早在NOI2016的时候就已深刻感受到了，不少比我强得多的大神考挂了。实力超强的C_SUNSHINE，WC垫底了（我只是开个玩笑，事实是他出国了而没法回国参加WC）。NOI前几名的AcrossTheSky有点惨，WC考挂差了几名退役了。isdkfj也挺遗憾的，WC 100+分并没有翻回来。FJOI一试rank1的zhshr和集训队的victbr也意外地考挂了。另外集训队也有些曾获得WC Au的神犇因为失误而没达到Au线[蜡烛]

不少人吐槽题目坑，尤其是第2题的卡常数。不过好像好多年WC都有人喷吧……比如WC2015的T2坑爹的“随堂测验”题，T3是个传统题十合一，已有不少人抗议；WC2016的T3也被点了很多差评，等等。当然今年T2的丧病底层优化常数题确实是我第一次见到= =（我比较好奇这题如果搬到UOJ，时限该怎么调，呵呵）这种题个人感觉也不会发展下去。

当然大多数的神犇都得到了很高的成绩。这里是我的个人看法：尽管有不少人吐槽WC的题不合理之类的，但区分度还是有的，集训队的成绩普遍比非集训队高，Au选手往往都有较高的实力，可以从NOIP成绩中看出来（当然NOIP考挂并不代表实力不强）。

最后，尽管我WC并没有什么遗憾，并没有写挂题，但我也明白自己的水平和真正的神犇之间还是有相当大距离的。接着就是第二轮作业、互测、论文答辩了，打算多刷一些Codeforces题，接触一些新知识点。