ryp 的博客本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-20 17:17:06
赛后诸葛亮系列。思路还是不够开。
赛时写了一堆模拟，最后发现越来越复杂。事实证明，ABC 从来没有复杂的模拟题，只有你想不到的思维题。
实际上用 DP 很自然就能做出来。$f(i)$ 为到前 $i$ 个元素正着的最高点，$g(i)$ 为反过来。我们要找的是正反的交汇点，也就是 $\min \{f(i), g(i)\}$。
然后我们考虑转移。很明显，对点 $i$，如果 $s_i \ge f(i-1)$，那么 $f(i)\gets f(i-1)+1$。否则，山在这里就断了，$f(i) \gets s_i$。$g()$ 同理。
最后取 $\min \{f(i), g(i)\}$ 的最大值。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-24 17:20:11
本题实际上和删边最短路差不多，都是考察对算法的理解。只不过这题是考察 Floyd，而我的删边最短路是考察 SPFA（其实我本来想把它做成一个 DP 题）。
已知每一个点的修建完成时间，实际上这就是每一个点的建立顺序。给定了一个时间，我们就知道存在哪些点，进一步知道我们可以用哪些边来组成这个最短路。
然后就很简单了。对于每次询问，我们找 $t$ 时间内可以修建完成的点，然后用这些点来进行部分的 Floyd：即将最外层的 $k$ 换成一个定点。然后就能得到 $u$ 到 $v$ 的最短路。
需要进行的检查是：因为进行 Floyd 时，所有能用的点已经是前面询问得到的，因此一定都是在当前时间前的（题目给定 $t$ 单调不降）。于是我们只需要检查 $u$ 与 $v$ 现在修建完了没。
看来删边最短路也能评绿了（
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-28 21:44:51
题意比较简单：走到每一条边的概率是起点的出度分之一，保证图联通无环，求路径总长度的期望。
这是一个简单的图上拓扑 DP。只需要设 $f(v)$ 代表走到点 $v$ 的概率，于是 $f(v) = \dfrac {f(u)}{d^+(u)}$。于是明显，走到边 $(u, v)$ 的概率就是 $\dfrac {f(u)}{d^+(u)}$。
由于图是联通且无环的，我们统计总和即可。
题意就是：给定了 $a_i$ 与 $b_i$ 之间的关系，求最小可能的 $a$ 与 $b$ 序列。
利用拓扑排序解决问题的关键在于找出顶点之间的关系与限制，然后用拓扑排序取得一个可行解。在这个问题中，很明显，限制就是元素之间的大小关系。
但是需要处理相等的情况。很明显，可以用一个并查集将相等的元素合并起来，因为无论怎么样，这些数的最终取值都是相等的。
之后一遍拓扑即可。
我们可以想到：两量方向向外的车，一定无关紧要；同理，两辆命中注定的车，一定共同指向内端。再考虑方向：根据上面的方案，不管两辆车是无关紧要还是命中注定，它们方向都相反。我们可以简单的设 $1$ 号车的方向向左，然后染色即可。
之后我们建图。其实可以用原图来删边，省空间，不过逆向思维不好想。
如果没有限制顺序的要求，简简单单拓扑就行了。但是这个限制没有看起来那么简单：要求的是编号小的尽可能往前，但这并不是说字典序尽可能小。考虑 $2314$ 和 $3124$，前者的字典序更小，但后者才是题中说的更优的。
那这怎么处理？把它翻转过来：我们要求小元素尽量靠前，反过来就是小元素尽量靠后，也就是大元素尽量靠前，这实际上就是说字典序最大。那么原来的要求反过来是什么？是说编号大的尽可能往后，是句废话，没法转化。
所以我们要做的就是建反图，用优先队列让大编号点尽可能往前，然后取逆序列。
题意（翻译）极其简洁。既然要 “最大值最小”，很明显二分。于是将最优化转化成可行性判定：是否能通过改变边权小于等于 $k$ 的边来使图变为有向无环图。
我们知道：如果不限制边权，那么一定能将一个图转化为无环图。方法如下：我们找到图中入度最小的点，把它的所有入边改成出边，这样就能让它脱环。将它删除后，对剩余图进行同样的操作。
于是我们知道：只要是由边权大于等于 $k$ 的边组成的图无环，我们就一定能仅仅通过改变边权小于 $k$ 的边，将这个图转化为无环的。判断有环是简单的，可以用拓扑，也可以用 DFS。
最后的问题就是怎么求方案。实际上也简单。我们对由边权大于等于 $k$ 的边组成的子图进行拓扑排序，得到每个点的拓扑序。然后对剩下的每一条边，使起点的拓扑序小于终点，否则改变方向。注意我们并不求改变方向的最少次数。
拓扑排序有两种题：图上 DP 与求限制方案。对于前者，实际上动态规划转移的过程就是在 DAG 上遍历。点就是状态，而边就是转移。我们设出点代表的状态，然后来找与此相关的边的转移。
对于后者，重要的是找到边的方向以及权值代表的实际意义。这需要我们理解拓扑的原理：起点在拓扑序中，一定在终点之前。通过这个原理，我们就能排出方案。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-28 21:51:02
如果没有这个 $k$ 的限制，本题可以降黑了（大雾）
可以用 DP 做，但因为 DP 本身就是 DAG 的一种其他形式，我们可以直接建一个新图。具体的，将原来的 $n$ 个点变为 $kn$ 个，每一个点 $jn+i$，代表使用 $j$ 张免费票时的点 $i$。再找边：由 $(j - 1)n + u$ 可以以零边权指到 $(j - 1)n+v$，由于无向，反着指也可以。同时，$jn+u$ 和 $jn+v$ 是以 $w$ 边权联通的，其中 $w$ 就是正常机票。
之后我们要求的就是 $s$ 到 $jn+s$ 的最短距离，$\text{s.t.} \space j \in [0,k]$（这是一个坑点）。这个题开空间也是个坑点，让我爆了好几遍紫。。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-01 15:07:56
本题题意明显，就是求次短路。
最开始的思路比较简单：找出最短路，删掉这些边，然后再跑一次最短路，但这也很明显是错的。
实际上，我们可以像维护最短路那样，维护一个次短路。设 $f(v)$ 是从源点出发到点 $v$ 的最短路，$g(v)$ 则是相同意义下的次短路。
对于每次在边 $<u, v, w>$ 上的松弛操作：
若可以更新最短路，即 $f(v) \gt f(u) + w$，那么 $g(v) \gets f(v)$，$f(v) \gets f(u) + w$
若最短路没法更新，但是可以用原最短路更新次短路，即 $f(v) \le f(u) + w$ 但 $g(v) \gt f(u) + w$，那么只更新次短路：$g(v) \gets f(u) + w$
如果能更新次短路，即 $g(v) \gt g(u) + w$，那么 $g(v) \gets g(u) + w$
上述三个操作是依次进行的。这样进行一次 SPFA 就可以了。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-01 21:14:46
其实就是找 $x$ 到 $y$ 上的边权最小值的最大值。
那么我们可以考虑建一个最大生成树，然后在上面用倍增（LCA）来取边权的最小值。容易证明，在这个最大生成树上的边权最小值，一定是可能的最大值。
建最大生成树的过程实际上和最小生成树的贪心策略是一样的（Kruskal），只是排序反过来。
LCA 的特殊之处在于需要维护一个最小值的倍增。
别的就是板子了。以上。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-02 05:25:48
考虑到我们可以枚举中间值，然后要求的就是在每个元素之前，小于这个元素以及大于这个元素的元素数量。用乘法原理即可得到最后答案。
形式化地，我们设 $l_i$ 是 $1$ 到 $i - 1$ 中小于 $x_i$ 的元素数量，$r_i$ 对称，那么最终答案就是 $\sum\limits_{i=1}^{n} l_i\times r_i$。
那么我们就是要求参数 $l_i$ 与 $r_i$。考虑离线 + 离散化 + 树状树组。这里树状树组实际上就是个桶前缀和。
然后做法明显。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-03 08:22:36
三维偏序实际上就是经典题目 —— 逆序对 的升级版。但是前者是三维，而后者只是一维（啥比了，逆序对是二维的）。
我们可以利用一些技巧压掉第一维度，即：将这些元素按主键元素排序，于是，对于所有的 $i \lt j$，都有 $a_i \le a_j$，于是第一维被压掉了。
接下来我们考虑怎么压掉第二维，以转化到我们熟悉的逆序对。这里要用到 CDQ 分治。
CDQ 分治适用于区间上的一些操作：通过将大区间上的操作分割成小操作并归纳，我们可以免去处理合并的问题，只考虑对区间进行统计。
例如此题中，我们在分治过程中得到了两个子区间，现在我们要做的就是统计这两个子区间之间的三维偏序数量。
不妨将两个区间排序，设为 $L$ 与 $R$，那么对于所有 $0 \le i, j \le T$，都有 $a(L_i) \le a(R_j)$（因为 $i$ 和 $j$ 在原序列中是增的）。我们接下来要找的是满足 $b_i \le b_j$ 且 $c_i \le c_j$ 的。用一个双指针即可。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-04 19:43:52
数位 DP 的状态模板是设 $f(i, j)$ 表示第 $i$ 位，限制为 $j$ 时的方案数量。其中，$j = 1$ 表示有限制，即这一位上最大为 $x_i$；否则，这一位上最大为 9。
本题在简单数位 DP 的基础上，还加了一个条件：两数相差至少为 2。
这时候，朴素状态显然无法保证这一条件。那么我们加一维度，设 $f(i, j, k)$ 表示第 $i$ 位，限制为 $j$，且这一位为 $k$ 时候的方案数量。那么我们就能得出一个明显的转移，懒得 $\LaTeX$ 了。
但是有一个问题：考虑前导零。如果我们就用上面的方式转移的话，很明显这会出错，因为 1 不会被考虑在内。这时候，我们可以手动处理一下特殊情况：将前导零的情况特判，然后再转移即可。
btw 数位 DP 这种东西好恶心）
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-05 12:47:02
我们注意到一个重要的性质：每一行每一列最多只能放两个炮。
我们可以设 $f(i, j, k)$ 表示已经放完前 $i$ 行，$j$ 列是空的，$k$ 列放了一个，那么有 $m - j - k$ 列放了两个。我们并不需要知道具体是哪一列放了一个两个或者零个，只需要统计方案。
转移（这里滥用 $\gets$ 表示在原来的值上加）：
不动，转移到下一行：$f(i, j, k) = f(i-1, j, k)$
放一个，分成放到一个原来空着的列：$f(i, j, k) \gets (j+1)\cdot f(i - 1, j + 1, k - 1)$
放到一个原来有一个的列：$f(i, j, k) \gets (k + 1)\cdot f(i - 1, j, k + 1)$。
放两个，又分成两个都放到原来空着的：$f(i, j, k) \gets \dfrac12 (j + 2)(j+1)\cdot f(i - 1, j + 2, k - 2)$
一个放到空着的，另一个放到原来有一个的：$f(i, j, k) \gets (k + 1)(j + 1)\cdot f(i - 1, j + 1, k + 1)$
都原来有一个的：$f(i, j, k) \gets \dfrac12\times (k+2)(k + 1) \cdot f(i - 1, j, k + 2)$
然后转移。
鲁ICP备2025150228号