T1
https://www.mxoj.net/problem/P110058?contestId=67
题意
\(n\) 个点，每个点高度为 \(a_i \in [1, m]\)。
你要找到一个 \(x\)，使得 \(a_i = a_{i - 1} + x \ \forall i \in (1,n]\)。
你可以修改一些 \(a_i\) 使他变成 \([1, m]\) 中的任意一个数。求最小操作次数。
\(n,m\leq 10^6\)。
Solution
考虑这个 \(x\) 之有 \(O(\frac{m}{n})\) 种，所以我们可以考虑如何 \(O(n)\) 算在 \(x\) 确定时的答案。
容易发现 \(a_i = (i - 1)x + h\)。所以我们只需要统计相同的 \(h\) 最多有几个即可。用数组实现。STL 常数有点大。
时间复杂度 \(O(n)\)。
Code
#include <bits/stdc++.h>using namespace std;const int N = 1e6 + 10, inf = 0x3f3f3f3f;int n, m, a[N], b[N];int main()
{cin.tie(0)->ios::sync_with_stdio(false);int _; cin >> _;while (_--) {cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i];int ans = n;for (int i = 0; i <= m / max(n - 1, 1) + 5; i++) {int c = 0;for (int j = 1; j <= n; j++) {if (a[j] >= (j - 1) * i + 1 && a[j] + (n - j) * i <= m) {b[a[j] - (j - 1) * i]++;c = max(c, b[a[j] - (j - 1) * i]);}}for (int j = 1; j <= n; j++) {if (a[j] >= (j - 1) * i && a[j] + (n - j) * i <= m) {b[a[j] - (j - 1) * i] = 0;}}ans = min(ans, n - c);}cout << ans << "\n";}return 0;
}
T2
https://www.mxoj.net/problem/P110059?contestId=67
题意
给你一张无向图，每条边上有一个隔板高 \(h_i\)。
每个点有一些雨水，当某个点雨水高度大于和他相连的边的隔板高度时，水会从多的地方流向少的地方。
设每个点最终的雨水量为 \(a_i\)，那么 \(a_i\) 是 \([1,H]\) 之间的整数。求有多少种 \(a\) 序列。对 \(998244353\) 取模。
\(n,m\leq 2\times 10^5,H\leq 10^9\)。
Solution
首先考虑如果一个隔板非常高，那么他可能是无用的。因为太高了，根本够不到他。
然后考虑如果水漫过了一个隔板，那么这两个点的水位只可能相等了。
也就是可以把他们看作一个点。所以这就很 Kruskal。
设最高的有用的隔板高为 \(p\)，那么答案肯定是由 \(< p\) 的部分 \(+ (p, H]\) 的部分拼成。
后面这部分是好算的，就是 \(H - p\)。前面这块考虑跑最小生成树的同时求出。
考虑设 \(ans_i\) 为第 \(i\) 个连通块 \(< mx_i\) 的答案，\(mx_i\) 就是这个连通块最高的隔板高度。
然后合并两个连通块的时候和最终求答案类似：
然后更新 \(mx\) 即可。
时间复杂度 \(O(n\log n)\)。
Code
#include <bits/stdc++.h>using namespace std;#define ll long longconst int N = 2e5 + 10, P = 998244353;int n, m, H, p[N];
ll mx[N], ans[N];struct node { int u, v, w; } e[N];int fifa(int x) { return p[x] == x ? x : p[x] = fifa(p[x]); }void merge(int x, int y, int w)
{x = fifa(x), y = fifa(y);if (x == y) return;p[x] = y;ans[y] = ((ans[x] + (w - mx[x])) % P * ((ans[y] + (w - mx[y]))) % P) % P;mx[y] = w;
}int main()
{cin.tie(0)->ios::sync_with_stdio(false);cin >> n >> m >> H;for (int i = 1; i <= m; i++) {int u, v, w; cin >> u >> v >> w;e[i] = { u, v, w };}for (int i = 1; i <= n; i++) ans[i] = 0, mx[i] = -1, p[i] = i;sort (e + 1, e + m + 1, [&](node x, node y) { return x.w < y.w; });for (int i = 1; i <= m; i++) {int u = e[i].u, v = e[i].v, w = e[i].w;merge(u, v, w);}cout << (ans[fifa(1)] + (H - mx[fifa(1)])) % P;return 0;
}
T3
https://www.mxoj.net/problem/P110060?contestId=67
题意
一共 \(2n\) 个点，每行 \(n\) 个共 \(2\) 行。每个点有颜色。
\((i, j)\) 表示左脚在 \(i\) 右脚在 \(j\) 上。
你一开始在 \((0, 0)\) 要走到 \((n + 1, n + 1)\)。你要保证两只脚所处的点的颜色相等。
你可以从 \((i,j)\) 选择 \((k,l),i<k,j<l\)。然后去到 \((k,l)\) 并花费 \((k - i)^2 + (l - j)^2\) 的代价。
求最小花费。
\(n\leq 3\times 10^3\)。
Solution
\(O(n^4)\) 暴力转移随便做。
然后考虑钦定每次只移动一个，可以先移动一个，然后移动另一个。
设 \(f_{i,j,0/1}\) 表示在 \((i,j)\)，现在该动哪只脚了。
转移就枚举这只脚去哪即可。\(O(n^3)\)。
然后转移是这样的：
\(f_{i,j,0} = \min f_{i,k,1} + (j - k)^2\)
\(f_{i,j,1} = \min f_{k,j,0} + (i-k)^2 \ (col_{i,0} = col_{j,1})\)
直接斜率优化转移即可。（但我不会）
Code
暴力
memset(f, 0x3f, sizeof f);
f[0][0][1] = 0;
for (int i = 0; i <= n + 1; ++i) {for (int j = 0; j <= n + 1; ++j) {// 计算 f[i][j][0]：最后动右脚，前序状态是右脚在k（k < j）// 中间状态，无需颜色相等for (int k = 0; k < j; ++k)f[i][j][0] = min(f[i][j][0], f[i][k][1] + (j - k) * (j - k));// 计算 f[i][j][1]：最后动左脚，前序状态是左脚在k（k < i）// 需满足颜色匹配条件a[i] == b[j]if (a[i] == b[j])for (int k = 0; k < i; ++k) f[i][j][1] = min(f[i][j][1], f[k][j][0] + (i - k) * (i - k));}
}
cout << f[n + 1][n + 1][1];
#include <bits/stdc++.h>
using namespace std;const int N = 3010;int n;
int f[N][N][2];
int a[N], b[N];
int q1[N], q2[N][N], l2[N], r2[N];int main() {freopen("stone.in", "r", stdin);freopen("stone.out", "w", stdout); scanf("%d", &n);for (int i = 0; i <= n + 1; i++) {scanf("%d", &a[i]);}for (int i = 0; i <= n + 1; i++) {scanf("%d", &b[i]);}memset(f, 10, sizeof(f));f[0][0][1] = 0;for (int i = 0; i <= n + 1; i++) {l2[i] = 1;}for (int i = 0; i <= n + 1; i++) {int l1 = 1, r1 = 0;for (int j = 0; j <= n + 1; j++) {// 优化f[i][j][0]的转移while (l1 < r1 && f[i][q1[l1 + 1]][1] + q1[l1 + 1] * q1[l1 + 1] - f[i][q1[l1]][1] - q1[l1] * q1[l1] <= 2 * j * (q1[l1 + 1] - q1[l1])) {l1++;}// 优化f[i][j][1]的转移while (l2[j] < r2[j] && f[q2[j][l2[j] + 1]][j][0] + q2[j][l2[j] + 1] * q2[j][l2[j] + 1] - f[q2[j][l2[j]]][j][0] - q2[j][l2[j]] * q2[j][l2[j]] <= 2 * i * (q2[j][l2[j] + 1] - q2[j][l2[j]])) {l2[j]++;}// 更新f[i][j][0]if (l1 <= r1) {f[i][j][0] = f[i][q1[l1]][1] + (j - q1[l1]) * (j - q1[l1]);}// 更新f[i][j][1]if (l2[j] <= r2[j] && a[i] == b[j]) {f[i][j][1] = f[q2[j][l2[j]]][j][0] + (i - q2[j][l2[j]]) * (i - q2[j][l2[j]]);}// 维护q2[j]队列if (f[i][j][0] < f[0][0][0]) {while (l2[j] < r2[j] && (f[i][j][0] + i * i - f[q2[j][r2[j] - 1]][j][0] - q2[j][r2[j] - 1] * q2[j][r2[j] - 1]) * (q2[j][r2[j]] - q2[j][r2[j] - 1]) <= (f[q2[j][r2[j]]][j][0] + q2[j][r2[j]] * q2[j][r2[j]] - f[q2[j][r2[j] - 1]][j][0] - q2[j][r2[j] - 1] * q2[j][r2[j] - 1]) * (i - q2[j][r2[j] - 1])) {r2[j]--;}q2[j][++r2[j]] = i;}// 维护q1队列if (f[i][j][1] < f[0][0][0]) {while (l1 < r1 && (f[i][j][1] + j * j - f[i][q1[r1 - 1]][1] - q1[r1 - 1] * q1[r1 - 1]) * (q1[r1] - q1[r1 - 1]) <= (f[i][q1[r1]][1] + q1[r1] * q1[r1] - f[i][q1[r1 - 1]][1] - q1[r1 - 1] * q1[r1 - 1]) * (j - q1[r1 - 1])) {r1--;}q1[++r1] = j;}}}printf("%d", f[n + 1][n + 1][1]);return 0;
}
T4
https://www.mxoj.net/problem/P110061?contestId=67
题意
有 \(n\) 个点，初始时第 \(i\) 个点为 \(i\)。
有 \(m\) 种操作形如：\(x,y\) 表示把颜色为 \(x\) 的点的颜色变为 \(y\)。
然后有 \(q\) 次查询，每次查询进行 \([l,r]\) 内的操作最终有多少极长连续段。
\(n,m,q \leq 5\times 10^5\)。
Solution
首先考虑固定 \(l\) 移动 \(r\)。
我们可以建图，直接连 \(x\to y\) 的边。但是如果有 \(1\to 2, 2 \to 1\) 就毁了。
考虑每次建立虚点 \(p\)，\(p \to x, p\to y\)，然后 \(p\) 的颜色和 \(y\) 一样。
这样当 \(r\) 移到最后的时候就建出来了一个森林。
考虑颜色段数量只需要知道相邻两个位置上的颜色是否一样。
对于 \(i, i + 1\) 他们首次变得一样的时刻是 \(lca\)。
用数据结构维护区间加减即可。
接下来考虑移动 \(l\)，这个我不会。
考虑在前面新建一个操作有什么影响。
其实只需要新建一个节点 \(p\) 作为 \(x,y\) 的父亲，然后 \(y\) 原本的父亲作为 \(p\) 的父
亲即可，可以发现只有 \(x\) 的祖先关系会更改，重构 \(x - 1, x, x + 1\) 之间的
贡献即可。
综上我们需要加叶子求 LCA 和树状数组，前者可以用倍增动态维护。
后面这部分还不会，先放个 std 吧。
Code
#include <bits/stdc++.h>
using namespace std;const int N = 2e6 + 7;inline int read() {int X = 0;bool flag = 1;char ch = getchar();while (ch < '0' || ch > '9') {if (ch == '-') flag = 0;ch = getchar();}while (ch >= '0' && ch <= '9') {X = (X << 1) + (X << 3) + ch - '0';ch = getchar();}if (flag) return X;return ~(X - 1);
}struct node {int id, l, r;
} q[N];bool cmp(node a, node b) {return a.l > b.l;
}int rot[N], dep[N];
int t, f[N][30];int LCA(int x, int y) {if (rot[x] != rot[y]) return 0;if (dep[x] < dep[y]) swap(x, y);for (int i = t; i >= 0; i--) {if (dep[f[x][i]] >= dep[y]) {x = f[x][i];}}if (x == y) return x;for (int i = t; i >= 0; i--) {if (f[x][i] != f[y][i]) {x = f[x][i];y = f[y][i];}}return f[x][0];
}int n, m, Q;
int x[N], y[N];
int tree[N];int lowbit(int x) {return x & (-x);
}void add(int x, int v) {for (int i = x; i <= m; i += lowbit(i)) {tree[i] += v;}
}int ask(int x) {int res = 0;for (int i = x; i; i -= lowbit(i)) {res = res + tree[i];}return res;
}void Extand(int i) {int p = i + n;dep[p] = dep[y[i]];dep[y[i]] = dep[x[i]] = dep[p] + 1;if (!f[y[i]][0]) {f[p][0] = p;} else {f[p][0] = f[y[i]][0];}f[y[i]][0] = f[x[i]][0] = p;for (int k = 1; k <= t; k++) {f[p][k] = f[f[p][k - 1]][k - 1];}for (int k = 1; k <= t; k++) {f[x[i]][k] = f[f[x[i]][k - 1]][k - 1];}for (int k = 1; k <= t; k++) {f[y[i]][k] = f[f[y[i]][k - 1]][k - 1];}rot[x[i]] = rot[y[i]];
}int ans[N];int main() {n = read();m = read();Q = read();t = log2(m);for (int i = 1; i <= m; i++) {x[i] = read();y[i] = read();}for (int i = 1; i <= Q; i++) {q[i].id = i;q[i].l = read();q[i].r = read();}sort(q + 1, q + Q + 1, cmp);for (int i = 1; i <= n; i++) {rot[i] = i;}int k = m + 1;add(1, n);for (int i = 1; i <= Q; i++) {while (k > q[i].l) {k--;if (x[k] == y[k]) continue;if (x[k] != 1) {int u = LCA(x[k], x[k] - 1);if (u) add(u - n, 1);}if (x[k] != n) {int u = LCA(x[k], x[k] + 1);if (u) add(u - n, 1);}Extand(k);if (x[k] != 1) {int u = LCA(x[k], x[k] - 1);if (u) add(u - n, -1);}if (x[k] != n) {int u = LCA(x[k], x[k] + 1);if (u) add(u - n, -1);}}ans[q[i].id] = ask(q[i].r);}for (int i = 1; i <= Q; i++) {printf("%d\n", ans[i]);}return 0;
}