ICPC 2026 Nanchang Mirror A-D H J
A
没什么好说的,签到题。
B
待补
C
赛时想半天没想出来,@free_fail 大手子倍增 dp 过了 唉,菜就还得多练 用 $f_{i, j, len}$ 表示从 $i$ 到 $j$ 能够 $2^k$ 步所需要的最小天数,则有转移:
$$ f_{i, j, len} = \min\limits_{i = 1}^n {f_{i, j, len}, max(f_{i, k, len - 1}, f_{k, j, len - 1})} $$
后面那个式子要取 max,因为要保证两部分都能达到 $2^{len - 1}$ 步数。转移的时候枚举顺序类似 Floyd 最短路,先 k 然后 i 和 j 的顺序。 然后对于询问,由于 w 是定死的,对 w 二进制拆分,然后预处理答案,直接输出即可。 赛时实测把 len 那一维放在最低位会 T,大概是因为内存访问不连续。后面进行了缓存优化,把 len 放到最高位就过了。 赛后重新写了一版代码。
J
@free_fail 提出可以 $O(n \sqrt n)$ 建图,具体是:
。。。待补
本来我以为建完图跑最小生成树,然后树剖就可以了。但是这样的时间复杂度是 $O(n \log^2 n)$ 的。题目中数据范围 n 最大是 $10^6$,又因为树剖天生的大常数,所以 T 了。贴一下 4.1K 的超长代码(~~有纪念意义的一集)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
char buf[1 << 20], *p1 = buf, *p2 = buf, obuf[1 << 20], *p3 = obuf;
#define getc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
#define putc(x) (p3 - obuf < (1 << 20) ? (*p3++ = x) : (fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf, *p3++=x))
inline ll read() {
ll x = 0, sgn = 0; char s = getc();
while(!isdigit(s)) sgn |= s == '-', s = getc();
while(isdigit(s)) x = x * 10 + s - '0', s = getc();
return sgn ? -x : x;
}
template<typename T> inline void read(T& x) { x = read(); }
template<typename T, typename... Args> inline void read(T& x, Args&... args) { read(x), read(args...); }
template<typename T> inline void print(T x) { if (x < 0) x = -x, putc('-'); if (x >= 10) print(x / 10); putc(x % 10 + '0'); }
template<typename T, typename... Args> inline void print(char c, T x, Args... args) { print(x), putc(c), print(args...); }
constexpr int N = 1e6 + 7;
struct edge {
int to, ne, w;
} e[N << 1];
int n, q, a[N];
int val[N], to[N], ne[N], fa[N];
int get(int x) { return x == fa[x] ? x : fa[x] = get(fa[x]); }
int cnt, head[N];
void add(int x, int y, int w) {
e[++cnt] = {y, head[x], w}, head[x] = cnt;
}
int b[N], dep[N], f[N], son[N], sz[N];
void dfs1(int x, int fa) {
dep[x] = dep[f[x] = fa] + (sz[x] = 1);
for (int i = head[x]; i; i = e[i].ne) {
int tn = e[i].to, w = e[i].w;
if (tn == fa) continue;
b[tn] = w;
dfs1(tn, x);
sz[x] += sz[tn];
if (sz[tn] > sz[son[x]]) son[x] = tn;
}
}
int top[N], loc[N], id[N], tot;
void dfs2(int x, int fa) {
top[x] = fa, id[loc[x] = ++tot] = x;
if (!son[x]) return;
dfs2(son[x], fa);
for (int i = head[x]; i; i = e[i].ne) {
int tn = e[i].to;
if (tn == f[x] || tn == son[x]) continue;
dfs2(tn, tn);
}
}
int mx[N << 2];
void build(int p, int l, int r) {
if (l == r) {
mx[p] = b[id[l]];
return;
}
int mid = l + r >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
mx[p] = min(mx[p << 1], mx[p << 1 | 1]);
}
void modify(int p, int l, int r, int x, int v) {
if (l == r) {
mx[p] = v;
return;
}
int mid = l + r >> 1;
if (x <= mid) modify(p << 1, l, mid, x, v);
else modify(p << 1 | 1, mid + 1, r, x, v);
mx[p] = min(mx[p << 1], mx[p << 1 | 1]);
}
int query(int p, int l, int r, int L, int R) {
if (L <= l && R >= r) return mx[p];
int mid = l + r >> 1, res = 1e9;
if (L <= mid) res = min(res, query(p << 1, l, mid, L, R));
if (R > mid) res = min(res, query(p << 1 | 1, mid + 1, r, L, R));
return res;
}
int qmin(int x, int y) {
if (!(x ^ y)) return 0;
int res = 1e9;
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
res = min(res, query(1, 1, tot, loc[top[x]], loc[x]));
x = f[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
res = min(res, query(1, 1, tot, loc[x] + 1, loc[y]));
return res;
}
int main() {
read(n, q);
for (int i = 1; i <= n; ++i) read(a[i]);
int mx = 1;
for (int i = 1; i <= n; ++i) {
mx = max(mx, a[i]);
ne[i] = to[a[i]];
to[a[i]] = i;
}
for (int i = 1; i <= n; ++i) fa[i] = i;
for (int x = mx; x >= 1; --x) {
int s = 0, t = 0;
for (int j = x, num = 1; j <= mx && num <= n - 1; j += x) {
for (int i = to[j]; i; i = ne[i]) {
if (!s) {
s = i, t = get(i);
continue;
}
int fi = get(i);
if (fi != t) {
fa[fi] = t;
add(s, i, x);
add(i, s, x);
++num;
}
}
}
}
dfs1(1, 0);
dfs2(1, 1);
build(1, 1, tot);
while (q--) {
int x, y;
read(x, y);
if (x == y) {
print(a[x]);
} else {
print(qmin(x, y));
}
putc('\n');
}
fwrite(obuf, p3 - obuf, 1, stdout);
return 0;
}
问完 AI 之后得到正解是 Kruskal 重构树的神秘科技。而且,好像这个科技还能解决一系列瓶颈路的问题,看来得学习一下了,把这道题的解析放到 Kruskal 重构树的学习笔记里面吧(挖坑待填)。
最后还是贴一下正解代码(3.1K)。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
char buf[1 << 20], *p1 = buf, *p2 = buf, obuf[1 << 20], *p3 = obuf;
#define getc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
#define putc(x) (p3 - obuf < (1 << 20) ? (*p3++ = x) : (fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf, *p3++=x))
inline ll read() {
ll x = 0, sgn = 0; char s = getc();
while(!isdigit(s)) sgn |= s == '-', s = getc();
while(isdigit(s)) x = x * 10 + s - '0', s = getc();
return sgn ? -x : x;
}
template<typename T> inline void read(T& x) { x = read(); }
template<typename T, typename... Args> inline void read(T& x, Args&... args) { read(x), read(args...); }
template<typename T> inline void print(T x) { if (x < 0) x = -x, putc('-'); if (x >= 10) print(x / 10); putc(x % 10 + '0'); }
template<typename T, typename... Args> inline void print(char c, T x, Args... args) { print(x), putc(c), print(args...); }
constexpr int N = 1e6 + 7;
struct edge {
int to, ne, id;
} e[N << 1];
int n, q, a[N];
int val[N], to[N], ne[N], fa[N << 1];
int get(int x) { while (fa[x] != x) fa[x] = fa[fa[x]], x = fa[x]; return x; }
int cnt, head[N << 1];
void add(int x, int y, int id) {
e[++cnt] = {y, head[x], id}, head[x] = cnt;
}
int qx[N], qy[N], ans[N];
int tot, w[N << 1], ch1[N << 1], ch2[N << 1], par[N << 1];
int top, stk[N << 2], v[N << 1];
int main() {
read(n, q);
int mx = 1;
for (int i = 1; i <= n; ++i) {
read(a[i]);
mx = max(mx, a[i]);
ne[i] = to[a[i]];
to[a[i]] = i;
}
for (int i = 1; i <= q; ++i) {
read(qx[i], qy[i]);
if (qx[i] == qy[i]) { ans[i] = a[qx[i]]; continue; }
add(qx[i], qy[i], i), add(qy[i], qx[i], i);
}
for (int i = 1; i <= n; ++i) fa[i] = i;
tot = n;
int num = n - 1;
for (int x = mx; x >= 1 && num; --x) {
int rt = 0;
for (int j = x; j <= mx && num; j += x) {
for (int i = to[j]; i; i = ne[i]) {
if (!rt) {
rt = get(i);
continue;
}
int ru = get(i);
if (ru == rt) continue;
int t = ++tot;
fa[t] = t;
w[t] = x, ch1[t] = rt, ch2[t] = ru, par[rt] = par[ru] = t;
fa[rt] = fa[ru] = t;
rt = t;
if (!--num) break;
}
}
}
int rt = tot;
for (int i = 1; i <= tot; ++i) fa[i] = i;
stk[++top] = rt;
while (top) {
int x = stk[top--];
if (x < 0) {
x = -x;
v[x] = 1;
for (int i = head[x]; i; i = e[i].ne) {
int id = e[i].id, tn = e[i].to;
if (v[tn]) ans[id] = w[get(tn)];
}
if (par[x]) fa[get(x)] = par[x];
continue;
}
stk[++top] = -x;
if (ch1[x]) stk[++top] = ch1[x];
if (ch2[x]) stk[++top] = ch2[x];
}
for (int i = 1; i <= q; ++i) print(ans[i]), putc('\n');
fwrite(obuf, p3 - obuf, 1, stdout);
return 0;
}