一直听说APIO是个神奇的比赛【以前似乎有CTSC Au的神犇挂APIO？】于是更加紧张了233

事实证明我实力还是不足最后200都没上

——————————

5月5日。

APIO前有个练习赛，在网上进行。练习赛有两道题，一道是交互题network，一道是传统题sequence。

今年APIO有交互题！然而我交互题巨弱无比怎么办？

其他同学都A了一题我才登进网站去做- -第一题network看起来似乎挺可做的？

第一题network，题目给一个无向无权图 $G=(V,E)$ 以及两点 $s,t\in V$，要求给出从 $s$ 到 $t$ 的任意一条最短路，其中可以调用 ping(i, j) 询问 $i$ 到 $j$ 的最短路长度。不管先敲了个 $O(n^2)$ 的大暴力再说，25分……一看怎么里面的点有的AC有的WA？

子任务制就是好（sang）啊！可以在一个子任务里塞一大堆点，然后卡各种方面的细节，只要有一点小问题就可以卡到0分。

后来强行优化并逐个通过了这些子任务（一共交了4次）。这题被大神犇 @lightning 吐槽为大水题（@lightning：原来是这么水的APIO！@immortalCO：XXX嫌APIO题水啊！后来@lightning在APIO的时候真的A了交互题，巨强）

第二题sequence是个算（xi）法（jie）好（keng）题，给一个长度为 $K$ 的十进制数字序列 $a_0,a_1,...,a_{K-1}$ ，求最小的 $N$ 使得对任意整数 $0\le i< K$，$N+i$ 的十进制表示包含数字 $a_i$。

这题 @immortalCO、@y0rkl1u、@dick32165401 等大神交流了一段时间以后都想出了AC做法，就我还傻呆呆地不会。

一开始完全没思路。想了很久发现问题具有递归性质？枚举 $N$ 的个位就可以得到一个规模为原来 $\frac{1}{10}$ 的子问题，问题缩小到 $K\le 2$ 就可以贪心了。但是细节很多，要判0什么的，推导了很久，最后还WA了一发因为预处理 $10^i$ 没处理满第二次才AC。【那时候是5月5日22点，第二天练习赛就关闭了，还好我及时

另外APIO能多次提交确实是个好东西不然就爆0了

然后刷了点别的题练手，@immortalCO把UR10的世界线A了，而我一直调不出来了，完蛋了我交互题真的要狗带了

——————————

5月6日。

第一天培训。讲的比我想象中的有意思。

上午先讲的是提交答案题的相关解法，讲题人为了避免大神觉得东西太无聊就放了一道题《坦克大战》让大家玩（反正我没玩……我比较弱）；然后讲启发式搜索，都是些非常神奇的智能化技巧，我能写的估计只有爬山了

下午是密码学，从此再也不敢以为密码学简单。NOIP2012的vigenere密码我都不会破解。其实我更感兴趣的是利用NP问题构造单向函数。

都好高大上啊！

明天的比赛，压力大，很大。要是部分分少就真的要Ag或Cu或Fe挂了。脑子一片空白，没心思想题去睡觉了。

——————————

5月7日。

8:30进场准备比赛。然后一直等到9:00开始等得我好着急……

8:50。

8:51。

8:52。

……

8:59。

终于可以开始做题了。

三道题：boat，fireworks，gap。

第一题boat一看觉得应该并不难，就是有$n$个区间，第$i$个区间$[a_i,b_i]$，求有多少个序列$x_1,x_2,...,x_n$满足对任意$i$，$x_i=0$或$a_i\le x_i\le b_i$，且将序列所有0去掉后是严格递增的。

于是准备先把这题干掉。

如果$a_i$和$b_i$范围小，可以直接DP递推，设$f(i,j)$为序列$(x_1,x_2,...,x_i)$满足条件且$x_i\le j$的方案数，递推式就不想了。因为这题$a_i$和$b_i$是$10^9$级别。

离散化！

向来喜欢处理半开半闭区间，把区间全改成了$[a_i,b_i+1)$，然后把端点$a_i,b_i+1$全部拿去排序离散化了。

接着还是$f(i,j)$表示序列$(x_1,x_2,...,x_i)$满足条件且$x_i\le j$的方案数，不过这时候$j$是离散化后的第$j$个数$\mathrm{num}_j$。

递推式……那就按块考虑吧，$x_i\in[\mathrm{num}_{j-1},\mathrm{num}_j)$，那就枚举之前第一个不在这个块内的数也就是最大的$k$使$x_k<\mathrm{num}_{j-1}$，然后$(k,i]$内有的$x$是0有的不是0，枚举有多少个不是0（设有$s$个），然后变成了类似这样的不等式：$0\le X_1 < X_2 < ...< X_s < M$，其中 $M=\mathrm{num}_j-\mathrm{num}_{j-1}$。这就是组合数$C_M^s$。

预处理一下组合数就做完了？

式子推完开始写代码，很快写好过样例，一交：9分！

这是什么鬼？哪里WA了？

发现有个地方手抖打错，改完再交：0分。又改了几个疑似的错误，再交，还是0分。什么鬼！！！

没办法，只好对拍了。居然 $n=2$ 都拍出错了。

然后才知道很神经地好几个地方变量都打错了。改完以后对拍不WA了。交上去，就貌似58分的样子了。

最后一个子任务TLE了一点点。

我想大概优化一下就能过掉了。于是加了几个预处理进去，交。

100分！

大点跑了0.75s左右吧，是卡常数卡过去的。自古APIO第一题卡常数？就这样在1个小时左右的时间里过掉了最简单的一题。

后面的过程相当不顺利。

看了第二题fireworks，给一个边权为正的有根树，每次可以把一条边的边权加1或减1，用最少的操作次数使从根到叶子的所有路径长度相等。

心想应该是个树形DP？似乎可以推出来？

再看了下第三题gap，有一个序列$a$，每次可以问一段区间内的最值，求$a_i-a_{i-1}$的最大值。天哪简直不可做。

想了想决定先搞第二题。事实证明我的决策是错误的。

和第一题一样权值也是$10^9$级别的，在想能不能离散化，但并没想出怎么离散化，似乎不可行。

绝对值函数应该就是个分段一次函数，那么能不能在节点处维护分段一次函数？

于是有了个大致的思路，推了下式子。觉得挺难推，和分段函数的最值有关，所以花了挺久时间。

感觉差不多的时候，发现这个做法挂了。因为题目有个条件：需保证边权非负。

而我的做法根本不能保证！

想通过对算法稍加修改来解决这个问题，但无济于事。因为如果要这样维护下去非常难写，而且还不能A。

等到这个时候我再去看第三题，才发现呵呵了，我没注意到序列是严格递增的！

然后开始想怎么做。30分很好搞，第$1$次询问$[0,10^{18}]$，得到答案$S_1,T_1$，第$i$（$i>1$）次询问$[S_{i-1}+1,T_{i-1}-1]$，得到答案$S_i,T_i$，最后搞出来的就是序列$S_1,S_2,...,S_\frac{N+1}{2},T_\frac{N+1}{2},T_{\frac{N+1}{2}-1},...,T_1$。

剩下70分感觉相当不可做，瞎搞了下搞了14。

于是这题分数就是44。

滚回去搞第二题的暴力，7分只要取中位数就行，另外19分可以暴力树形DP。写完交了一发，26分到手。

接着担心第二题大家都会做，就继续狂想，但并没有想出来。

最后一个小时。

此时分数170，想到去年分数线都200+了，似乎要Ag滚粗了。

还是去搞第三题吧。

然后有了点思路，就是把序列分块询问，不过由于并没有想清楚，导致最后结果没有保证。准备交的时候评测机卡住了，坑爹。

工作人员说现在暂时不要交。看来没法多次提交看结果了。

然后由于我本地调试交互题能力太差，不怎么会调，最后选择弃疗。

最后一小时是以????的状态度过的。

结束了。100+26+44=170。

后4个小时的分数还没第1个小时高，200分都不到，只有可怜的170分。

感觉要被神犇怒虐了。

出来以后问了下情况，@lightning A了第3题，果然是秒交互题的大神。@immortalCO 虽然第3题没做出来，不过还是得了66左右的分数，反正都比我44分高就是了。

非常虚。

——————————

5月8日。

上午讲物理引擎，好像很高深的样子，不过挺有趣的，还可以手玩游戏。（然后顿时感到自己的代码能力真是弱得不行）

下午讲线段树以及一些黑科技（比如位运算生成树），似乎很神奇，回去写写看？

晚上颁奖会。担心自己能不能Au。还好最后分数线没我想象的高，150分Au。

然而排名相当靠后……被众人虐的节奏……

第1题有40人AC，是所有题目中AC人数最多的题。

要是A完第一题专心搞第3题就能226分了我为何如此SB就这样被众多大神踩了。【我并没有估计一道题的难度的能力233

实力弱，只会做水题，考场没有好的决策。要是再这样下去NOI就要被踩了。

回家了。继续训练。