HNOI2018 题解

前言

感觉\(HNOI2018\)的难度相比之前突然就上了一个档次......

瑟瑟发抖(TAT)。

[HNOI2018]道路

Tag：DP

感觉是2018年唯一的一道良心题。

设\(f_{i,a,b}\) 表示到了\(i\)点，\(i\)到根还有\(a\)个共路未修，\(b\)个铁路未修的最小代价。

转移直接记搜，枚举修哪一条然后递归处理。

到叶子节点时根据记录的\(a,b\)把对应贡献算出来即可。

[HNOI2018]游戏

Tag：单调栈、线段树

首先注意到有一档部分分是\(y\leq x\) 。

这一档现在看其实二维数点随便做，然而这对正解是没有任何启发性的。

所以考虑更优做法。

对于每个点，我们假设知道它的最远左右扩展区间\([l,r]\)，那么询问就随便做了。

由于\(y\leq x\)，所以左端扩展是恒定的。

我们从右往左加点，然后考虑加入点的最远右扩展。

如果我们能够从\(i\)走到\(i+1\)，那么\(r_{i+1}\)也一定能够走到。

考虑维护一个右端点的单调栈。

那么每次加入一个元素后，我们判断当前栈顶的那扇门是否能被打开(因为左端点进行了新一轮扩展)。

如果可以，那么弹栈，并把当前点的右扩展变大，这样复杂度就是\(O(n)\)了。

考虑没有\(y\leq x\)时怎么做。

现在相当于我们的左扩展是不确定的了，需要动态求。

注意到每次弹栈后，右扩展增大，就有可能捡到可以增大左扩展的钥匙。

设此次弹栈后，我们当前扩展的右端点为\(r_i\)。

那么左扩展其实就是找到左侧第一个满足\(y\ge r_i\)的门。

线段树上二分即可。

直接二分是\(log^2\)的，这里可以使用一个小\(trick\)。

首先获取\(log\)个区间，二分找到答案点的包含区间。

然后再在那个区间上二分位置，这样二分复杂度就变成\(O(logn)\)了。

[HNOI2018]转盘

Tag：贪心、线段树、单调栈

首先扔一个结论：在原地等一定是不优的。

为什么呢？考虑二分答案\(t\)，那么原问题可以看做时间逆流。

也就是说在\(T_i\)时刻，\(i\)物品会消失，现在要求你在\(t\)时刻内标记到所有物品。

这显然一直向前走是最优的。

所以对于答案\(t\)，设从\(i\)出发，那么对于任意一点\(j\)需要满足\(t-(i-j)\ge T_j\)

所以\(t=max_{j}\{ (T_j-j)\}+i\)

把环倍长，就有答案$Ans = \min_{i\in[n,2n]}{max_{j\in[i-n+1,i]}{T_j-j}+i} $。

等效替换一下有：

\(Ans = min_{i\in[1,n]}\{max_{j\in[i,i+n-1]}\{T_{j}-j\}+i\}+n-1\)

又因为\(T_{i+n} -(i+n)= T_{i}-(i+n)
所以：

\[Ans = min_{i\in[1,n]}\{max_{j\in[i,2n]}\{T_{j}-j\}+i\}+n-1\]

我们考虑枚举\(j\)，那么符合条件的\(i\)就是所有后缀最大值为\(T_j-j\)的位置。

若\(T_j-j\)为后缀最大值，那么\(i_{min}\)为前方比其大的第一个位置加一。

若\(T_{j}-j\)不是后缀最大值，那么答案同后方第一个后缀最大值的答案。

也就是说有效贡献来自于一个关于\(T_j-j\)的单调栈。

而我们现在需要支持修改\(T_j-j\)，所以可以想到类似"楼房重建"的使用线段树维护单调栈。

线段树维护单调栈自然就要考虑合并。

我们用右方的最大值去切割左方的单调栈。

如果当前最大值都比切割线小，那么直接返回\(l\)+切割线即可。

因为这些点都不会出现在单调栈中了，并且他们的后缀最大值都是切割线。

否则，若右儿子最大值还比切割线大，那么递归右儿子，并直接返还左儿子原来的答案。

否则，递归左儿子。

注意合并时，当走到叶子节点时，应该返回\(l+1\)+切割线。

因为\(l+1\)是最小的以切割线为后缀最大值的位置，而不是\(l\)。

最后关于算答案。

我们有限制\(i\leq n\)，所以算答案不能算到\([n+1,2n]\)去了。

注意到\([n+1,2n]\)的最大值就是\([1,n]\)最大值\(-n\)。

所以我们相当于用切割线\(mx_{[1,n]}-n\)去切割左侧单调栈得到答案。

所以只用维护\([1,n]\)的单调栈就行了。

输出时把用\(mx_{[1,n]}-n\)切割得到的答案和左侧内部答案取\(min\)即可。

[HNOI2018]排列

Tag：贪心、堆

注意到\(a_i\)其实就表示\(a_i\)必须要出现在\(i\)前面。

那么定义\(a_i\)为\(i\)的父亲，构建出一张图。

如果有环显然就是无解了，否则这张图一定是一个以\(0\)为根的树，因为每个点只有一个父亲。

现在问题变为：树上的点在选之前必须先选父亲节点。

我们找到树上权值最小的点。

那么如果选了它的父亲，我们一定会立刻选它，所以不妨把它与父亲合并。

多次合并后，每个节点都是一个操作序列。

考虑两个操作序列(对应两个节点)，设为\(a,b\)。

考虑合并它们的代价：

• \(W_{a,b} = \sum_{i=1}^{len_a} w_{pa_i} + \sum_{j=1}^{len_b} (len_a + w_{pb_j})\)


• \(W_{b,a} = \sum_{i=1}^{len_b} w_{pb_i} + \sum_{j=1}^{len_a} (len_b+w_{pa_j})\)

那么有：若\(W_{a,b}\leq W_{b,a}\)，则\(\frac{\sum_{i=1}^{len_a}}{w_{pa_i}} \leq \frac{\sum_{i=1}^{len_b}}{w_{pb_i}}\)。

我们用堆来实现找到\(\frac{\sum_{i=1}w_i}{len}\)最小的位置，找到后将其与父亲合并。

答案的计算我们拆式子，那么每次合并时加上对应贡献即可。

[HNOI2018]寻宝游戏

Tag：思维、构造、基数排序

这真的是一道神仙题，完全没思路只能对着题解orz......

首先注意到，\(\&1\)对答案没影响，\(\&0\)会使得\(1\)变为\(0\)。

然后注意到，\(|\ 0\)对答案没影响，\(|\ 1\)会使得\(0\)变为\(1\)。

那么考虑分二进制考虑。

我们枚举二进制位\(j\)，然后把\([1,n]\)的每一个数的该位提出来构成一个\(0/1\)序列。

我们读入目标值后，设其第\(j\)位的值为\(v\)。

如果\(v = 1\)，那么如果有\(\&0\)，那么后面一定要有\(|\ 1\)。

如果\(v = 0\)，那么如果有\(|\ 1\)，那么后面一定要有\(\& 0\) 。

考虑构造一种比较方式，使得上述条件能够快速呈现。

神仙网友真是厉害......

定义\(\&\)为\(1\)，定义\(|\)操作为\(0\)。

那么把符号排成一排后，操作序列也是一个\(0/1\)序列。

把两个\(0/1\)看成二进制数，其中\(n\)位置为最高位。

定义操作序列这个二进制数为\(A\)，数字序列该二进制数为\(B\)。

回头看上述两个限制。

定义\((a,b)\)表示操作序列某一位为\(a\)，数字序列对应位为\(b\)。

若\(v=1\)，如果有\((1,0)\)，那么更高位必须存在\((0,1)\)，即\(A
若\(v=0\)，如果有\((0,1)\)，那么更高位必须存在\((1,0)\)，即\(A\ge B\)。

所以将每一位都分析一遍后，我们的\(A\)就得到了一个取值区间。

这个取值区间的大小就是方案数了。

最后的问题在于如何找到上下界。

直接暴力把每\(63\)位压到一起比较也过了......

然而我们追求更优秀的做法，如果能够一开始就把所有\(B\)都排好序就好了。

这样每次询问时只需要顺序枚举即可。

莫名想到后缀数组......

所以就基数排序吧，这样复杂度就变为严格\(O(nm+Qm)\)了。

[HNOI2018]毒瘤

Tag：虚树、DP

设\(s = m-n\)，注意到\(s\leq 10\) 。

独立集\(dp\)：\(f_{u,0} = \prod_{v} (f_{v,0}+f_{v,1})\)，\(f_{u,1}=\prod_{v} f_{v,0}\) 。

所以一个直接想法就是暴力枚举涉及的点是否选择，然后暴力\(dp\)，复杂度\(O(3^{s}n)\)。

可以拿到\(55\)分。

考虑容斥，先算不合法的方案数。

枚举哪些限制是不合法的，然后做独立集\(dp\)，容斥计算答案，复杂度\(O(2^{s}n)\) 。

这样就可以拿到\(80\)分的高分了，这是考场上的正确姿势。

然后来看正解。

考虑优化\(55\)分做法，注意到每次\(dp\)有大量的点都重复计算。

所以建虚树，我们只把限制涉及到的点给提出来，建一棵虚树。

考虑在虚树上\(dp\)，对于虚树上的一个点，我们预处理没有关键点的子树的\(dp\)值。

然后考虑虚树的边\(E(u,v)\)，对于\(v\)转移到\(u\)，这条边中间省略了一堆点。

如果我们能把转移系数求出来就好了。

转移系数形如：

• \(f_{v,0} * coef_{v,0,0} \to f_{u,0}\)


• \(f_{v,0} * coef_{v,0,1} \to f_{u,1}\)


• \(f_{v,1} * coef_{v,1,0} \to f_{u,0}\)


• \(f_{v,1} * coef_{v,1,1} \to f_{u,1}\)

关键在于这个\(coef\)怎么求。

直接暴力就好了，对于虚树上的每一条边，在原树上爆跳父亲把系数顺便算出来即可。

复杂度\(O(n+2^ss)\) 。

实现起来细节巨多，注意代码实现和细节。