ICPC 2026 Nanchang Mirror A-D H J

link

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;
}
This article was updated on