2025年夏季个人训练赛第四场

A. 牛人#

随便按照一项标准排序，如果一个人排完序后他后面的人的另一项标准都不比他大他就是牛人。

需要注意的是如果排序的主键相等的人的副键是不需要比较的，会导致后缀最大值出一点问题，按主键正序副键逆序就可以解决这个问题，或者也可以用滑动窗口。

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

4
using namespace std;
5

6
const int N = 100010;
7
pair<long long, long long> a[N];
8
long long b[N];
9

10
int main() {
11
    int n;
12
    scanf("%d", &n);
13
    for (int i = 1; i <= n; ++i) scanf("%lld", &a[i].first);
14
    for (int i = 1; i <= n; ++i) scanf("%lld", &a[i].second);
15
    sort(a + 1, a + n + 1, [](pair<long long, long long> a, pair<long long, long long> b) {
16
        return a.first == b.first ? a.second >= b.second : a.first < b.first;
17
    });
18
    for (int i = n; i; --i) b[i] = max(b[i + 1], a[i].second);
19
    int res = 0;
20
    for (int i = 1; i <= n; ++i) {
21
        if (a[i].second == b[i]) res++;
22
    }
23
    printf("%d\n", res);
24
    return 0;
25
}

B. 斯诺克台球#

太阴间了，题目要求都说不清，看代码吧……

需要注意的地方是

两个人用的一个桌子和一套球，甲连续打完之后乙再连续打
打完最后一个红球之后仍然可以任选一个彩球打，不会移除这个彩球也不会触发犯规

1
#include <iostream>
2

3
using namespace std;
4

5
int aa[50], bb[50];
6

7
int main() {
8
    int n, m;
9
    int a = 0, b = 0, cnt = 15;
10
    scanf("%d%d", &n, &m);
11
    for (int i = 1; i <= n; ++i) {
12
        int t;
13
        scanf("%d", &t);
14
        aa[i] = t;
15
        if (i == n) {
16
            if (t == 0) b += 4;
17
            else if ((i & 1) && t != 1 && cnt > 0 || cnt <= 0 && i > 30 && i - 29 != t) b += max(4, t);
18
            else if (cnt > 0 && i % 2 == 0 && t == 1) b += 4;
19
            else a += t;
20
        }
21
        else {
22
            if (t == 1) cnt--;
23
            a += t;
24
        }
25
    }
26
    for (int i = 1; i <= m; ++i) {
27
        int t;
28
        scanf("%d", &t);
29
        bb[i] = t;
30
        if (i == m) {
31
            if (t == 0) a += 4;
32
            else if ((i & 1) && t != 1 && cnt > 0 || cnt <= 0 && i + n > 30 && i + n - 29 != t) a += max(4, t);
33
            else if (cnt > 0 && i % 2 == 0 && t == 1) b += 4;
34
            else b += t;
35
        }
36
        else {
37
            if (t == 1) cnt--;
38
            b += t;
39
        }
40
    }
41
    printf("%d %d\n", a, b);
42
    return 0;
43
}

C. 演出队列#

线性 dp，额外开一个状态记录是否已经删了一段，正常更新就可以。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 5010;
6
int f[N][2], a[N];
7

8
int main() {
9
    int n;
10
    scanf("%d", &n);
11
    for (int i = 1; i <= n; ++i) {
12
        scanf("%d", &a[i]);
13
    }
14
    int res = 0;
15
    for (int i = 1; i <= n; ++i) {
16
        for (int j = 0; j < 2; ++j) {
17
            if (a[i] > a[i - 1]) f[i][j] = f[i - 1][j] + 1;
18
            else f[i][j] = 1;
19
        }
20
        for (int j = 1; j < i; ++j) {
21
            if (a[i] > a[j]) f[i][1] = max(f[i][1], f[j][0] + 1);
22
        }
23
        res = max(res, f[i][1]);
24
    }
25
    printf("%d\n", res);
26
    return 0;
27
}

D. 利比亚行动#

我看到这道题的时候我知道怎么写，但是被前面恶心的不行了……放弃了写的欲望。

大概思路是分层图 dijkstra，一个点拆成 maxc 个点跑 dijkstra 就能跑出来。

E. 抓鱼#

经典的贪心问题，一直抓效率最高的就行。

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

4
using namespace std;
5

6
typedef long long LL;
7
const int N = 100010;
8

9
pair<LL, LL> a[N];
10

11
bool cmp(pair<LL, LL> a, pair<LL, LL> b) {
12
    return a.second < b.second;
13
}
14

15
int main() {
16
    int n;
17
    LL t, res = 0;
18
    scanf("%d%lld", &n, &t);
19
    for (int i = 1; i <= n; ++i) {
20
        scanf("%lld", &a[i].first);
21
    }
22
    for (int i = 1; i <= n; ++i) {
23
        scanf("%lld", &a[i].second);
24
    }
25
    sort(a + 1, a + n + 1, cmp);
26
    for (int i = 1; i <= n; ++i) {
27
        if (t >= a[i].first * a[i].second) {
28
            res += a[i].first;
29
            t -= a[i].first * a[i].second;
30
        }
31
        else {
32
            res += t / a[i].second;
33
            break;
34
        }
35
    }
36
    printf("%lld\n", res);
37
    return 0;
38
}

F. PACM Team#

背包问题求方案，多开一个数组记录选择即可。

难点是维度太多了，稍不留神就写挂了。

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

4
using namespace std;
5

6
const int N = 37;
7
// 按理说可以把第一维压掉，但是我一直写挂，最后加回来了……
8
int f[2][N][N][N][N];
9
bool p[N][N][N][N][N];
10
int a[N][4], g[N];
11

12
int main() {
13
    int n, b[4];
14
    scanf("%d", &n);
15
    for (int i = 1; i <= n; ++i) {
16
        scanf("%d%d%d%d%d", &a[i][0], &a[i][1], &a[i][2], &a[i][3], &g[i]);
17
    }
18
    scanf("%d%d%d%d", &b[0], &b[1], &b[2], &b[3]);
19
    for (int i = 1; i <= n; ++i) {
20
        int t = i & 1;
21
        for (int j = b[0]; j >= 0; --j) {
22
            for (int k = b[1]; k >= 0; --k) {
23
                for (int l = b[2]; l >= 0; --l) {
24
                    for (int m = b[3]; m >= 0; --m) {
25
                        if (j >= a[i][0] && k >= a[i][1] && l >= a[i][2] && m >= a[i][3] && f[t ^ 1][j][k][l][m] < f[t ^ 1][j - a[i][0]][k - a[i][1]][l - a[i][2]][m - a[i][3]] + g[i]) {
26
                            p[i][j][k][l][m] = true;
27
                            f[t][j][k][l][m] = f[t ^ 1][j - a[i][0]][k - a[i][1]][l - a[i][2]][m - a[i][3]] + g[i];
28
                        }
29
                        else f[t][j][k][l][m] = f[t ^ 1][j][k][l][m];
30
                    }
31
                }
32
            }
33
        }
34
    }
35
    stack<int> res;
36
    int j = b[0], k = b[1], l = b[2], m = b[3];
37
    for (int i = n; i; --i) {
38
        if (p[i][j][k][l][m]) {
39
            res.push(i);
40
            j -= a[i][0], k -= a[i][1], l -= a[i][2], m -= a[i][3];
41
        }
42
    }
43
    printf("%ld\n", res.size());
44
    while (!res.empty()) {
45
        printf("%d ", res.top() - 1);
46
        res.pop();
47
    }
48
    printf("\n");
49
    return 0;
50
}

Star's Blog