本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-21 20:56:05

这两道题都是状态压缩的题目。

P1879 [USACO06NOV] Corn Fields G

我们知道，对于一个状态 j，为了使它每一个 $1$ 之间不相邻，我们有 j & (1 << j) 为零。而要使它与前一行的状态 $k$ 不冲突，我们需要有 j & k 为零。

这就告诉我们怎么进行状态之间的转移。我们设 $f(i, j)$ 表示第 $i$ 行，状态为 $j$ 的时候的方案数。我们知道，$f(i, j)$ 可以由 $f(i - 1, k) \text{ s.t. } k \text{&} j = 0$ 转移而来，其中 $k$ 表示的是前一行的状态。

最终，我们有

$$ f(i,j) = \begin{cases} 0 & i = 0, j = 0\ \sum\limits_{k & j = 0} f(i-1,k) & \text{otherwise} \end{cases} $$

最终我们要统计的就是第 $m$ 行所有状态的方案数量和。

P1171 售货员的难题

旅行商问题嘛。依然是设状态 $f(i, j)$， 表示由状态 $j$ 走到第 $i$ 个点的最短距离，其中 $i \notin j$。

我们如果知道了 $f(i, j)$，就可以推出 $f(i, j\cup \{k\}) = f(i,j) + P_{j, k}$。归纳边界 $f(0, 1) = 0$。

我们要求的就是在最终的满状态里选一点，从这一点走到 $0$，找最小值。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-23 09:51:40

这道题的转移方程还不算难列：

$$ f(i, j) = \begin{cases} \frac 1 2 f(i, i) & j = 1 \ \frac 1 2 f(i - 1, j - 1) + \frac 1 2 f(i, j - 1) & \text{otherwise} \end{cases} $$

但是问题是，这个转移方程是带环的：

$$ \begin{aligned} f(2, 1) = \frac 1 2 f(2, 2) \ f(2, 2) = \frac 1 2 f(2, 1) + \frac 1 2 f(1, 1) \end{aligned} $$

但是我们发现，这个方程组是有通解的：

$$ \begin{aligned} f(n, 1) = \dfrac {\sum\limits_{i=1}^{n - 1} 2^{i-1} \times f(n - 1, i)}{2^n - 1} \ f(n, i) = \frac 1 2 f(n - 1, i - 1) + \frac 1 2 f(n, i - 1) \end{aligned} $$

于是，$f(n, 1)$ 的计算是 $O(n)$ 的，而 $f(n,i), \text{s.t.} \space i \neq 1$ 的计算是 $O(1)$ 的。

然后推出即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-12 22:54:59

题意

给定整数列 $A(A_1, A_2, \cdots, A_N)$ 与 $P(P_2, P_3, \cdots, P_N)$ ($1 \leq P_i \leq i$).

有以下操作：

• 对 $i = 2, \cdots,N$，将 $A_{P_i}$ 加上 $A_i$

重复以上操作 $10^{100}$ 次，问 $A_i$ 正负性。

分析

根据样例 1 有推导：

第一次操作后： $$ \begin{aligned} A_1 = A_i + A_2 \ A_2 = A_2 + A_3 \ A_3 = A_3 + A_4 \ A_4 = A_4 \end{aligned} $$

第二次操作后： $$\begin{aligned} A_1 = A_1 + A_2 = A_1 + 2A_2 + A_3 \ A_2 = A_2 + 2A_3 + A_4 \ A_3 = A_3 + 2A_4 \ A_4 = A_4 \end{aligned}$$

第三次操作后： $$\begin{aligned} A_1 = A_1 + 3A_2 + 3A_3 + A_4 \ A_2 = A_2 + 3A_3 + 3A_4 \ A_3 = A_3 + 3A_4 \end{aligned}$$

第 $10^{100}$ 次（在本问题下可以看作趋向正无穷）操作后： $$\begin{aligned} \lim_{n\rightarrow \infty} A_1 = n\times A_2 \ \lim_{n\rightarrow \infty} A_2 = n \times A_3 \ \lim_{n\rightarrow \infty} A_3 = n\times A_4 \end{aligned} $$ 显然，$A_3$ 的正负性由 $A_4$ 决定。同理 $A_2$ 的正负性由 $A_3$ 决定，$A_1$ 的正负性便是由 $A_2$ 决定。

于是确定 $A_1$ 的正负性就变成了从 $A_n$ 开始向上的一条推导的长链。

但是我们需要考虑 $P$ 值重复，例如 $A_2 = A_2 + A_3 + A_4$ 的情况。实际上这并不是问题，因为很明显可以将 $A_3 + A_4$ 视作整体处理。

因此我们的策略便是，构建出一颗以 $1$ 为根的树，从下到上推导每一层的正负性，低一层的正负性决定更高一层的。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-13 20:01:47

虽然标签给的是拓扑排序，但是本题实际上可以看成是联通性问题。

一头牛的排名能够确定，当且仅当它与其他所有奶牛都能够比较出优劣。也即，在图中，它需要与其他所有奶牛都联通。

题目便是统计这样的点的数量。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-13 21:12:18

图的割点

割点可以理解为是图中这样一种点：去掉它之后，原来的图割成了更多个子图，也即，这个图的极大连通分量数增加了。

图的割点可以用暴力的方法求得：遍历每一个点，删除并计算新的连通分量数。当然这个方法就跟它看起来那样愚蠢。

求图的割点可以使用 Tarjan 算法。

Tarjan 算法的分析

Tarjan 算法是类似 DFS 的算法：它对每一个点计算两个值，low 和 dfn。

其中 dfn 是这个点的访问顺序，类似树的深度；而 low 是这个点所连接到的最高的点的 dfn（当然不包括它的父亲）。

通过这两个数据，我们怎么判断一个点是不是割点呢？

low 是关键。

low 的实质是某个点所能连到的最高祖先。对于一个点 A，如果它的一个孩子 B 能够连接到比 A 更高的点，即 low[b] < dfn[a] 那么明显删除了 A 对 B 没有任何影响，因为 B 可以通过 low 中存储的祖先来与图联通。

但是如果 low[b] >= dfn[a]，也就是说 B 不能连接到比 A 更高的点，那么把 A 删除，明显会让 B 和整个图断开连接。所以，只要存在这样的孩子点，A 就是一个割点

（B：A，至少对我来说，你是不可或缺的）。

Tarjan 算法的实现

自然是 DFS。以 P3388 【模板】割点（割顶） 为例。

存图用邻接链表即可。之后对每一个没有访问过的点 i （vis[i] == false），我们进行一次 Tarjan（因为题目中提到本图不一定联通）。

DFS 中先设置 vis 和 dfn，然后将 low 初值设为 dfn。然后对每一个孩子进行 DFS，同时若孩子能连到比自己更高的点，便更新 low 与孩子的 low 相同。

之后我们判断是否是割点：如果 low[t] >= dfn[u] 并且这个点没有被找到过（因为我们需要进行多次 Tarjan，防止重复计算）我们就更新割点数量。

这里和普通 DFS 有一点不同：当孩子已经被访问过时，我们也需要对其处理，以更新 low 值。

同时还需要注意一点：

开始 Tarjan 的点需要进行特判，但也十分简单。我们知道，只要它有两个以上孩子，那么它一定是割点（因为起始点的入度是为零的）

以上就是 Tarjan 算法求割点的具体步骤。代码可参考 OI Wiki。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-14 10:18:57

题意就是求一个图中的最小环。但本题的边有很大的特殊性，因此可以用并查集完成。

有怎样的特殊性？

—— 本题中一个点最多有两条边相连，一条出边一条入边。所以可以用并查集解决。

并查集可以轻松判断是否形成环。但是要怎样计算环的长度？

实际上当一个点 A 在这个图（并查集）中形成环的时候，这个环的长度就是它到祖先的距离， find 过程递归的次数。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-14 10:40:27

本题虽然没有图，但是是明显的图论题。一只猴子想要到达所有的树，当且仅当它的跳跃能力要大于等于到所有树的最大距离。

这个“到所有树的最大距离”，很明显是最小生成树。

于是求出最小生成树，并且维护最大距离。之后对每一个猴子进行比较即可。

复杂度 $O(N^2 + M)$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-14 11:36:38

最开始考虑的是把 dis 初值设为挖井的代价，还兴致勃勃打了一大堆 Prim，最后发现狗屁不通。

看了一眼第一篇题解茅塞顿开。我们可以将“挖井”的操作看成是与地下相连。权重就是挖井的代价。Kruskal 即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-14 13:04:04

乍看本题以为是二分，但正解实际上是 MST。

“部落” 实际上就是连通块，而本题所要求的就是让连通块之间的路径最大（两个最近的部落之间尽可能远离）。

我们可以求这个图的最小生成树，这样，这棵 MST 中前 k 大的边就是所要断开的部落之间的路径。所以，这前 k 大的边中最小的也就是整个 MST 的边中的第 k - 1 大的边。

在 Prim 中维护所生成的 MST，最后输出第 k - 1 大即可。

我有一车对 WyOJ 的设想。很多可以实现，很多很难实现，很多我想实现，很多我不怎么想实现。

• 有一个可以实时预览的 Markdown 编辑器。难度不算太高，但是需要学现在 UOJ 用的这套前端框架，我没啥兴趣

• 评论可以用 Markdown 等。同理，难度不算很高，但是我不想学 marked 与 MathJax 怎么用，我对前端有零个兴趣。也许以后某天闲的时候会做

• 热全量备份系统。WyOJ 到现在只有一个本地的温数据库备份系统和冷数据备份系统（刻到光盘），我想做一个热全量备份系统。难度不高，我计划用 Glusterfs，但是发现 Alpine 没有 Glusterfs，于是暂时搁置。

• 博客的预览。很简单，只是懒得写。

• WyOJ 一车小功能 fix。太杂太麻烦，没有修复的欲望。

• 将洛谷专栏导入到 WyOJ。这个我非常想做，且正在做。具体方案是用开源的保存站（luogu-server）部署到本地来完成。正在学习。

• 与 CF、AtCoder 等联动。这个也很想做，但是还没有认真学习 Codeforces / Atcoder API，所以暂时没有能力。

• 接入一个基于深度学习的题目推送网络。这个项目是商业级的，我如果能把这玩意儿做好了，估计一大段时间不用打工了。但是我还没有学深度学习，正在买书 + 学习。

• 还有很多架构上的更新，太冗杂，没有兴趣。

大家谁如果有兴趣修复这些问题，可以联系我。