ad-hoc 精选集

Ender32k / 2024-10-23 / 原文

校内讲题。

传统

Sheriruth

一个连通块如果连不了边，那么一定形如一棵内向树或者一棵内向基环树。前者只需要判断祖先关系，后者需要讨论是否在环上。

否则考虑一个点 $u$ 如果有多条出边 $(u,v_1),(u,v_2),\cdots,(u,v_m)$，那么 $v_1,v_2,\cdots,v_m$ 会互相连边形成一个团（无向完全子图），并且此时 $v_i$ 能到的所有点也会被合并到这个团中。

于是最后连通块一定形如一个团和若干棵内向树，其中每棵内向树的根连向团中的某些点。大小为 $s$ 的团上相异两点 $u,v$ 的路径条数为 $\sum_i(s-2)^{\underline i}$，于是直接做就行了。注意特判如果 $u$ 直接走到团上的 $v$ 的情况。

构造

没有改了的。

交互

World Ender

题解 markdown 流失了，看官方 beamer 的题解吧，大概是一样的。

通信

Broken Device

考虑相邻两位一组，用三进制表示 $X$，每组有损坏/0/1/2 四种情况。那么损坏对应 $00$，$0,1,2$ 对应 $01,10,11$。这样构造能取到的上界为 $3^{150/2-40}$ 大概是 $5\times 10^{16}$。

然后把所有位随机打乱一下，这样的话损坏的组的期望就会减少，期望上界会到 $10^{19}$。具体打乱做法就是让 Anna 和 Bruno 共用一个随机种子，这样随机打乱的结果是相同的。

考虑把损坏的段也利用起来，如果有一段是 $\mathtt{X\_}$，那么可以填入 $01$；如果是 $\mathtt{\_X}$，可以填入 $10$。这样就能过了。

因为是随机打乱的，所以很难构造数据卡掉。

Message

参考了 u 群里面的做法，这个做法不用关心数据包被纂改的情况。

首先肯定不能传一个长度 $S$ 的信息，因为如果 $S=1024$ 的话你至少要 $1024+31=66\times 16-1$ 个 bit 来传输消息和可能被纂改的位置的信息，这样你要在 $1$ bit 之内传入长度，这太难了。

所以可以先把 $S$ 末尾加上形如 $0111\cdots$，形成长度为 $1025$ 的二进制串 $S'$，这样的话我们把 $S'$ 还原出来然后把最后一个 $0$ 以及后面的位全删掉就行了。

然后考虑如何使用 $31$ 个 bit 来传输 $31$ 位中哪些位是可能被纂改的。

我们把所有不会被纂改的位，也就是所有 $C_i=0$ 的 $i$ 拿出来，从小到大记为 $p_0,p_1,\cdots,p_{15}$。

注意到 $16>\frac{1}{2}\cdot 31$，所以可以构造一个唯一的最大值：具体地，如果我们将 $p_i$ 向 $p_{(i+1)\ \bmod\ 15}$ 连有向边，那么无论其余 $\{0,1,\cdots,31\}\setminus \{p_0,p_1,\cdots,p_{15}\}$ 中任意一个位置如何连出一条边，这个图都会构成一个内向基环树。而 $p_0,p_1,\cdots,p_{15}$ 为这个基环树的唯一最大环。

那么我们只需要考虑如何传输连边的信息：对于任意的 $C_i=0$，记录 $d_i=(p_{(i+1)\ \bmod 15}-p_i) \bmod 31$，我们在前 $d_i-1$ 个数据包的第 $i$ 位传 $0$，在第 $d_i$ 个数据包的第 $i$ 位传 $1$。然后接收的时候就只需要对每一位 $i$ 算出第一个 $1$ 的位置 $d'_i$，然后 $i$ 向 $(i+d'_i)\bmod 31$ 连边就行了。这样的话 $C_i=0$ 的位连的边一定是对的，$C_i=1$ 的位连的边可以任意。找到最大环就找到了所有 $C_i=0$ 的位。