小清新
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 ) (a,b) (a,b)(不考虑顺序)
直接猜 X X X 种元素构出的最大长度就是 不同的二元组个数,不是最大长度的话显然删掉序列末尾一定不会变得不合法
这个数量是平方级别的,也就是元素种类数大概就是根号
再想发现把数都取成质数就能完全等价于二元组了
接下来想怎么构造出来这个上界
相邻位置的传递可以看成连边, ( a , b ) (a,b) (a,b) 的二元组就看成 a → b a\to b a→b 的一条边,二元组需要全部出现,就是边要全部经过,由此想到欧拉路径
重新表述一下:答案上界的构造等价于 X X X 个点的完全图的一条欧拉路径
分讨, X X X 为奇数显然直接满足; X X X 为偶数的话每个点度数都是奇数,上界就取不到了
考虑增量构造,从 X − 1 X-1 X−1 推过来,发现最优的肯定是两两匹配后再删一条边
直接按这个上界构造即可
注意不能把所有的 X X X 都预处理,这样是 n n n\sqrt n nn 的,每次询问的时候现做即可,复杂度 O ( n ) O(n) O(n)
G
难评的一道题
显然有暴力思路是每次枚举一条边反转后重新跑
画画图发现只有反转最短路上的边才需要重新跑,其他可以分讨出来
F
嗯
以下是不会的题
C
感觉是比较套路的题 虽然我不会
最小生成树,以前见的都是魔改一下经典算法的过程然后什么数据结构维护一下
还有一种套路:边数很多的时候(比如完全图),通常可以分析出来许多边是没用的,只保留那些较优的边,再跑最小生成树算法
假设三条线段 x , y , z x,y,z x,y,z 两两相交,若 a x < a y < a z a_x<a_y<a_z ax<ay<az,那么只需保留 a x → a y , a y → a z a_x\to a_y,a_y\to a_z ax→ay,ay→az,显然第三条边是没用的
稍稍推广一下:考虑数轴上的一个位置,如果被多条线段同时覆盖,只需要按 a a a 排序后相邻两条线段连边即可
好对啊!set 简单维护之
B
好牛的题
貌似括号序列的限制是挺多的,找找性质
- x x x 与 y y y 连通
- x x x 必须是 ( ( ( , y y y 必须是 ) ) )
- x x x 到 y y y 需要存在一条长度为偶数的路径
- 会反复横跳的一定是在两个相同字符的点之间
… …
感觉这些都还差点意思
从边的角度分析:边要么是连接不同字符,这样的边反复横跳是没意义的;否则就是相同字符,反复横跳一次就会在串里面插入两个 ( ( ( 或者 ) ) )
再考虑路径:简单的情况是不经过第二类边,那么路径上一定是 ( ) ( ) ( ) ( ) ( ) . . . ()()()()()... ()()()()()...,这是好维护的
否则是从 x x x 出发走一段 ( ) ( ) . . . ()()... ()()...,接下来必定是走过 ( ( (( (( 的边若干次 后继续走
后半部分倒过来看,从 y y y 出发走一段 ( ) ( ) . . . ()()... ()()...,接下来走过 ) ) )) )) 边若干次后继续走
考虑只保留一类边进行并查集,得到若干连通块
记从 x x x 出发走到的第一个在同一连通块中,且连有一条 ( ( (( (( 的点为 p p p,对称的记 y y y 对应的点为 q q q,我们继续分析 p p p 走到 q q q 的过程
因为 p p p 和 q q q 均有 ( ( (( (( 和 ) ) )) )) 的边,可以通过反复横跳来修正中间括号匹配的限制,那么唯一的限制就是 存在偶数长度的路径!!
判断这个有比较 trick 的做法:
第一种方式比较好做,直接维护就行了