SCCPC 2026 做题笔记

A - 那一年的秘密基地

难度：hard

典中典小 DS 题。

拆分成两个问题。一个问题是静态问题，另外一个问题是动态询问两个点的贡献。

考虑对于二元组 $(i,j)(i\lt j)$，会对哪些节点产生 $1$ 的贡献。先随便找一个点 $1$ 作为根。然后分析 $i$ 和 $j$ 的位置关系。

第一种情况，$a_i$ 为 $a_j$ 的祖先或同祖先的子孙。如图 A-1，这里 $a_i=4,a_j=9$。$f$ 权值加 $1$ 仅对 $\text{Sub 9}$ 即以 $9$ 号节点为根的子树有生效。不难发现实际在 dfn 序列上是一段区间，即只需要执行 dfn 序列区间 $+1$ 即可。

第二种情况，$a_i$ 为 $a_j$ 的子孙。如图 A-2，这里 $a_i=9,a_j=4$。注意到实际上是对于除了以 $7$ 号节点为根的以外的子树的节点，其余节点均有贡献。这里 $7$ 号节点是 $9$ 的祖先且深度与 $4$ 号节点仅差 $1$。同样考虑在 dfn 上的表现，即除了 $[in_7,out_7]$ 区间其余区间都有 $+1$ 的贡献。

【子问题 1】

这里是静态问题，如果考虑每个有序二元组 $(i,j)$ 显然不行，我们可以考虑只枚举 $j$ 这一维，然后把 $i$ 这维的信息整合在一起统计。

对于所有 $a_i$ 为以 $a_j$ 的子树的节点，设 $a_i$ 的 $dep_{a_i}-dep_{a_j}-1$ 级祖先为 $u$，则会为 $[1,in_u)$ 和 $(out_u,n]$ 两个区间产生 $+1$ 的贡献。为了整合所有 $u$ 相同的节点 $a_i$，可以用树状数组去维护；对于要求最小的危险值以及区间 $+1$ 的贡献，可以用一个线段树去支持全局 $\min$ 和区间加的操作。

【子问题 2】

交换 $a_i,a_{i+1}$，影响的只是有序对 $(i,i+1)$。根据子问题前的两种情况分类讨论 $a_i,a_{i+1}$ 的位置关系，同样用线段树维护。

C - 精灵对战

难度：medium

小模拟也好 ** 恶心。

直接扫过一遍序列。贪心地考虑问题，如果第 $i-1$ 只最多战斗到 $j$，那么第 $i$ 只尽可能延长对局局数。由于没有后效性，所以局部最优解等同于全局最优解。

接下来考虑第 $i$ 只从 $l$ 出发最大能到达的 $r$ 是多少。首先我们希望前面的尽可能打败对手，维护一个集合 $S$ 存储前面所有局能战胜对方的种类的交集，处理第 $j$ 个对手的时候也是与对手的压制集合取交。

当交集为空集的时候，当前就无法做到赢对方，那么剩下两个结果，两败俱伤和输掉尽可能选择两败俱伤。能做到两败俱伤必须是当前集合至少存在一个元素的压制集合不包含对手 $j$。

REP(i,1,m){
	vector<int>vec;
	for(auto v:E[a[i]])if(s.count(v))vec.push_back(v); // vec 是两个集合的交集
	if(vec.empty()){ // 交集为空，赢不了了
		if(s.empty()){ // 己方精灵刚刚开始比赛，s 必定为空
			++res;
			for(auto v:E[a[i]])s.insert(v);
		}else{
			if(check(s,a[i])){ // 判断是否能平局
				s.clear();
			}else{
				s.clear();
				for(auto v:E[a[i]])s.insert(v);
				++res; // 不能平局
			}
		}
	}else{
		s.clear();
		for(auto v:vec)s.insert(v); // 取交
	}
}

时间复杂度 $\Theta(nk)$。把这份代码的 set 改成 vector 就可以实现了，但是有些麻烦。

D - 那一天的回文字符串

难度：simple

这不就是统计奇位置和偶位置的 $\text{cnt}$ 嘛！ $\bmod 4$ 分类讨论一下就好了。

E - 永恒的奥古斯都

难度：medium

计数入门题。

转换之后不难发现 $1\to 0$ 完全等同于 $0\to 1$ 的逆操作。所以给定某种 $0\to 1$ 的到达态问你可以有多少种初始态，完全等价于给定一个 $1\to 0$ 的初始态问你可以有多少种到达态。

注意到对于根节点颜色为 $1$ 的子树相对于颜色 $0$ 自由度更高，所以可以猜测一下根节点颜色为 $1$ 的子树的一些性质。不难猜测到当这个节点颜色变成 $0$ 时，以该节点为根的子树的其他节点可以取到所有颜色的情况且完全独立。

若某个节点初始颜色为 $1$，那么下面的所有节点必定可以取到所有情况；某个节点初始颜色为 $0$，若祖先节点变化，使其颜色变成 $1$，然后同样可以让子节点取到所有情况。所以我们发现，关键在于祖先节点有没有变化。设两个状态分别为祖先节点有变化，和没有变化，然后转移即可。线性复杂度。

F - 交换余生

难度：medium

我印象中我可能很久以前做过原题，但是忘了。但思路挺直接的。

即序列重排后要求每一个前缀 $⁡\gcd$ 和对应后缀的 $⁡\gcd$ 不能相同。

先把数组的最大公约数降成 $1$，不失一般性。否则可能会干扰后续操作。

不难发现前缀 $\gcd$ 必然单调不增，后缀单调不减。由于不可能出现一个 $d\gt 1$ 使得存在一个前缀和对应后缀使得 $⁡\gcd$ 均为 $d$（这样的话就意味着序列 $⁡\gcd$ 恰好为 $d$ 了），所以存在不满足题目条件的情况只能是至少存在一个前缀和对应后缀 $\gcd$ 恰好为 $1$。

对于一个合法的序列，前段有一个公约数 $d_1\gt 1$，后段有一个公约数 $d_2\gt 1$。所有元素中最多只能存在一个元素同时不能被 $d_1,d_2$ 整除，放在序列中间，如果可以被 $d_1$ 整除放在前段，如果可以被 $d_2$ 整除放在后段。对于 $d_1$ 可以枚举 $a_1,a_2$ 所有因数 $d_1$ 做判断（若存在合法序列，则 $a_1,a_2$ 中至少有一个能被 $d_1$ 整除）。每次判断的时候筛掉每一个不能被 $d_1$ 整除的元素，在剩下的序列里面用同样的方法枚举 $d_2$ 再次筛掉同样不能被 $d_2$ 整除的元素判断剩下的元素个数是否小于等于 $1$。若可以，说明中段存在放 $1$ 个同时不能被 $d_1,d_2$ 的元素的方案，否则不行。

G - 禁忌教典的消失咒文

难度：easy

在线做，用 map 存前缀和，然后好像没啥可说的了。挺典的。分类讨论正负号别忘记了。

H - 最大权独立集问题

难度：simple

注意到两个点有边当且仅当 $\text{popcount}$ 的奇偶性不同。

所以根据 $\text{popcount}$ 的奇偶性分成二分图，即在问二分图最大权独立集，就做完了。

K - 环基基环树

难度：hard

你是？不就板子叠叠乐嘛，和 A 题坐一桌。

容易想到先把所有桥拆掉，注意到目前拆掉的所有桥都是原基环树上枝条的边。那么剩下的一堆边双剩下一个原基环树环和若干个基环树点。

可以通过判断边数和点数是否相等从若干个边双中找到这个原基环树上的环。现在关键是要拆环。如果你不想像其他题解一样再写一个并查集去缩点找环，那么你可以像我一样再写两遍 Tarjan。具体地，对于原环上的每一条边 $(u,v)$ 在新图，必然有 $\deg u\ge3,\deg v\ge3$，但是注意到可能存在在一个点扩成的环上连续两个点都在原环上，所以不能直接根据 $⁡\deg$ 的性质特判。但是注意到只要是 $\deg u\ge 3$ 的点必然在原环上，所以随便找到一个 $\deg\ge 3$ 的点拎出另外一个点 $\deg\ge 3$ 的边判断一下断掉这条边剩下的部分是否还是一个大边双。若不是，断的就是原环边；若是，断的不是原环边。

void solve(){
	n=read(),m=read();
	idx=k=0;
	REP(i,1,n){
		E[i].clear();
		dfn[i]=low[i]=col[i]=sz[i]=0;
		cnt[i]=deg[i]=vis[i]=0;
	}
	REP(i,1,m){
		int u=read(),v=read();
		E[u].push_back(v);
		E[v].push_back(u);
	}
	tarjan(1,0);
	REP(u,1,n)for(auto v:E[u]){
		if(u>v||col[u]!=col[v])continue;
		++cnt[col[u]];
	} // 切割每一个边双
	p=0;
	REP(i,1,k)if(cnt[i]!=sz[i])p=i; // 通过判断点数边数是否一致找原环
	REP(i,1,n)if(col[i]==p)vis[i]=1;
	REP(u,1,n)for(auto v:E[u]){
		if(col[u]!=p||col[v]!=p||u>v)continue;
		++deg[u],++deg[v];
	}
	sz[p]=0;
	REP(u,1,n)for(auto v:E[u]){
		if(!p)break;
		if(!vis[u]||!vis[v])continue;
		if(deg[u]<3||deg[v]<3)continue; // 找到 deg>=3 的边
		U=min(u,v),V=max(u,v);
		if(check(u)){ // 判断剩下的是否是一个大边双
			REP(i,1,n)dfn[i]=low[i]=0;
			idx=0;
			tarjan3(u,0);
			break;
		}
	}
	writeln(k);
	REP(u,1,n)for(auto v:E[u]){
		if(col[u]==col[v]||u>v)continue;
		write_(col[u]),writeln(col[v]);
	}
}

彩蛋：Tunyu1s：写得一坨勾石。

L - 博德之跃 3

难度：hard

不知道是老了还是怎么样，感觉现在做贪心的题目很吃力啊！

贪心地考虑问题。对于 $\text{A}$ 序列串 $\text{s}[l\dots r]$，如果 $s_l\neq s_r$，那么选字典序较小的弹出。

剩下的情况就是 $s_l=s_r$，令 $c=s_l=s_r$，$i$ 为从左到右第一个不等于 $c$ 的下标，$j$ 为从右到左第一个不等于 $s_r$ 的下标。分类讨论问题：

• 当 $s_i,s_j\gt c$ 时，尽可能拖延 $c$ 的时长，所以 $\text{A}$ 序列左右弹出所有 $c$ 以及 $\text{B}$ 序列后面补上长度为 $\max(i-l,r-j)$ 的 $c$ 串。
• 当 $s_i,s_j$ 有一个 $\lt c$，一个 $\gt c$ 时，不失一般性地假设 $s_i\lt c\lt s_j$。则我们尽可能让 $s_i$ 尽快出现，所以左边弹出 $i-l$ 个 $c$，右边弹出 $\min(i-l,r-j)$ 个 $c$，以及 $\text{B}$ 序列后面补上长度为 $i-l$ 的 $c$ 串。
• 当 $s_i,s_j\lt c$ 且 $s_i=s_j$ 时，可是尽可能让 $s_i/s_j$ 尽快出现，所以左右边各弹出 $\min(i-l,r-j)$ 个 $c$，以及 $\text{B}$ 序列后面补上长度为 $\min(i-l,r-j)$ 的 $c$ 串。
• 当 $s_i,s_j\lt c$ 且 $s_i\neq s_j$ 时，不失一般性地假设 $s_i\lt s_j$。同样地，我们尽可能让 $s_i$ 尽快出现，所以左边弹出 $i-l$ 个 $c$，出于字典序最小的考虑，$s_j$ 越早出现一定是更优的，所以右边弹出 $\min(i-l,r-j)$ 个 $c$，以及 $\text{B}$ 序列后面补上长度为 $i-l$ 的 $c$ 串。

感觉讲得不是很好，如果有问题可以评论或者私信问问。