UOJ NOI Round #4 Day2 题解

这次的题目背景大部分是vfleaking写的。

出题人 01,02,03 只是主人公的名字，和真实出题人没有任何的关系。

同构判定鸭

from Picks，标程 by Aprilgrimoire，数据、题解 by zhouyuyang 和 vfleaking。

算法0

这题好不可做啊!

print 'Same'

期望得分: $0$

算法1

我会爆搜！

在wc上学了高超的搜索技巧感觉充满了力量！

期望得分: $15 \sim 35$ 。

算法2

对于 DAG 的情况，显然若存在坏串则坏串长度不超过 $max {n_{1}, n_{2}}$ 。

适当选取一种对字符串集合的哈希函数之后，我们就可以对于每一个结点 $v$ 和每一个 $k$ ，递推计算出从 $v$ 出发可匹配的且长度为 $k$ 的字符串集合的哈希值。然后就容易根据哈希值计算出坏串的最短长度了。

输出字典序最小的最短坏串可以通过按位贪心来实现。

时间复杂度 $O (n^{2} m)$ 或 $O (n m)$ 。

期望得分: $20 \sim 40$ 。

算法3

DAG 的情况启发我们去思考：如果存在坏串，那么最短的坏串长度是否比较短呢？

注意如果不是比较短的话，题目也不会让我们输出方案的。不然岂不是出题人亲自邀请大家炸测评机？

实际上我们确实能证出如下结论：

结论：如果存在坏串，则最短的坏串长度不超过 $n_{1} + n_{2}$ 。

证明是这样的。首先我们可以把 $G_{1}, G_{2}$ 拼成一个 $n_{1} + n_{2}$ 个点的大图 $G$ （ $G_{2}$ 的结点编号都加上 $n_{1}$ ）。给定一个字符串 $s = s_{1} s_{2} \dots s_{L}$ ，想统计 $s$ 在 $G_{1}$ 和 $G_{2}$ 中的出现次数之差，我们可以用 $f_{k, v}$ 表示 $G$ 中长度为 $k$ 且与 $s_{1} \dots s_{k}$ 匹配且最后一个结点是 $v$ 的路径条数，然后递推求出 $f$ 。最后如果 $\sum_{1 \leq v \leq n_{1}} f_{L, v} - \sum_{n_{1} < v \leq n_{1} + n_{2}} f_{L, v} = 0$ 则出现次数相等，否则不相等。

仔细分析递推式可以发现这是个线性的递推式，且相同的 $k$ 的转移只跟 $s_{k}$ 和 $v$ 有关。那么我们可以把转移写成 $26$ 个矩阵 $M_{a}, M_{b}, \dots, M_{z}$ 。若把初始的 $f_{0, v}$ 写成一个行向量 $u_{I}^{⊤}$ （一个元素均为 $1$ 的行向量），那么最终 $f_{L, v}$ 就是 $u_{I}^{⊤} M_{s_{1}} M_{s_{2}} \dots M_{s_{L}}$ 。令 $u_{O}$ 为前 $n_{1}$ 个元素都是 $1$ ，其他元素都为 $- 1$ 的向量，则 $s$ 在 $G_{1}, G_{2}$ 中出现次数相等当且仅当 $u_{I}^{⊤} M_{s_{1}} M_{s_{2}} \dots M_{s_{L}} u_{O} = 0$ 。

现在我们令 $V_{K}$ 为所有 $L \leq K$ 的 $s$ 对应的行向量 $u_{I}^{⊤} M_{s_{1}} M_{s_{2}} \dots M_{s_{L}}$ 组成的集合。如果 $G_{1}, G_{2}$ 不等价，就说明存在一个 $K$ 使得 $V_{K}$ 内有元素 $u^{⊤}$ 满足 $u^{⊤} u_{O} \neq 0$ 。

下面要用到一点点向量空间的概念。对于一个行向量集合 $V$ ，我们用 $span (V)$ 表示所有 $V$ 中元素的线性组合组成的集合，也即 $V_{K}$ 张成的向量空间。数学表达式为： $span (V) = {\sum_{i = 1}^{m} λ_{i} u_{i}^{⊤} : m \geq 1, u_{1}^{⊤}, \dots, u_{m}^{⊤} \in V, λ_{1}, \dots, λ_{m} \in R}$ 比如共线的向量张成的是一条线，共面的向量张成的是一个平面。对于每个 $V_{K}$ ，我们令 $U_{K} = span (V_{K})$ 。容易看出， $V_{K}$ 内有元素 $u^{⊤}$ 满足 $u^{⊤} u_{O} \neq 0$ 当且仅当 $U_{K}$ 内有元素 $u^{⊤}$ 满足 $u^{⊤} u_{O} \neq 0$ 。

对于一个行向量集合 $V$ 和一个矩阵 $M$ ，我们用 $V M$ 表示 ${u^{⊤} M : u \in V}$ 。那么 $V_{K}$ 是可以递推的： $V_{K} = V_{K - 1} \cup (⋃_{c \in {a, \dots, z}} (V_{K - 1} M_{c}))$ 。因此 $span (V_{K})$ 也是可以递推的： $U_{K} = span (U_{K - 1} \cup (⋃_{c \in {a, \dots, z}} (U_{K - 1} M_{c})))$

根据定义， $U_{1} \subseteq U_{2} \subseteq U_{3} \subseteq \dots$ 。那么 $U_{K}$ 是否会随着 $K$ 的增大而一直变大呢？根据向量空间的性质和上面的 $U_{K}$ 的递推式，答案是不会的。

这里要用到向量空间的维数的概念。直观上一个向量空间 $U$ 的维数就是你直观所以为的那个维数（线是 $1$ ，面是 $2$ ）。数学上，维数的一个等价定义是你在 $U$ 中最大的线性无关组的大小。其中线性无关组是指一组向量 $u_{1}, \dots, u_{d}$ ，满足性质：任意线性组合 $\sum_{i = 1}^{d} λ_{i} u_{i}$ 等于 $0$ 当且仅当 $λ_{i}$ 全为 $0$ 。对于两个有限维的向量空间 $U \subseteq U^{'}$ ，可以证明要么 $U$ 的维数比 $U^{'}$ 大，要么 $U = U^{'}$ 。这是因为 $U \neq U^{'}$ 的时候我们可以取一个 $u^{'} \in U^{'} ∖ U$ 加到 $U$ 的最大线性无关组里，就得到一个 $U^{'}$ 的线性无关组了。

显然， $U_{K}$ 的维数不会超过 $n_{1} + n_{2}$ ，因为这些向量就 $n_{1} + n_{2}$ 个坐标嘛。因此， $U_{K}$ 的维数先会随着 $K$ 严格单调递增，然后到某个 $K = K^{*}$ 时 $U_{K^{*}} = U_{K^{*} + 1}$ ，且这里 $K^{*} \leq n_{1} + n_{2}$ 。根据递推式我们可以看出相同的 $U_{K - 1}$ 一定推出的是相同的 $U_{K}$ 。所以一旦 $U_{K^{*}} = U_{K^{*} + 1}$ ，则 $U_{K^{*}} = U_{K^{*} + 1} = U_{K^{*} + 2} = \dots$ 大家都相等了。这就说明如果存在 $U_{K}$ 内有元素 $u^{⊤}$ 满足 $u^{⊤} u_{O} \neq 0$ ，则最小的 $K \leq n_{1} + n_{2}$ ，就证好啦。

细节不太清楚的可以去找本自己看得懂的线性代数教材瞧瞧向量空间的具体定义。不知道是否有不依赖于线性代数的证明，如果有的话欢迎分享下咯。

回到算法上来。现在我们知道了，如果对于所有长度不超过 $n_{1} + n_{2} + 1$ 的序列均合法则可以对于所有串均合法。

因此可以通过哈希确定坏串最短长度后即可按位确定答案。

时间复杂度 $O (n^{2} m)$ 或 $O (n m)$ 。

期望得分: $70 \sim 100$ 。

我和算法3一样为什么我挂掉了

你的哈希函数 $H$ 需要满足： $H ("ab") \neq H ("ba")$ 且 $H ("bc") + H ("de") \neq H ("be") + H ("cd")$ ，否则你的算法就会是错的。

Aprilgrimoire 在验题的时候加了一个extest把这种情况干掉了

一些正确的哈希姿势

例如从后往前数，位于不同位置的相同字符有着不同的哈希值。字符串的哈希值就是字符哈希值的乘积，多串的哈希值是每个串哈希值的和。

另一种方法是把字符串的哈希值设为 $b^{\sum_{i} s_{i} a^{i}}$ ，然后多串的哈希值还是每个串哈希值的和。

还有一种方法是把哈希值设成矩阵的形式，例如每个字符都对应一个 $3 \times 3$ 的随机小矩阵。

OIer 当然可以使用反正法说明哈希的正确率：“反正哈希正确率很高！” 但我们这里还是分析一下第一种方法。

第一种方法即事先随机出 $x_{i, c}$ 共 $(n_{1} + n_{2}) \times 26$ 个随机数，然后每个字符串的哈希值即 $H (s_{1} \dots s_{L}) = \prod_{i = 1}^{L} x_{L - i + 1, s_{i}}$ 。我们递推求出的是对于每个 $L \leq n_{1} + n_{2}$ ，两个图各自对应的哈希值： $f_{1} (L) = \sum_{s_{1} \dots s_{L}} g_{1} (s) H (s)$ 和 $f_{2} (L) = \sum_{s_{1} \dots s_{L}} g_{2} (s) H (s)$ 。这里我们用 $g_{1} (s), g_{2} (s)$ 表示 $s$ 在 $G_{1}, G_{2}$ 中的出现次数。

现在我们将 $x_{i, c}$ 看成变量而非随机数，则 $f_{1} (L, x), f_{2} (L, x)$ 都可以看作是 $x_{i, c}$ 的 $L$ 次多项式。不存在长度为 $L$ 的坏串，等价于 $f_{1} (L, x), f_{2} (L, x)$ 作为两个关于 $x$ 的多项式时是相等的（也即多项式系数相等，也即这两个函数在带入任意一组 $x$ 的时候都相等）。

因此就是要看看两个多项式不相等，但随机一组 $x$ 带入进去之后导致 $f_{1} (L, x) = f_{2} (L, x)$ 的概率是多少。我们可以用 Schwartz-Zippel 引理来说明：对于某个域 $F$ 上的不超过 $d$ 次的多项式 $f (x_{1}, \dots, x_{m})$ ，如果每个 $x_{1}, \dots, x_{m}$ 都是从 $F$ 中的一个大小为 $S$ 的子集中独立地均匀随机选取的，那么 $f (x) = 0$ 的概率不超过 $\frac{d}{S}$ 。

对于本题，大家当然会在模一个素数 $p$ 的情况下计算。令 $F = F_{p}, f (x) = f_{1} (L, x) - f_{2} (L, x), d = n_{1} + n_{2}, S = p$ ，就可以知道失败概率不超过 $(n_{1} + n_{2}) / p$ 。

但这个失败概率仅仅是做一次“用哈希值相等来判断两个字符串集合相等”的失败概率。算法中我们要枚举长度，还要按位贪心，所以大概要做 $O ((n_{1} + n_{2}) Σ)$ 次，其中 $Σ$ 是字符集大小。使用 union bound 可知总的失败概率是 $O ((n_{1} + n_{2})^{2} Σ / p)$ 。取个大点的 $p$ 就可以高枕无忧啦。

对这个问题有兴趣的同学可以搜一下 Polynomial Identity Testing (PIT) 学习一波。

Bonus

如果要求严格字典序最小，能否证明在存在严格字典序最小的情况下，答案串长度是否有限？若有限，答案串长度是否存在上界？

己酸集合

from zhouyuyang，数据、标程、题解 by zhouyuyang。

把题目名字的拼音拿出来，JiSuanJiHe，这提示了这是一道计(Ji)算(Suan)几(Ji)何(He)题。

算法0

我会暴力！

每次询问暴力计算答案!

期望得分 $15$ 。

如果利用算法 $2$ 中的方程判断，可能可以通过Subtask $3$ 。

算法1

我会KD-Tree!

随机数据KD-Tree的复杂度看上去很真实。

极端情况下会被卡到 $O (n Q)$ ，但是跑跑subtask $2$ 应该没啥问题。

事实证明KDT是一个死掉的算法。

期望得分: $45$ 。

算法2

我会写方程!

写出圆方程 $x_{i}^{2} + (y_{i} - z_{i})^{2} \leq R_{i}^{2}$ 。

移项得到 $x_{i}^{2} + y_{i}^{2} \leq R_{i}^{2} - z_{i}^{2} + 2 y_{i} z_{i}$ 。

如果我们把 $(x_{i}, y_{i})$ 映射到 $(y_{i}, x_{i}^{2} + y_{i}^{2})$ ,则问题转化为询问直线 $l : k x + b$ 以下的点个数。其中 $k = 2 z_{i}, b = R_{i}^{2} - z_{i}^{2}$ 。

维护斜率固定时的点的相对顺序，每次询问二分即可。

时间复杂度 $O ((n^{2} + Q) \log n)$ 。

期望得分: $30$ ，结合算法 $1$ 期望 $60$ 。

算法3

欸 $n = 12000$ 好像不太能继续用算法 $2$ 了。

欸能不能把 $n$ 给分成若干块，每块单独计算贡献。

如果按照分块的思路去维护，设把点序列分成 $S$ 块，每一块按照算法 $2$ 的思路来处理，则时间复杂度为 $O ((\frac{n^{2}}{S} + Q S) \log n)$ 。

取 $S = \frac{n}{\sqrt{Q}}$ 时最优，为 $O (n \sqrt{Q} \log n)$ 。

期望得分: $100$ 。

我和算法3一样为什么我又挂掉了

坐标范围是 $10^{9}$ 因此用 double 精度有可能会爆炸。

出题人没有说过点集互不相同，公告里也更新过了，所以对于相同点要又高超的处理技巧。

可能将点坐标转换后会出现三点共线，同时sort是不稳定排序，因此需要一些小技巧处理这种情况。

挑战哈密顿

from peehs_moorhsum，数据、标程、题解 by peehs_moorhsum。

算法0

我会暴力！

暴力搜索哈密顿路径，或者状压DP，可以通过前两个点。

期望得分 $20$ 。

算法1

第三个点是 $D A G$ ，第四个点缩强连通分量之后每个分量很小。

可以对于每个分量搜任两点之间有没有哈密顿路。

期望得分 $40$ 。

算法2

第五个点到第十个点是在一条链上随机加边生成的。

有各种乱搞姿势，看起来能在这些点获得10~57分不等

结合算法1，可以获得50~97分

算法3

接下来是标算。

维护边的一个尽量大的子集，满足只考虑这些边时每个点出入度都不超过1，且不构成圈。

如果子集大小达到 $n - 1$ ，则找到了一条哈密顿路。

考虑调整维护子集。按随机顺序考虑边，如果加入后不构成圈，且加入之后所有点度数均仍合法，则加入这条边。

否则如果不构成圈，但有一个点度数不合法，则以一半概率加入并把该点相连的与新加入边矛盾的边断掉。

用最暴力的方法实现，也能总用时在10秒左右跑出前9个点，10分钟左右跑出最后一个点。

期望得分: $100$ 。

如果利用LCT维护是否构成圈，能够快很多。~~但出题人因为太懒，并没有写~~

一些彩蛋

关于有向图哈密顿链，似乎是有不少论文的。

验题人实现了其中一些，发现都~~是反向优化~~没有很好的表现。

所以欢迎~~吊打论文的~~大家在题解区交流做法ww

另：这道题主角真的是03

peehs_moorhsum的博客

博客