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

给定一个长度为 n01 序列,第 i 位是 0 代表 节点 i 到节点 imodn+1 有一条有向边,第 i 位是 1 代表 节点 imodn+1 到节点 i 有一条有向边。

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

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

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


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

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