乱搞
「CF353E」 Antichain-乱搞
· ✏️ 650 words · ☕ 2 mins read

给定一个长度为 $n$ 的 $01$ 序列,第 $i$ 位是 $0$ 代表 节点 $i$ 到节点 $i \bmod n + 1$ 有一条有向边,第 $i$ 位是 $1$ 代表 节点 $i \bmod n + 1$ 到节点 i 有一条有向边。

我们称一个节点对 $(u,v)$ 是妙的当且仅当不存在 $u$ 到 $v$ 和 $v$ 到 $u$ 的路径任何两者之一。

现在你要从这个图里面挑出一个集合,使得集合中任意两个不同的节点 $u$ 和 $v$ 之间构成的节点对 $(u,v)$ 都是妙的。

请你输出这个集合的大小的最大值。


「CF804D」Expected diameter of a tree-树的直径+乱搞
· ✏️ 1006 words · ☕ 3 mins read

给定一个含有 $n$ 个点, $m$ 条边的森林。有 $q$ 个询问,每次给出两个点 $u_i,v_i$ ,如果 $u_i$ 在联通块 $A$ 内,$v_i$ 在联通块 $B$ 内,我们随机选择两个点 $a \in A,b \in B$ ,我们在 $(a,b)$ 之间连一条边,如果这个连接成后新联通块不构成一个树,输出 $-1$ ,否则输出新联通块树的直径的期望。所有边权均为 $1$ 。