NOIp2016/2017/2018简要题解

## $NOIp2016$ ### $toy$ 好像是直接模拟？ ### $running$ 其实这题并不难啊$\cdots\cdots$ 一开始想$\log^2$的树剖，苦苦思索后无果；然后决定想一个$\log$的线段树合并，然后发现因为时间会变，合并上去非常不好维护，而且还有从上往下走的路径，非常难受。 然后瞄了一眼$Beng$哥的博客，原来可以拆路径啊还有不变量啊，傻逼了。 然后发现由于路径是从下往上差分的所以线段树合并没有问题。 简单来说，对于一条路径$x\to y$，我们把它拆成$x\to lca,lca\to y$两条路径；对于第一条路径来说，$dep[x]+w[x]$是定值，对于第二条路径来说，$dep[x]-w[x]$是定值。 那么就直接线段树合并就好了啊，我们在$x,y$分别打上$+1$标记，再在$lca$打上$-1$标记(两棵线段树都要减，用个$pair$)，注意去重和差分的区别就可以了。动态开点线段树资瓷负下标所以非常方便。 时间$O((n+m)\log n(3n))$，空间复杂度$O(m\log n(3n))$。 ### $classroom$ 按题意~~模拟~~DP即可。 ### $problem$ ~~耻辱~~ 随便$O(n^2)$预处理一下二维前缀和即可。 ### $queue$ 好像直接按单调性用$queue$维护一下。~~不会不会~~ ### $bird$ ~~我记得前年我看到$Kiana$兴奋的一比~~ $O(n^2)$可以枚举出所有直线，然后可以状压这条直线能够打到哪些猪。 然后$O(2^nn^2)$直接状压DP就可以了。注意也可以用一条直线只打枚举的第一个猪。 ## $NOIp2017$ ### $problem$ ```cpp printf("a*b-a-b"); ``` ~~至今不会证明~~ ### $complexity$ 好像是个栈。 ### $park$ 这题是个不错的启发，告诉我们拓扑DP不一定要缩点。 首先考虑如果有一个零环在$mindis+k$路上，就直接输出$-1$就可以了。一个点的$dgr$是$-1$就代表它在环上。这个通过两个$dijkstra$就可以了。 然后好像$\cdots$似乎就是直接按照拓扑序DP就可以了。先搞出最短路图（这里指的是在$1\to n$最短路上的边集）的拓扑序方便累计答案，再枚举每个点判断一下当前的转移是否满足$<=mindis+k$的限制，就可以直接把方案数推过去。 为什么这样是对的呢？我们考虑一条返祖边也就是环边。只要在我们的转移区域内不出现零环，那么你现在从这条环边推过去的方案一定会在之后的枚举中计算，而最后一次推过去的方案一定是没有意义的。 为了方便，直接按照最短路图拓扑序转移。时间复杂度$O(nk)$。 ### $cheese$ 并查集判连通性。 ### $treasure$ 考虑深度不方便，那么就按深度转移。 考虑枚举同深度的一层节点转移，这也是一种生成树/二分图/图等DP的一种思路。 枚举当前点集$S$和新增点集$T$，$dp[S|T][dep+1]=dp[S][dep]+mindis[T][S]\times dep$。 其中$mindis$在实现上因为空间复杂度原因处理一个点连接一个点集的最短距离就可以了，于是可以做到$O(3^n\times n^2)$。 当然这样有可能有一些错误的代价增大了的转移，但最优解一定可以转移出来。 **UPD:** 只要你预处理的枚举顺序和DP的顺序相同，那么你就对每个状态开一个$vector$记一下对子集的补集的$mindis$，这样就可以做到时间复杂度$O(3^n\times n)$，空间复杂度$O(3^n)$了。 ### $phalanx$ ~~我是不是只会做数据结构了啊~~ 发现我们可以维护不变量，也就是我们利用动态开点线段树，删一个点就把那个点留空，然后再在后面插入，最后一列单独开个线段树维护就可以了。 实现上，为了不初始化，我们直接维护空位置的和，然后区间内数就用区间长度减掉就可以了；如果我们查询到的位置没有标记，直接依据线段树的下标就可以输出答案了——因为方阵是有初始位置的。另外操作一定会落到一个非空的点，这个可以脑补一下线段树的结构。 此外，我们可以让$update$有返回值，直接达到询问的目的。这样写非常方便，加上30行的读入优化，整个题不到90行。时间复杂度$O(q(\log(n+q)+\log(m+q)))$。 ## $NOIp2018$ ### $road$ 显然可以发现（虽然我考场上没有发现）一个数比左边那个数大多少就有多少的贡献。$O(n)$直接扫一遍吧。当然也可以直接模拟。 ### $money$ 猜的结论是每个数如果能被前面的数组成就没有用。 用$O(nV)$完全背包验证就可以了。 ### $track$ 显然是二分答案，贪心的话用$set$二分匹配较小的数，再把剩下没能匹配的数中选最大的向上传。$O(n\log^2 n)$的。 ### $$ ### $$ ### $$