注意到题目的难点在于施法的处理，但观察到 n 比较小，所以考虑枚举施法的次数。假设当前枚举到施法 k 次，则得到颜色为 i 的史莱姆需要获得颜色为 i,i-1,\cdot\cdot\cdot,i-k 的史莱姆其中一个（注意这里和下文中所有涉及到下标减法的都是在模意义下的），对应抓史莱姆时已经施法过的次数为 k,k-1,\cdot\cdot\cdot,0。所以如果想获得第 i 种颜色，除去施法的时间还需要 \min_{j=i-k}^i\{a_j\} 的时间。记 b_{i,k}=\min_{j=i-k}^i\{a_j\}，则最终答案即为 k\times x+\sum_{i=1}^n b_{i,k}。直接枚举 k,i 并对于每个 i 暴力计算 b 的时间复杂度为 \mathcal{O}(n^3)，不足以通过本题。不过有个很显然的优化，b_{i,k}=\min(b_{i,k-1},a_{i,k})，这样就可以每次 \mathcal{O}(1) 算出 b 了，时间复杂度 \mathcal{O}(n^2)。
#include <cstdio>
#include <algorithm>
const int N = 2e3 + 10;
int a[N], b[N]; long long ans;
int main()
{
int n, x; scanf("%d%d", &n, &x);
for (int i = 0; i < n; ++i)
scanf("%d", &a[i]),
b[i] = a[i], ans += a[i];
long long ret;
for (int k = 1; k <= n; ++k)
{
ret = 0;
for (int i = 0; i < n; ++i)
{
b[i] = std::min(b[i], a[(i - k + n) % n]);
ret += b[i];
}
ret += 1ll * k * x;
ans = std::min(ans, ret);
}
printf("%lld\n", ans);
return 0;
}
C - AND Grid
有两个 n\times m 的网格图。第一个被人涂上了若干 四连通 的红色格子，第二个被另一个人涂上了若干 四连通 的蓝色格子。现在把这两个网格图按同一方向重叠，如果格子上既有蓝色也有红色，则显示为紫色。现在给出所有显示紫色的格子，保证网格图的边缘不为紫色，构造出一组可能的原网格图。(3\le n,m\le500)
首先根据题目描述，我们能很轻松建立起一个图论模型。给出一张 n 个结点 n 条边的有向图，对于每个点 i 都有一条到 a_i 的有向边。注意到原题中给出的条件说明这张图是弱连通的，问题即为最少改变多少个有向边的终点能使得从任意结点出发经过恰好 k 条边都能到达 1。
能猜测到的一个结论是，改变完边之后，一定有 a_1=1，即在 1 处存在自环。证明也不难，因为从 1 出发走 k 步能到达 1，说明 1 被包含在一个大小是 k 的因数的环上。假设 a_1=r\ne 1，则 r 应该也在上述环上，而 r 走恰好 k 步会回到 r。又由于任意点走 k 步会到 1，所以 r=1，假设不成立。所以 a_1=1 成立。
又因为 $1$ 处的自环可以消耗次数，所以原问题就变为了从任意点出发，经过 **至多** $k$ 条边都能到达 $1$。来看一个当 $k=2$ 时的可能解法（同来自 AT 原题解）：
即把一些边改到连向 $1$ 来缩短距离。这样看，原题面又可以转化为：
> 给出一棵有根树，你要删掉最少的边，使得对于每个连通块都有：
> - 以根节点为根的子树深度最多为 $k$。
> - 不以根节点为根的子树深度最多为 $k-1$。
删边就是把原边改为指向 $1$，这样不以根节点为根的子树还需要一次机会走一条边到 $1$，所以最多为 $k-1$。这样就简单了，可以用 $\rm dfs$ 轻松实现。具体来讲，对于一个点 $x$，如果它有一个儿子 $y$ 满足以 $y$ 为根的子树深度为 $k-1$ 且 $x$ 不为根，就割掉 $x,y$ 之间的边，最终答案即为割掉的边数。时间复杂度 $\mathcal{O}(n)$。
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 1e5 + 10;
struct edge{ int v, next; }E[N]; int p[N], cnt, a, k, ans;
inline void init() { memset(p, -1, sizeof (p)); cnt = 0; }
inline void insert(int u, int v) { E[cnt].v = v; E[cnt].next = p[u]; p[u] = cnt++; }
int dfs(int u, int fa)
{
int dep = 0;
for (int i = p[u], v; i + 1; i = E[i].next)
v = E[i].v, dep = std::max(dep, dfs(v, u));
ans += ((++dep) >= k && (fa > 1)); return dep % k;
}
int main()
{
init(); int n; scanf("%d%d%d", &n, &k, &a); ans += (a != 1);
for (int i = 2; i <= n; ++i) scanf("%d", &a), insert(a, i);
dfs(1, 0); printf("%d\n", ans); return 0;
}
```
#### E - Salvage Robots
有一个 $n\times m$ 的网格图，其中每个格子可能有以下三种状态：
- 这个格子是空的。
- 这个格子是出口，整个网格图中出口有且仅有一个。
- 这个格子里有一个机器人。
现在想通过以下操作把尽可能多的机器人送到出口：
- 选择上下左右四个方向的一个，然后所有机器人沿着这个方向行进一步。如果一个机器人在到达出口前走到了边界外，它就会爆炸消失。
问最多能把多少机器人送到出口。($2\le n,m\le100$)
发现一堆机器人的状态不好描述，所以我们反向考虑，不移动机器人，而是去移动整个网格图和出口，并描述出口的移动情况。注意到描述出口移动情况的关键在于它移动的最远端。具体来讲，我们用一个四元组 $(l,r,d,u)$ 表示出口往左最多移动了 $l$ 格，往右 $r$，往下 $d$，往上 $u$。而这样的话，从上边界往下 $d$ 格，从下边界往上 $u$ 格，从左边界往右 $r$ 格，从右边界往左 $l$ 格都是已经出界过的地方，里面不可能有机器人了，有可能是爆炸了，有可能在爆炸前到出口了。当然，出口经过的地方也没有机器人了，因为它们出去了。总的来说，如下图（又来自 AT），黄色部分是出口到达的地方，红色部分是没有机器人的地方：
换句话说，上图中所有带颜色的格子都不会有机器人，白色格子里面机器人还是原来的样子。考虑设 $f_{l,r,u,d}$ 表示当前状态用 $(l,r,u,d)$ 描述时能救出多少机器人。则转移即为尝试拓展这个黄色的部分并计算贡献。具体来讲，我们分别尝试把黄色部分往四个方向拓展一格，则新救下的机器人即为新拓展的黄色部分和原来白色部分的交集。如下图（还是来自 AT），当往下拓展一格，可以救下紫色部分的机器人，当往右拓展一格可以救下绿色部分的机器人，往其他方向拓展不能救下新机器人：
直接 $\mathcal{O}(n^2m^2)$ 转移即可，具体细节见代码。
```cpp
#include <cstdio>
#include <algorithm>
const int N = 110; int f[N][N][N][N], v[N][N][2]; char s[N];
int main()
{
int n, m, x, y, ans = 0; scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
{
scanf("%s", s + 1); //计算列/行机器人的前缀和方便计算转移
for (int j = 1; j <= m; ++j)
{
if (s[j] == 'E') x = i, y = j;
else
{
v[i][j][0] = v[i - 1][j][0] + (s[j] == 'o');
v[i][j][1] = v[i][j - 1][1] + (s[j] == 'o');
}
}
}
//这里底下转移的时候取 min/max 其实就是计算白色部分。具体来讲就是红色边界和黄色边界取一个 min/max。
for (int l = 0; l < y; ++l)
for (int r = 0; r <= m - y; ++r)
for (int u = 0; u < x; ++u)
for (int d = 0, s; d <= n - x; ++d)
{
//最终答案即为所有状态取 max
ans = std::max(ans, s = f[l][r][u][d]);
if (l + r < y - 1)
f[l + 1][r][u][d] = std::max(f[l + 1][r][u][d],
s + v[std::min(x + d, n - u)][y - l - 1][0] -
v[std::max(x - u - 1, d)][y - l - 1][0]);
if (l + r < m - y)
f[l][r + 1][u][d] = std::max(f[l][r + 1][u][d],
s + v[std::min(x + d, n - u)][y + r + 1][0] -
v[std::max(x - u - 1, d)][y + r + 1][0]);
if (u + d < x - 1)
f[l][r][u + 1][d] = std::max(f[l][r][u + 1][d],
s + v[x - u - 1][std::min(y + r, m - l)][1] -
v[x - u - 1][std::max(y - l - 1, r)][1]);
if (u + d < n - x)
f[l][r][u][d + 1] = std::max(f[l][r][u][d + 1],
s + v[x + d + 1][std::min(y + r, m - l)][1] -
v[x + d + 1][std::max(y - l - 1, r)][1]);
}
printf("%d\n", ans); return 0;
}
```
#### F - Namori
给出一张 $n$ 个点 $m$ 条边的连通无向图，初始时所有结点颜色均为白色。我们定义一次操作为：
- 选择两个相邻同色结点，把它们的颜色翻转，也就是黑变白，白变黑。
问能否通过若干次操作使得原图所有结点变为黑色。($2\le n\le m,n-1\le m\le n$)
这道题看起来非常难下手，所以我们先来考虑数据范围里面比较简单的那一档 $m=n-1$。但即使在树上，原问题依然很棘手，所以我们要想到一个转化。注意到树一定是二分图，那我们把原图黑白染色后，原题即变为：
> 能选择两个相邻异色结点，把它们的颜色翻转，问能否通过若干次操作使得原图从初始状态变为所有结点都颜色翻转的状态。
以样例 1 为例。原题的操作是这样：
而经过黑白染色后的操作就变为了：
我们还可以通过棋子的模型把原题的题意进一步解释：
> 现在有一棵树，一些结点上有棋子，每次操作可以把棋子推到相邻的空位上，给出初始状态和结束状态，问能否通过若干次操作使原图从初始状态到结束状态。
这看起来就可做多了，下文中我们称初始状态为 $S$，结束状态为 $T$。首先当 $S$ 和 $T$ 状态下的棋子数目不一样时，显然不可能，否则一定存在一种方案。我们来对每条边分别考虑，显然一条边会把树分为两个连通块 $G_1,G_2$，则经过这条边的棋子数量即为 $S$ 下 $G_1$ 中的棋子数量与 $T$ 下 $G_1$ 中的棋子数量之差的绝对值。因为是最终操作是反色嘛，所以这个其实就是 $G_1$ 在 $S$ 下棋子数量和空位数量之差，我们钦定 $G_1$ 是那个子树连通块，这就可以一遍 $\rm dfs$ 求出来了，时间复杂度 $\mathcal{O}(n)$。
接下来我们来考虑 $m=n$ 的情况。这种情况显然是一棵基环树，但基环树也分种类。偶环基环树是二分图，情况跟树类似，我们先来考虑，而奇环基环树不是二分图，情况有所变化。对于偶环基环树，我们依然采用跟树一样的棋子模型。考虑环上的一条边 $e_i=(u,v)$，我们设在最终按方向 $u\rightarrow v$通过这条边的棋子数量为 $x$。（如果按照 $v\rightarrow u$ 通过则会做一个 $-1$ 的贡献）考虑割掉这条边之后，原图会变成一棵树，我们可以用上文所述算法算出这一部分的贡献 $a_{i}$，所以这条边的贡献为 $|a_i+x|$。所以最终答案即为 $\sum_{i=1}^c |a_i+x|$，其中 $c$ 表示偶环的大小。显然可以通过 $a_i$ 的中位数来找到答案的最小值（当然题解说也可以三分，我不是很会三分就不介绍了）。时间复杂度 $\mathcal{O}(n)