洛谷5284 [十二省联考2019]字符串问题
LuoguLOJ分析容易想到一个图论模型，即从每个 A 类串向它所支配的 B 类串连边，从每个 B 类串向以它为前缀的 A 类串连边，并将所有 A 类串的权值设为长度。这样问题变为求最长路，如果有环输出 -1。第一类边可以直接连，但第二类边暴力连显然不行，考虑一些优化。对反串建 SAM，此时 Parent 树上每个点的祖先都是它的前缀，于是我们只需要将树上每个 B 类串对应的节点向子树中所有...
标签 拓扑排序 下的文章
- 首页
- 拓扑排序
LOJ6252 「CodePlus 2017 11 月赛」大吉大利，晚上吃鸡！
LOJ分析先考虑第一个条件。设 $c_i$ 为经过 $i$ 的 $s\to t$ 的最短路数，那么应该有 $c_a+c_b=c_t$。再考虑第二个条件。我们可以对每个点求出最短路图上不能到达它的且它不能到达的点集，然后存到一个 bitset 里。这可以直接拓扑排序求出。枚举 $a$，合法的 $b$ 应该满足 $c_t-c_a=c_b$。开一个 map 存下每个 $c$ 对应的点集，再和之前预...
JOISC2018 部分题解
高速道路の建設 / Construction of Highway这个操作长得很像 LCT 中的 access。于是我们每次只要 access 一下并把所有颜色段拿出来，然后树状数组求逆序对数，再把对应的边连上并把整条重链的颜色赋值为 $c_v$。因为 access 是均摊 $\mathcal{O}(\log n)$ 的，所以每次颜色段数也是均摊 $\mathcal{O}(\log n)$ ...
CF1062F Upgrading Cities
Codeforces分析一个结论：拓扑排序时，任意时刻同时在队列中的两个点不能互相到达。设已经访问到的点数为 $tot$，那么如果队列中只有 $u$ 一个点，那么它可以到达剩下的 $n-tot$ 个点。如果队列中有 $u,x$ 两个点，那么首先 $u$ 不能到达 $x$；其次如果 $x$ 的出边中有一个点 $v$ 入度为 $1$，则 $u$ 一定无法到达那个点，那么 $u$ 就不满足条件了。...
AGC027F Grafting
AtCoder分析先考虑如果有一个点没有被操作过该怎么做。我们把这个点作为根，在两棵树上分别 DFS 一遍，那么如果有解的话答案一定是在两棵树上父节点不同的点数。现在的问题在于如何判无解。首先如果 A 中一个点不要被操作但它的父节点要被操作，那么一定是无解的。否则，考虑到 A 中一个点的父节点要在它之后被操作，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-...