# HNOI2012 ~ HNOI2018 题解

HNOI2012 题解

[HNOI2012]永无乡

Tag:线段树合并、启发式合并
联通块合并问题。
属于\(easy\)题,直接线段树合并 或 启发式合并即可。

[HNOI2012]排队

Tag:组合数学、高精度
因为男生没有限制,首先把男生排成一列。
然后分情况讨论:

  • 两个老师之间有男生:
    首先把两个老师插入到\(n\)个男生中,方案数\(\binom{n+1}{2}\) 。
    然后把女生插入到老师与男生中,方案数\(\binom{n+3}{m}\)。

  • 两个老师之间无男生:
    那么两个老师之间只能是一个女生,所以把该女生与老师绑在一起。
    然后把绑在一起的三人插入到男生中,方案数\(\binom{n+1}{1}\) 。
    再把剩下的女生插入到已经形成的队列中(不能两个老师之间),方案数\(\binom{n+2}{m-1}\)。

注意每个人有区别,所以最后乘\(n!m!2!\) ,需要些高精度。

[HNOI2012]集合选数

Tag:构造、状压DP
对于最小为计数的点\(x\),构造矩阵:
\(x\ \ \ 3x\ \ \ 9x\ ....\)
\(2x\ 6x\ \ 18x\ ....\)
\(4x\ 12x\ 36x\ ....\)
然后相当于不能选择矩阵中相邻的元素。
注意到该矩阵的大小最多只有\(17*11\),直接暴力状压即可。

[HNOI2012]矿场搭建

Tag:贪心、割点
把所有的割点求出来,
并把割点删去后把图分成很多联通块,割点算作一个单独联通块。
对于一个联通块,考虑其连接的割点个数。

  • 若割点个数为0
    若联通块大小为\(1\),那么显然只需要放一个。
    若联通块大小大于\(1\),则需要放两个,以防放置点被炸毁。

  • 若割点个数为\(1\),需要放置一个,以防割点被炸毁。
  • 若割点个数大于\(1\),不需要放置。
    因为无论哪个割点被炸毁,都可以通过其他割点进行逃生。

方案数什么的用联通块大小算一算即可。

[HNOI2012]双十字

Tag:DP、计数
枚举每一列为中轴,对每一列单独做一遍计数。
枚举下面的横梁中点,最长延伸长度为\(l_2\),设上面的的横梁中点最长延伸长度为\(l_1\)。
讨论:

  • \(l_1 > l_2\) 方案数为\(\frac{l_2(l_2-1)}{2}\)
  • \(l_1 \leq l_2\) ,直接算方案数不好算,考虑总方案减不合法。
    总方案数为\(l_1 * l_2\) 。
    不合法方案数\(\frac{l_1(l_1+1)}{2}\)
    故方案数为\(l_1*l_2 - \frac{l_1(l_1+1)}{2}\) 。

可以看出树状数组维护即可。
至于向上、向下延伸的方案数对应的乘一下就行了。

[HNOI2012]与非

Tag:构造、思维
考虑我们用与非这个运算可以干什么。

  • \(notand(a,b) = not(a\ and\ b)\)
  • \(and(a,b) = not(a\ notand\ b)\)
  • \(notand(notand(a,a) , a)\) 为一个每一位都为\(1\)的数,然后就可以做\(not\)了。
  • \(not((not\ a)\ and\ (not\ b))=a\ or\ b\)

所以我们有了与非运算后,可以做\(\&\)、\(|\)、\(not\)三种操作。
然后我们就可以构造类似线性基的基础元了。
注意到,若某两位\((i,j)\)对于\(n\)个数都满足这两位相等,那么运算后这两位也一定相等。
对于没有限制的单位,我们一定可以构造一个只有该位为\(1\)的基础元。
构造:首先把该位不为\(1\)的数全部\(not\),然后把\(n\)个数全部\(and\)起来。
此时一定只有该位为\(1\),若其它为也有\(1\),则说明这两位是有限制的,与前提条件矛盾。
对于有限制的,类似方法可以构造出只有这些为位\(1\)的基础元。
然后依旧考虑线性基的原理,
我们问题变为:用这些基础元通过\(or\)运算可以构造出多少小于等于\(N\)的数。
从高位往低位,若当前位未被确定并且可以放,则有两种决策,答案直接加上不放的方案数即可。
当前位的确定关系以及限制关系用并查集维护一下就行了。
感觉这题还是比较难的......

HNOI2013 题解

[HNOI2013]游走

Tag:概率、高斯消元
设每个点被经过的期望次数为\(p_i\),度数为\(d_i\)
那么一条边的期望次数即为:\(\frac{p_u}{d_u} + \frac{p_v}{d_v}\) 。
问题变为求\(p_i\),显然\(p_u = \sum_{v}\frac{p_v}{d_v}\),高斯消元即可,注意\(1\)号点和\(n\)号点特殊处理。

[HNOI2013]切糕

Tag:建图、网络流
唯一的问题是如何解决距离不超过\(d\)。
设从列\(A\)走到列\(B\),对\(A\)列和\(B\)列建一个回路,强制割\(B\)列的一段中的一个即可。

[HNOI2013]数列

Tag:组合数学
注意到\(M(K-1)<N\),所以枚举差分数组\(s\)。
设枚举了一个差分数组\(s_1,s_2,...s_{K-1}\) ,和为\(S\),则方案数为\(N-S\) 。
所以\(Ans = \sum_{s_1,s_2....,s_{K-1}} (N-\sum_{i=1}^{K-1} s_i)\) 。
\(Ans = M^{K-1}N - \sum_{s_1,s_2...,s_{K-1}\sum_{i=1}^{K-1}s_i}\) 。
对于每一个\(s_i\),单独提出来:
\(Ans = M^{K-1}N - (K-1)(\sum_{s_i=1}^{M}1) M^{K-2}\) 。
所以\(Ans = M^{K-1}N - (K-1)M^{K-2}\frac{M(M+1)}{2}\)。

[HNOI2013]消毒

Tag:暴力、二分图匹配
注意到\(a*b*c\leq 5000\),所以\(min(a,b,c)\leq 17\) 。
所以暴力枚举一面的情况,然后暴力二分图匹配即可。

[HNOI2013]比赛

Tag:搜索、哈希
按照顺序暴力搜索,考虑减少搜索数。
设我们搜完了\(s\)个人,还剩下\(t\)个人。
将他们此时的分数排序,所有结果相同的状态方案数都一样。
所以就把这个东西哈希起来后记忆化即可。

[HNOI2013]旅行

Tag:思维、构造、单调队列
题目大意:给定一个只由\(1\)、\(-1\)构成的序列,
现在要求将其分为恰好\(m\)段,使得所有段的和的绝对值的最大值\(ans\)最小。
设序列长度为\(n\),后缀和为\(sum\),后缀和为\(0\)的位置有\(cnt\)个,序列和为\(S\)。
先扔结论:\(ans = \lceil \frac{|S|}{m} \rceil\) 。
注意到\(S=0\)时事情好像有点不太对劲...所以单独讨论一下\(S=0\)的情况。
当\(S=0\)时:

  • 若\(cnt[1]\ge m\) ,则\(ans=0\),直接选最后一个和\(m-1\)个后缀和为\(0\)的即可。
    我们顺次确定答案,设当前确定第\(i\)个休息点。
    只要后面的后缀\(0\)个数大于等于\(m-i\)就把元素入队,维护单调队列即可。

  • 若\(cnt[1]<m\),则\(ans=1\)。
    假设\(ans=0\),那么选的倒数第二个的后缀和得要是\(0\),同理倒数第三个也是\(0\)...
    然而我们后缀和为\(0\)的位置不足\(m\),故答案不可能是\(0\)。
    然而我们是一定有办法让答案变成\(1\)的,我们把后缀和的变化曲线画出来。
    那么合法的一段就是一个类似等高线的东西,我们调整等高线一定能使答案变为\(1\)。
    至于构造方案与\(S\neq 0\) 的情况放在一起。

当\(S\neq 0\)时,\(ans = \lceil \frac{|S|}{m} \rceil\)。
考虑把\(-1\)与最近的\(1\)缩到一起,那么最后序列就是由\(S\)个\(1\)或\(-1\)构成的。
所以答案自然就是\(\lceil \frac{|S|}{m} \rceil\)。
我们假设已经确定了上一个休息点为\(last\),当前确定第\(i\)个休息点。
那么新的休息点\(a\)需要满足条件:

  • \(n - a\ge m - i\)
  • \(\lceil \frac{|sum[a+1]|}{m-i} \rceil \leq ans\)
  • \(|sum[last+1] - sum[a+1]| \leq ans\) 。

这个好像没法做了.....没法做就暴力呗!
对每一种\(sum\)单独开一个单调队列,
每次暴力\(for\)一下\(sum\in[sum[last+1]-ans,sum[last+1]+ans]\) 的元素。
如果满足\(n-a\ge m-i\)就加入答案队列。
对于答案队列,当队头出现\(pos\leq last\)时弹掉队头即可。
复杂度:\(O(m\lceil \frac{|S|}{m} \rceil) = O(|S|)\),可以说这题是相当神仙了。

HNOI2014 题解

[HNOI2014]米特运输

Tag:思维
注意到确定了一个点那么整棵树的取值都确定了。
我们以\(1\)号点为基准,算出每个点为\(1\)号点的多少倍。
然后统计相同倍数的点对个数即可,至于连乘的话直接取\(log\)即可。

[HNOI2014]抄卡组

Tag:哈希

  • 若所有串都没有通配符,直接哈希比较即可。
  • 若所有串都有通配符,
    把无通配符的前缀 和 无通配符的后缀哈希后比较即可。
    中间部分由于通配符的存在,一定可以使所有串匹配。
  • 若部分串有通配符,
    首先把所有无通配符的字符串比较好。
    现在问题变为,能否通过通配符使每个串变为一个模板串。
    首先把前后缀比较好,然后就是中间部分。
    其实只需要让有通配符的串的中间部分与模板串匹配就可以合法。
    怎么匹配呢?暴力啊!反正是\(O(n)\)的。

输入比较恶心,稍微注意一下即可。

[HNOI2014]道路堵塞

Tag:最短路
根据\(k\)短路那套理论,很容易想到先把一条最短路抠出来。
如果删除边不在这条最短路上,那么对答案无影响。
否则会产生影响,需要我们想办法额外计算,考虑\(spfa\)的优良性质。
我们先把这条路径全部\(ban\)掉,然后按照\(S\to T\)的顺序一条边一条边加入。
设加入\((u,v)\),那么从\(v\)点直接增广即可(不用清空最短路数组!)。
这就是\(spfa\)的优点,因为它不像\(Dij\)那样是贪心算法,而是一个增广算法。
设我们增广到了一个最短路径上的点\(r\),
那么删掉\(v\to r\) 这一段上的边的答案都可以用当前距离更新。
直接拿个线段树暴力更新一下就行了。
但是由于卡\(spfa\)的泛滥化,这个题已经没有真正的解法了......

[HNOI2014]江南乐

Tag:博弈论、数论分块
根据\(SG\)定理,游戏结果即每一个子游戏的异或和。
所以只需要考虑每堆石子的\(SG\)值。
根据\(SG\)函数定义,该函数的值为所有后继状态的\(SG\)的\(mex\)。
设当前有\(n\)个石子,分为\(m\)堆。
那么有\(al_2=n-\lfloor\frac{n}{m}\rfloor m\)堆变为\(\lfloor \frac{n}{m} \rfloor +1\)个,
有\(al_1=m - al_2\)个变为了\(\lfloor \frac{n}{m} \rfloor\) 个。
显然我们只关心\(al_1\)和\(al_2\)的奇偶性(因为\(SG\)合并为异或运算)。
显然要数论分块,设\(x = \lfloor \frac{n}{m} \rfloor\) 。
那么\(al_2 = n - mx\) , \(al_1 = m - al_2\) 。
注意到\(m\)增加\(1\)后,\(al_2\)的奇偶性可能改变,而\(al_1\)的奇偶性一定不变。
所以分块后,我们只需要计算两次(\(l\)和\(l+1\))即可。
记忆化搜索即可。

[HNOI2014]世界树

Tag:虚树、DP、倍增
注意到\(\sum 询问点数 \leq NUM\) ,显然是虚树。
我们把虚树构建出来,通过换根\(DP\)求出虚树上的每个点的管辖点。
那么对于一条边\((u,v)\),由于是虚树,边上被省略的点的管辖贡献需要我们想办法计算。
如果\(belong[u] = belong[v]\),那么边上的所有点显然归\(belong[u]\)管辖。
否则,二分加倍增找出那个分界点,然后为两端的管辖点分别加上对应贡献即可。
细节较多,注意实现细节。

HNOI2015 题解

[HNOI2015]开店

Tag:主席树
简单转换后问题变为求\(\sum_{i=l}^r dep[LCA(i,S)]\) 。
用主席树,每次把\(u\)到根的路径权值全部加\(1\)。
那么上式的值就是\(S\)到根的路径权值之和。

[HNOI2015]菜肴制作

Tag:拓卜排序
逆序拓扑排序消除后效性即可。

[HNOI2015]接水果

Tag:整体二分、扫描线
对所有询问一起二分答案。
显然\(Check\)可以做树上扫描线算法。
问题转化为求一个点被多少个矩形覆盖,直接树状数组即可。

[HNOI2015]落忆枫音

Tag:拓扑排序、DP
首先如果不加边那么方案数就是\(ALL=\prod_{i=2}^n degree[i]\) 。
加了一条边\((s,t)\)后,不合法情况就是形成了环,此时的方案数为\(\frac{ALL}{\prod_{u\in loop}degree[u]}\) 。
那么显然\((s,t)\)一定在环中。
所以问题转化为求\(\sum_{road(t\to s)} \prod_{u\in road} \frac{1}{degree[u]}\) 。
注意到原图是一个\(DAG\),所以反向建边后直接拓扑序DP即可。

[HNOI2015]亚瑟王

Tag:期望、DP
我们考虑一张牌\(u\),在前\(i\)次尝试中成功发动技能的概率\(E_{u,j}\)。
枚举那一次成功,显然有\(_{u,j} = \sum_{j=1}^i (1-p_u)^{j-1}p_u\)。
一轮一轮的不好\(DP\),考虑按照顺序。
设\(f_{u,j}\) 表示前\(u\)张牌,成功发动了\(j\)张的技能的期望伤害。
只设\(f\)没法加入当前牌的贡献,所以额外设\(g_{u,j}\)表示前\(u\)张牌,成功发动了\(j\)张的技能的概率。
那么转移:

  • 当前这张牌未能发动技能
    \(f_{u,j} = f_{u,j} + f_{u-1,j} * (1.0 - E_{u,m-j})\)
    \(g_{u,j} = g_{u,j} + g_{u-1,j} * (1.0 - E_{u,m-j})\)

  • 当前这张牌成功发动技能:
    \(f_{u,j} = f_{u,j} + f_{u-1,j-1}*E_{u,m-(j-1)} + d_u*E_{u,m-(j-1)}*g_{u-1,j-1}\)
    \(g_{u,j} = g_{u,j} + g_{u-1,j-1}*E_{u,m-(j-1)}\)

最后答案就是\(\sum_i f_{n,i}\),复杂度\(O(n^3)\)。

[HNOI2015]实验比较

Tag:DP
首先把质量相同的图片全部用并查集缩到一起。
注意到"小\(D\)都最多只记住了某一张质量不比\(i\)差的另一张图片\(K_i\)"。
设图\(u\)的质量比图\(v\)好,那么把\(u\)作为\(v\)的父亲,这样建出来的一定是一个森林。
方便起见我们额外增加点\(Root\)使森林变成树。
设\(f_{u,j}\) 表示把\(u\)子树内的元素分为\(j\)段的方案数,
分为\(j\)段的意思即使用\(j-1\)个\(<\)连接整个序列。
然后考虑将一个儿子\(v\)合并到当前\(u\)的\(f'\)中去:\(f'_{u,j} f_{v,k} \binom{i-1}{j-1}\binom{j-1}{k-(i-j)} \to f_{u,i}\)
即首先把原来的\(j-1\)段(除去\(u\)点)放到\(j-1\)个位置中,
然后用\(v\)中的\((i-j)\)个把空位填满,剩下的与原来\(u\)的元素进行组合。
复杂度用\(LCA\)那套理论分析出来是\(O(n^3)\)的。

HNOI2016 题解

[HNOI2016]网络

Tag:链剖分、线段树
注意到查询为不收单点影响的路径。
所以每次加入一条路径时,我们把不在这条路径上的点加入当前元素。
链剖分后这些点构成了\(log\)个区间,直接暴力即可。

[HNOI2016]序列

Tag:莫队、st表
暴力莫队,考虑移动端点\(r\)时答案的变化量。
我们预处理\(pre_i\)表示区间\([1,1],[1,2]...[1,i]\)的答案和。
设莫队移动\([l,r]\to [l,r+1]\) ,
首先找到区间最小值位置\(p\),那么区间\([l,r+1],[l+1,r+1]...[p,r+1]\) 的答案都是\(p\) 。
剩下的部分呢?增量是\(pre_r - pre_p\) ,因为\(p\)已经是区间最小值了。

[HNOI2016]大数

Tag:莫队、暴力
首先求出模意义下后缀数的余数\(b_i\)。
那么对于区间\([l,r]\)所代表的数\(x\),有\(10^{n-r}x + b_r = b_l\) 。
当模数\(p\)是\(2\)或\(5\)的时候,我们暴力统计余数即可。
否则,若\(x = 0\),根据上式则一定满足\(b_l = b_r\) 。
所以变成了经典问题:区间内权值相同的点对有多少对,直接莫队即可。

[HNOI2016]树

Tag:模拟、主席树、倍增
注意到每次复制的都是模板树的子树,所以没必要把所有点都建出来。
对于每个复制子树,我们只建一个点表示即可。
考虑复制子树操作,首先我们需要找到对应的父亲节点。
由于我们没有把所有点都建出来,所以我们首先要找到代表该父亲所在子树的点。
二分即可。
找到该点后,我们需要求出该父亲对应原树上的哪个点。
这相当于一个子树第\(K\)大问题,我们对模板树建主席树,然后直接维护。
现在考虑求距离。
当我们新复制一个子树时,将新建点与其父亲所在子树的代表点连边。
这个边长设为新建点到父亲子树代表的的根的实际距离,这个直接在模板树上查询即可。
那么查询距离分几种情况:

  • 两个点在同一代表点内:直接在模板树上查询。
  • 一个点\(v\)为另一个点\(u\)的\(lca\):
    首先让\(u\)跳到其代表点,然后从代表点移动到\(v\)的代表点的下方。
    这个距离在新树上查询。
    然后上跳一步到达\(v\)所在子树,再在模板树上查询对应移动距离。
  • 两个点的\(lca\)非这两个点:与第二种情况类似。

对新树建立倍增数组就可以完成上述所有操作,注意实现细节。

[HNOI2016]最小公倍数

Tag:KD-Tree、分治、并查集
该题引发出了一个黑科技:KD-Tree分治。
把询问建成线段树式\(KD-Tree\),那么每条边能够影响到的询问就是一个区间。
直接类似线段树分治进行覆盖。
然后遍历一遍KD-Tree,用并查集维护联通块的最大边权,到达叶子结点时回答询问即可。

HNOI2017 题解

[HNOI2017]礼物

Tag:FFT
式子\(\sum_{i=1}^{n}(x_i-y_i)^2\)唯一需要解决的为:\(\sum_{i=1}^n x_iy_i\) 。
对\(x_i\)、\(y_i\)分别构建多项式,然后把所有情况都算出来就行了。

[HNOI2017]单旋

Tag:模拟、LCT、set
手玩一下就会发现,单旋极值后整棵树的形态不会变。
所以单旋涉及的操作为:断边、连边。
考虑直接用\(LCT\)模拟这个过程,无脑直接模拟即可,顺便维护深度(链长)。
唯一需要考虑的是插入,我们用\(set\)维护极值。
那么插入一个元素时,在\(set\)中找到前驱后继,其父亲一定是深度较深的那个点。

[AH2017/HNOI2017]影魔

Tag:线段树、单调栈
两个贡献的限制:

  • \(p_1\):左右端点分别为区间最大值、次大值。
  • \(p_2\):左右端点一个为区间最大值,另一个非区间最大值。

第一个其实非常好求,维护后继中第一个比其大的位置\(suf\),
那么可以注意到对于一个点\(u\),只有\([u,suf]\)会产生\(p_1\)的贡献。
加上询问的区间限制\([l,r]\)就变成了二维数点,随便怎么做都行。
然而这对正解并没有什么用,但还是相当有启发性的。
考虑把限制放松一点,我们先只算有一端为最大值得所有区间。
先算左端点为最大值的区间。
从右往左枚举每个点\(u\),那么每次就是把\([u,suf_u-1)\)全部加上\(p_2\)。
把查询挂在左端点,线段树对应区间查询\([q.l,q.r]\)即可。
右端点为最大值的区间倒过来做一遍即可。
然后注意到,我们这样做是把所有的\(p_1\)都当做\(p_2\)算了。
而我们已经知道如何计算\(p_1\)的个数了。
所以对每个区间算一遍\(p_1\)的个数\(cnt\),答案加上\(cnt(p_1-p_2)\)即可。

[HNOI2017]大佬

Tag:动态规划、bfs、two-point
题目给了一堆决策,其实就是唬你的。
显然只要不死就行了,剩下的天就可以干别的事了。
所以事先简单\(dp\)出最多能用几天干别的事,设这个天数为\(Day\)。
然后打一血那个决策显然也没用,因为这显然是用来补刀的。
然后就只剩下了升级、翻倍、放大招三种决策了。
注意到大招只能放两次......
\(What\ the\ Hell?\)
事情好像有点不太对劲。
只能放两次,很自然的就可以联想到two-point。
问题在于two-point啥。升级和翻倍的目的就是提升大招的伤害。
所以假设我们有很多二元组\((d,f)\),表示用\(d\)天升级翻倍使得大招伤害达到\(f\)。
那么两次大招需满足:

  • \(f_1 + f_2 \leq Health\)
  • \(d_1+d_2+2+(Health-f_1-f_2) \leq Day\)

以\(f\)为限制的two_point模型已经非常显然了。
最后的问题就在于如何求出所有这样的二元组。
官方题解说爆搜就行了。
虽然看起来非常假,然而搜出来最多状态好像就\(600w\)左右。
所以没有问题,直接暴力\(bfs\)即可。
记得写一个哈希表来判断当前状态是否出现过。

HNOI2018 题解

[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)<T_{i}-i\)
所以:
\[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<B\)。
若\(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)\) 。
实现起来细节巨多,注意代码实现和细节。

上一篇:JavaScript基础6


下一篇:JavaScript-Typescript:私人成员突然未定义