2025牛客暑期多校训练营1

同样也是 vp 的，大概情况是这样的

STATUS	COUNT
AC	4
赛后补	2

重现赛排名 166，这套比较难，简单的做完之后到后面集体罚坐了😴。

不得不说，出题人非常喜欢卡常，后来补的两道题都和卡常沾点边。

E. Endless Ladders#

又是我贡献了全场唯一的罚时，左边界第一个数被卡了，如果 d < 4 左边那一项就成负数了。

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
    int T;
7
    scanf("%d", &T);
8
    while (T--) {
9
        long long l, r;
10
        scanf("%lld%lld", &l, &r);
11
        long long d = abs(r * r - l * l);
12
        printf("%lld\n", max(0LL, d / 4 - 1) + (d + 1) / 2 - 1);
13

14
    }
15
    return 0;
16
}

G. Symmetry Intervals ^队友#

全场第二水的题。

H. Symmetry Intervals 2 ^补#

上一道题的升级版，传说比赛的时候常数小的暴力能卡过去，后来改了时间限制，我想到了预处理每个分段，但是没想到对齐的方法，题解看完之后就明白了，把两半的二进制状态用位运算分别拆出来再拼接就可以实现。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 100000;
6
const int b = 16;
7
unsigned short s[N];
8
bool t[N];
9
tuple<int, int, int> f[1 << b]; // lz, rz, ms
10

11
void println(unsigned short x) {
12
    for (int i = 0; i < b; ++i) cout << (x >> i & 1);
13
    cout << endl;
14
}
15

16
unsigned short get(int p, int l) {
17
    int id = p / b, pos = p % b;
18
    if (l <= b - pos) return s[id] >> pos;
19
    else {
20
        // println((((1 << (l - (b - pos))) - 1) & s[id + 1]) << (b - pos));
21
        return (s[id] >> pos) | (((1 << (l - (b - pos))) - 1) & s[id + 1]) << (b - pos);
22
    }
23
}
24

25
int main() {
26
    for (int mask = 0; mask < (1 << b); ++mask) {
27
        int lz = 0, rz = 0, ms = 0;
28
        int i, j;
29
        for (i = 0; i < b; ++i) {
30
            if (mask >> i & 1) break;
31
            else lz++;
32
        }
33
        for (j = 15; j >= 0; --j) {
34
            if (mask >> j & 1) break;
35
            else rz++;
36
        }
37
        if (lz == b) f[mask] = {b, 0, 0};
38
        else {
39
            int cur = 0;
40
            for (; i <= j; ++i) {
41
                if (mask >> i & 1) {
42
                    ms += (cur + 1) * cur / 2;
43
                    cur = 0;
44
                }
45
                else cur++;
46
            }
47
            f[mask] = {lz, rz, ms};
48
        }
49
    }
50
    int n, m, q;
51
    scanf("%d%d", &n, &q);
52
    m = (n + b - 1) / b;
53
    for (int i = 0; i < n; ++i) {
54
        int c;
55
        scanf("%1d", &c);
56
        s[i / b] |= c << (i % b);
57
    }
58
    while (q--) {
59
        int op;
60
        scanf("%d", &op);
61
        if (op == 1) {
62
            int l, r;
63
            scanf("%d%d", &l, &r);
64
            l--, r--;
65
            t[l / b] ^= 1, t[r / b] ^= 1;
66
            s[l / b] ^= (1 << (l % b)) - 1;
67
            s[r / b] ^= (1 << (r % b + 1)) - 1;
68
        }
69
        else {
70
            int l, x, y;
71
            scanf("%d%d%d", &l, &x, &y);
72
            x--, y--;
73
            bool flp = false;
74
            for (int i = 0; i < m; ++i) {
75
                flp ^= t[i];
76
                t[i] = false;
77
                if (flp) s[i] = ~s[i];
78
                // for (int j = 0; j < min(b, n - b * i); ++j) cout << (s[i] >> j & 1);
79
            }
80
            // cout << endl;
81
            long long res = 0, cur = 0;
82
            int lim = l / b * b;
83
            for (int i = 0; i < lim; i += b) {
84
                unsigned short b1 = get(x + i, b), b2 = get(y + i, b);
85
                // println(b1 ^ b2);
86
                auto [lz, rz, ms] = f[b1 ^ b2];
87
                if (lz == b) cur += b;
88
                else {
89
                    // cout << lz << ' ' << ms << ' ' << rz << endl;
90
                    cur += lz;
91
                    res += cur * (cur + 1) / 2 + ms;
92
                    cur = rz;
93
                }
94
            }
95
            if (l % b != 0) {
96
                unsigned short b1 = get(x + lim, l - lim), b2 = get(y + lim, l - lim);
97
                for (int i = 0; i < l - lim; ++i) {
98
                    if ((b1 >> i & 1) ^ (b2 >> i & 1)) {
99
                        res += cur * (cur + 1) / 2;
100
                        cur = 0;
101
                    }
102
                    else cur++;
103
                }
104
            }
105
            if (cur) res += cur * (cur + 1) / 2;
106
            printf("%lld\n", res);
107
        }
108
    }
109
    return 0;
110
}

I. Iron Bars Cutting ^补#

这道也很重量级，主要也是卡常，还卡空间， $\Theta (n^4)$ 比较好想，在 dp 的数组里排序再二分属实就有点不好想了，另外

1
>>> 420 ** 3 * 8 / 1024 ** 2
2
565.24658203125

按说开一个 420³ 的 long long 数组就该爆空间了，实际上开了两份也没爆，可能是没利用的空间被优化了吧……

提交记录里面给的内存占用只有 503932 KB.

1
#include <iostream>
2
#include <cmath>
3
#include <algorithm>
4
using namespace std;
5

6
typedef long long LL;
7
const int N = 421;
8
pair<LL, LL> f[N][N][N];
9
LL mn[N][N][N];
10
LL s[N];
11

12
int main() {
13
    int T;
14
    scanf("%d", &T);
15
    while (T--) {
16
        int n;
17
        scanf("%d", &n);
18
        for (int i = 1; i <= n; ++i) {
19
            scanf("%lld", &s[i]);
20
            s[i] += s[i - 1];
21
        }
22
        for (int len = 2; len <= n; ++len) {
23
            for (int i = 1; i <= n - len + 1; ++i) {
24
                int j = i + len - 1, t = (int)ceil(log2(s[j] - s[i - 1]));
25
                for (int k = i; k < j; ++k) {
26
                    LL b = abs((s[k] - s[i - 1]) - (s[j] - s[k]));
27
                    LL v1, v2;
28
                    int l = i - 1, r = k - 1;
29
                    if (l == r) v1 = 0;
30
                    else {
31
                        // cout << b << endl;
32
                        while (l < r) {
33
                            int mid = l + r + 1 >> 1;
34
                            if (f[i][k][mid].first <= b) l = mid;
35
                            else r = mid - 1;
36
                        }
37
                        if (l == i - 1) {
38
                            f[i][j][k] = {5000000000000, 5000000000000};
39
                            continue;
40
                        }
41
                        v1 = f[i][k][l].second;
42
                    }
43
                    l = k, r = j - 1;
44
                    if (l == r) {
45
                        v2 = 0;
46
                    }
47
                    else {
48
                        while (l < r) {
49
                            int mid = l + r + 1 >> 1;
50
                            if (f[k + 1][j][mid].first <= b) l = mid;
51
                            else r = mid - 1;
52
                        }
53
                        if (l == k) {
54
                            f[i][j][k] = {5000000000000, 5000000000000};
55
                            continue;
56
                        }
57
                        v2 = f[k + 1][j][l].second;
58
                    }
59

60
                    f[i][j][k] = {b, v1 + v2 + min(s[k] - s[i - 1], s[j] - s[k]) * t};
61
                }
62
                if (len != n) {
63
                    sort(f[i][j] + i, f[i][j] + j);
64
                    for (int k = i + 1; k < j; ++k) {
65
                        f[i][j][k].second = min(f[i][j][k].second, f[i][j][k - 1].second);
66
                    }
67
                }
68
            }
69
        }
70
        for (int i = 1; i < n; ++i) {
71
            printf("%lld ", f[1][n][i].second == 5000000000000 ? -1 : f[1][n][i].second);
72
        }
73
        printf("\n");
74
    }
75
    return 0;
76
}

K. Museum Acceptance ^队友#

按照他的条件，把边看成点只能是很多个环，稍微恶心一点的点在编号和去重

1
#include <iostream>
2
#include <vector>
3
#include <unordered_map>
4
#include <stack>
5
#include <algorithm>
6

7
using namespace std;
8

9
const int N = 200010;
10
unordered_map<long long, int> mp;
11
int ne[N * 3], res[N * 3];
12
bool vis[N * 3];
13
int h[N];
14

15
int main() {
16
    int n, m = 0;
17
    scanf("%d", &n);
18
    for (int i = 1; i <= n; ++i) {
19
        int q;
20
        scanf("%d", &q);
21
        vector<int> t(q);
22
        for (int j = 0; j < q; ++j) {
23
            scanf("%d", &t[j]);
24
            if (i < t[j]) {
25
                mp[(long long)i * N + t[j]] = m++;
26
                mp[(long long)t[j] * N + i] = m++;
27
            }
28
        }
29
        t.emplace_back(t[0]);
30
        for (int j = 0; j < q; ++j) {
31
            ne[mp[(long long)t[j] * N + i]] = (mp[(long long)i * N + t[j + 1]]);
32
        }
33
        h[i] = mp[(long long)i * N + t[0]];
34
    }
35
    for (int i = 1; i <= m; ++i) {
36
        if (!vis[i]) {
37
            int x = i;
38
            vector<int> cir;
39
            while (!vis[x]) {
40
                vis[x] = true;
41
                cir.emplace_back(x);
42
                x = ne[x];
43
            }
44
            sort(cir.begin(), cir.end());
45
            int t = 0;
46
            for (int j = 0; j < cir.size(); ++j) {
47
                if (j == cir.size() - 1 || (cir[j] ^ cir[j + 1]) != 1) t++;
48
            }
49
            for (int j : cir) {
50
                res[j] = t;
51
            }
52
        }
53
    }
54
    for (int i = 1; i <= n; ++i) {
55
        printf("%d\n", res[h[i]]);
56
    }
57
    return 0;
58
}

L. Numb Numbers ^队友#

离散化 + 权值线段树可以直接莽过去，~~然后我就又在补题的时候被边界卡了~~

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <map>
5
#include <cstring>
6

7
using namespace std;
8
typedef long long LL;
9
const int N = 200010;
10
LL a[N], b[N];
11
int tr[N * 8];
12
vector<pair<int, int>> qu;
13
vector<LL> values;
14
int m;
15

16
void clear_tree(int u, int l, int r) {
17
    tr[u] = 0;
18
    if (l == r) return;
19
    else {
20
        int mid = l + r >> 1;
21
        clear_tree(u << 1, l, mid), clear_tree(u << 1 | 1, mid + 1, r);
22
    }
23
}
24

25
void pushup(int u) {
26
    tr[u] = tr[u << 1] + tr[u << 1 | 1];
27
}
28

29
void modify(int u, int l, int r, int p, int v) {
30
    if (l == r) tr[u] += v;
31
    else {
32
        int mid = l + r >> 1;
33
        if (p <= mid) modify(u << 1, l, mid, p, v);
34
        else modify(u << 1 | 1, mid + 1, r, p, v);
35
        pushup(u);
36
    }
37
}
38

39
int query_kth(int u, int l, int r, int k) {
40
    if (l == r) return l;
41
    else {
42
        int mid = l + r >> 1;
43
        if (tr[u << 1] >= k) return query_kth(u << 1, l, mid, k);
44
        else return query_kth(u << 1 | 1, mid + 1, r, k - tr[u << 1]);
45
    }
46
}
47

48
int query_cnt(int u, int l, int r, int ql, int qr) {
49
    if (ql > qr) return 0;
50
    if (ql <= l && r <= qr) return tr[u];
51
    else {
52
        int mid = l + r >> 1;
53
        int res = 0;
54
        if (ql <= mid) res = query_cnt(u << 1, l, mid, ql, qr);
55
        if (qr > mid) res += query_cnt(u << 1 | 1, mid + 1, r, ql, qr);
56
        return res;
57
    }
58
}
59

60
void print(int u, int l, int r) {
61
    if (l == r) cout << tr[u] << ' ';
62
    else {
63
        int mid = l + r >> 1;
64
        print(u << 1, l, mid), print(u << 1 | 1, mid + 1, r);
65
    }
66
}
67

68
int get_idx(LL val) {
69
    return lower_bound(values.begin(), values.begin() + m, val) - values.begin() + 1;
70
}
71

72
int main() {
73
    int T;
74
    scanf("%d", &T);
75
    while (T--) {
76
        int n, q;
77
        scanf("%d%d", &n, &q);
78
        qu.resize(q);
79
        values.clear();
80
        for (int i = 1; i <= n; ++i) {
81
            scanf("%lld", &a[i]);
82
            b[i] = a[i]; // 备份一份
83
            values.emplace_back(a[i]);
84
        }
85
        for (int i = 0; i < q; ++i) {
86
            scanf("%d%d", &qu[i].first, &qu[i].second);
87
            a[qu[i].first] += qu[i].second;
88
            values.emplace_back(a[qu[i].first]);
89
        }
90
        sort(values.begin(), values.end());
91
        m = unique(values.begin(), values.end()) - values.begin();
92
        // memset(tr, 0, sizeof(int) * m * 4 + 1);
93
        clear_tree(1, 1, m);
94
        for (int i = 1; i <= n; ++i) {
95
            modify(1, 1, m, get_idx(b[i]), 1);
96
        }
97
        // print(1, 1, m);
98
        // cout << endl;
99
        int mid = (n + 1) >> 1;
100
        for (auto [i, k] : qu) {
101
            modify(1, 1, m, get_idx(b[i]), -1);
102
            b[i] += k;
103
            modify(1, 1, m, get_idx(b[i]), 1);
104
            int t = query_kth(1, 1, m, mid);
105
            int res = query_cnt(1, 1, m, 1, t);
106
            if (res > mid) res = query_cnt(1, 1, m, 1, t - 1);
107
            // print(1, 1, m);
108
            // cout << endl;
109
            printf("%d\n", res);
110
            // cout << endl;
111
        }
112
        // for (auto i : values) printf("%d ", i);
113
        // printf("\n");
114
        // cout << endl;
115
    }
116
    return 0;
117
}

Star's Blog

E. Endless Ladders#

G. Symmetry Intervals 队友#

H. Symmetry Intervals 2 补#

I. Iron Bars Cutting 补#

K. Museum Acceptance 队友#

L. Numb Numbers 队友#

G. Symmetry Intervals ^队友#

H. Symmetry Intervals 2 ^补#

I. Iron Bars Cutting ^补#

K. Museum Acceptance ^队友#

L. Numb Numbers ^队友#