「AHOI2013」联通图-线段树分治+并查集

给定一个 $n$ 个点 $m$ 条边的无向连通图 $G$ 和若干个小集合 $S$,每个小集合包含 $c(1 \le c \le 4)$ 条边,对于每个集合,你需要确定将集合中的边删掉后改图是否保持联通。

集合间的询问相互独立。

「APIO2008」免费道路-生成树+并查集

给定一个 $n$ 个点,$m$ 条边的无向图,每条边有两种权值: $0$ 或者 $1$ 。

先询问能不能找出一个生成树,使得其中恰有 $k$ 条 $0$ 边,若存在,输出任意一个方案,否则输出 no solution

「NOI2015」品酒大会-后缀数组

简单版题意:

给定一个长度为 $n$ 的字符串,和一个长度为 $n$ 的数列 $\{a_n\}$ ,求对于 $r$ 从 $0$ 到 $n-1$ ,所有满足 $1 \leq p < q \leq n$ 且 $lcp(p,q) \geq r$ 的数对个数以及满足上述条件的数对中 $a_p \times a_q$ 的最大值。( $a_i$ 可以为负数)

「CF990G」GCD Counting-并查集/点分治

给定一个 $n$ 个节点的树,每个点有一个正整数权值 $a_i$ 。我们定义 $g(x,y)$ 为 $x,y$ 之间简单路径上所有点(包括端点)的权值的最大公约数。

现在请求出对于所有的 $i \in [1,2×10^5]$ ,满足 $1 \le x \le y \le n$ 且 $g(x,y) = i$ 的点对 $(x,y)$ 的数目。

「NOI2002」银河英雄传说-并查集

初始时,第$i$号战舰处于第$i$列$(i = 1, 2, …, 30000)$。

有两种指令:

合并指令为$M i j$,含义为将第$i$号战舰所在的整个战舰队列,作为一个整体(头在前尾在后)接至第$j$号战舰所在的战舰队列的尾部。

询问指令为$C i j$。该指令意思询问第$i$号战舰与第$j$号战舰当前是否在同一列中,如果在同一列中,那么它们之间布置有多少战舰。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×