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)\) 。
实现起来细节巨多，注意代码实现和细节。