UOJ Logo owaski的博客

博客

noip2016 伪题解

2016-11-20 14:18:47 By owaski

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

就这样吧。

owaski Avatar