CF1062F Upgrading Cities
Codeforces分析一个结论：拓扑排序时，任意时刻同时在队列中的两个点不能互相到达。设已经访问到的点数为 $tot$，那么如果队列中只有 $u$ 一个点，那么它可以到达剩下的 $n-tot$ 个点。如果队列中有 $u,x$ 两个点，那么首先 $u$ 不能到达 $x$；其次如果 $x$ 的出边中有一个点 $v$ 入度为 $1$，则 $u$ 一定无法到达那个点，那么 $u$ 就不满足条件了。...
标签 拓扑排序 下的文章
- 首页
- 拓扑排序
AGC027F Grafting
AtCoder分析先考虑如果有一个点没有被操作过该怎么做。我们把这个点作为根，在两棵树上分别 DFS 一遍，那么如果有解的话答案一定是在两棵树上父节点不同的点数。现在的问题在于如何判无解。首先如果 A 中一个点不要被操作但它的父节点要被操作，那么一定是无解的。否则，考虑到 A 中一个点的父节点要在它之后被操作，B 中一个点的父节点要在它之前被操作，这样子就有若干个偏序关系，我们只需要拓扑排序...
洛谷5284 [十二省联考2019]字符串问题
LuoguLOJ分析容易想到一个图论模型，即从每个 A 类串向它所支配的 B 类串连边，从每个 B 类串向以它为前缀的 A 类串连边，并将所有 A 类串的权值设为长度。这样问题变为求最长路，如果有环输出 -1。第一类边可以直接连，但第二类边暴力连复杂度爆炸，考虑一些优化。对反串建 SAM，此时 Parent 树上每个点的祖先都是它的前缀，于是我们只需要将树上每个 B 类串对应的节点向子树中所...
51nod2883 城市
51nod分析容易想到建出最短路图，则我们只需要求出最短路图上去掉一条边后有多少个点无法到达。这个似乎不太好做，可以对每条边建一个虚点，然后建支配树即可。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // ====================...
CF757F Team Rocket Rises Again
CodeforcesLuogu分析容易想到建出最短路图，问题变为求最短路图上去掉一个点后有多少个点无法到达。这是一个经典问题（[ZJOI2012]灾难），直接建出支配树即可。题解代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // ========...
洛谷2597 [ZJOI2012]灾难
Luogu分析似乎是 DAG 支配树的板子题。具体求法是拓扑排序，并将每个点的父节点设为所有前驱的 LCA 即可。实现时可以倍增 LCA 也可以 LCT。这样子每个点的答案就是它在支配树上的子树的大小减 $1$（因为自己不算）。代码// =================================== // author: M_sea // website: http://m-...
AtCoder Grand Contest 001 简要题解
比赛地址BBQ Easy排序后相邻的两个放一组即可。正确性显然。Mysterious Light可以发现每次反射之后问题都变为一个子问题，于是直接递归做下去即可。可以发现边界为 $n\bmod x=0$。Shorten Diameter当 $k$ 为偶数时，枚举一个根，然后删掉所有到根距离 $>\frac{k}{2}$ 的点。在所有这样算出来的答案中取 $\min$ 即可。当 $k$ ...
JOI 2018 Final 简要题解
寒冬暖炉同 CF1110B Tape。先令每个客人来的时刻都开暖炉，其它时刻关暖炉。那么每次选最短的一段间隔不关直到只有 $k$ 段即可。代码美术展览显然将所有艺术品按 $A_i$ 排序后答案一定是连续的一段。设 $sum_i$ 表示 $\sum_{j=1}^iB_j$，那么题目给的那个式子可以拆成 $sum_r-sum_{l-1}-A_r+A_l$。因此我们从后往前扫，维护 $sum_i-...
洛谷5025 [SNOI2017]炸弹
LuoguLOJ分析最简单的想法是每个炸弹向能炸到的所有炸弹连一条边，然后统计每个炸弹能到达多少个点。然而这样子边数是 $O(n^2)$ 级别的。注意到一个炸弹一定是向一段区间连边，那么线段树优化连边即可。统计的话，注意到每个炸弹能到达的的点一定是一段区间。那么缩点后按拓扑序算一下能到达的最小编号和最大编号就好了。写起来还是很休闲的代码`// ========================...
AGC001F Wide Swap
AtCoderLuogu分析令 $a_{p_i}=i$。注意到要使 $p$ 的字典序最小，则应使 $a$ 的字典序尽量小。那么题目变为：给定排列 $a_{1..n}$，如果 $|a_i-a_j|\geq k$ 且 $|i-j|=1$ 则可以交换 $a_i,a_j$，求可能排列中字典序最小的。注意到如果 $a_i,a_j$ 不可能发生交换（也就是说 $|a_i-a_j|<k$），那么两者...