洛谷5284 [十二省联考2019]字符串问题
Luogu LOJ 分析 容易想到一个图论模型，即从每个 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 中一个点的父节点要在它之前被操作，这样子就有若干个偏序关系，我们只需要...
JOI 2018 Final 简要题解
寒冬暖炉 同 CF1110B Tape。 先令每个客人来的时刻都开暖炉，其它时刻关暖炉。那么每次选最短的一段间隔不关直到只有 $k$ 段即可。 代码 美术展览 显然将所有艺术品按 $A_i$ 排序后答案一定是连续的一段。 设 $sum_i$ 表示 $\sum_{j=1}^iB_j$，那么题目给的那个式子可以拆成 $sum_r-sum_{l-1}-A_r+A_l$。 因此我们从后往前扫，维护 ...
洛谷5025 [SNOI2017]炸弹
Luogu LOJ 分析 最简单的想法是每个炸弹向能炸到的所有炸弹连一条边，然后统计每个炸弹能到达多少个点。 然而这样子边数是 $O(n^2)$ 级别的。注意到一个炸弹一定是向一段区间连边，那么线段树优化连边即可。 统计的话，注意到每个炸弹能到达的的点一定是一段区间。那么缩点后按拓扑序算一下能到达的最小编号和最大编号就好了。 代码 `// ==========================...
AGC001F Wide Swap
AtCoder Luogu 分析 令 $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$）...
洛谷5332 [JSOI2019]精准预测
Luogu LOJ 分析 每个人在每个时刻只有 $2$ 种状况，考虑 2-SAT 。 设 $(x,t,0/1)$ 表示 $x$ 在 $t$ 时刻活着/死了。那么直接连边就好了。 另外还有一个隐藏条件：如果 $x$ 在 $t$ 时刻活着，那么在 $t-1$ 时刻也活着；如果 $x$ 在 $t$ 时刻死了，那么 $x$ 在 $t+1$ 时刻也死了。这个同样要连边。 问题变为在建好的图上，从 $(...