华中地区 19th 做题笔记

A - 聚魔石

难度：medium

区间 dp+期望板子。

最开始看错数据范围，以为平方复杂度过不去，然后思考了半小时未果，发现看错数据范围了。

期望题目倒过来做，如果正着做还要同时算概率很麻烦。设 $f_{l,r}$ 为区间 $[l,r]$ 向外扩展之后发生共鸣的期望次数。转移显然有：

$f_{l,r}=\frac{w_{l-1}}{w_{l-1}+w_r}\cdot(f_{l-1,r}+[p_{l-1}\gt\max_{i\in[l,r]}p_i])+\frac{w_{r+1}}{w_l+w_{r+1}}\cdot(f_{l,r+1}+[p_{r+1}\gt\max_{i\in[l,r]}p_i])$

。注意 $[s,s]$ 的贡献也是 $1$ 。

B - 迷向术式

难度：medium

注意到路径可以重边，所以在非二分图中可以通过不断绕奇环去改变原有路径长度的奇偶性，也就是非二分图中任意两个不同节点都同时存在长度为奇和偶的路径。相反地，在二分图中任意两个不同节点只存在长度为奇或长度为偶的路径。

如果当前节点 $a_p$ 所在联通块为非二分图，那么只要满足 $a_i$ 在当前联通块内的 $a_i$ 都能够到达。相反地地，如果当前节点 $a_p$ 所在联通块为二分图，满足 $a_i$ 在当前联通块内的同时，满足下列两个条件之一：

$a_i$ 和 $a_p$ 路径长度为偶数， $i$ 和 $p$ 奇偶性一致；
$a_i$ 和 $a_p$ 路径长度为奇数， $i$ 和 $p$ 奇偶性相反。

不难发现，无论是二分图还是非二分图， $a_i$ 的连通都具有传递性，即：

传递性：若 $a_i,a_j$ 能够互相到达，且 $a_j,a_k$ 能够互相到达，那么 $a_i,a_k$ 也能够互相到达。

那么我们发现实际上由 $a$ 序列建出的图是若干的完全子图。由于题目中的询问带有下标严格递增的限制，所以子完全图有了方向，变成了传递竞赛图。作为先手只有开局无路可走才会输，否则只要一步跨到最远点就必赢。即只要查询 $a[l+1\dots r]$ 中是否存在与 $a_l$ 在新图中同一完全子图就可以了。离线不难处理。

C - 拱辰封仪

难度：hard

难点在卡常。你怎么也是二分图。注意到 $O$ 是魔法总和为奇数，也就是为魔法值为奇数的元素共有奇数个，不难想到对这个能不能进行 $-1$ 的赋权操作。注意到

$E^2-O^2$

可以因式分解成：

$(E+O)(E-O)$

。前者相当于所有方案数，后者就是对所有魔法值为奇数的元素进行 $-1$ 赋权了。在进行生成函数卷积的时候，前者系数为 $1$ ，后者为 $-1$ 。

两点之间存在奇数的路径，不仅满足两点处于同一连通块中，且满足下列条件之一：

该联通子图为非二分图，即存在奇环。
该联通子图为二分图，且两点分属左部和右部。

不难发现对于不同的连通块之间的贡献相互独立。相同连通块中，若该连通块为非二分图，则该连通块最多选出一个点；若为二分图，则左部和右部不能同时选点。

接下来刻画一下生成函数状物。对于非二分图，生成函数必然形如 $(1+px)$ 。对于二分图而言，左部和右部的贡献分开算，然后由于在该连通块中两者是相互独立切不能叠加产生贡献，所以最后把左部右部生成函数加起来。注意 $f_0$ 实际上被加了 $2$ 次，但是考虑到空集在左部右部图的意义一模一样，所以需要记得将 $f_0$ 减去 $1$ 。

对于单独的一部图，在 $(E+O)$ 里每个元素的贡献是 $(1+x)$ 。元素叠加贡献即 $(1+x)^{|S|}$ 。然后这里有一个优化是，可以直接通过预处理组合数直接算 $(1+x)^{|S|}$ 的系数，不用将 $|S|$ 个 $(1+x)$ 进行合并。

在 $(E-O)$ 需要考虑 $a_i$ 为奇数的情况，不难发现 $a_i$ 为奇数的贡献是 $(1-x)$ 。元素叠加贡献即 $(1+x)^{|S_{\text{even}}|}(1-x)^{|S_{\text{odd}}|}$ 。这也是可以用组合数分开处理的。处理完合并两个函数即可。

合并多个生成函数时，我们通过合并大小最小的两个函数以做到像启发式合并一样地优化复杂度。这个东西叫做 Huffman 式顺序合并。感兴趣的读者可以去维基百科上搜一下。时间复杂度证明类似启发式合并。

NTT 的部分，那我问你，你都做到这题了，不会 NTT 说不过去吧。

卡常的部分就各位各显神通了吧。强烈要求出题人加大时限。

E - 魔物

难度：easy

贪心？分类讨论？听不懂。和我的 Slope Trick 大运说去吧。

应该是能解决每一天 $x,y,z$ 都在变化的版本。我们可以实时维护每一天的当前正在激活状态的聚魔石数量。由于每一颗聚魔石在每天必然有至少 $1$ 的正贡献，所以聚魔石数量 $j$ 不可能超过 $n$ 。那么可以设计状态 $f_{i,j}$ 表示第 $i$ 天激活的聚魔石数量为 $j$ 魔力的最大值。状态两维，转移一维。 $\Theta(n^3)$ 。过不去。

好像只有 Slope Trick 才能优化这样的一般结构了吧。不妨研究函数的性质。显然函数 $f_i$ 单调不增。如果存在 $j_1\lt j_2$ 使得 $f_{i,j_1}\lt f_{i,j_2}$ ，那么状态 $\{i,j_2\}$ 扔掉 $j_2-j_1$ 个聚魔石有 $Z(j_2-j_1)$ 的贡献，显然 $f_{i,j_1}\lt f_{i,j_2}+z(j_2-j_1)$ ，不是最大值矛盾。那么接下来研究一下斜率。发现 $X$ 相当于斜率函数在和 $y=-Xx$ 做 $(\max,+)$ 卷积， $Y$ 是斜率函数全局加 $Y$ ， $Z$ 是斜率函数在和 $y=-Zx$ 做 $(\max,+)$ 卷积，不过卷积方向是反的。不难证明斜率函数必然单调不增。具体地，通过实现一个双端队列 deque 维护相同斜率段， $X$ 和 $Z$ 操作分别是改变队尾和队首斜率。由于有斜率全局加，然后还要记录一个懒标记。

while(p>=j&&q[p][0]-(i-2)*y>x){
	maxn-=q[p][1];
	fmax+=q[p][1]*(q[p][0]-(i-2)*y);
	--p;
}
if(fmax>=x){
	++p;
	q[p][0]=x+(i-2)*y,q[p][1]=fmax/x;
	maxn+=q[p][1];
	fmax-=q[p][1]*(q[p][0]-(i-2)*y);
}
fmax+=maxn*y;
ll v=0;
while(p>=j&&q[j][0]-(i-1)*y<z){
	v+=q[j][1];
	f0-=q[j][1]*(q[j][0]-(i-1)*y);
	++j;
}
if(v){
	--j;
	q[j][0]=z+(i-1)*y,q[j][1]=v;
	f0+=q[j][1]*(q[j][0]-(i-1)*y);
}

G - 列星衡仪

难度：simple

维护一下前缀和后缀 $\min$ 和 $\max$ 就好了。没有什么难度。

I - 时间的含义

难度：simple

字符顺序显然不影响答案。所以按照 ASCII 码排序。然后答案是 $\sum_{1\le i\le \frac{n}{2}}\text{ord}(s_{2i})-\text{ord}(s_{2i-1})$ 。

J - 时间之书

难度：medium

提供一种不一样的构造方法。

有一个比较直接的思路，即维护每一个点所属编号，然后找到每一个三角形三个端点所属编号，可以通过获取顶点编号进行 update 和 query 操作。用一个 map 存每个编号所对应的点的权值。对于 extend，不用做任何事情。

现在问题是，要将这些节点赋什么编号。有一个想法是，让每个三角形的三个顶点分别赋上 $(i,A),(i,B),(i,C)$ 的编号。这个想法的问题在于一个点可能是若干个三角形的公共顶点。这样重复编号会使得 update 操作需要改变以该点为顶点的所有三角形的对应编号对应值。这很麻烦，而且可能要修改很多三角形。有没有什么不重不漏的修改方法呢？

如下图，这是 extend 一个初始三角形两层的示意图：

extend 两层的三角形

为了方便，本章节将 $1$ 个点朝上， $2$ 个点分别朝下方左右的称为 正三角形， $1$ 个点朝下， $2$ 个点分别朝上方左右的称为 倒三角形。请勿与一般的正三角形概念混淆。

绿色点是大三角形的三个顶点，红色点是第一层 extend 新增的三个点，蓝色点是第二层 extend 新增的九个点。不难发现，除了大三角形的三个顶点，每一层新增的点集相当于上一层新增的正三角形的边中点点集。

在上图中，红色点点集 $\{D,E,F\}$ 恰好为第零层大三角形的三条边的中点，蓝色点点集 $\{G,H,I,J,K,L,M,N,P\}$ 恰好为第一层三个正三角形（即 $\triangle AEF/4,\triangle BDF/5,\triangle CDE/7$ ）的三条边的中点。

根据这个性质，我们可以规定每轮新增的在编号为 $i$ 的正三角形内的三个顶点编号为 $(4i+2,A),(4i+2,B),(4i+2,C)$ 。特别地，规定大三角形的三个顶点编号为 $(1,A),(1,B),(1,C)$ 。

接下来是如何求出一个三角形所代表的顶点编号。我们可以模拟 extend 的过程，维护 extend 每一层对应三角形的信息。比如，要查询 $\triangle25$ ，我们模拟 extend 的过程是 $\{\triangle1,\triangle6,\triangle25\}$ 。扩展到下一层显然要知道当前三角形的三个顶点编号。问题是在扩展到下一层时如何求出下一层三角形的三个顶点编号。由于顶点编号与三角形为正三角形还是倒三角形有关，那么我们根据当前三角形 $\triangle i$ 和下一层三角形 $\triangle 4i+k(k\in\{0,1,2,3\})$ 是正三角形还是倒三角形分类讨论：

为了方便，本章节将 $\triangle i$ 相邻的大小相同的最多三个三角形（如果有）称作 $\triangle i$ 的邻域三角形。

当 $\triangle i$ 和 $\triangle 4i+k$ 均为正三角形时， $\triangle 4i+k$ 的三个顶点为 $\triangle i$ 的一个顶点和 $\triangle 4i+2$ 的两个顶点（即编号为 $4i+2$ 的三个顶点其中之二）；
当 $\triangle i$ 为正三角形且 $\triangle 4i+k$ 为倒三角形时， $k=2$ （恰好编号为 $4i+2$ 的三个顶点）；
当 $\triangle i$ 为倒三角形且 $\triangle 4i+k$ 为正三角形时， $k=2$ ，三个顶点为 $\triangle i$ 的三个邻域三角形 $\triangle j$ 的分别某条边的中点，即 $(4j+2,\alpha)$ ；
当 $\triangle i$ 和 $\triangle 4i+k$ 均为倒三角形时，的三个顶点为 $\triangle i$ 的一个顶点和三个邻域三角形之二 $\triangle j$ 的分别某条边的中点，即 $(4j+2,\alpha)$ 。

然后我们会发现当且仅当 $\triangle i$ 是倒三角形时，我们需要同时维护邻域三角形的编号。注意要将编号次关键字 $A,B,C$ 的方向固定。

这里给出笔者的 $\text{get\_id}$ 函数供大家参考。

vector<pi>get_id(int x){
	vector<int>v;
	while(x>1){
		v.push_back(x&3);
		x>>=2;
	}
	reverse(v.begin(),v.end());
	pi d0=pi(1,0),d1=pi(1,1),d3=pi(1,3);int t0=0,t1=0,t3=0;bool flag=0;
	for(auto c:v){
		int mid=(x<<2)|2;
		if(c==0){
			if(!flag){
				d1=pi(mid,3);
				d3=pi(mid,1);
				t0=t1=t3=0;
			}else{
				d1=pi((t3<<2)|2,3);
				d3=pi((t1<<2)|2,1);
				t0=mid,t1=(t1<<2)|3,t3=(t3<<2)|1;
			}
		}else if(c==1){
			if(!flag){
				d0=pi(mid,3);
				d3=pi(mid,0);
				t0=t1=t3=0;
			}else{
				d0=pi((t3<<2)|2,3);
				d3=pi((t0<<2)|2,0);
				t0=(t0<<2)|3,t1=mid,t3=(t3<<2)|0;
			}
		}else if(c==2){
			if(!flag){
				d0=pi(mid,0);
				d1=pi(mid,1);
				d3=pi(mid,3);
				t0=(x<<2)|0,t1=(x<<2)|1,t3=(x<<2)|3;
			}else{
				d0=pi((t0<<2)|2,0);
				d1=pi((t1<<2)|2,1);
				d3=pi((t3<<2)|2,3);
				t0=t1=t3=0;
			}
		}else if(c==3){
			if(!flag){
				d0=pi(mid,1);
				d1=pi(mid,0);
				t0=t1=t3=0;
			}else{
				d0=pi((t1<<2)|2,1);
				d1=pi((t0<<2)|2,0);
				t0=(t0<<2)|1,t1=(t1<<2)|0,t3=mid;
			}
		}
		flag^=c==2;
		x=(x<<2)|c;
	}
	return {d0,d1,d3};
}

K - 归途

难度：simple

判断边上两个方向有没有路径就好了。切记在 n=1\or m=1 的时候没有答案。

L - 后记

难度：easy

贪心板子，每个物品仅与 $w-s$ 的值有关。由于顺序固定，当出现冲突时，需要删掉前面 $w-s$ 最大的以保证正确性。用优先队列维护。

至于贪心正确性证明可以参考拟阵的证明。