HNOI 2018 题解

本文主要是介绍HNOI 2018 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

[HNOI2018]转盘
把环复制一遍，$ans=min(max(a_j-j)+i)(n+1\le i\le n\ast 2,i-n+1\le j\le i)$
不妨令 $t_i=a_i-i$，则 $ans=min(max(t_j)+i)+n-1(1\le i\le n,i\le j\le i+n-1)$
发现 $t_j>t_{j-n}$，于是 $ans=min(max(t_j)+i)+n-1(1\le i\le n,i\le j\le n\ast 2)$
考虑每一个 j 能取到的最小的 $i$, 左边第一个大于 $t_j$ 的为 i 的话，j 的答案就是 $t_j+i+1$
于是可以用线段树来维护一个单调递减的单调栈，右子树的答案可以直接取，然后用右子树的最高点在左子树二分即可
[HNOI2018]游戏
玄学，不会正解，暴力的做法就是先预处理每个点往左走能走到哪儿，往右走能走到哪儿
然后预处理每个点往右往左一起能走到哪儿，可以用第一个预处理出来的跳？
应为如果直接只往左或往右走通的很少，处理第一个的时间会变少，第二个就跳得慢
但如果打通的多，第一个会变多，第二个就跳得快，于是就玄学卡过
[HNOI2018]道路
发现深度$\le 40$ 所以可以直接把到根剩几条没有翻修的铁路公路压到状态里，但是空间要凉
发现每一次从左右儿子得到了 $ans$ 后，左右儿子的状态就没有用了，可以回收掉动态分配空间
[HNOI2018]毒瘤
一棵树的情况
$f_{u,0}=\prod (f_{v,0}+f_{v,1}),f_{u,1}=\prod f_{v,0}$
然后发现非树边只有 3 种可能 $(0,0),(0,1),(1,0)$，前两种可以看做强制 $u$ 不选，后一种可以看做强制$u$选，$v$不选，于是枚举所有非树边的状态再做一遍 dp 就可以了
发现每次都会做大量重复运算，于是我们想到建一棵虚数

然后需要预处理系数（雾）
[HNOI2018]排列
题意：给一棵树，父亲先于儿子选，一个点的贡献是 $time\ast w_i$，问最大贡献
考虑先按权值从小到大排序，如果 i 有父亲，那么选了它的父亲就选 i 最优，如果没有父亲，选 i 最优
选了 fa 就选 i 最优，我们考虑把它们合并，一个点合并多次后就是一个序列
考虑序列 a 和 序列 b 怎么接起来最大
$a+b=\sum i\ast w_{a_i}+\sum (i+si{z}_a)\ast w_{b_i}$
$b+a=\sum i\ast w_{b_i}+\sum (i+si{z}_b)\ast w_{a,i}$
$f_{a+b}-f_{b+a}=si{z}_a\ast \sum w_{b_i}-si{z}_b\sum w_{a_i}$
如果 $>0$ 说明$si{z}_a\ast \sum w_{b_i}>si{z}_b\sum w_{a_i},\frac{\sum w_{a_i}}{si{z}_a}<\frac{\sum w_{b_i}}{si{z}_b}$
于是用堆按平均值排序合并就可以了
[HNOI2018]寻宝游戏
一道很妙的思维题…
按位考虑，假设当前位的序列为 x
我们将操作op抽象成一个 0/1 序列，0表示或，1表示与
如果最后一个 |1, 在最后一个 &0 之前，则为1，反之为 0
也就是说，从后往前枚举，第一个不同的地方，如果(x,op)=(0,1), 那么答案为0，否则为1
于是我们把x，op从后到前作为一个二进制数，如果 x > op 那么最高为的不同很明显是 (1,0),答案自然是1
于是就变成了比大小了，如果当前位结果为0，那么把下限改到 x，否则把上限改到 x-1
读入的时候顺便基数排序，就可以 $O(nm+mq)$做了

这篇关于HNOI 2018 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---