感觉我的高二并没有什么进步唉。。。省选Day2连滚两题被翻，WC提答滚粗，CTSC Day2爆炸，APIO被虐。。。依旧一堆题不会做。。。

LOJ NOI Round

Day 1

和省队集训Day 0冲突，用手机在空余时间写的。

T1看完想到O(n^2)的DP，再想想就会O(n+k)了，很快写完。

T2看完想到清华集训2015D1T1，然而细节还是折腾了好一段时间，花了好久才调好。

T3没时间搞，打了个不知道啥复杂度的暴力，实测1e13能跑出来。

期望得分100+100+78=278，实际得分100+80+78=258。

T2写的应该是正解，不明原因被卡常。

又是rank 4。

回宾馆改题，T2跑一组数据发现瓶颈在求逆元，换成标程的那种exgcd就快了一倍，卡过去了。时限1.2s的题标程跑了0.9s，有点想骂出题人。

T3给我的O(sqrt(N))程序加了两个优化就直接AC了。然而考场上没时间了，唉。

AK的hzq84621好像T3写的是O(N^(3/7))标算？好强啊orz

嗯，继续努力。

Day 2

和省队集训Day 2冲突，没时间打。吃完午饭回宾馆想rush一下T1的75分，没rush出来。

期望得分0+0+0=0，实际得分0+0+0=0。

垫底了。

最后两天总分258。Au线364，Ag线283，Cu线216。拿了个Cu。

省队集训

作为非省队选手参加了省队集训。。。果然被屠了。

Day 0

省队互测，大概是15个省队队员加我一个非省队，每人准备一道题完成讲解。（大概是看我去年进了省队但去年没互测于是就给了我这个机会，十分感动。。。于是我成为参加互测的最差选手）

萌萌哒aufeas姐（额好像不能这么称呼。。）第一个上场，dp优化网络流真有趣。虽然她的题我好像不到一小时做出来了。。。

张队长和初三大佬zzq的字符串题也好劲啊。作为不会**自动机的选手在听wrz和张队长题时只能当吃瓜群众。

victbr的原创题也很强。表示我也掉了分块坑。

闫神太巨了，出了一道神级结论题，做法是转成图论问题然后怎么怎么解决。第一步都没看出来的我表示一脸懵逼。。。

猫锟强，临场讲了好几题的更优算法。（然而一直说我是猫说yhx是猫说wrz是猫是什么鬼啊。。。

yhx和ct讲的都是猫锟出的模拟赛题。

作为非正式选手的我最后一个讲。。。讲的是我去年出的校内模拟题。做法很sb，没用什么算法，就是打表找规律然后构造。。。感觉我是最菜的出题人。。。

讲题时台下很欢乐。

zzq现场切了我的题，写出来了。

不得不说现在的省队爷都好劲啊，技不如人甘拜下风。整个听讲过程我不是在膜出题人就是在膜锟膜闫神膜zzq，然而只会膜不会提高自己姿势水平有什么卵用呢。就要退役了我还是啥都不会怎么办啊。

Day 1

出题人：猫锟（immortalCO）

看了三题，T1是个字符串题，T2是个APIO2016T1的改版，好像能做，T3像之前一道校内训练的题，但是改了，题面很长没看完。

先做T2，想了一会儿发现原题做法用不了，，只能用维护分段函数的做法。O(n^3)。然后花了2h才打对，我好菜啊。

测了一组极限数据直接就跑不出来了，感觉600过不去只能过100。

然后做T1，推推式子发现对S的每个前缀和每个后缀求出它与所有s[i]的LCP之和就做完了。由于不懂SAM的性质就打了个后缀数组+Trie+二分，3e7*log(3e6)的。

又花了1.5h才打完。随机了一组极限数据又跑不出来了，把n改小了看看后缀数组循环次数，发现n=100000只循环了4轮，n=300000却循环满了，感觉像写挂了，就调了很久但无果。后来想想好像Windows的rand有奇怪的循环节就貌似明白了，没管。感觉只拿30+分。

最后只剩半个小时了，T3勉强看完题没时间做，随便打了个贪心连样例都过不去，就结束了。

期望得分在50到140之间吧。

听说很多人都A了两题，好虚啊。

成绩出来了，在期望得分之内，38+18+0=56，rank5。

T2果然被卡常GG。去申诉，重测了一发T2变成31分了。还有不少人申诉，很多原来分数很低的人都翻上来了。

最后成绩38+31+0=69，rank9。

aufeas姐好强啊130怒拿rank1。闫神A掉T2怒拿rank2。T2脑抽了，本来只要维护一个函数，我按<,=,>三个符号维护了三个函数，2s时限跑了2.5s，100被卡成31，打满暴力都比这个高分。不过想想能有前10也还凑合。

回去改题，T2果然换一种记状态方法直接常数除以3，就AC了。T1瓶颈在后缀数组……3e6log3e62比3e7*log3e7还慢，果然后缀数组常数大如nlogn。

下场加油吧。

Day 2

出题人：n+e（Trinkle）

T1看完以后想到二分答案BIT判定，复杂度nlog²n不知道能不能过3e5。写完之后随便构了一组极限数据跑0.8s+，感觉不是很虚就扔一边了。

T2是个提答，感觉正解是构造，然而想了很久还是不会构造，连个可行解都构不出来，一分都没有，就先跳过。

T3就是个方格取数的简单DP，然而一副卡常数的样子。写完过了样例以后把样例的n，m改大，跑了8s+，优化了一发数组访问跑了4s+，不知道能不能A。

回去搞T2，写了个贪心结果根本不能出可行解，又各种修改贪心姿势仍然无果。手玩了一会儿小数据也构造不出来。浪费了很多时间提答还是0分，非常虚。

接着放弃了贪心，考虑别的做法。先想能不能状压DP，结果第一个点棋盘大小就巨大。。 又分析了一下性质，对于源点入度=0，对于汇点出度=0，其它点入度=出度<=1。这样就能费用流了？

怒写费用流，跑了会跑出前三个点60分，后两个点跑不出来。尝试优化费用流无果。

后来打算退而求其次跑可行解骗分，也跑不出来。

最后期望得分220-260之间吧。

成绩出来，预计得分之内，100+60+90=250，rank2。T3被卡常数了。

已经连续三场比赛被卡常数了。

ditoly 296分虐场了，T2用primal dual跑了96分，不能更神。

后来知道我T3为什么被卡常数了，我作死在读入的时候对输入的数做了前缀和，然后访问2.5e7大小的64位数组慢得要死。

Day 3

出题人：叶队长（isdkfj）

第一题看完感觉出现恰好一次的数对应的区间可以化成平面矩形区域，找出每个数的下一个和它相等的数之后就可以用线段树维护了，似乎不难写。

第二题看完感觉是个神题，先跳过。

第三题是个提交答案题，输入文件是一个C++程序，要求给一组输入使其输出最小。似乎很好玩。

于是刚了2h的第三题，觉得大概能有80分的样子。有几个点看不出怎么做就随机化乱搞。

回去写掉第一题，发现n=500000极限数据要跑2.2s，有点萎。优化常数无果。可能要被卡成60了。

剩下一个半小时开搞第二题。推了一会儿式子，把和式交换了下求和次序，又套了一层反演，推出一个O(n^3)算法。然而数据范围第一个点n就是2000，完蛋了要爆0了。

写了O(n^3)过了样例，想继续优化复杂度但没时间了。

期望得分140-190。

听说有人推出T2的100分做法FFT，感觉我今天要滚粗啦。

最后还是预期之内，100+0+76=176，rank1。提答有几个点小范围暴搜猜错结论掉了不少分，最后一个点随机化直接爆0。ditoly 175分，rank2，算上前两天ditoly在我前面很多的样子，感觉ditoly要win啦。

fateice提答95分，跪烂。

T2全场都是0分，有毒。

Day 4

出题人：闫神（fateice）

第一题看完没有除了数据结构优化DP以外的任何想法，然后想想发现树状数组似乎不行，就写了线段树。写完测下极限数据1.4s，怕TLE，就优化了一会儿线段树的常数，又写了个输入优化卡到0.9s，感觉能过就不管了。

第二题是个几何题，求包含边长为1的正n边形的最小正m边形，要求两者中心相同。感觉不是很有思路就先写了特判部分数据，剩下的分段爬山。期望50分。

第三题是个类似ZJOI随机树生成器的提答，要求识别树是随机kruskal生成的还是其点分治树。手写了个生成器然后打出各种特征，发现直径的区分效果最明显，就用直径划分来判断生成了out。后来想想小数据好像有反例，又搞了很久的第一个点，加了各种特征发现和原来的输出没差别就不玩了。期望得分90-100。

回去推第二题，发现了一些奥妙重重的性质，推了好久的端点，貌似取过顶点第一条线的倾斜角为π*gcd(n,m)/nm好像就行了。然而式子一直写错，直到考试最后几分钟才调出来。尽管如此还是担心卡精度不知道能不能拿到100。

期望得分240-300。

一开始文件不小心放在子文件夹里面，考完以后闫神问我为什么没交，才改过来。差点爆0。

最后得分100+100+99=299，rank2。第一题只跑了0.3s+，第二题也没卡精度，第三题第一个点掉了1分。

zzq AK了，orz。wrz第二题模拟退火过了，也是299。ct第三题A了，好强啊。

看完题解发现我第三题SB了，直接判断一棵树是否可能是点分治树就行了，还面向数据找了那么久的规律，就跪了。想想我到现在还不会分析问题性质，吃枣药丸。

Day 5

出题人：wyf

T1是求把平面点集用一条不经过任何点的直线分成两组的方案数，要求某些点集属于同一组。看完我大致想到一种做法，枚举两个点连一条直线切成两块，判断是否合法。然而线上的点要归哪一边？有点懵逼地继续想，好像可以假设线上的点归同一边。但是好像会算重，那就hash去重咯。

然后就开始考虑枚举一个点，其他点极角排序以后扫描。然而这东西细节真的多。。。旋转的时候分上下有没有点考虑了各种情况。也不知道有没漏。

折腾了快2h终于过样例，然后随便拍几组数据就炸了，调的时候发现bug一大堆。于是继续改改，改了好久，随机数据答案终于对了。

已经2.5h了，时间过半，感觉后两题不太可能都做出来。T2是个字符串计数，T3是个纯数据结构，凭感觉估计T3是什么黑科技题，不太能做，就打了T3的暴力，之后全程刚T2。

T2求的是长度和s相同的小写字符串有多少个字典序不大于s，且它的本身是其所有循环同构中字典序最小的。

一开始把最小表示串打出来想找规律，结果找了很久没发现有用的性质。接着想到，这其实就是求不循环同构的字符串个数，可以burnside引理搞搞。

然而字典序不会处理。又推了好久，把字典序转成了子串包含约束，然后貌似可以KMP搞搞？

先写了个暴力过了样例。

这时候大概剩半个多小时了，推KMP+DP各种环上细节处理不清楚。似乎想出了40～70分，结果最后还是没能写出哪怕比暴力分高一点点的做法。

期望得分150。第一题可能会挂所以还是很虚。

最后果然就滚粗了，0+20+30=50，rank11。T1写挂爆0。

全世界都A了T3。

全程刚前两题，结果一题写挂，一题没刚出来。感觉我这是回家种田的节奏。

晚上调T1，看了会代码发现我犯了一个弱智错误：输入的点编号从1开始，我数组下标从0开始，忘了减1。对拍的数据不是m=0就是分组很规律而且答案很小，没发现问题。于是只可能过m=0的点，然而我m=0的点被卡常数TLE了。改完弱智错误就80分了，再写个radix sort就100分了。

T2推了一晚还是只会n^3。然而T3的分块想了十分钟，打了一个多小时就A了。看来T3真的比T2可做得多，以及我真的很蠢。

Day 6

出题人：ExfJoe

T1又是类似清华集训2015遥远的星系的题，一开始打了个并查集，结果好像会爆long long，就把并查集全删了改成DFS树。改完以后过了大样例，感觉不是很虚就扔一边了。

T2是树的动态加边求连通块最大基数独立集。看完想想不会是链分治模板题吧，上次写链分治写一下午没调出来已经有心理阴影了，而且这个做法常数很大，200000 1s应该没救。看来一定有更简单做法。只是一时没想到，先跳过。

T3是个十合一提答，求10份代码的输出的期望。代码不用C++用Javascript差评，虽然我看得懂。

折腾了2h搞出了六七个点，也不知道有没错。看了下时间只剩一个半小时了再不做T2就来不及了。

思考了一下觉得这题的性质在于最大基数，可以贪心从下往上取独立集。接着就会了一种启发式合并+暴力扫描到根的链的做法，应该能有50分，写完过了大样例。

继续想这东西怎么数据结构维护，似乎记一个c表示翻转i会不会导致i的父结点状态改变就可以了？找到第一个这样的祖先，端点讨论一下。这可以用树剖线段树维护。

只剩不到半小时，狂码树剖线段树以及维护独立集和c数组，然而主过程还没打，就结束了。

于是乎T2只剩暴力分了。

期望得分210-220。

最后100+35+61=196，rank 4。T2喜闻乐见地挂了50分，然而子任务3水过去了，得分35。很多人T2都是85或者100。

dick32165401虐场了。

回去调代码，发现把启发式合并改成大的往小的里面合并样例就过不去了，原来是因为我记fu是u所在并查集的根，交换u，v的时候忘了重新求fu。然而样例是按子任务3（逐个添加叶结点）造的，没查出错。白丢50分。

后来出题人发现T2一堆人过85分是因为数据造水了。。。然后改数据重测。惊讶地发现我T2还是35分。。。数据还是水？于是莫名其妙地rank 1了。

总结

省队集训结束，成绩比去年还糟。我做出来的题都是一堆人A，我花大量时间想搞的题最后没有一题做出来。

不是自己退步了，就是别人进步得更快。

挺后悔自己高二没有认真刷题的。平时总觉得自己已经很努力了，然而一到考试才明白别人比我努力得更多。

CodeM 复赛

T1看完以为值就是<个数减>个数，随手DP了下组合数结果没过样例，跑了下n=2才知道哪里错了，<>是2不是0。。。然后想到状态里记还没匹配的>个数的一个n^2 DP，写完发现又炸了才知道转移不对，把记一个东西改成了记两个东西，又推了好一会儿才推对。浪费了不少时间。

T2看完发现求的是链上单调栈大小这一玩意，感觉强行树剖维护单调栈不太行。接着直接照着题意想，就想到一个算法：先找出第一个大于c的祖先，然后每次找最近的大于当前点的祖先往上跳。用倍增优化下就一个log了。然后就很快搞定了。

T3求的是一个模线性方程组，不过变量之间的关系构成了基环外向树。那就环上绕一圈列个方程解出来，外向树直接递推。调过样例以后不放心，随机生成了一组数据，结果WA了。调了调发现数据生成器写错了。再生成又WA，发现树的父结点记错了2333总之改了很久才A。

T4看完题以为i能作为最终结果的条件是i右上没有点，左上和右下都在i后面。写完以后样例没过，再想想发现结论是错的。接着想枚举出现过的点集S，是x，y严格递增的，然后确定剩下的点的位置，把剩下点插进S有(n-1)!/∏(i右上角点数|i∈S且i不是S最后一个点)种方案。把枚举换成DP就n^2了，用BIT优化就nlogn了。

T5是个构造题，一开始想贪心，结果构造出来的是fibonacci数列，不是根号的而是log的。想二进制分解也不行。想用多进制数来构造，分成两组，每组递归下去，然后一组乘个系数加个常数，结果打出来发现甚至不如fibonacci数。想构1²，2²，3²……到8就出反例，想打表找规律结果没发现任何规律。

最后还是没做出T5。去看T6想到一种两个log的线段树优化DP，感觉过不去。最后抱着弃疗的心态写，没写完。

最后过了4题，名次好像很后面的样子。考后讨论了下全世界都会T5的构造，zzq好像还是一眼秒的，做法是取一个sqrt(n/2)以内的质数p构造2pi+(i²mod p)。感觉我打死也想不到。。。一定是我太弱了。

还是很好奇大家是怎么想出来的。。。

总结

构造题姿势水平不够，要多接触这类问题。

Codeforces Round #424 Div. 1

A题看完就会做了，最优解people和key的对应关系不会交叉，排序以后DP一下就行了。

B题好像是个大模拟，排序以后按环的顺序取，用个树状数组维护区间内被取出的数量。半小时左右的时候写完。

C题看完想到UOJ#21缩进优化，不过n<=100，a<=10^9，那就是用UOJ#21的70分做法咯。由于怕多个log被卡，写了radix sort对端点排序。一遍过Pretest有点爽。

D题想分成过根的和不过根的路径考虑，如果过根并且被根分成的两段在同一子树，就要用2条路径覆盖一个子树。然后想到的做法是f(i,j)表示用j条路径覆盖i层图的方案数，转移分了好多类情况讨论。居然写完就过样例了，好爽。

E题想了一段时间，想出了有环的图以及存在度数大于3的点的图如何构造，并且还构造错了。。。图是二叉树的情况没搞出来（也许直接输出NO？糟糕，有反例。。。），于是E题就没过。

最后rank 10，涨了201的rating，终于上红了，十分感动。这也是我打了这么多场CF里面成绩最好的一次，这场CF难度似乎比以往水，前4题都很快想到了做法，并且也都写对了。往常打CF我最多做出3题。当然也有可能仅仅是我这次的题我刚好会做。

NOI2017 网上同步赛

Day 1

滚粗。

T1目测线段树裸题，结果花了2h才调过所有样例。

T2目测链表+hash裸题，花1h过完样例之后发现样例5开-m32要跑1s+，感觉过不了最大的点，要卡成80了。

T3。。。连续三年NOI D1T3都是读入O(1)的题。。。

我的想法是，如果要求那个玩意，就要用一个单调栈。那么能不能状压单调栈呢？

发现好像可以，而且只要状压2sqrt(K)段的样子。。。然后就觉得N<=1000，K<=10的稳了。

然后我就掉坑了。。。一直在想这个东西怎么优化，优化不了，就想能不能换一种记状态的方式。然而从头到尾思路都是从左到右确定每个高度，压根没想到枚举最小值的位置DP。。。然后还想容斥，也不行。。。于是2h都没想出来。。。唉。。。

最后交了40分暴力，感觉上不了金牌线了。

期望得分：100+80+40=220

去年Day1都有247。。。幸亏早生一年。

后来大家说T3和UNR D2T1撞题，想想发现还真是。。。而且UNR我还做过！人家学的是OI，我学的是什么？暴力？

出成绩，全世界都会T3我不会，一堆人A了T3我只有40。matthew99，fateice，RXDoi都是292，我220。pyz5715，fjzzq2002，victbr也都比我高分。

估计了下我的排名只有30+，比去年还糟糕。

晚上回去把T3的正解打出来了。

心情很不好。

为什么这么简单的一个DP我就是想不到。

为什么最大子矩形我没有除了单调栈和容斥以外的别的想法。最土的办法都没有想到。

枚举第一个最小值在什么位置，求出靠底边的最大子矩形，然后沿最小值位置分开递归下去。

这个可能我高一的时候都会吧。

状压单调栈完全没有优化的余地，我却想了很久怎么优化。

为什么做UNR的时候我都懂这个道理，在考场上就忘了。

白丢60分。

我的脑子去哪了？

我真的是学OI的吗？

曾经以为我学了这么久OI，面对题目必有高论。

然而真正在题目面前，我感受到了自己是多么无力。

看看周围的人，没有一个人像我这么SB，唯独我SB了。

Day 2

滚粗更严重了。

T1看完题目就大致会做了，2^d暴力枚举x的状态2-SAT。写了1.5h。然而发现极限数据要跑1s+，过不了。

然后简单写了个check测了下样例，一开始check写错以为样例过了，后来故意把out改错发现check还是输出OK，才发现check写错了。改完以后样例挂了，就改了改过了样例。

这时候过了2h。

T2看完以后感觉很可做。

然后开始想，一开始想贪心，想了一会儿的结论发现很迷。。。就去看了下样例，手玩了一会儿发现不对？

然后发现题目理解错了。。。原来不是每次-x，而是变质的部分是确定的。。。md浪费了一个小时。。。

接着发现原先想的结论都是错的，继续想。

想了一会儿感觉好像还是可以贪心的，但是不知道怎么处理s的限制。。。

接着又开始想别的思路，想想发现费用流好像可以做？

接着开始写费用流，写完以后过了样例1，样例2根本跑不出来。输出了下中间结果比对了下好像是对的。

然后想优化费用流，想了一种思路以后发现有问题，叉掉了。。。

又想贪心，然而不知道哪个地方想错了，都贪不对。

剩一个多小时的时候很慌，赶紧去打了T3暴力，回来继续想。

当时十分紧张，感觉要是想不出来就GG了，结果越紧张越想不出来。

折腾了快三个小时，还是只会暴力费用流。

最后十几分钟想到了把图反过来建，好像可以优化，然而时间不够，只好放弃。

期望得分：90+40+20=150

然而更悲剧的事情在后面。

T2挂成4分。

于是总分90+4+20=114。

Cu分数吧。

当时我的心情是绝望的。

结果两天加起来334，如果算上笔试和A队439，集训队线436，刚好超过集训队线一点点。。。感动。当然这个成绩我还是十分不满意的。

回去调费用流，发现我答案没开64位整数以及每天的最后一条边忘了把边权设为剩余库存，改完就60分了。挂成这样居然能过样例1和样例2的一部分，还能有4分让我不至于掉出集训队线，真是喜闻乐见。

继续推费用流，发现我考场上SB地多建了一层点。把图反过来建再去掉这一层点就直接变成喜闻乐见的贪心模型了。

如此简单的80分算法，被我硬生生丢掉了20，又挂成了4分。

我的脑子去哪里了？

这个思想我在校内训练出过不止一次的。

为什么我考场上就是没想出来？

我又问了一次自己，我真的是学OI的吗？

T2我考场上完全应该得到至少80分的。

然而大家都拿到了，我没有。

也许我考场上不是在想题，是在挣扎。

害怕自己想不出来，越想越紧张。

结果越挣扎越出不来。

越挣扎陷越深。

这时，我才真正感受到心态有多么重要。

心态毁了我一整场比赛。

可是，又该怎么办呢？

总结

总结这次NOI的情况，就是：一试脑抽，二试脑抽+心态爆炸+写挂一题，最后名次十分惨淡。

一方面，我从高一到现在几乎没有进步，甚至退步。平时看起来都在努力，但颓的时间太多，而别人的努力比自己多得多。

另一方面，我总以为过了这一年进步很大，考场上总以一种拿前3的目标去打，然后越想不出来，就越急，越急，思路就越乱。比如这次D2T2，参数很多，如果思路急是一定不可能想清楚的。但我由于一开始看错题浪费一个小时，导致只剩两小时左右时就紧张了，思路开始混乱。其实考场上我已经想到了优化费用流，如果我冷静下来，得到80分算法完全没有问题的。这次NOI让我第一次感受到，考场心态真的很重要。

这次NOI没有一题是我得心应手的，暴露了我的实力和心态方面的诸多问题。可以说是IOI前的一次教训。