Contest Notes

VP 2021 ICPC 上海

The 2021 ICPC Asia Shanghai Regional Contest
Date 2025/10/11
Solved 7/13

A B C D E F G H I J K L M
O O O O O Ø Ø

fa[root][0] = root

M - Harmony in Harmony

在神哈哈的国度，有 $n$ 个部落。春天时，哈哈把一块总面积为 1 的田地平均分成 $n$ 份，每块面积为 $\frac{1}{n}$。
秋天时，哈哈再次凭“记忆”把田地分成 $n$ 份（仍然每份面积相等），但划分方式不同。

每个部落只能收割到与自己春天播种区域重叠的部分。
他们希望知道：无论哈哈怎么划分，能保证每个部落至少能收割的最小面积是多少？

我们要输出这个最小保证值，精确到 9 位小数。

设：

  • 春天划分集合为 $S = {S_1, S_2, \ldots, S_n}$
  • 秋天划分集合为 $A = {A_1, A_2, \ldots, A_n}$

两者都是对单位面积的划分：

$$
|S_i| = |A_j| = \frac{1}{n}, \quad \forall i,j
$$

若部落 $i$ 被分配到秋天的地块 $A_{p_i}$，其能收获的面积是 $|S_i \cap A_{p_i}|$。

我们要计算：

$$
\min_{S,A} \max_{p} \min_{i} |S_i \cap A_{p_i}|
$$

定义一个完全二分图 $G = (U \cup V, E)$：

  • 左侧顶点集 $U = \lbrace S_1, \ldots, S_n \rbrace$
  • 右侧顶点集 $V = \lbrace A_1, \ldots, A_n \rbrace$
  • 边权：$w(i,j) = |S_i \cap A_j|$
  • $\sum_{j=1}^{n} w(i,j) = \frac{1}{n}, \quad \sum_{i=1}^{n} w(i,j) = \frac{1}{n}$

每种分配方案 $p$ 对应一个完美匹配。

我们希望保证每个部落的最小收获面积至少为 $x$。这意味着，我们要寻找一个排列 $p$，使得对所有的 $i$，都有 $|S_i \cap A_{p_i}| \ge x$。
这等价于在二分图中寻找一个完美匹配，其中我们只连接那些满足 $|S_i \cap A_j| \ge x$ 的顶点对 $(S_i, A_j)$。

根据 Hall 定理，这样一个完美匹配存在的充要条件是：对于左边顶点的任意一个子集 $I \subseteq \lbrace S_1, \ldots, S_n \rbrace$，其在图中的邻居集合 $N(I)$ 的大小满足 $|N(I)| \ge |I|$。

我们的目标是找到最大的 $x$，使得对于任意的划分方案 $S$ 和 $A$，上述二分图都满足霍尔条件，从而保证完美匹配的存在。

类似反证法，我们先假设对于某个给定的 $x$，霍尔条件不成立。

这意味着，存在某种划分方案 $S, A$ 和一个春季土地的子集 $I$（不妨设 $|I|=k$，其中 $1 \le k \le n$），使得 $I$ 中所有土地的邻居数量小于 $k$，即 $|N(I)| \le k-1$。

$N(I)$ 的定义是所有与 $I$ 中至少一个元素相连的秋季土地的集合。如果 $|N(I)| \le k-1$，那么我们可以找到一个大小为 $k-1$ 的秋季土地子集 $J$，使得 $N(I) \subseteq J$。

根据我们对边的定义，这意味着对于 $I$ 中的任意一块土地 $S_i$ ($i \in I$) 和 $J$ 之外的任意一块土地 $A_j$ ($j \notin J$)，它们之间的交集面积都小于 $x$，即：

$$|S_i \cap A_j| < x \quad \forall i \in I, \forall j \notin J$$

现在我们来计算这些交集面积的总和。一方面，由于 $|I| = k$ 且 $|J| = k-1$，所以 $J$ 之外的土地有 $n-(k-1)$ 块。因此，上述不等式共有 $k \cdot (n-k+1)$ 个。将它们全部相加，我们得到：

$$\sum_{i \in I} \sum_{j \notin J} |S_i \cap A_j| < k(n-k+1)x$$

另一方面，我们从面积关系上对这个总和给出一个下界。这个总和等于 $I$ 中所有土地的并集（记为 $U_I = \bigcup_{i \in I} S_i$）与 $J$ 外所有土地的并集（记为 $U_{J^c} = \bigcup_{j \notin J} A_j$）的交集面积：

$$\sum_{i \in I} \sum_{j \notin J} |S_i \cap A_j| = \left| \left(\bigcup_{i \in I} S_i\right) \cap \left(\bigcup_{j \notin J} A_j\right) \right| = |U_I \cap U_{J^c}|$$

我们知道 $|U_I| = \sum_{i \in I} |S_i| = k \cdot (1/n) = k/n$，

以及 $|U_{J^c}| = \sum_{j \notin J} |A_j| = (n-(k-1)) \cdot (1/n) = (n-k+1)/n$

根据集合面积的公式：$|U_I \cup U_{J^c}| = |U_I| + |U_{J^c}| - |U_I \cap U_{J^c}|$。

由于 $U_I \cup U_{J^c}$ 是整个土地的一部分，其面积不能超过总面积 1，即 $|U_I \cup U_{J^c}| \le 1$。

因此，我们可以得到 $|U_I \cap U_{J^c}|$ 的一个下界：

$$|U_I \cap U_{J^c}| \ge |U_I| + |U_{J^c}| - 1 = \frac{k}{n} + \frac{n-k+1}{n} - 1 = \frac{k+n-k+1-n}{n} = \frac{1}{n}$$

结合我们之前得到的两个关于总面积和的不等式，可以推出：

$$\frac{1}{n} < k(n-k+1)x$$

$$x > \frac{1}{n \cdot k(n-k+1)}$$

这个结论的含义是：如果对于某个 $k$ 值，霍尔条件被违反了，那么 $x$ 必须大于 $\frac{1}{nk(n-k+1)}$。

反过来说，如果我们选择的 $x$ 满足 $x \le \frac{1}{nk(n-k+1)}$，那么对于这个 $k$ 值，霍尔条件就不可能被违反。

$x$ 的最大值就是 $\frac{1}{nk(n-k+1)}$ 的最小值，即让分母 $f(k) = k(n - k + 1)$ 最大。

$$
f(k) = -k^2 + (n+1)k
$$

该函数在 $k = \frac{n+1}{2}$ 处取最大值：

$$
f_{\max} = \left\lfloor \frac{n+1}{2} \right\rfloor \cdot \left\lceil \frac{n+1}{2} \right\rceil
$$

最终答案为：

$$
\boxed{\text{Answer} = \frac{1}{n \cdot \left\lfloor \frac{n+1}{2} \right\rfloor \cdot \left\lceil \frac{n+1}{2} \right\rceil}}
$$

1
2
3
4
5
6
7
8
void solve() {
    int n = read();
    double t1 = floor((n + 1) / 2.0);
    double t2 = ceil((n + 1) / 2.0);
    double ans = 1.0 / (n * t1 * t2);
    cout << fixed << setprecision(9);
    cout << ans << '\n';
}

J - Two Binary Strings Problem

给定长度为 $n$ 的两个二进制字符串 $A=a_1a_2\dots a_n$ 和 $B=b_1b_2\dots b_n$。

定义一个整数 $k$ 为 lucky，如果对于所有 $1 \le i \le n$，都有：

$$
\text{众数}(\max(i-k+1,1), i) = b_i
$$

要求输出一个长度为 $n$ 的字符串 $C$，其中：

$$
C_k = 1 \iff k \text{ 是 lucky}
$$

输入有多组测试，总长度不超过 50000。

把 $0$ 设成 $-1$，$s$ 为前缀和数组

对于每个 $i$：
若 $b_i=1$，要求 $s[\max(i-k,0)]<s[i]$；
若 $b_i=0$，要求 $s[\max(i-k,0)]\ge s[i]$。

设 $t=i-k$。当 $k\le i$ 时，$t\ge0$；当 $k>i$ 时，$t=0$。问题转化为对每个 $i$，找出使条件成立的 $k=i-t$。

将所有下标 $0..n$ 按 $s[i]$ 降序排序。维护集合 vis，表示已访问的 $t$，即 $s[t]\ge s[i]$。遍历每个 $i$

实际实现时，通过右移将 $t=i-k$ 映射到第 $k$ 位。

若 $b_i=1$，执行

$$
ans \mathrel{|=} (vis \gg (n-i))
$$

若 $b_i=0$，执行

$$
ans \mathrel{|=} ((vis \oplus flip) \gg (n-i))
$$

其中 flip 是全 1 bitset，用于取补集。
之后将 $t=i$ 标记进 vis，即 vis[n-i]=1。

当 $k>i$ 时 $t=0$。若 $b_i=1$ 且 $s[i]\le0$，或 $b_i=0$ 且 $s[i]>0$，则所有 $k>i$ 都不合法。单独维护下这个合法位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
const int N = 5e4 + 5;

void solve() {
    int n = read();
    string a, b; cin >> a >> b;
    a = " " + a, b = " " + b;

    vector<int> s(n + 1);
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + (a[i] == '0' ? -1 : 1);
    }

    vector<int> p(n + 1);
    ranges::iota(p, 0);
    ranges::sort(p, [&](int i, int j) {
        if (s[i] == s[j]) return i < j;
        return s[i] > s[j];
    });

    bitset<N> bad, vis, mask;
    for (int i = 1; i <= n; i++) mask.set(i);

    int tg = n + 1;
    for (int i : p) {
        if (i) {
            if (b[i] == '1') {
                bad |= (vis >> (n - i));
                if (s[i] <= 0) tg = min(tg, i + 1);
            } else {
                bad |= ((vis ^ mask) >> (n - i));
                if (s[i] > 0) tg = min(tg, i + 1);
            }
        }
        vis[n - i] = 1;
    }

    for (int i = 1; i <= n; i++) {
        if (bad[i] or i >= tg) {
            cout << "0";
        } else {
            cout << "1";
        }
    }
    cout << '\n';
}

H - Life is a Game

一张带边权带点权无向图。从某点出发，有初始声望。

每第一次到达一个点将获得点权等值的声望加成。

经过一条边需要满足边权等值的最低声望限制。

多次给出起点和初始声望，询问能达到的最大声望。

按照边权从小到大建立 Kruskal 重构树。

每次询问都是从叶子出发，在树上倍增。

向上找到第一条不能通过的边（即，该边下面的子树的 叶子点权和 加上 初始声望 小于该边边权），

把下面子树的 叶子点权和 加上 初始声望 即为答案。

复杂度 $O((n + m) \log m + q \log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
struct DSU {
    std::vector<int> f, siz;
    DSU() {}
    DSU(int n) { init(n); }
    void init(int n) { f.resize(n), std::iota(f.begin(), f.end(), 0), siz.assign(n, 1); }
    int find(int x) { while (x != f[x]) x = f[x] = f[f[x]]; return x; }
    bool same(int x, int y) { return find(x) == find(y); }
    bool merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;
        siz[x] += siz[y], f[y] = x;
        return true;
    }
    int size(int x) { return siz[find(x)]; }
};

void solve() {
    int n = read();
    int m = read();
    int q = read();

    vector<int> a(n * 2 + 1);
    for (int i = 1; i <= n; i++) a[i] = read();
    
    vector<tuple<int, int, int>> edge(m);
    for (auto &[u, v, w] : edge) {
        u = read(), v = read(), w = read();
    }
    ranges::sort(edge, [&](auto i, auto j) {
        return get<2>(i) < get<2>(j);
    });

    int tot = n;
    DSU dsu(2 * n + 1);
    vector f(2 * n + 1, vector(25, 0ll));
    auto need = f;
    for (auto [u, v, w] : edge) {
        u = dsu.find(u);
        v = dsu.find(v);
        if (u == v) continue;

        tot++;
        a[tot] = a[u] + a[v];
        dsu.merge(tot, u), dsu.merge(tot, v);
        f[u][0] = f[v][0] = tot;
        need[u][0] = w - a[u];
        need[v][0] = w - a[v];
    }
    n = tot;
    f[n][0] = n;
    for (int j = 1; j <= 20; j++) {
        for (int i = 1; i <= n; i++) {
            f[i][j] = f[f[i][j - 1]][j - 1];
            need[i][j] = max(need[i][j - 1], need[f[i][j - 1]][j - 1]);
        }
    }

    while (q--) {
        int x = read(), k = read();
        for (int i = 20; i >= 0; i--) {
            if (need[x][i] <= k) x = f[x][i];
        }
        cout << k + a[x] << '\n';
    }
}

I - Steadily Growing Steam

把两组的差值作为状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
const int M = 3000;

void solve() {
    int n = read();
    int k = read();

    vector<pii> a(n);
    for (auto &[v, t] : a) {
        v = read(), t = read();
    }

    vector dp(M + 1000, vector(k + 1, -inf));
    dp[0][0] = 0;
    for (auto [v, t] : a) {
        auto ndp = dp;

        for (int w = 0; w <= M; w++) {
            for (int j = 0; j <= k; j++) {

                auto upd = [&](int nw, int nj) -> void {
                    nw = abs(nw);
                    ndp[w][j] = max(ndp[w][j], dp[nw][nj] + v);
                };

                upd(w - t, j);
                upd(w + t, j);
                if (j >= 1) upd(w - 2 * t, j - 1);
                if (j >= 1) upd(w + 2 * t, j - 1);
            }
        }

        dp = move(ndp);
    }

    int ans = 0;
    for (int j = 0; j <= k; j++) {
        ans = max(ans, dp[0][j]);
    }
    cout << ans << '\n';
}

G - Edge Groups

$n$ 个物品两两分组的方案数为 $f(n) = (n - 1) \times f(n - 2) = (n - 1)!!$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
void solve() {
    int n = read();

    vector<vector<int>> g(n + 1);
    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        g[u].eb(v), g[v].eb(u);
    }

    vector<int> siz(n + 1);
    vector<Z> dp(n + 1);

    vector<Z> fac(n + 1);
    fac[0] = 1, fac[1] = 1;
    for (int i = 2; i <= n; i++) fac[i] = fac[i - 2] * i;
    auto getFac = [&](int x) -> Z {
        return x < 0 ? 1 : fac[x];
    };


    [&](this auto&& dfs, int u, int fa) -> void {
        // debug(u);
        siz[u] = 1;
        Z prod = 1;
        int k = 0;
        for (int v : g[u]) {
            if (v == fa) continue;
            dfs(v, u);
            siz[u] += siz[v];
            prod *= dp[v];
            if (siz[v] & 1) k++;
        }
        if (k & 1) {
            dp[u] = getFac(k) * prod;
        } else {
            dp[u] = getFac(k - 1) * prod;
        }
        // debug(dp[u]);
    } (1, 0);

    cout << dp[1] << '\n';
}

D - Strange Fractions

令 $x = \frac{b}{a}$，解一元二次方程即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve() {
    int p = read(), q = read();

    int t = p * p - 4 * q * q;
    int x = sqrt(t);

    if (x * x != t) {
        cout << "0 0\n";
        return;
    }

    int a = p + x;
    int b = 2 * q;
    int g = gcd(a, b);
    a /= g, b /= g;

    cout << a << " " << b << '\n';
}

E - Strange Integers

排序以后从小到大贪心即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void solve() {
    int n = read(), k = read();

    vector<int> a(n);
    for (auto &x : a) x = read();

    ranges::sort(a);

    int las = -1;
    int ans = 1;
    for (int x : a) {
        if (las == -1) {
            las = x;
            continue;
        }
        if (x - las >= k) {
            las = x;
            ans++;
        }
    }
    cout << ans << '\n';
}

VP 2021 ICPC 上海

https://tosakaucw.github.io/vp-2021-icpc-上海/

Author

TosakaUCW

Posted on

2025-10-11

Updated on

2025-10-14

Licensed under

#

Comments

Catalogue

×