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$），那么两者...
Educational Codeforces Round 69 题解
比赛地址我真的什么都不会了嘤嘤嘤DIY Wooden Ladder语文题设次大的 $a$ 为 $x$ 。那么显然答案为 $\min\left\{n-2,x-1\right\}$ 。代码Pillars从大到小考虑所有盘子，如果它到最大的那个盘子中没有比它小的就可以移过去。写一个 ST 表 / 线段树 / 平衡树 / 分块 / …… 求区间最小值即可。代码Array Splitting假设分成两...
洛谷5284 [十二省联考2019]字符串问题
LuoguLOJ分析后缀自动机+树上倍增+后缀树优化连边+拓扑排序。考虑这样的构图方式：所有 $A$ 类串向它所支配的 $B$ 类串连边，所有 $B$ 类串向以这个 $B$ 类串为前缀的 $A$ 类串连边，同时把所有 $A$ 类串的长度作为该点的点权，那么我们就等于要求最长路。直接做是 $O(n^3)$ 的，考虑怎么优化这个东西。对反串建后缀自动机，然后第二类边就等于每个节点向子树中所有节点...
洛谷5361 [SDOI2019]热闹又尴尬的聚会
LuoguLOJ分析奇妙的构造题。因为尴尬的聚会比较难搞，所以考虑让热闹的聚会的人数最大。先考虑热闹的聚会怎么搞。二分答案 $mid$ ，然后把所有度数 $<mid$ 的点全部删掉，然后类似拓扑排序，把其它度数 $<mid$ 的点也删掉。然后如果剩下的点 $>mid$ 就可行。再考虑尴尬的聚会怎么搞。首先找到一个最小的满足条件的 $q$ 。考虑随机。把所有点 $\text{...
洛谷5332 [JSOI2019]精准预测
LuoguLOJ分析每个人在每个时刻只有 $2$ 种状况，考虑 2-SAT 。设 $(x,t,0/1)$ 表示 $x$ 在 $t$ 时刻活着/死了。那么直接连边就好了。另外还有一个隐藏条件：如果 $x$ 在 $t$ 时刻活着，那么在 $t-1$ 时刻也活着；如果 $x$ 在 $t$ 时刻死了，那么 $x$ 在 $t+1$ 时刻也死了。这个同样要连边。问题变为在建好的图上，从 $(i,T+1,...
AGC010E Rearranging
AtCoderLuogu分析好神啊...先考虑如果先手已经给出了序列，后手怎么做才能让字典序最大。容易发现，两个不互质的数的相对位置一定不会改变。对于每个数，向后面的与它不互质的数连边，然后在做一遍字典序最大的拓扑排序即可。考虑先手怎么做。我们把不互质的数间连双向边，那么先手的任务就相当于给每条边定向。手玩一下发现，先手从每个连通块中最小的点出发给所有边定向即可。正确性证明不会，感性理解一下...
洛谷3243 [HNOI2015]菜肴制作
LuoguBZOJ分析一开始我觉得，显然可以用拓扑排序来做，只要求字典序最小的拓扑序列就行了。然后$\color{red}{\mathrm{WA\ on\ \#Example\ 3}}$于是冷静分析一波，发现要求的其实是字典序最大的倒序的拓扑序列。具体来讲，对于每一个条件 $(u,v)$ ，从 $v$ 向 $u$ 连边，然后再跑一遍拓扑排序求出字典序最大的拓扑序列，最后倒序输出即可。正确性比...