T1 U
题目
你在一个滑冰场滑冰，这个滑冰场可以看作一个 \(H\times W\) 的网格，其中每一个格子都铺着一块砖——要么是冰砖要么是石砖，但还有一个特殊的格子，上面放着奖品，称为奖品格。
你的滑行方式是：
出发时，你可以选择上下左右四个方向中的一个滑行。
在滑行过程中，你只能沿着上下左右四个方向中的一个滑，并且每次只能滑过一个格子。
当你滑过冰砖时你不能改变方向，比如你从一块冰砖的左边进入你就只能从右边滑出。
当你滑过石砖时你可以改变成任意方向，包括转 90 度、继续走和原路返回。
当你到达放着奖品格时停止滑动。
当你滑出界时也停止滑动，这时候你就永远无法达到奖品格。
由于你的冰刀会磨损，所以你滑冰时的速度也会变化，具体地：
你从一个格子滑到一个与它相邻的格子需要 \(k\) 秒，初始时 \(k\) 为 \(1\)。
当你滑过一个石砖时，\(k\) 会增加 \(1\)（如果初始时就在一个石砖，则滑出第一步后 \(k\) 仍然为 \(1\)）。
你现在已经得到了这个滑冰场的地图，你想要知道从每个格子出发滑到奖品格最短要多少秒。
\(H,W\le 777, \# \le 7777\)
Solution
一眼广搜题，再看一眼发现根本没这么简单。
首先因为要知道每个格子出发到终点的距离，所以考虑倒着搜，从终点开始倒着搜。
会发现石砖的数量只有 \(7777\) 个，所以可以考虑计算出到石砖的距离然后用每个石砖向四个方向拓展得到其它冰砖的答案。
同时看到速度是变化的，所以可以建分层图，第 \(i\) 层向 \(i+1\) 层连边表示速度为 \(i\)，会发现这样连边后会构成一张 DAG，所以可以对每一层逐层进行扫描然后计算最短路。
因为是从终点出发，所以需要建反图，计算答案的时候也需要从上到下计算。
另外一个细节就是分层图的层数与石砖个数同阶，如果硬开这么多条边的话数组存不下，所以可以维护一个同层之间石砖的连边，然后对于每一层枚举到下一层的石砖，最后用倒数第 \(2\) 层的石砖更新冰砖的答案。
#include<bits/stdc++.h>
using namespace std;
constexpr int _SIZE = 777, _C = 7777;
struct EDGE{
int nxt, to, l;
}edge[(_C << 3) + 5];
int tot, head[_C + 5];
void AddEdge(int x, int y, int l) {
edge[++tot] = {head[x], y, l};
head[x] = tot;
}
int n, m, sx, sy, cnt;
int a[_SIZE + 5][_SIZE + 5];
char temp;
int dx[] = {0, 0, -1, 1}, dy[] = {1, -1, 0, 0};
bool check(int x, int y) {return x >= 1 && x <= n && y >= 1 && y <= m;}
int d[_C + 5][_C + 5], D[_SIZE + 5][_SIZE + 5];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
cin >> temp;
if (temp == '.') a[i][j] = -1;
else {
a[i][j] = ++cnt;
if (temp == 'G') sx = i, sy = j;
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (a[i][j] == -1) continue;
for (int t = 0; t < 4; t++) {
int x = i + dx[t], y = j + dy[t];
for (; check(x, y) && a[x][y] == -1; x += dx[t], y += dy[t]);
if (check(x, y)) AddEdge(a[i][j], a[x][y], (abs(x - i) + abs(y - j)));
}
}
memset(d, 0x3f, sizeof d), memset(D, 0x3f, sizeof D);
for (int i = 0; i <= _C; i++) d[a[sx][sy]][i] = 0;
for (int i = _C + 3; i; i--) {
for (int j = 1; j <= cnt; j++) {
if (d[j][i] == 0x3f3f3f3f) continue;
for (int k = head[j]; k; k = edge[k].nxt) {
int twd = edge[k].to;
d[twd][i - 1] = min(d[twd][i - 1], d[j][i] + i * edge[k].l);
}
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (a[i][j] == -1) continue;
if (d[a[i][j]][1] == 0x3f3f3f3f) continue;
for (int t = 0; t < 4; t++) {
int x = i + dx[t], y = j + dy[t];
for (; check(x, y) && a[x][y] == -1; x += dx[t], y += dy[t])
D[x][y] = min(D[x][y], d[a[i][j]][1] + abs(i - x) + abs(j - y));
}
}
for (int i = 1; i <= n; i++, cout << '\n')
for (int j = 1; j <= m; j++) {
int temp = (a[i][j] == -1) ? D[i][j] : d[a[i][j]][0];
cout << (temp == 0x3f3f3f3f ? -1 : temp) << ' ';
}
return 0;
}
T2 T
题目
有一场比赛，分两天举行。这场比赛有 \(N\) 个选手参加，在两天比完赛之后，会根据每名选手两天成绩之和排序（如有同分则随机排序），然后给第一、二、三名分别颁发金、银、铜牌。
现在比赛已经进行完第一天了，你得到了这 \(N\) 个选手第一天的成绩，分别为 \(A_1,A_2,\ldots,A_N\)，满足它们均为整数且 \(\forall 1\le i<j\le N,A_i\ne A_j\)。同时，作为第二天的出题人，你知道这些选手在第二天的得分将会是一个 \(1,2,\ldots,N\) 的排列。
给定 \(P\)，你想统计满足下述条件的三元组 \((X,Y,Z)\) 的个数：
若 \(P=1\)，则 \(A_X>A_Y>A_Z\)；否则 \(A_X>A_Z>A_Y\)。
第 \(X,Y,Z\) 名选手在第二天结束后可能分别获得金、银、铜牌。
\(N\le 10^6\)
Solution
\(P=1\) 的情况稍微容易一点，所以先讨论 \(P=1\) 的情况。
先将 \(A\) 按照降序排列，那么会有一个重要的结论：\(A_1+1\ge A_2 + 2 \ge \cdots \ge A_{n-1}+n-1 \ge A_n+n\)。
-
\((1,2,3)\) 肯定是合法的，一种可行的方案是：\((n-2,n-1,n,1,2,\cdots,n-3)\)。
-
考虑 \((1,2,x)(x\ge3)\) 什么时候合法，显然是当 \(A_x+n\ge A_3+1\) 时符合题意。此时的可行方案是 \((n-2,n-1,1,2,\cdots,n,\cdots,n-3)\)。
-
\((1,x,y)(2 < x < y)\) 只能在 \(A_y+n > A_2+1\) 合法，可行的方案是 \((n-2,1,2,\cdots,n-1,\cdots,n,\cdots,n-3)\)。
-
\((x,y,z)(1<x<y<z)\) 只能在 \(A_z+n>A_1+1\) 合法，可行的方案是 \((1,2,\cdots,n-2,\cdots, n-1,\cdots,n,\cdots,n-3)\)。
显然可以线性的统计。
这对于 \(P=2\) 的情况也有启发。
-
\((1,x,2)(x>2)\) 只在 \(A_x+n>A_2+1\) 时合法。
-
\((1,x,y)(2<y<x)\) 只在 \(A_x+n>A_2+1\) 时合法。
-
\((x,y,z)(2<x<z<y)\) 只在 \(A_y+n>A_1+1\) 时合法。
和 \(P=1\) 时需要统计的东西相同，只是少了 \((1,2,x)\) 的情况，所以甚至可以把两个放在一起统计。
时间复杂度显然是 \(\mathcal O(n\log n)\) 的，瓶颈在于排序。
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int _SIZE = 1e6;
int n, a[_SIZE + 5], T, P;
namespace SOLUTION1 {
void solve() {
int ans = 0;
for (int i = 3; i <= n; i++) if (a[i] + n >= a[3] + 1) ans++;
for (int i = 3; i <= n; i++) if (a[i] + n >= a[2] + 1) ans += (i - 3);
for (int i = 3; i <= n; i++) if (a[i] + n >= a[1] + 1) ans += (i - 2) * (i - 3) / 2;
cout << ans << '\n';
}
}
namespace SOLUTION2 {
void solve() {
int ans = 0, i = 3;
for (; i <= n && a[i] + n >= a[1] + 1; i++) ans += (i - 1) * (i - 2) / 2;
for (; i <= n && a[i] + n >= a[2] + 1; i++) ans += (i - 2);
cout << ans << '\n';
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> T;
while (T--) {
cin >> n >> P;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1); reverse(a + 1, a + n + 1);
if (P == 1) SOLUTION1::solve();
else SOLUTION2::solve();
}
return 0;
}
T3 S
题目
你有一个长度为 \(N\) 的数组 \(\{a_i\}_{i=1}^N\)，你还有 \(Q\) 个区间 \(\{[l_i,r_i]\}_{i=1}^Q\)，还有一个整数 \(M\)。
你可以将至多 \(M\) 个 \(a_i\) 变为 \(0\)，你想要最小化 \(\sum_{i=1}^Q\max_{l_i\le j\le r_i}\{a_j\}\)，输出这个最小值。
\(N,M,Q\le 50\)
Solution
一眼顶针，鉴定为纯纯的区间 \(\texttt{DP}\)。
看到 \(50\) 的数据范围，估计可以往 \(\mathcal O(n^5)\) 的区间 \(\texttt{DP}\) 想，并且转移肯定是枚举询问的区间带来的 \(\mathcal O(n)\) 复杂度，所以就尝试设计一个 \(n^4\) 的状态。
注意到转移与区间内最大的 \(a_i\) 相关，所以不如先把 \(a_i\) 离散化到 \(b_i\) 内，然后在状态中添加一维关于 \(b_i\) 的域，所以到这里，状态的设计就显而易见了。
设 \(f(t,l,r,lim)\) 表示区间 \([l,r]\) 还剩下 \(t\) 次修改操作可用，并且区间内大于 \(lim\) 的值都被修改成为 \(0\) 后的答案。考虑怎么转移。
显然可以先从大到小枚举修改的数是多少，假设 \(\forall b_k<lim,b_j<lim\) 有 \(b_k\ge b_j\)，即 \(b_k\) 是区间内 \(lim\) 的前驱，那么对于当前数显然有修改和不修改两种选择。
-
修改，那此时的问题递归进入 \(f(t,l,r,b_k)\) 解决。
-
不修改，那就计算当前 \(a_k\) 将会对答案带来多少贡献，然后将问题递归入 \(f(i,l,k-1,b_k)\) 和 \(f(t-i,k+1,r,b_k)\) 解决。转移方式就是 \(f(t,l,r,b_k)=\displaystyle\sum\limits_{i=0}^tf(i,l,k-1,b_k)+f(t-i,k+1,r,b_k)+cost\)，其中 \(cost\) 就是 \(a_k\) 对答案的贡献。
最后的答案就是 \(f(m,1,n,n)\)，时间复杂度为 \(\mathcal O(n^5)\)，不过区间 \(\texttt{DP}\) 的常数很小，所以可以过这道题。
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int _SIZE = 5e1;
int n, m, q;
int f[_SIZE + 5][_SIZE + 5][_SIZE + 5][_SIZE + 5], a[_SIZE + 5];
int L[_SIZE + 5], R[_SIZE + 5], b[_SIZE + 5], p[_SIZE + 5];
int solve(int t, int l, int r, int lim) {
int &res = f[t][l][r][lim];
if (res != -1) return res;
if (l > r) return res = 0;
res = LLONG_MAX / 3;
int p = 0;
for (int i = l; i <= r; i++) {
if (b[i] >= lim) continue;
if (b[i] > b[p]) p = i;
}
if (t) res = solve(t - 1, l, r, b[p]);
if (!p) return res = 0;
int cost = 0;
for (int i = 1; i <= q; i++)
if (L[i] >= l && R[i] <= r && L[i] <= p && R[i] >= p) cost += a[p];
for (int i = 0 ; i <= t; i++)
res = min(res, solve(i, l, p - 1, b[p]) + solve(t - i, p + 1, r, b[p]) + cost);
return res;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> q;
for (int i = 1; i <= n; i++) cin >> a[i], p[i] = i;
for (int i = 1; i <= q; i++) cin >> L[i] >> R[i];
sort(p + 1, p + n + 1, [&](int x, int y) {
return a[x] < a[y];
});
for (int i = 1; i <= n; i++) b[p[i]] = i;
memset(f, -1, sizeof f);
cout << solve(m, 1, n, n + 1) << '\n';
return 0;
}
T4 V
题目
你有一棵 \(N\) 个节点的树，初始每条边长度都为 \(1\) 。你可以使用魔法：每次魔法可以任意选择一条边并使它的长度增加 \(1\)。
给定 \(Q\) 次询问，每次询问给出 \(K_i\)，你必须正好使用 \(K_i\)次魔法，你想要让最终树的直径尽可能短，求最短直径。(询问与询问之间相互独立)。
\(N,Q\le 2\times 10^5\)
Solution
将树的直径中点看作树的根，将所有边变成向外发散的形式，这样这棵树看起来就变成了一个不太圆的圆，那么要使用满 \(K_i\) 次魔法还要保证直径尽可能小，那么肯定就是要尽量这棵树给扩成一个圆 （各方面全面发展） 。假定一个中心，使得树的半径是 \(R\)，那么让这棵树扩成一个圆至少需要 \(R\times leaf-dis\)（\(leaf\) 表示叶子数量，\(dis\) 表示叶子深度和）次操作。那么对于答案，可以用类似方程的方式表示：\(k=(r+x)\times leaf - dis\)，会发现每个点如果作为中心的话，对答案的贡献都是呈现一个斜率相同的一次函数的，所以可以将询问全部离线下来然后找到最优的这条一次函数。
现在还有另一个问题就是树的中心可能在点上，但是当直径并不是偶数的时候，中心就在边上，这时候上面的统计方法就不适用了。这时候有一个 trick，就是将边拆成一个点和两条边，这样原来长度为 \(1\) 的边就变成了两条长度为 \(1\) 的边，就保证了中心一定在点上。在最后统计答案的时候再判断一下这个点是不是边拆出来的特判一下就行了（可以用半径的奇偶性判定，要方便一点）。现在就把上面的式子 \(\div 2\) 就可以继续用来统计了。
还有一个问题，就是当叶子节点作为中心的时候，叶子节点数目会发生改变，这样会导致每个点作为中心的时候斜率不一定相等。不过可以发现当叶子节点作为中心的时候一定不会比与其邻接的点作为中心的情况更优，因此就可以将叶子节点的情况不计入讨论。
时间复杂度是 \(\mathcal O(n + q\log q)\)，瓶颈在于排序。
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int _SIZE = 4e5;
struct EDGE{
int nxt, to;
}edge[(_SIZE << 1) + 5];
int tot, head[_SIZE + 5], deg[_SIZE + 5];
void AddEdge(int x, int y) {
edge[++tot] = {head[x], y};
head[x] = tot; deg[x]++;
}
int n, q, f[_SIZE + 5][2], son[_SIZE + 5], dep[_SIZE + 5], d[_SIZE + 5], siz[_SIZE + 5];
int a[_SIZE + 5], b[_SIZE + 5], leaf;
int dis[_SIZE + 5], k[_SIZE + 5], val[_SIZE + 5], minn[_SIZE + 5];
int kb[2], ans[_SIZE + 5];
void dfs1(int x, int fa) { // 第一次 dfs 求直径，顺便记录下最长链来自于哪一个儿子
if (deg[x] <= 1) siz[x] = 1, dis[1] += dep[x];
for (int i = head[x]; i; i = edge[i].nxt) {
int twd = edge[i].to;
if (twd == fa) continue;
dep[twd] = dep[x] + 1;
dfs1(twd, x);
siz[x] += siz[twd];
if (f[x][0] < f[twd][0] + 1) f[x][1] = f[x][0], f[x][0] = f[twd][0] + 1, son[x] = twd;
else if (f[x][1] < f[twd][0] + 1) f[x][1] = f[twd][0] + 1;
}
}
void dfs2(int x, int fa) { // 第二次 dfs 求叶节点总距离和每个点作为中心的 R
for (int i = head[x]; i; i = edge[i].nxt) {
int twd = edge[i].to;
if (twd == fa) continue;
d[x] = max(f[x][son[x] == twd], d[fa] + 1);
dis[twd] = dis[x] + leaf - (siz[twd] << 1);
dfs2(twd, x);
}
d[x] = max(f[x][0], d[fa] + 1);
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
kb[0] = kb[1] = LLONG_MIN / 3;
for (int i = 1; i < n; i++) { // 读入 + 拆边
static int u, v;
cin >> u >> v;
AddEdge(u, n + i), AddEdge(n + i, u);
AddEdge(n + i, v), AddEdge(v, n + i);
}
n = (n << 1) - 1;
dfs1(1, 0);
for (int i = 1; i <= n; i++) leaf += deg[i] <= 1; // 统计叶子节点数量
for (int i = head[1]; i; i = edge[i].nxt) { // 跑出R和叶节点总深度存在 d 和 dis 中
int twd = edge[i].to;
dis[twd] = dis[1] + leaf - (siz[twd] << 1);
d[1] = f[1][son[1] == twd];
dfs2(twd, 1);
}
d[1] = f[1][0];
cin >> q;
for (int i = 1; i <= q; i++) cin >> k[i];
for (int i = 1; i <= n; i++)
val[i] = (d[i] * leaf - dis[i]) >> 1;
iota(a + 1, a + n + 1, 1);
iota(b + 1, b + q + 1, 1);
sort(a + 1, a + n + 1, [&](int x, int y) { // 将每个点的贡献排序
return val[x] < val[y];
});
sort(b + 1, b + q + 1, [&](int x, int y) { // 将询问排序
return k[x] < k[y];
});
minn[n + 1] = LLONG_MAX;
for (int i = n; i; i--)
minn[i] = min(minn[i + 1], d[a[i]]); // 求最优答案
for (int i = 1, j = 1; i <= q; i++) {
int u = b[i];
while (j <= n && val[a[j]] < k[u]) {
int v = a[j++];
kb[d[v] & 1] = max(kb[d[v] & 1], val[v] - (d[v] >> 1) * leaf); // kb[0] 就是原树上中心在点上，kb[1] 在边上
}
ans[u] = min({minn[j], (k[u] - kb[0] + leaf - 1) / leaf * 2, (k[u] - kb[1] + leaf - 1) / leaf * 2 + 1}); // kb[1] 需要向旁边的点移一步，(+ leaf - 1) / leaf 就相当于向上取整
}
for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
return 0;
}