11.21 小清新图论专场训练

小清新

A

怎么感觉不是很简单呢

分析一下发现操作的自由度是很高的，不妨认为 一个连通块内不需要考虑边的方向，只需考虑当前是否还有空位

空位的判定条件就是是否已经加出一个环了

int n , L ;
int a[N] , b[N] ;
int bin[N] ;
bool vis[N] ;
int Find( int x )
{
	if( x == bin[x] ) return x ;
	return bin[x] = Find(bin[x]) ;
}
//最终状态？ 
// 一个联通块最多只有一个环 

int main()
{
	scanf("%d%d" , &n , &L ) ;
	for(int i = 1 ; i <= L ; i ++ ) bin[i] = i ;
	for(int i = 1 ; i <= n ; i ++ ) {
		scanf("%d%d" , &a[i] , &b[i] ) ;
		int fx = Find(a[i]) , fy = Find(b[i]) ;
		if( fx^fy ) {
			bin[fx] = fy ;
			if( vis[fx]&&vis[fy] ) printf("SMECE\n") ;
			else printf("LADICA\n") ;
			vis[fy] |= vis[fx] ;
		}
		else {
			if( !vis[fx] ) vis[fx] = 1 , printf("LADICA\n") ;
			else printf("SMECE\n") ;
		}
	}
	return 0 ;
}

D

构造题，先猜出答案的下界/上界

容易想到先不考虑乘积相等的情况，相邻位置看成二元组 $(a,b)$（不考虑顺序）

直接猜 $X$ 种元素构出的最大长度就是 不同的二元组个数，不是最大长度的话显然删掉序列末尾一定不会变得不合法

这个数量是平方级别的，也就是元素种类数大概就是根号

再想发现把数都取成质数就能完全等价于二元组了

接下来想怎么构造出来这个上界

相邻位置的传递可以看成连边，$(a,b)$ 的二元组就看成 $a\to b$ 的一条边，二元组需要全部出现，就是边要全部经过，由此想到欧拉路径

重新表述一下：答案上界的构造等价于 $X$ 个点的完全图的一条欧拉路径

分讨，$X$ 为奇数显然直接满足；$X$ 为偶数的话每个点度数都是奇数，上界就取不到了

考虑增量构造，从 $X-1$ 推过来，发现最优的肯定是两两匹配后再删一条边

直接按这个上界构造即可

注意不能把所有的 $X$ 都预处理，这样是 $n\sqrt{n}$ 的，每次询问的时候现做即可，复杂度 $O(n)$

G

难评的一道题

显然有暴力思路是每次枚举一条边反转后重新跑

画画图发现只有反转最短路上的边才需要重新跑，其他可以分讨出来

F

嗯

以下是不会的题

C

感觉是比较套路的题 虽然我不会

最小生成树，以前见的都是魔改一下经典算法的过程然后什么数据结构维护一下

还有一种套路：边数很多的时候(比如完全图)，通常可以分析出来许多边是没用的，只保留那些较优的边，再跑最小生成树算法

假设三条线段 $x,y,z$ 两两相交，若 $a_x<a_y<a_z$，那么只需保留 $a_x\to a_y,a_y\to a_z$，显然第三条边是没用的

稍稍推广一下：考虑数轴上的一个位置，如果被多条线段同时覆盖，只需要按 $a$ 排序后相邻两条线段连边即可

好对啊！set 简单维护之

B

好牛的题

貌似括号序列的限制是挺多的，找找性质

• $x$ 与 $y$ 连通
• $x$ 必须是 $($ ，$y$ 必须是 $)$
• $x$ 到 $y$ 需要存在一条长度为偶数的路径
• 会反复横跳的一定是在两个相同字符的点之间
  … …

感觉这些都还差点意思

从边的角度分析：边要么是连接不同字符，这样的边反复横跳是没意义的；否则就是相同字符，反复横跳一次就会在串里面插入两个 $($ 或者 $)$

再考虑路径：简单的情况是不经过第二类边，那么路径上一定是 $()()()()()...$，这是好维护的

否则是从 $x$ 出发走一段 $()()...$，接下来必定是走过 $(($ 的边若干次 后继续走

后半部分倒过来看，从 $y$ 出发走一段 $()()...$，接下来走过 $))$ 边若干次后继续走

考虑只保留一类边进行并查集，得到若干连通块

记从 $x$ 出发走到的第一个在同一连通块中，且连有一条 $(($ 的点为 $p$，对称的记 $y$ 对应的点为 $q$，我们继续分析 $p$ 走到 $q$ 的过程

因为 $p$ 和 $q$ 均有 $(($ 和 $))$ 的边，可以通过反复横跳来修正中间括号匹配的限制，那么唯一的限制就是 存在偶数长度的路径！！

判断这个有比较 trick 的做法：

第一种方式比较好做，直接维护就行了