题解-AGC046F Forbidden Tournament/CF1338E JYPnation (hard)

这两道题所要求的竞赛图性质都是:不存在一个三元环连向同一个点。所以我们考虑这样的图的性质。


对于竞赛图,我们经常会考察他的强连通分量。这题中,如果存在多个强连通分量,并且第一个强连通分量大小 \(\ge 2\),那么一定可以在第一个强连通分量中找出一个三元环,并连往后面的一个点。

所以我们可以先不停地删掉入度为 \(0\) 的点,剩下的点就只有一个强连通分量了。

显然对于任意一个点,连向他的点形成一张 \(\rm DAG\)。不妨考察第一个点,设 \(V_1\) 为存在 \(x \to 1\) 的点集,\(V_2\) 为存在 \(1 \to x\) 的点集。

考虑两个点 \(x \in V_2\),\(y \in V_2\) 满足 \(x \to y\):如果 \(x \to z\),\(z \to y\),并且 \(z \in V_1\)。那么 \((x,y,z,1)\) 形成一个不合法点集。所以设 \(S_x\) 为满足 \(x \to z\) 且 \(z \in V_1\) 的点集,必有 \(S_x \subseteq S_y\)。

那么如果 \(V_2\) 中存在一个三环 \((x,y,z)\),必有 \(S_{x} = S_{y} = S_{z} = \emptyset\)。对于剩下的点 \(r \in V_2\),则必然存在 \(v \in \{x,y,z\}\) 满足 \(r \to v\)。则 \(S_r = S_v = \emptyset\)。所以对于任意 \(x \in V_2\),\(S_x = \emptyset\)。那么 \(V_1\) 中入度最小的点入度为 \(0\)。矛盾。

所以 \(V_2\) 也是一个 \(\rm DAG\)。

不妨 \(arr1_i\) 为 \(V_1\) 中点的排列满足任意 \(x < y\) 都有 \(arr_y \to arr_x\)。类似地定义 \(arr2\)。

对于 \(x \in V_2\),若存在 \(i < j < k\) 满足 \(x \to arr1_i, arr1_j \to x, x \to arr1_k\),那么 \((x,arr1_i,arr2_j,arr1_k)\) 不和法。所以 \(x\) 连向的 \(arr1\) 中的点是一段区间。

而显然 \(arr2_{1}\) 连向 \(arr1_{|arr_1|}\)。所以 \(arr2_{1}\) 连向的是一段后缀。

上一篇:刷题-空格替换


下一篇:[AGC001E]BBQ Hard