题解：P14450 [ICPC 2025 Xi'an R] Directed Acyclic Graph

_Ch1F4N_ · 2025-11-12 16:27:05 · 题解

考虑构造两层点，不妨给第一层点编号 1 \sim k 第二层点编号 k+1 \sim 2 \times k。

如果能让编号为 i 的点可以抵达编号在 [k+1,k+i) \cup (k+i,2 \times k] 中所有点，那么就可以构造出 2^k-1 种可达性两两不同的集合，于是考虑前后缀优化建图即可，如果把其他的点作为叶子挂在 1 上则大概可以构造出 O(n+2^{\frac{m-n}{3}}) 个可达性两两不同的集合（认为 m-n 远小于 n，下文均如此）。

后来验题队验题的时候有高手爆标了，于是加强了本题，新的做法考虑将上面的两侧点中的每个点都替换为一组三个点，并以原来的点编号作为新的组编号，我们另第一层第 i 组的第三个点可以抵达第二层 [k+1,k+i) \cup (k+i,2 \times k] 中所有组的第一个点，这里用与前面做法一样的前后缀优化建图。并令第一层第 i 组第一个点可以抵达第二层第 k+i 组第二个点，令第一层第 i 组第二个点可以抵达第二层第 k+i 组第三个点。那么第一层第 i 组选第一个点会导致第二层第 k+i 组只有两个点能被抵达，第一层第 i 组选第二个点会导致第二层第 k+i 组只有最后一个点能被抵达，第一层第 i 组选第三个点会导致第二层第 k+i 组没有点能被抵达，第一层第 i 组不选点则第二层第 k+i 组所有点均能被抵达（默认选了可以抵达所有点的点 1），如果把其他的点作为叶子挂在 1 上则大概可以构造出 O(n+2^{\frac{m-n}{2.5}}) 个可达性两两不同的集合。为了避免卡常开了很松的界。