NOI2016，最终我以一道水题不会做没到平均分滚粗了运气好进了前50。

7月21日

就要NOI了。紧张。

然而我连矩形面积并都不会写显然是要挂的

突然想起不会 $O(n^2)$ 的LCIS和石子合并，赶快去看

和immortalCO交流了一道模板题，给他看题以后几分钟就催我要数据（秒题真快），给他数据以后他又说我出的数据太弱可以水过2333

果然我是既不会乱搞也不会卡乱搞的蒟蒻

iCat%%%

无聊把果冻运输剩下两个点跑出来A了

7月22日

早上很早起来出发。

在机场和immortalCO交流算法。

在飞机上和immortalCO交流算法。

到了以后继续和immortalCO交流算法。

（1）

WAer蒟蒻：我发现DP的决策单调性我完全做不动

immortalCO：决策单调性就是找规律

WAer蒟蒻：……

UPDATE：NOI Day2的第2题我确实找了规律，然而没调出来= =

（2）

WAer蒟蒻：NOI2012的题我很多不会。

immortalCO：说谎！

WAer蒟蒻：魔幻棋盘我就不会做。想到了和关键点有关，考虑了差分，但还是不会。

immortalCO：你都想到维护差分了为什么不会？

WAer蒟蒻：……

（3）

WAer蒟蒻：CTSC2014的手写识别好丧，要我的话肯定只能搞十几二十分。

immortalCO：AKF这题分数很高。

WAer蒟蒻：我的想法是，先找出每个数字的一堆样本，取平均数，然后对每个数字把它的各个像素点和样本的差的平方加起来，取个最小的，这样正确率极低无比。

immortalCO：AKF就是手标数字以后，把图片用高维向量表示，然后用最近邻居【不知道具体是怎么样，大概是这样，如果错了是我SB】

WAer蒟蒻：……（一定是我太弱了）

然后还讨论了一些离线询问的技巧、线段树的一些用法、几道有趣的题。

到宿舍。本渣和lxe神犇、lightning神犇、wyh神犇住一间。

immortalCO神犇和y0rkl1u神犇住一间。Interesting。

晚上背笔试，调可持久化线段树。

7月23日

上午照相+开幕式。照相就是等得久了点。开幕式略有槽点，一开始就是打学校的广告，还秀高考成绩233【祝高考顺利？？？

回宿舍，lxe、lightning、wyh都睡觉去了，我还在背笔试【如果像UNR那样炸成97就跪了

下午笔试。

我做完以后一直在检查，这时候immortalCO已经开始搞练习赛了%%%

笔试顺利100。终于有机会考出不比immortalCO低的成绩，感人。

然后搞练习赛的提交答案题，然而由于时间不够只搞了5个点。

我毕竟还是太弱了。

明天Day1，考前日常膜神犇。

膜IOI大爷kfdong。

膜WC rank3，CTSC rank8的最强神犇immortalCO。

膜isdkfj，fateice，lxe，DXR，lightning，wyh，ExfJoe。

希望大家这两试都拿高分吧。

7月24日

NOI的Day1。

第1题：给字符串 $s$，求有多少组 $l_1<l_2<m<r_2<r_1$ 满足 $s[l_1..l_2-1]=s[l_2..m-1]$ 且 $s[m..r_2-1]=s[r_2..r_1-1]$。多组数据，数据组数 $T\le 10$，$|s|\le 30000$。

字符串题，似乎可以想一想？

一眼暴力：枚举 $l_1,m,r_1$，然后判是否满足条件。

这样枚举量是 $O(n^3)$ 的，发现分数很低。

两个条件是独立的，看来枚举 $m$，对每个 $m$ 分别算出有 $c_l$ 个 $l_1$ 和有 $c_r$ 个 $r_1$，答案加上 $c_l{c}_r$ 就可以了？

判断字符串相等用暴力总复杂度是 $O(n^3)$ 的。

想了想只要预处理出每对后缀的LCP就能做到 $O(n^2)$ 了。

然后就写完 $O(n^2)$。

样例WA了。

发现有几个地方写错了。

前几个样例都过了，最后一个样例过不了。

算了感觉分数还可以，就不想了。

第2题：给一个 $n\times m$ 的网格和 $c$ 个格子，把 $c$ 个格子挖掉，求最少再挖掉几个格子才能使网格不连通。多组数据，数据组数 $T\le 20$，$n,m\le {10}^9$，$\sum c\le {10}^5$。

坑爹的网格图问题，没想出什么好的做法。

以为又是什么和平面图最小割转最短路之类的有关的问题。

后来想了想不对。

觉得答案不会超过 $2$。

【$n\ge 4$ 时，取最上面一行最左边的格子，删掉相邻的两个就能不连通

看了样例，确实没有超过 $2$ 的。

于是就是判有没割点？

果断写了个Tarjan。

由于Tarjan严重不熟练，多次写错。

经过各种折腾终于过掉了小样例。

这时广播通知：请注意第2题的边界情况。

感觉好多细节没处理，好虚。

算了还是先看下一题吧。

第3题：给定 $n,m,k$，求有多少个不同的分数满足分子 $x\in [1,n]\cap \mathbf{Z}$，分母 $y\in [1,m]\cap \mathbf{Z}$，且 $\frac{x}{y}$ 在 $k$ 进制下是纯循环小数。$n,m\le {10}^9$，$k\le 2000$。

推了好久（还借助了打表找规律），然后……

卧槽NOI居然考莫比乌斯反演？！

反正就写下看看吧。

一开始写的是 $O(m)$ 暴力，发现才24分，不开心。花了一段时间改成了 $O(n)$，这样大概就有84了吧？

然而觉得还是会被坑细节。很虚。

最后回去检查第2题，发现 $c$ 很小的时候还是可以搞一搞的？

又搞了点部分分。大样例居然过了。

然后继续磕第3题，觉得想正解很困难，不过 $n={10}^8$ 时限 $2\mathrm{s}$ 似乎还能卡过去？

就开始改数组，改写法，卡了卡常数。改完以后然而总觉得有点奇怪然而样例能过？和暴力一拍果然WA飞。及时改对。

不知能否多卡过去一两个点。

然后快结束了，打算检查第一题，然而没对拍很虚。

结束了。

一出来看到immortalCO，他第一题也写了 $O(n^2)$，第二题也写了 $O(nm)$，第三题也写了莫比乌斯反演。

感觉今天这个大概就是个大众分？希望不要写挂。

等成绩。

中午倒是大家都没睡了。

讨论了一下大家差不多也是这个分。isdkfj似乎A了第1题，强。

14点45分去看成绩。

登录进去，打开pdf……

等等，这是题目不是成绩……

重新打开……

第1题95分。

第2题60分。后面的点都WA，还真的是细节狗了。

第3题92分。$O(n)$ 多卡过去两个 ${10}^8$ 的点。

【另外段错误都显示为Wrong Answer？

于是没上250分了= = 95+60+92=247。

第2题离散化要特判 $n=1$ 或 $m=1$ 的情况，坑爹。

因为原先我的想法是把所有挖掉的点的横、纵坐标离散化，而 $n=1$，$c=0$ 的时候割点不在离散化的格子里面！

而且我似乎还有别的细节没处理好。

于是 $c$ 小的数据只过了一个点。被怒踩。

然后听说myy AK啦%%%

后来据说第2题出现了一些不科学的得分分布。有点想吐槽= =

每题都有一堆人A。

但愿Day2能考好吧。

y0rkl1u第1题写 $O(n^3)$ 做法得了90分。

immortalCO第2题用【我不知道的方式】乱搞得了72分。

isdkfj第1题最后一个点似乎WA了？不明觉厉。

wyh第2题CE了，sad。

据说第2题有人只靠特判数据拿了68分？还有人写了正解没判 $min\{n,m\}=1$ 被卡到低分？

怪不得提醒要注意第2题的边界情况……我就是这么不注意边界情况丢了好多分

小火车第3题怒踩标程orz

感觉Day2的题会更难。做好炸Day2的准备。

7月25日

上午去了中物院核科技馆和富乐山公园。

总体没啥意思，就是在科技馆看到了许多exciting的东西。

下午在宿舍颓。

想想觉得就要Ag滚粗了，并没有刷题的欲望。

继续膜immortalCO、lightning、y0rkl1u

7月26日

Day2

感觉今天的题目都比较难。没有写正解的欲望2333

第一题是求从 $n$ 个给定的闭区间里取 $m$ 个使得交集非空，并且所选区间长度的极差最小。$n\le 500000$，$m\le 200000$。

开场写了个60分 $O(n^2)$ 暴力。

感觉继续优化要用数据结构（二分答案+线段树？）

然而一时没想出来。就跳过了。

第二题：给 $n$ 个 $h_i$，每次选取任意多个 $h_i$ 然后把它们改成这些 $h_i$ 的平均值，求 $k$ 次操作以后 $h_1$ 的最大值。$n\le 8000$。

题目给了一个高精小数库，要求输出 $p$ 位小数，$p\le 3000$。

暴力都难写……

算了还是硬着头皮写个 $O(2^{nk})$ 暴力吧。还好暴力部分 $p=5$。

第三题是一道有趣的提交答案题，要求用一个神奇的模型（神经网络？？）计算一些式子。

觉得这场大概只能靠这题了。开搞。

看懂了题目。

搞第一个点。

搞第二个点。

搞第三个点……等等怎么搞来着？

然后发现除了某个S节点以外其它都是线性的，没法判正负。真是坑爹。

不过S节点的那个函数……怎么和判正负的那个函数那么像？

Interesting。

然后就把输入的数乘一个非常大的数再用S节点搞一搞，搞出来了。

第四个点是求绝对值，也想了一会儿，但失败了。

算了只搞6分吧。

第五个点是二进制转十进制，开始发现要写C++代码了。节点太多。

受到以前做过的某题的启发，把每种节点封装成一个函数，然后调用函数表示新建节点并返回节点编号。

第五个点挺容易AC的吧……然后做第六个点。

之后的点一个也没搞出来。

第六个点居然是十进制转二进制。脑补了一个 $7{\log }_{2}a$ 的做法得了8分。

第七个点先用第六个点的程序分解加了个按位异或再跑第五个点的程序也得了8分吧。

第八个点……实在没想出什么好的做法，就写了个二进制分解，得了9分。

后面两个点都搞不动。

感觉第1题有60而第2题只有20，滚回去研究第2题。

……

……

没想出来。

……

还是没想出来。

发现搞第3题的时间太久了，快没时间了！！

打表找一发规律？

嗯。把暴力程序改成能输出方案的。

好。

然后写个数据生成器。

开始跑随机数据看方案。

首先测的是 $k\ge n-1$ 的，这时候的方案似乎和样例二差不多，把大于 $h_1$ 的从小到大和 $h_1$ 连。

写了个程序，对拍了几百组都过了。

再测 $k$ 小的。

有趣的是似乎仍然是从小到大选取。

【于是我让数据生成器帮我排个序】

然后规律就直观多了，每次取连续一段，并且每一段之间没有空隙，可以DP，$f(i,j)$ 表示前 $i$ 个里面取了 $j$ 段之后 $h_1$ 的最大值。

然后要枚举段的起点……复杂度是 $O(n^3)$ 的，再加上高精的话……

想了想觉得有决策单调性。

写个斜率优化吧。

写完，一测，WA。

这时离比赛结束没多久了吧。

调了半天不知道错在哪。

最后还是删了，改成在凸壳上二分。

看了下也有60~70分吧，也行了。

测了下小样例和大样例没问题，然而没时间拍了，好虚。

觉得第1题短时间内不太可能rush出什么分数来，就去rush第3题了。

最后把第9个点和第10个点rush了少量分数，大概就是用扣分工具，一个点6分吧。

最后总体检查了一遍比赛就结束了。

觉得要完了。

回去听说lightning搞出了第一题，第二题大家都60~70，第三题大家都70~80。

看样子我要完了。好虚啊好虚啊。

而且我第一题没拍，第二题没拍。

第三题如果最终测试数据和checker不一样的话……

啊，怎么办？

难道要滚粗了吗？

紧张等成绩。

……

13:30

……

14:00

……

14:30

……

终于等到出成绩了。

迫不及待把密码敲进去然后打开结果（这回我直接开了成绩，没再傻逼先把题目的pdf打开）。

直接拉到最下面。

看最后一个数。

218。

没挂的样子？

往前翻。

然后发现自己RP真是好到爆了。

第一题本来60分，多卡过去一个点。65分。

第二题本来65分，多卡过去一个点。70分。

第三题83分。

65+70+83=218。就这么拿了个单调递增的成绩。

总分100+247+218=565。看起来是能Au的。

lightning第一题果然A了，今天分数比我高。

immortalCO似乎考炸了，不过他还是凭借超强实力Au进集训队了。

有机会在NOI上拿到和immortalCO一样的奖牌。运气真不错。

然后去看排名。

一眼看到fateice rank9，福建rank1，膜。

然后下面居然是我？我这样的蒟蒻居然能rank10？？

今年的NOI真是比谁没写挂啊。一题也不会都能rank10，感动。

成功伪装强者哈哈哈【大家好我是NOI Au的神犇】

isdkfj队长也Au了。xyf也Au了。

【然后悲催地发现咱们宿舍的似乎都挂了……貌似是由于D1T2都挂了的缘故吧……】

Day2第1题好多人A，没A的也好多80分以上。平均分67~68？？

连平均分都没上的我2333

仔细一想……卧槽好像还真是傻逼题……

果然是一道考场就SB的我。

Day2一堆人比我高……果然我水平不足唉……

UPD：等到UOJ上有了区间这题我迫不及待把它A了，考后AC理性愉悦

总体而言，这次NOI暴露了我的几个问题：

（1）细节考虑不够周到，D1T2的 $c$ 比较小的部分分尤其是 $c=0$ 和 $c=1$ 的都应当拿到，然而由于细节没考虑清楚导致丢分；

（2）畏难情绪，受到Day1每一题都不容易AC的影响，以为D2T1也是一道不可做题，没有仔细去想，于是少了许多分；

（3）没有尽力取得部分分，尤其是Day2，第2题可以用 double 拿部分分，然而我并没有写。

7月27日

没团抗差评，在宿舍颓。

下午颁奖。

看颁奖名单，感觉今年NOI真是大爆冷门啊，挂了好多神犇，甚至有好多拿过NOI Au的神犇挂成了Ag甚至Cu。或许是某些题（D1T2）坑点多容易挂的缘故吧。

于是开始担心明年考挂了- -我毕竟还是RP选手，只有RP好才能Au。

小火车真是劲啊！写挂一题依旧rank8在前面，要我的话写挂一题就早死了。

所以说我还需要提高自己的水平啊。

今年的【NOIP】【清华集训】，明年的【WC】【省选一试】【省选二试】【CTSC】【APIO】【NOI】能做到一场不挂吗？总之今年我已经多次临近滚粗边缘，明年的话不是很好说。

7月28日

颓一天。

晚上回家，和immortalCO讨论一些神奇的题目。在飞机上睡着醒过来发现躺在immortalCO身上，尴尬

进队啦，要准备清华集训啦，要开始好好研究数学啦