2019.07.03【NOIP提高组】模拟 B 组总结

今天90+100+50=240

还不错。

第一题：4809. 【NOIP2016提高A组五校联考1】挖金矿

本想着用dp，先将第一层的必须选了，然后设f[i]表示选i个数的最大价值，最后答案就是MAX{ ( sum+f[i] ) / ( i+n ) }。但是发现这样时间是O(n^2m^2)的，想了很久终于看到平均值就想到了二分答案，然后将每个数减去平均值，最后只要选出若干个数看看总和是否大于0即可。

第二题：4810. 【NOIP2016提高A组五校联考1】道路规划

我们发现要符合题目必须第一行选的数的顺序和第二行是恰好相反的，因此我们将第二行的数编号后对应到第一行做一遍最长不下降子序列即可。

第三题：4811. 【NOIP2016提高A组五校联考1】排队

多种解法。

有一点要发现的是，每个点的优先级是确定的，所以我们先处理出来。

对于第一问可以用链表找到前x个未打标记的数并打上标记，第二问跳倍增找到当前点到根节点的路径中最上面一个被打标记的点，然后直接将它变为0。最后我们记录一个head，表示每次跳链表时的起始位置，若修改的点在head前面，那么就将head变为修改的点的位置，否则就跳head直到next[head]>x>head，然后将x和前后的链表接起来，最后将head变回原先的位置即可。

对于修改的数如果不多是没事的，如果多的话未打标记的数就会少，所以总时间复杂度是能过的。

第一题精度问题没有拿满分，需要注意。

第三题没有想到，还需努力。