欢迎来到考场没做出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。
就这样吧。