Week Tasks 4 - 洛谷保存站

### [$\color{red}{T157981 比赛【2020-11-29NOIP模拟赛】}$](https://www.luogu.com.cn/problem/T157981)

不得不说，这题真的恶心。

主要恶心在$3$个方面，一是读入，二是大模拟$+$搜索，三是纯模拟$+$搜索会$\color{red}{TLE}$

主要思路如下：

因为题总共才$10$道，所以我们可以生成做题顺序的“全排列”，若时间超过或全部通过就直接计算当前所能获得的钱数，取$max$即可（$10!=3628800$）

像这些零碎的首次提交通过，最后一个提交通过啥的，问题都不大，$O(1-10)$都能解决，问题主要在于查排名上，如果一个个比过去，那么时间复杂度就提升到了$O(10!n)=1088640000>10^9$，恭喜$\color{red}{TLE}$

其实这问题也好解决，直接预处理好其他人的排名，然后二分查询即可，时间复杂度$O(10!logn)$，稳过

### [$\color{red}{T157995 树【2020-11-29NOIP模拟赛】}$](https://www.luogu.com.cn/problem/T157995)

简化题意，给定$n$个点的无边权树，$Q$次询问，求若干个点的“中心”，“中心”是指这些点到这个点的距离最大值最小，查询点总和$\le 10^6$

如果我们直接暴力遍历求解的话，会发现其实很多点都是没有用到的，所以如果我们用“虚树”来表示的话，复杂度就可以大大降低。

何为“虚树”？

选定原树中少量的点，以两点$lca$为父节点不断向上合并的过程形成的树。

所以只需找到树的直径，（设$len$为树的直径长度）$\lceil \frac{len}{2}\rceil$就是答案。

然而建“虚树”容易$\color{red}{TLE}$……

通过观察，我们可以发现这仍然可以优化，“虚树”的叶子节点就是原结点，而树的直径的一段肯定在树的叶子结点上$ヽ(✿ﾟ▽ﾟ)ノ$

### [$\color{red}{T157996 宝藏【2020-11-29NOIP模拟赛】}$](https://www.luogu.com.cn/problem/T157996)

考场上在$YY$最短路的我惨遭爆零o(一︿一+)o

我们考虑哪些是对答案贡献固定的。

对于第$n$类宝物，无论怎么走，都必经$2\times n-1$点与$2\times n$的路径，这是一个切入点。

如果把$n$类宝藏看作$n$层图，第$n$层为切入点，第$1$层为出口，我们可以直接考虑第$i$层到$i-1$层的关系。因为路径是无向的，所以可以把路径转为“拓展”，对于第$i$层的两点，有两种拓展办法，一个是直线下拓，一个是交错拓展，每层之间互不影响，所以直接$dp$出正解。

正在渲染内容...