高二第二次参加省冬令营以及省选。退役前的倒数第二次冬令营。

并不希望得到多么好的成绩，只希望不要挂得太惨。

1月18日

报到。由于是外地生，和Paladin100100住进了宾馆。宾馆的质量不想吐槽。

晚上刷TC。一个晚上才刚出一道SRM 594的550网络流，1000想了个DP感觉可以优化然而没做出来，SRM 595的900调细节调了好久没调出来。我好菜啊。

1月19日

省冬第一天。

上午讲了一些偏基础的图论建模技巧，包括网络流建模技巧。有几道题还是蛮有趣的。

中午吃完饭发现手机屏幕又坏了，不明原因。有点郁闷。

下午训练。只有三个小时，手速赛差评。

第一题：给定 $h\times w$ 的矩阵，常数 $m$ 以及 $n$ 个子矩形，每个子矩形可以用 $x_1,y_1,x_2,y_2,v$ 描述，表示从 $(x_1,y_1)$ 到 $(x_2,y_2)$ 的子矩形最大值为 $v$。问有多少个矩阵满足每个数都是 $1$ 到 $m$ 的整数，且满足子矩形要求。$h,w,m\le 10^4$，$n\le 10$，$1\le x_1\le x_2\le h$，$1\le y_1\le y_2\le w$，$v\le m$。

看到 $n\le 10$ 想了想就是个容斥裸题。花了十几分钟写了个离散化+容斥过了样例就不管了。

第二题：题意比较复杂，简单的说就是给定有向图 $G=(V,E)$ 和 $s\in V$，求所有点对 $(u,v)$ 满足存在两条点不相交的路径 $s\rightarrow u$ 和 $s\rightarrow v$。$|V|\le 10^3$，$|E|\le 10^4$。

理解了很久的题意，感觉是支配树？因为如果 $s$ 到 $u,v$ 有同一个必经点就挂了，否则……好像都能构造出两条路径……可是我不会写支配树QAQ

第三题：给定字符串 $s$ 和常数 $K$，支持两种操作，一种是给定 $l,r,c$，对所有 $l\le i\le r$ 修改 $s_i$ 为 $c$，另一种是给定 $l,r$，求有多少对 $l\le l'\le r'\le r$ 且 $r'-l'+1 \le K$ 使得 $s[l..r]$ 是回文串。

看起来挺可做的啊……我来推一下。如果建个线段树，那么信息怎么合并？好像合并是 $O(K)$ 的于是单次 $O(K\log|s|)$ 不是很优秀啊。不太会。那就分块试试？以 $B>50$ 为块大小，记录下块内和块间的长度不超过 $K$ 的回文串个数，修改和查询时枚举整个的块，不满的用 manacher 暴力统计即可，就可以做到修改和查询复杂度均为 $O(B+\frac{|s|}{B}+K)$ 了？然而细节很多的样子……先是推导过程已经让我挺烦的，然后觉得这题如果不做出来应该没什么救，就刚了2个小时……写完分块准备敲 manacher 发现并不熟练QAQ

决定回去做第二题。数据规模这么小，能否不写支配树？那就是枚举两个点，把非源的必经点集合求个交，如果为空说明可行。$O(|V||E|+\frac{|V|^3}{w})$ 不知道能不能A。

第三题写了个暴力，分块写完 manacher 还没写，发现似乎有问题，然而没剩多少时间了，决定交暴力。

感觉今天正常应该有100+100+20=220吧？

出了考场，突然意识到一个问题——我离散化没检查，似乎写错了！样例里面的相邻矩形边界相差都是 $1$，发现不了这个问题！！

卧槽！！！

最后得分0+100+30=130，在省冬排名第14。一个很糟糕的名次。

fjzzq2002 240分 rank1 orz

lyq等泉州七中神犇都上了200分 orz（今年泉州七中好强啊）

集训队爷victbr 150+，去年女A队DXR 150+

等等（反正都比我高）

前2题讲的做法和我想的差不多。第3题用了线段树，感觉好像有新姿势。

郁闷的一天。

回宾馆调第1题，果然离散化挂了，ys[j+1]-ys[j] 打成 ys[i+1]-ys[i] 这么严重的错误居然没有看出来。然后发现第3题有20分没有TLE却WA了，原来是 $K=1$ 的时候枚举了一个长度为 $2$ 的回文串。我好没救啊。

学了一年多的OI，如今在省里都进不了前10。唉，搞了这么久OI却都在颓，一直都没什么进步，到头来连初三的水平都不如。简单题写不对，复杂题写不出，省队肯定不需要我这样的渣渣。

果然我这样的辣鸡实力还是比较适合退役。即使进了省队，我也是省队最弱选手而已。

晚上把以前校内训练做过还A过的SRM 597第3题交上去，结果尼玛FST了，卧槽。原来是求组合数没判 $m>n$ 时 $C_n^m=0$ 然后访问了负的数组下标，这居然当时都能AC。然后挣扎了一晚上的SRM 598。怎么这种难度的题我都要折腾这么久啊。

后来听说第3题数据不合法。不过看了下榜发现改完以后还是rank14。算了吧。

晚上听说从第二天开始延迟30min做题时间，资磁。

1月20日

上午是讲搜索。发现我现在搜索剪枝的水平和一年多以前初学OI的时候差不多。

整天都说要多做题，多进步，然而事实上呢？事实上是我一年多来几乎没进步。都高二了，看到当年似曾相识的题目，却依旧毫无思路。一直说做题却都在说谎（immortalCO：说谎！），谎称自己在做题却实际上都在颓，A*、DLX等一个我都没写过，还是只会前年初学的最简单的BFS和DFS。相比之下fjzzq2002只有初三，但进步比我快多了，水平也远远在我之上。实在是惭愧。

下午的做题依旧不顺利。

第1题：给定正整数 $\mathrm{atk}$，三个长度为 $n$ 的正整数序列 $a_i,b_i,h_i(1\le i\le n)$，一开始令 $S=0$，每次可以选一个 $i$，把 $h_i$ 减少 $\mathrm{atk}$，同时 $S$ 加上 $a_i+b_{i-1}+b_{i+1}$（假设 $b_0=b_{n+1}=0$），如果 $h_i \le 0$，接着把 $a_i,b_i,h_i$ 从序列中删除，删除后 $i$ 左右两个数将变成相邻。求最优的方案使得删掉整个数列后 $S$ 最小，输出 $S$ 最小值。$n\le 400$，$\mathrm{atk},a_i,b_i,h_i\le 10^3$。

看到题还想吐槽一句为什么又出原题。就准备码DP。仔细一看发现和原题不一样。

一个 $h_i$ 可以减很多次。那么能不能假设对于最优方案，减同一个 $h_i$ 在操作序列中一定是连续的呢？如果这样的话直接DP就行了。可是……好像是错的……

貌似可以先把一个 $h_i$ 打到快挂了，再打掉另一个 $h_j$，再打这个 $h_i$。而且好像有可能更优。

挣扎了半个多小时无果。实在没想出怎么做，就写了个30分（有30分部分分 $h_i=1$）DP做法不管了。

第2题：给定长度为 $n$ 的数字串 $S$，$0\le S_i\le 9(0\le i < n)$，要求进行两种操作：（1）修改 $S_i$ 为 $x$；（2）定义交错和 $\mathrm{Sum}[l,r]=\sum_{i=l}^r(-1)^{i-l}S_i$，给出 $l,r$，询问 $\sum_{l\le l'\le r'\le r}\mathrm{Sum}[l',r']$ 对 $10^9+7$ 取模的值。

看起来就是算出每个位置的系数用几个BIT维护一下就做完了。然而我是口胡选手，写不动。暴力只有20分。

第3题是求网格图的斯坦纳树的提交答案题。看了前4个点，点数 $n\le 8$，写个裸斯坦纳树就可以了？第5~8个点，纵坐标 $y$ 只有两种取值，也就是两行的那种网格图，似乎可以随便DP一下过掉？最后两个点看起来挺随机的，不会。

感觉自己能拿80分。

于是开始码斯坦纳树……DP，记 $f(x,y,S)$ 为以节点 $(x,y)$ 为根，里面放 $S$ 点集的最小权值，然后……分两种情况转移……前者枚举 $S$ 的划分……后者……是个最短路不然我写个Bellman-Ford吧2333（反正是提交答案题，时间不虚）

然后由于要输出方案很蛋疼QAQ折腾了好久，挂了好几次，最后检查出各种问题……总算是输出完成了……试着手玩了第1个点玩出19的解，我的程序跑出了18，check过了。看样子没啥大问题。

前4个点到手。接着搞中间4个点。

看起来两行的DP挺简单的样子，实际上挺复杂的。一开始一直没想清楚状态如何设计，然后怎么推都推不对。最后总算是想好了，转移挺复杂的，不得不写成以顺推的形式转移才写出来。

调了一会儿终于过check了，跑出了挺靠谱的解。看起来有80分了？有点紧张，因为不知道评分参数……

最后两个点看起来很随机，不会搞，直接输出MST骗分。

最后只剩大概1h了，专心搞第二题。

首先打了个表找规律发现就是把奇数或偶数的项取出来乘上一个等差数列然后求和，循环串区间很复杂那就拆成完整的区间和不满的区间，把串倍长以后用BIT维护奇数和偶数部分的 $S_i$ 前缀和以及 $iS_i$ 前缀和。看起来除了细节以外没什么难度了？

然而最后1h我并没有把第二题搞出来……最后5min过了样例，结果，随机了一组数据就WA了……没时间调了。

于是，最后我把20分暴力交了上去。

讲题的时候听说大家第一题都和我写一样做法，第二题很多人都A了，第三题很多人都写了高分做法。感觉第1题似乎这样做是对的？

最后测出来，第1题过了，第2题20分，第3题……前8个点A了……最后两个点……

也A了？？？不是很相信……原来是第3题最后2个点评分标准很低，随便搞都能A，于是排行榜上出现了大量选手这题只有最后2个点A了。

于是100+20+100=220，排名第6……

一堆人A掉第2题，就算没A的也都有40分。

fjzzq2002再次rank1。orz

晚上爸妈到我宾馆给我带了个备用手机。低端机的质量槽点多多，首先是不能接在电脑上充电（会断断续续，不明原因），其次是——我用QQ用了一半半，突然——QQ闪退了！接着点回QQ显示未安装此应用，刷新以后QQ从我的主菜单上消失了！什么鬼啊。也不知道什么时候QQ又突然出现了。奇怪的bug。

晚上做TC的SRM 599，发现后两题都做不动，最后一题感觉是个复杂度不靠谱的状压DP，想了想似乎证明出了是 $50\times 6^8$，不是很确定不过还是硬着头皮写了下来，写了半个晚上才写对。想想TC一场比赛才75min，而我做一题都用了不止75min，这样下去迟早要完。最后终于是写出来过了（跑得很慢，应该不是正解）。中间一题想了半个晚上没想出优于 $O(L^2)$ 的算法，最后交了个5KB的打表，毕竟打表从提交的程序上来说是 $O(L)$ 的……

一晚上才做了2题。现在我做题为何如此吃力？现在我还有好几道TC的hard没做出来，1月24日就是deadline了，剩下的题我恐怕只能靠题解了。和immortalCO、C_SUNSHINE、matthew99等秒完集训队作业的大神相比，我实在是太差，太差了。

1月21日

最近身体状况不太好。

上午是国家候选队爷wwx讲数据结构。果然NOI2015 rank4的实力不是盖的，难度比前两天的都大不少。

想想下午的题该有多丧呢？

准备用笔记本电脑刷TC发现TC有比赛，意味着我今天交不了题。有点郁闷。

下午的比赛又是挂成**了。

第1题：设置换 $E=(1\ 2\ ...\ n)$，给定 $n(n\le 5\times 10^5)$ 阶置换 $P$ 和正整数 $q\le 2\times 10^9$，求最小的 $t\in\mathbf{N}\*$ 使得 $P^t=E$，输出 $t\bmod q$。

水题，循环分解以后设每个环大小为 $t_1,t_2,...,t_k$，答案为 $\mathrm{lcm}\{t_1,t_2,...,t_k\}$，质因数分解算一下就做完了。

由于这几天老是写挂题，写完以后不放心，对拍了一会儿，果然拍了几十组就WA了。原来是我把 $x$ 加进答案以后清空数组的时候清空的不是 $x$ 的所有质因子 $p_1,p_2,...,p_m$ 而是 $x,x/p_1,x/p_1p_2,...$。及时发现。

第2题：给一个Trie树 $T$，字符集大小不超过 $300$，求 $\max\{\mathrm{lcp}(u,v)+\mathrm{lcs}(u,v)|u,v\in V(T)\}$，其中 $V(T)$ 为 $T$ 的节点集合，一个节点表示它到根的路径连接得到的字符串，$\mathrm{lcp},\mathrm{lcs}$ 表示最长公共前/后缀。$|V(T)|\le 2\times 10^5$。

做过的一道原题，构完后缀数组以后用 set 启发式合并就做完了，$O(n\log^2n)$（$n=|V(T)|$），不知道能不能过。还是写吧反正比暴力高。

于是写啊……写啊……写了一个半小时……写完了……样例过了……自己出的数据挂了……

然后发现倍增构SA细节狗。合并细节狗。调了好久才调不出问题。

这时候2h+了吧，开始思考第3题。

第3题：定义元素是一个元素对（递归定义），$S,T$ 是两个元素，$S=(S,S),T=(T,T)$，规定 $S < T$，两个元素 $(a,b)=(c,d)$ 的条件是 $(a,b)=(c,d)$，$(a,b) < (c,d)$ 的条件是 $a < c$ 或 $a=c,b < d$。一开始有 $S,T$ 两个元素，要进行 $n\le 5\times 10^4$ 次操作，每次选出已有的两个元素 $a,b$ 构成一个新的元素 $(a,b)$，问已经构出的元素中有多少个元素小于或等于 $(a,b)$。

好复杂啊……想了一会儿只会30分 $O(n^2)$ 暴力？

接着从一些玄学的角度思考这个问题。先是想能不能当成树的结构，然后发现不是树而是DAG，然后想能不能用类似二分的思想，可惜也不行……就算可以，复杂度也是单次 $O(\log 2^n)=O(n)$，过不了。

还是想想别的做法吧。经过考虑，感觉可以直接在暴力基础上修改，维护当前已有元素的偏序关系，加入新元素的时候用递归定义比较，在原有的偏序关系里面直接查就行了。至于复杂度……偏序关系我只会用平衡树（Splay）维护，插入的时候只会二分插入点，这样就 $O(n\log^2 n)$，不过 $n\le 50000$ 也许就过了。

剩下半小时左右吧，开始写Splay。基本操作写完了写提取第k小节点。然后写二分。写完之后测了下样例，发现出了点问题。

剩下10min-。

也许，有希望的。

调出一些 <= 打成 < 的小问题，过了样例。由于不放心，自己随机了一组 $n=1000$ 的数据，和暴力对上了。

最后1min，把第3题的Splay和前两题程序交上去了。好险。

结局呢？

一开始测的时候由于数据出了点奇怪的问题。

我的程序得了60分。

TLE了？

没TLE。

中间WA了一些。

后来。

由于数据有错。

改完数据。

重测。

看起来能A了？

……

……

测完了。

打开result一看。

……

我的程序。

……

……

只有30分了！

100+100+30=230。好几个人A掉第3题。我校选手 ziqian（wrz）、dick32165401（yhx）也都A了第3题。

victbr（xyf）rank1 orz

调了一发代码，发现我又犯了个大错误——我没考虑相同的节点。考试时以为这样不会出什么问题，把每个节点 $i$ 插到严格大于 $i$ 的节点前面，结果自己太naive，这样在平衡树里查不出两个元素是否相等，相等就判成了不等，自然爆炸。调的时候还发现了一处小细节问题。改完以后AC了。

作为数据结构强国（AK锟：中国是数据结构强国。）的OIer，我居然三天数据结构题都没调出来。太丢脸了。正如教练cy说的，我的代码能力太弱了。

三天的考试，第一天有120分写错丢了，第二天有80分没调出来丢了，第3天（今天）再丢70分，排名情况十分不理想。别人能轻松A掉的题，我愣是一会儿写挂一会儿做不出。也许我比较适合退役吧，然而我并不想退役。我还有什么可以做的呢？

等FJOI一试考挂、WC考挂以后，多刷一些TopCoder，多刷一些Codeforces题，多刷一些LYDSY题？之前也和自己承诺过这些东西，到最后计划赶不上变化，没用。

或者说，既然不想退役，那就只把OI当作自己的兴趣，不要追求多高的名次，进不进省队也罢，NOI2017能不能Au也罢，都不重要了。就像初中时我把研究数学题作为自己的爱好，现在也是这样，把研究OI题作为自己的爱好多好，何必在意自己水平低呢？做题、出题开心就好，把OI当成压力的话甚至可能丧失兴趣。

去年省冬的时候我只有一场掉到rank8？（忘了具体名次）另外几场名次都在前5吧？（不清楚了）可是今年我的发挥比去年还差，也许就是被比赛压垮而导致水平骤减吧？

不想这么多了。说过了，就算考挂也不能挂太惨。这几天还得加油。

1月22日

今天讲的是数学专题。有趣的是今天的课是实用主义的，各种介绍骗分乱搞方法。“我们这样搞，可以不用写扫描线！”“这个做法目前还没有被卡掉……”

下午全是做过的原题。只是第三题卡常数，优化了一阵子。所以下午的考试时间主要都在调之前的题。

调第二天第二题，发现犯了两个错误，一个是把式子 +q*(q+1)*n 写错成了 -q*(q+1)/2，另一个是 a 很大的时候 a/n 爆 int 了。

调第一天第三题，我到现在还写不动manacher，写出来以后复杂度还炸了。要被CJK打屁股了。

离作业deadline只剩2天了，赶紧把TC还没搞出来的题补完。剩下不会做的题只能看题解看代码了QAQ

晚上看结果。第三题最后居然卡过去了，喜闻乐见。

听说明天有大代码数据结构题。好可怕。

1月23日

上午是ExfJoe神犇讲动态规划。好多题看起来很简单结果我都没想到正解。退役的前奏。

下午的题目兼具思维和代码难度，第1题是我做过的原题。然后第2题不会做，想了一个多小时没有分析出关键性质，GG，暴力分。还好暴力有60分。

出成绩第2题有不止一个85分而且似乎都是被卡常数。深刻感受到自己的水平有待提高。

1月24日

省选一试。

首先看第一题，看到题目好长啊一定很复杂，就先扔一边。然后看第二题，第一眼最大独立集，这不会是NPC问题吧，然后想到了以前做过某道根据所有质数的幂次和奇偶性来搞的一道二分图题，这就是个二分图最大匹配嘛，好像不难。于是就先写第二题，感觉 $a_i\le 5\times 10^7$ 暴力质因数分解似乎会超时，于是筛了 $7071$ 以内的质数，一共 $909$ 个，然后枚举一遍这些数，枚举量超过 $10^8$，不过时限2s，不知道会怎么样。建图就对每个数枚举删掉哪个质因子，边数 $O(N\log a_i)$ 流应该能过？也许会TLE，有点虚。

花了40min写完第二题，构了几组答案比 $N$ 小一些的数据和大暴力拍了一会儿，感觉没什么问题。测极限数据也没RE，打算放心的时候发现我数组按最后一档部分分只开了 $3000$，然而前面有一档 $5000$ 的数据。好险，改过来了。

接着看第三题，是个原题，就是省冬Day1我写挂的第一题。然而时限有点紧，就把枚举子集修改矩阵权值改成了DFS枚举，可能会快一些吧。吸取经验这次一定要对拍。写完和暴力拍又发现两个 y 打成 x。改完以后过了对拍，测极限数据0.6s+，有点虚。

对拍完后两题剩两个多小时，专攻第一题。第一题挺长的，理解完题意发现会一个 $O(n^4)$ 的DP，用hash优化以后就是 $O(n^3)$，然而 $n\le 23000$ 肯定超时。开始想怎么优化，脑子里全是LCP、LCS之类的东西，思维很混乱，两种转移都没想出好的优化方法，后者转移想了下好像会 $O(n^2\log n)$ 然并卵照样TLE于是时间就这么过去了一个多小时。紧张。

最后不到1h决定优化一下第一题的暴力，一开始想用后缀数组什么的枚举LCP差不超过多少的区间，掉了半个小时的坑意识到这东西现在不太可能写出来。直觉上答案分段都比较小的样子那我就只枚举长度不超过某个数的区间转移吧，然后发现后者转移hash常数比较大就优化成了滚动数组DP求LCP常数就小了，有一维还可以只枚举到LCP看起来随机数据可以跑很快。出了好多组随机数据结果答案都是-1。怎么办？把字符集改成2看下。于是答案就不是-1了。测了下感觉长度卡到 $10^3$ 可能可以多水过一些分吧。

最后10min和 $O(n^4)$ 暴力拍了下字符集2的数据过了。检查了下另外两题。于是考试就这么结束了。

心想今天要是有很多人想出第一题我就滚蛋了。

最后看了下成绩，我的第一题乱搞居然水过去了，第三题被卡常数了，得分100+100+80=280。复测的时候发现第3题常数卡得实在厉害，简直了。后来才知道原来不是卡常数而是复杂度多一个log。

查了下居然还是并列最高的，双十神犇zhshr和我都是280分，不过我也知道这并不是我的实力，只是被我错误算法水了一题100罢了。

比较好奇其他人第1题AC或者拿高分是怎么做的。

后来了解情况发现我校除了wzt以外全跪，得分都200以下。yhx（dick32165401）、wrz（ziqian）、ct（chentong）分数在120~140之间。可惜了。三中神犇ysy（fateice）也挂了，220。听说泉州七中也都考跪了，lyq 130感觉A队还是挺稳的。

感觉下一个考挂的就是我了。WC考挂一下，省选二试再考挂一下就可以退役了啊……然而我真的不想这么早退役……

今晚作业Deadline。赶作业期间，第一遍有没FST是次要的，做完是重要的。于是不再考虑SRM 586 Div1 1000会不会超时直接交了，测了下居然跑得飞快。

SRM582经过长时间的理解终于搞出来了。爽。

SRM572一直WA。SRM596怎么做都MLE。一定是我姿势不对。然而实在无力。这两题扔了。

最后作业交错了。惨啊。

不管怎么说，省选退役（如果省选二试考挂了）或者NOI退役（如果省选二试没考挂）还是有点惨的。之后继续尽自己最大努力发挥吧。能搞OI的时间不多，有时也能体验一下FST掉rating的快感。

说明

关于“rank1怎么退役”这个问题，说明如下：

首先省选还没结束，还有二试。目前虽然我依靠水过一道题拿了rank1，但如果二试没考好仍然非常危险。只要我二试少50分就比rank4低了，如果再少100多分就比rank15低了。从我省冬的发挥来看，尽管考过rank1，但也考过rank14，可见我的发挥并不稳定，二试滚粗还是很有可能的。

另外就算进省队，NOI也有可能考挂。NOI2016就有不少已经进过集训队的神犇惨挂而没有进集训队。像我在NOI2016就十分符合“RP选手”的特征：简单题不会做，多水过不少分而不至于太差。所以我NOI2017滚粗也是很有可能的。

不过退役毕竟是很惨的事。我还是希望能考好。