2025春训第一场 - Star's Blog

考场上只做出来了 A、B、C、D，而且 C 和 D 做的很煎熬，E 是因为知识的缺失，F 那一条关键的性质不太好想。

A. 好的序列#

签到题，最长上升子序列变体，但是前置状态是固定的，直接开一个标记数组即可。

1
#include <iostream>
2
#include <cstring>
3

4
using namespace std;
5

6
int f[100010], a[100010];
7

8
int main() {
9
    memset(f, -1, sizeof(f));
10
    int n, res = 0;
11
    cin >> n;
12
    f[0] = 0;
13
    for (int i = 1; i <= n; ++i) {
14
        cin >> a[i];
15
        if (f[a[i] - 1] != -1) {
16
            f[a[i]] = f[a[i] - 1] + 1;
17
            res = max(res, f[a[i]]);
18
        }
19
    }
20
    cout << res << endl;
21
    return 0;
22
}

B. 一路向上#

对于每个点向比他高的点建边，拓扑排序找最长的路径即可。

1
#include <iostream>
2
#include <queue>
3

4
using namespace std;
5

6
const int N = 1000010;
7
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, 1, -1};
8
int ver[N * 4], head[N], ne[N * 4], deg[N], tot;
9
int a[N], f[N];
10

11
void add(int x, int y) {
12
    ver[++tot] = y;
13
    ne[tot] = head[x];
14
    head[x] = tot;
15
    deg[y]++;
16
}
17

18
int main() {
19
    int n, m;
20
    scanf("%d%d", &n, &m);
21
    for (int i = 1; i <= n; ++i) {
22
        for (int j = 1; j <= m; ++j) {
23
            scanf("%d", &a[(i - 1) * m + j]);
24
        }
25
    }
26
    for (int i = 1; i <= n; ++i) {
27
        for (int j = 1; j <= m; ++j) {
28
            for (int k = 0; k < 4; ++k) {
29
                int ti = i + dx[k], tj = j + dy[k];
30
                if (ti > 0 && ti <= n && tj > 0 && tj <= m && a[(i - 1) * m + j] < a[(ti - 1) * m + tj]) {
31
                    add((i - 1) * m + j, (ti - 1) * m + tj);
32
                }
33
            }
34
        }
35
    }
36
    queue<int> q;
37
    for (int i = 1; i <= n * m; ++i) {
38
        if (deg[i] == 0) {
39
            f[i] = 1;
40
            q.push(i);
41
        }
42
    }
43
    int res = 0;
44
    while (!q.empty()) {
45
        int x = q.front();
46
        q.pop();
47
        res = max(res, f[x]);
48
        for (int i = head[x]; i; i = ne[i]) {
49
            int y = ver[i];
50
            f[y] = max(f[y], f[x] + 1);
51
            if (--deg[y] == 0) q.push(y);
52
        }
53
    }
54
    printf("%d\n", res);
55
    return 0;
56
}

C. 神使#

每轮票只可能投到战力值最大的或者最小的，所以按照 $a_i$ 排序，不断比较头和尾的票数进行淘汰，直到剩下最后一个。

1
#include <iostream>
2
#include <algorithm>
3
#include <unordered_map>
4

5
using namespace std;
6

7
const int N = 1000010;
8
pair<int, int> a[N];
9

10
int main() {
11
    ios::sync_with_stdio(0);
12
    cin.tie(0), cout.tie(0);
13
    int n;
14
    cin >> n;
15
    for (int i = 1; i <= n; ++i) {
16
        cin >> a[i].first;
17
        a[i].second = i;
18
    }
19
    sort(a + 1, a + n + 1);
20
    int h = 1, t = n;
21
    while (h < t) {
22
        int m = a[h].first + a[t].first >> 1;
23
        int l = h, r = t;
24
        while (l < r) {
25
            int mid = l + r + 1 >> 1;
26
            if (a[mid].first <= m) l = mid;
27
            else r = mid - 1;
28
        }
29
        if (l - h + 1 >= t - l) t--;
30
        else h++;
31
    }
32
    cout << a[h].second << endl;
33
    return 0;
34
}

D. 遥远的她#

$(x_1,y_1)$ 和 $(x_2, y_2)$ 之间互相可达，当且仅当 $||x_1 - x_2| - |y_1 - y_2||\ \%\ 2 = 0$ .

把坐标系旋转 45˚（我这里是顺时针旋转的），把单位长度设置成 $\frac{\sqrt{2}}{2}$ ，每组内按其中一个分量排序，另一个分量用数状数组维护，最后除以2即可。

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

6
using namespace std;
7

8
const int N = 200010;
9

10
pair<long long, long long> f[2][N];
11
int len[2];
12
long long tr[N];
13
int cnt[N], m;
14

15
void add(int u, long long v) {
16
    for (; u <= m; u += u & -u) {
17
        tr[u] += v;
18
        cnt[u]++;
19
    }
20
}
21

22
int qcnt(int u) {
23
    int res = 0;
24
    for (; u; u -= u & -u) {
25
        res += cnt[u];
26
    }
27
    return res;
28
}
29

30
long long query(int u) {
31
    long long res = 0;
32
    for (; u; u -= u & -u) {
33
        res += tr[u];
34
    }
35
    return res;
36
}
37

38
int main() {
39
    int n;
40
    cin >> n;
41
    for (int i = 1; i <= n; ++i) {
42
        int x, y;
43
        cin >> x >> y;
44
        int t = (x & 1) ^ (y & 1);
45
        f[t][++len[t]] = {x, y};
46
    }
47
    long long s = 0;
48
    for (int t = 0; t < 2; ++t) {
49
        m = 0;
50
        memset(tr, 0, sizeof(tr));
51
        memset(cnt, 0, sizeof(cnt));
52
        map<int, int> mp;
53
        for (int i = 1; i <= len[t]; ++i) {
54
            f[t][i] = {f[t][i].first - f[t][i].second, f[t][i].first + f[t][i].second};
55
            mp[f[t][i].second];
56
        }
57
        sort(f[t] + 1, f[t] + 1 + len[t]);
58
        for (auto &i : mp) i.second = ++m;
59
        long long ps = 0;
60
        for (int i = 1; i <= len[t]; ++i) {
61
            int tt = qcnt(mp[f[t][i].second]);
62
            s += f[t][i].first * (i - 1) - ps + f[t][i].second * tt - query(mp[f[t][i].second]) * 2 - f[t][i].second * (i - tt - 1) + query(m);
63
            ps += f[t][i].first;
64
            add(mp[f[t][i].second], f[t][i].second);
65
        }
66
    }
67
    cout << s / 2 << endl;
68
    return 0;
69
}

E. spongebob#

这道题是后来补的，显然最后叠加出来的函数是单峰的，用三分求峰值即可。

需要注意：三分的 rps 应该比题目要求的小，因为最坏的情况有 3e5 个 1e6 倍的 x 叠加。

1
#include <iostream>
2
#include <cmath>
3

4
using namespace std;
5

6
const int N = 300010;
7
int a[N], b[N], n;
8

9
double sum(double x) {
10
    double res = 0;
11
    for (int i = 1; i <= n; ++i) {
12
        res += fabs(x * a[i] + (double)b[i]);
13
    }
14
    return res;
15
}
16

17
int main() {
18
    scanf("%d", &n);
19
    for (int i = 1; i <= n; ++i) {
20
        scanf("%d%d", &a[i], &b[i]);
21
    }
22
    double l = -1e6, r = 1e6;
23
    while (r - l > 1e-12) {
24
        double mid1 = (l * 2 + r) / 3, mid2 = (l + r * 2) / 3;
25
        if (sum(mid1) > sum(mid2)) l = mid1;
26
        else r = mid2;
27
    }
28
    printf("%lf\n", sum((l + r) / 2));
29
    return 0;
30
}

F. patrick#

每个 h 对应的答案可以用数状数组或者线段树在线维护，我这里用的数状数组。

考虑每个点和他左侧点的关系，初始化 $a_0 = a_{n + 1} = 0$ , 对于每个 $i \in [1, n]$ , 若 $a_i > a_{i - 1}$ ，此时会在 $h \in [a_{i - 1} + 1, a_i]$ 时额外产生一座岛，所以把区间内的答案 +1。
需要维护的操作：区间修改，单点查询（可以通过差分数组转化成单点修改，前缀和查询）。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 500010;
6
int tr[N], a[N];
7

8
void add(int u, int v) {
9
    for (; u <= 500000; u += u & -u) {
10
        tr[u] += v;
11
    }
12
}
13

14
int query(int u) {
15
    int res = 0;
16
    for (; u; u -= u & -u) {
17
        res += tr[u];
18
    }
19
    return res;
20
}
21

22
int main() {
23
    int n, q, last = 0;
24
    scanf("%d%d", &n, &q);
25
    for (int i = 1; i <= n; ++i) {
26
        scanf("%d", &a[i]);
27
        if (a[i] > a[i - 1]) add(a[i - 1] + 1, 1), add(a[i] + 1, -1);
28
    }
29
    while (q--) {
30
        char op[2];
31
        scanf("%s", op);
32
        if (op[0] == 'Q') {
33
            int c;
34
            scanf("%d", &c);
35
            c ^= last;
36
            printf("%d\n", last = query(c));
37
        }
38
        else {
39
            int p, v;
40
            scanf("%d%d", &p, &v);
41
            p ^= last, v ^= last;
42
            if (a[p] > a[p - 1]) add(a[p - 1] + 1, -1), add(a[p] + 1, 1);
43
            if (a[p + 1] > a[p]) add(a[p] + 1, -1), add(a[p + 1] + 1, 1);
44
            a[p] = v;
45
            if (a[p] > a[p - 1]) add(a[p - 1] + 1, 1), add(a[p] + 1, -1);
46
            if (a[p + 1] > a[p]) add(a[p] + 1, 1), add(a[p + 1] + 1, -1);
47
        }
48
    }
49
    return 0;
50
}