欢迎来到考场没做出D2T2的弱智儿童博客= =。

这个题解有的题写的很不靠谱，意会一下就好了。。。

Day1

toy

就是$\mod n$的一个圈，按照题意模拟。

running

这题我的做法不是最优的。

首先$S\rightarrow T$的路径，可以从$LCA$处拆成两条链，一条链的深度$D+$时间$T$为定值设为$A$，另一条链的深度$D-$时间$T$为定值设为$B$。那么我们将问题转化成对于树上每个点，询问有多少条链的$A$值等于当前点的深度$D+$给定的$W$，有多少条链的$B$值等于当前点的深度$D-$给定的$W$，这样我们就可以把同样值的点和链放在一起，考虑每个点被多少条链覆盖。

这个问题就有很多做法了，我是用$dfs$序，链顶$-1$，链底$-1$，然后树状数组统计子树和即可。（这里可以做到$O(n)$，可以直接$dfs$出来的，我当时也是傻了。。。）

时间复杂度$O(n\log n)$，本机跑了$1.4s$不知道最后数据会不会超。。。（这题极限可以做到$O(n)$，但是太tm麻烦了，鬼才会去写= =）

classroom

最短路果断$floyd$，$v$才$300$，$0.2s$就跑出来了。

经典背包$dp$，只是套了个期望而已。

设$f[i][j][0/1]$表示前$i$节课，已经用了$j$次申请机会，第$i$节课是否使用申请机会，的最小期望，然后就枚举$i - 1和i$的选择来用之前求出的最短路转移，$O(v^3+n^2)$。

Day2

problem

就直接$O(n^2)$预处理组合数$\mod k$然后求一个前缀和即可。

earthworm

mdzz居然考场上没想出来。

考虑把整体$+q$的操作变一下，变成整体不变，新的两个数$-q$，然后记一下变了几次，就可以还原出原来的数了。

然后我们把初始序列排序，搞三个从大到小的队列，第一个存原序列，第二个存所有用$\left\lfloor px \right\rfloor$产生的数，第三个存所有用$x - \left\lfloor px \right\rfloor$产生的数，因为我们是从大到小提出来的数，因此产生的$\left\lfloor px \right\rfloor$和$x - \left\lfloor px \right\rfloor$也是同样从大到小的，这样就是单调的了，复杂度$O(n\log n + m)$。

angrybirds

考虑对每个点求出所有包括它的能够被一个二次函数覆盖的集合，对每个点是$O(n)$的。

然后考虑状压$dp$，设$f[i]$表示覆盖集合$i$的最少次数，我们可以用$f[0\sim 2^i - 1]$以及包括$i$的集合来转移，因为$\sum{2^i}=O(2^n)$的，所以这样就可以做到$O(2^nn)$了。

一些感想

最后一次noip没能AK真是太遗憾了= =。

这次noip的难度比较迷，比如D1T2比D1T3要简单之类的。当然这是相对的，对于不同的人吧。。。

个人感觉比去年灵性一些，当然也有可能是我太傻了QAQ。

就这样吧。