Contest Notes

VP 2025 ICPC 浙江省赛

The 2025 ICPC China Zhejiang Province Programming Contest (22nd)
The 3rd Universal Cup. Stage 36: Wulin
「睿琪杯」浙江省第 22 届大学生程序设计竞赛
Date 2025/10/22
Upsolved 7/13

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

A. Outer LIS

给定一个长度为 n 的二元组序列，每个元素为 $(a_i, w_i)$。
$q$ 次查询，每次查询给出一个区间 $[l,r]$，问该区间的元素一个都不选的情况下的带权 LIS。

$n \le 10^5$
$q \le 10^5$
$1 \le a_i \le n$

预处理 $f_i, g_i$ 分别表示 $i$ 结尾 / 开头 的 LIS 长度

那么对于一个区间 $[l, r]$ 的答案，可能是：

  • $\max_{i \in [1, l)} f_i$
  • $\max_{i \in (r, n]} g_i$
  • $\max_{i \in [1, l), j \in (r, n]} f_i + g_j$

前两个很好得到，考虑第三个怎么维护

把序列分成 $m = O(\sqrt n)$ 块

预处理出 $pre_{i, j}$ 表示 $[1, i]$ 块中 $a$ 至大为 $j$ 的 $f$，$suf$ 类似

用 $pre$ 和 $suf$ $O(n \sqrt n)$ 预处理出 $ans_{i, j}$ 表示第 $[1, i]$ 块和 $[j, m]$ 块中的最优匹配，即 $\max_{k} pre_{i, k} + suf_{j, k}$

那么对于询问的话就很简单处理了，两个零散块元素的组合可以排序然后双指针算

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
#define int i64
#define pb push_back
#define ep emplace
#define eb emplace_back
using namespace std;
int read(int x = 0, int f = 0, char ch = getchar()) {
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while (48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for (auto x : a) cout << x << " "; cout << "\n";
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; i++) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; i++) cerr << *i << " "; cerr << '\n'; }
#define fi first
#define se second
template<class T> bool cmin(T &a, T b) { return (b < a) ? (a = b, true) : false; }
template<class T> bool cmax(T &a, T b) { return (a < b) ? (a = b, true) : false; }
using pii = pair<int, int>;
using tup = tuple<int, int, int>;
const int inf = 1e18;

template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;
    Fenwick(int n_ = 0) { init(n_); }
    void init(int n_) { n = n_; a.assign(n, T {}); }
    void set(int x, const T &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = max(a[i - 1], v);
        }
    }
    T qry(int x) {
        T ans {};
        for (int i = x; i > 0; i -= i & -i) {
            ans = max(ans, a[i - 1]);
        }
        return ans;
    }
};

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

    vector<int> a(n + 1), w(n + 1);
    for (int i = 1; i <= n; i++) {
        a[i] = read(), w[i] = read();
    }

    int m;
    vector<int> rk(n + 1);
    {
        vector v(a.begin() + 1, a.end());
        ranges::sort(v);
        v.erase(unique(v.begin(), v.end()), v.end());
        m = v.size();
        for (int i = 1; i <= n; i++) {
            rk[i] = ranges::lower_bound(v, a[i]) - v.begin() + 1;
        }    
    }
    // debug(rk);

    vector<int> f(n + 1);
    {
        Fenwick<int> bit(m + 1);
        for (int i = 1; i <= n; i++) {
            int r = rk[i];
            int res = bit.qry(r + 1);
            if (res == -inf) res = 0;
            f[i] = res + w[i];
            bit.set(r, f[i]);
        }
    }
    vector<int> g(n + 1);
    {
        Fenwick<int> bit(m + 1);
        for (int i = n; i >= 1; i--) {
            int r = m - rk[i] + 1;
            int res = bit.qry(r + 1);
            if (res == -inf) res = 0;
            g[i] = res + w[i];
            bit.set(r, g[i]);
        }
    }
    // debug(f);
    // debug(g);

    int N = n + 5;
    int B = sqrt(n) + 5;
    int M = n / B + 5;
    vector pre(M, vector(N, 0ll));
    vector suf(M, vector(N, 0ll));
    vector ans(M, vector(M, 0ll));
    auto blk = [&](int x) { return (x - 1) / B + 1; };
    auto lb = [&](int x) { return (x - 1) * B + 1; };
    auto rb = [&](int x) { return min(n, x * B); };

    int cntb = blk(n);
    for (int x = 1; x <= cntb; x++) {
        for (int i = 1; i <= rb(x); i++) {
            cmax(pre[x][a[i]], f[i]);
        }
        for (int i = lb(x); i <= n; i++) {
            cmax(suf[x][a[i]], g[i]);
        }
        for (int i = 2; i <= n; i++) {
            cmax(pre[x][i], pre[x][i - 1]);
        }
        for (int i = n - 1; i >= 1; i--) {
            cmax(suf[x][i], suf[x][i + 1]);
        }
    }

    for (int i = 0; i <= cntb; i++) {
        int res = pre[i][n];
        for (int j = cntb + 1; j >= i + 1; j--) {
            for (int k = lb(j); k <= rb(j); k++) {
                cmax(res, pre[i][a[k]] + g[k]);
            }
            ans[i][j] = res;
        }
    }

    while (q--) {
        int l = read(), r = read();
        int x = blk(l), y = blk(r);
        int res = ans[x - 1][y + 1];

        for (int i = lb(x); i < l; i++) {
            cmax(res, f[i] + suf[y + 1][a[i]]);
        }
        for (int i = r + 1; i <= rb(y); i++) {
            cmax(res, pre[x - 1][a[i]] + g[i]);
        }

        if (lb(x) < l and r < rb(y)) {
            vector<pii> v;
            for (int i = r + 1; i <= rb(y); i++) {
                v.eb(a[i], g[i]);
            }
            ranges::sort(v);
            for (int i = v.size() - 2; i >= 0; i--) {
                v[i].se = max(v[i].se, v[i + 1].se);
            }

            for (int i = lb(x); i <= l - 1; i++) {
                auto it = ranges::lower_bound(v, pii(a[i], 0));
                if (it == v.end()) continue;
                cmax(res, f[i] + it->se);
            }   
        }

        cout << res << '\n';
    }
}

signed main() {
    // for (int T = read(); T--; solve());
    solve();
    return 0;
}

F. Challenge NPC III

对每种颜色跑，同时维护最短路和次短路

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
void solve() {
    int n = read(), m = read(), k = read();

    vector<int> c(n + 1);
    for (int i = 1; i <= n; i++) c[i] = read();

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

    auto bfs = [&](int col) -> bool {
        queue<tup> q;
        vector vis(n + 1, vector(2, 0));

        for (int i = 1; i <= n; i++) {
            if (c[i] != col) continue;
            q.ep(i, 0, i);
            vis[i][0] = 1;
        }

        while (!q.empty()) {
            auto [u, d, s] = q.front(); q.pop();

            if (d >= k - 1) continue;
            for (auto v : g[u]) {
                if (c[v] == col and v != s) return 0;

                if (!vis[v][0]) {
                    vis[v][0] = s;
                    q.ep(v, d + 1, s);
                } else if (!vis[v][1] and vis[v][0] != s) {
                    vis[v][1] = s;
                    q.ep(v, d + 1, s);
                }
            }
        }
        return 1;
    };

    for (int i = 1; i <= 50; i++) {
        if (!bfs(i)) { cout << "NO\n"; return; }
    }
    cout << "YES\n";
}

G. Tariff-ied

越加倍率越小，二分倍率阈值

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
void solve() {
    int n = read();
    int k = read();

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

    auto judge = [&](double lim) -> int {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            t[i] = max(0LL, (int)floor(lim - 100.0 / a[i]));
            cnt += t[i];
        }
        return cnt;
    };

    double res = 0;
    for (double L = 0, R = 1e6; R - L >= 1e-7; ) {
        double mid = (L + R) / 2;
        if (judge(mid) <= k) {
            res = mid, L = mid + 1;  
        } else { 
            R = mid - 1; 
        }
    }

    for (int x = judge(res); x < k; x++) {
        auto calc = [&](int i) -> double {
            return (100.0 + a[i] * (t[i] + 1)) / (100.0 + a[i] * t[i]);
        };
        int id = 0;
        for (int i = 1; i < n; i++) {
            if (calc(i) > calc(id)) id = i;
        }
        t[id]++;
    }

    double ans = 1;
    for (int i = 0; i < n; i++) {
        ans *= (1.0 + 1.0 * (a[i] * t[i]) / 100.0);
    }

    cout << fixed << setprecision(8);
    cout << ans << '\n';
}

D. Too Clever by Half

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
void solve() {
    int n = read();

    vector<int> c(n + 1);
    for (int &x : c) x = read();

    string ans;
    for (int i = 1; i <= n; i++) {
        ans += 'R';
        c[i]--;

        while (c[i - 1] > 1) {
            ans += 'L';
            ans += 'R';
            c[i - 1]--, c[i]--;
        }

        if (i < n and c[i] < 1) {
            cout << "Impossible\n";
            return;
        }
    }    

    if (c[n]) {
        cout << "Impossible\n";
        return;
    }
    ans += string(n, 'L');
    cout << ans << '\n';
}

L. Nailoongs Always Lie

n 个点 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
void solve() {
    int n = read();
    vector<int> a(n + 1), ind(n + 1);
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        ind[a[i]]++;
    }

    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (!ind[i]) q.ep(i);
    }

    vector<int> vis(n + 1);

    int ans = 0;
    while (!q.empty()) {
        int x = q.front(); q.pop();
        ans++;
        vis[x] = 1;
        int y = a[x];

        if (!vis[y]) {
            vis[y] = 1;
            ind[a[y]]--;
            if (!ind[a[y]]) {
                q.ep(a[y]);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;
        
        int len = 0;
        for (int j = i; !vis[j]; j = a[j]) {
            len++, vis[j] = 1;
        }
        ans += len / 2;
    }

    cout << ans << '\n';
}

B. Turn on the Light 3

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

    vector<int> vis(n + 1);
    for (int i = 0; i < m; i++) {
        int x = read();
        if (vis[x]) {
            cout << "the lights are already on!\n";
            continue;
        }

        int ans = 0;
        for (int t = x; t <= n; t += x) {
            if (!vis[t]) ans++;
            vis[t] = 1;
        }
        cout << ans << '\n';
    }
}

I. Version Number

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
void solve() {
    string s, t;
    cin >> s >> t;

    int a[4] {};
    int b[4] {};

    int id = 0;
    for (auto ch : s) {
        if (ch == '.') id++;
        else a[id] = a[id] * 10 + ch - 48;
    }
    id = 0;
    for (auto ch : t) {
        if (ch == '.') id++;
        else b[id] = b[id] * 10 + ch - 48;
    }

    int f = 0;
    for (int i = 0; i < 4; i++) {
        if (a[i] > b[i]) { f = 1; break; }
        else if (a[i] < b[i]) { f = -1; break; }
    }

    if (f == 1) cout << "A\n";
    if (f == -1) cout << "B\n";
    if (f == 0) cout << "Equal\n";
}

VP 2025 ICPC 浙江省赛

https://tosakaucw.github.io/vp-2025-icpc-浙江省赛/

Author

TosakaUCW

Posted on

2025-10-23

Updated on

2025-11-03

Licensed under

#

Comments

Catalogue

×