day0
第一件事当然是去酒店入住+领一堆东西。
感觉酒店不错，而且离学校挺近的，走路10分钟不到，骑车5分钟就到了。
然后去学校吃饭。我们在教工饭堂吃饭，饭菜还不错，但是没有筷子差评。
吃完饭后找了一下附近的咖啡厅，然而并没有找到。
剩下的时间都在玩手机。
day1
有半个小时试机时间，就敲了三个板子（NTT，SA，LCT），结果一个都没用到。
开场先看A，发现是个傻逼题，10分钟切掉。
然后看B，想了一会感觉不会做，就跳过了。
接着发现C是傻逼题，一个小时写完+拍完。
D也想了一会想不出来，也跳过了。
这时候已经过了两个小时了。
后面两个小时都在死磕B题，想过两个DP，但都过不了拍。最后写了一个\(O(n^2)\)的DP。
出考场后问了一下B题怎么做，发现差分一下就是联赛题了。
我退役把.jpg
中午一直在玩手机。
下午讲评，D是一个数学+生成函数题，感觉这种题做四个小时都做不出来。
最终得分：100+60+100+0=260
题解
A：傻逼题不解释
B：差分之后就变成：有\(n\)个数，你每次可以把一个数\(+1\)，同时把另一个数\(-1\)，问你最少需要多少步才能让所有数\(\bmod m\)都变成零。排序+贪心就行了。
C：如果把所有的深度（插入＆询问）加上时间的话，就是一个单点修改矩形求和的题了。CDQ分治＋树状数组。貌似树套树也能过。
D：考虑缩点以后整个图会长什么样。假设有\(k\)个强连通分量，就一定存在一条长度为\(k\)的链。我们可以枚举这条链上相邻两个点的连边，那么这条边前面的连通分量连到后面的边的方向都是固定的。所以我们可以算出每一条边出现的概率，然后连通分量个数\(=\)上面的边数\(+1\)。
实际上是枚举这条边前面的点数。
\[
ans=\sum_{i=1}^{n-1}\binom{n}{i}{(\frac{1}{2})}^{i(n-i)}
\]
然后考虑有告诉你路径的时候要怎么做。
对于每条路径，我们可以枚举这条边是在这条路径的哪两个点之间，这样就有一个\(O(n^2)\)的DP了。
如果一条路径跨过了这条边，那么就会对上面那条式子有\(2\)的贡献（因为有一条边的方向确定，抵消一个\(\frac{1}{2}\)）。
所以我们可以对于一条长度为\(k\)的路径列一个生成函数：\(1x^0+2x^1+2x^2+\ldots+2x^{k-1}+1x^k\)
设把这些生成函数乘起来后的生成函数是\(\sum_{i=0}^na_ix^i\)，那么答案就是\(\sum_{i=1}^{n-1}a_i{(\frac{1}{2})}^{i(n-i)}\)
day2
开场先看A，果然是一道最短路题（话说d2t1除了最短路&BFS还出过什么？）。不过感觉到了出题人深深的恶意，因为把莫比乌斯反演强行塞进了一道签到题。
做完之后去看B，发现是一道套路题，可以直接二项式展开，也可以变换一下变成组合数。
然后。。。就发现C和D一道都不会。
在思考了半个小时后，想到了D的正解之一。很不幸的是，我找了几个看上去这个算法会错的数据把这个算法叉了，就把这个算法扔掉了。最后写了一个暴力。
最后一个小时一直在思考第三题，突然想到可以枚举\(h\)，找满足条件的\(x\)在那个区间内。接着发现数据随机，就写了一个两个\(\log\)的线段树做法。本机测了一下极限数据，跑了\(6\)秒，应该是过不了的。
中午还是一直在玩手机。
下午讲评前听说C大常数两个\(\log\)做法过了，觉得很不可思议。
最终得分：100+100+100+50=350
题解
A：求两点之间的边权可以用莫比乌斯反演，然后二分+最短路。
\[
\begin{align}
&\sum_{i=1}^n\sum_{j=1}^mi+j[\gcd(i,j)=1]\\
=&\sum_{d=1}^{\min(n,m)}d\mu(d)(\frac{n}{d}S(\frac{m}{d})+\frac{m}{d}S(\frac{n}{d}))\\
S(n)=&\sum_{i=1}^ni
\end{align}
\]
B：可以直接二项式展开+DP，也可以推一下式子变成
\[
\sum_{i=0}^k\begin{Bmatrix}k\\i\end{Bmatrix}i!\sum_{S\subseteq V}\binom{f(S)}{i}
\]
然后还是DP。
后面这个做法可以优化到\(O(nk)\)
C：可以发现求答案的过程就是在笛卡尔树上面跳，因此可以暴力维护笛卡尔树。因为数据随机，所以树高和 子树大小的期望都是\(O(\log n)\)
D：以\(x\)为起点跑一棵最短路树。那么最小环一定只经过一条非树边。
直接处理出每个点在\(x\)的哪棵子树内，然后枚举那条非树边。
最短路可以用不加堆优化的dijkstra，因为是稠密图。
day3
今天在电子阅览室考。
开场先看A，题目说的是二维偏序，但我脑子里想的一直是三位偏序。我只会\(\log^2\)的做法，很明显会MLE，就跳过了。
然后看B，感觉不太好做，也跳过了。
然后发现C是个水题，就花了30分钟切掉了（我在试机的时候写过一个SA模板，直接搬过来用了）。
做完C之后突然发现A是二偏维序，也花了30分中去写+对拍。
接着就一直在搞B，写了个两个\(\log\)的做法，推了好久的式子+一堆细节。
写完前三题只剩下一个小时了，就开始思考第四题，发现无法理解题目。问了评委，评委让我仔细阅读题目。
那我也没什么办法啊。。。就一直盯着题目猜题意，过了几分钟才看懂。但是已经没时间写正解了。就写了个 暴力。
下午发现B的后面5个点挂了，而且第一问都是错的。
我也很绝望啊。。。明明都拍上了。。。
UPD：问题找到了，有一个求子树内点数的地方加了一个取模。。。
最终得分：100+50+100+20=270
为什么出题人那么喜欢出NOIP三合一啊。。。
题解
A：\(O(n^2)\)做法是tarjan求强连通分量。正解是用线段树优化建图。
B：第一问就是求重心，第二问只需要求出一个点的子树内所有点到这个点的距离和，可以DP或者用其他方式搞一搞。
C：求有多少条不同的路径就是求整个图的最大流，求答案可以二分+哈希或者把每个猴子的串排序后求第\(k\)小的相邻两个之间的LCP。
D：先用tarjan把所有小岛找出来，再用树型DP求直径，最后用DP求分拆数（五边形数定理）。
总结
这次比赛暴露了许多问题。
1.在想一道题时如果往一个方向想了很久也做不出来，不妨换个思路。
2.要积累一些常见的容易忽略的道路，如：差分，分块，二分答案等等。
3.在想到一个做法后不要轻易地否定这个做法，一定要确保这个做法一定是错的再扔掉。如果有时间不妨实现以下，可能修改一些小的细节之后就正确了。
4.其实第一点和第三点有一点矛盾，所以你要想规划好每道题要花多少时间去想。我给自己的时间是半个小时，想不出来/改不好就换题或换思路。
5.写题速度不够快，第三天出现了会正解但写不完的情况。
6.很多要取模的题可以在对拍的时候换一下模数（比如说换成特别小的模数），以检验是否有不该取模的地方加了取模，该取模的地方没有取模。