2023年中国高校计算机大赛-团队程序设计天梯赛（GPLT）上海理工大学校内选拔赛

A. A Xor B Problem

思路

记录每个数出现的次数，结果为每个数出现的次数的平方和

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;

void solve()
{
    int n;
    cin >> n;
    vector<int> cnt(N);
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        cnt[x]++;
    }

    ll ans = 0;
    for (int i = 0; i < N; i++)
        ans += 1LL * cnt[i] * cnt[i];
    cout << ans;
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

B. 吃苹果

思路

将每天按晚上吃和白天吃的愉悦值之差进行排序，选前 \(k\) 个晚上吃，其他的白天吃

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
    int n, k;
    cin >> n >> k;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i].first >> a[i].second;

    sort(a.begin(), a.end(), [](pair<int, int> &x, pair<int, int> &y)
         { return x.second - x.first > y.second - y.first; });

    ll ans = 0;
    for (int i = 0; i < n; i++)
    {
        if (i < k)
            ans += a[i].second;
        else
            ans += a[i].first;
    }
    cout << ans;
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

C. n皇后问题

思路

每个皇后的攻击范围为

  • 行号相同
  • 列号相同
  • 行号和列号的差相同
  • 行号和列号的和相同

查询之前是否出现过即可

使用数组记录需考虑下标为负的情况

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
    int n, t;
    cin >> n >> t;
    unordered_set<int> row, col, diag1, diag2;
    for (int i = 0; i < t; i++)
    {
        int x, y;
        cin >> x >> y;

        if (row.count(x) || col.count(y) || diag1.count(x - y) || diag2.count(x + y))
        {
            cout << "No" << '\n';
            continue;
        }

        row.insert(x);
        col.insert(y);
        diag1.insert(x - y);
        diag2.insert(x + y);
        cout << "Yes" << '\n';
    }
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

D. 分苹果

思路

高中线性规划问题，已知苹果不会在线的上，所以将苹果的坐标 \((x,y)\) 代入直线方程 \(ax+by+c = 0\) 中

\(ax+by+c>0\) 和 \(ax+by+c<0\) 表示苹果在线的两侧

通过 01串 表示苹果在哪一块区域

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
    int n;
    cin >> n;
    vector<tuple<int, int, int>> v(2);
    for (int i = 0; i < 2; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        v[i] = {a, b, c};
    }

    vector<int> ans(4);
    for (int i = 0; i < n; i++)
    {
        ll x, y;
        cin >> x >> y;

        int flag = 0;
        for (int j = 0; j < 2; j++)
        {
            auto [a, b, c] = v[j];
            ll d = a * x + b * y + c;
            if (d > 0)
                flag |= 1 << j;
        }
        ans[flag]++;
    }
    sort(ans.begin(), ans.end());
    for (int i = 0; i < 4; i++)
    {
        cout << ans[i] << ' ';
    }
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

E. 完型填空

思路

动态规划问题

dp[i][j][k][l] 表示选择了 \(A,B,C,D\) 四个选项分别选择了 \(i,j,k,l\) 次的最大期望

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int dp[26][26][26][26];
void solve()
{
    int n;
    cin >> n;
    vector<array<int, 4>> v(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> v[i][0] >> v[i][1] >> v[i][2] >> v[i][3];

    for (int i = 0; i <= n / 4; i++)
    {
        for (int j = 0; j <= n / 4; j++)
        {
            for (int k = 0; k <= n / 4; k++)
            {
                for (int l = 0; l <= n / 4; l++)
                {
                    auto [a, b, c, d] = v[i + j + k + l];
                    if (i != 0)
                        dp[i][j][k][l] = max(dp[i][j][k][l], dp[i - 1][j][k][l] + a);
                    if (j != 0)
                        dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j - 1][k][l] + b);
                    if (k != 0)
                        dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k - 1][l] + c);
                    if (l != 0)
                        dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k][l - 1] + d);
                }
            }
        }
    }
    cout << dp[n / 4][n / 4][n / 4][n / 4];
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

F. 坐火车

思路

通过 \(BFS\) 计算出从 \(1\) 到任何城市所需经历的最少城市数量

再使用 \(dijkstra\) 在经历最少城市数量的前提下寻找最短路，即对于 \(u \to v\)，需要满足 \(d[v] = d[u] + 1\)，其中 \(d[i]\) 表示从 \(1\) 到 \(i\) 需要经历的最少城市数量

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
    int n, m;
    cin >> n >> m;

    vector<vector<pair<int, ll>>> g(n + 1);
    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    vector<int> d(n + 1);
    function<void()> bfs = [&]()
    {
        queue<int> q;
        q.push(1);
        vector<bool> vis(n + 1);
        vis[1] = true;
        d[1] = 1;
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (auto [v, w] : g[u])
            {
                if (vis[v])
                    continue;
                vis[v] = true;

                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    };
    bfs();

    vector<ll> dis(n + 1, 0x3f3f3f3f3f3f3f3f);
    function<void()> dijkstra = [&]()
    {
        priority_queue<int> q;
        q.push(n);
        vector<bool> vis(n + 1);
        dis[n] = 0;
        while (!q.empty())
        {
            int u = q.top();
            q.pop();
            if (vis[u])
                continue;
            vis[u] = true;

            for (auto [v, w] : g[u])
            {
                if (d[v] != d[u] - 1)
                    continue;
                if (dis[v] > dis[u] + w)
                {
                    dis[v] = dis[u] + w;
                    q.push(v);
                }
            }
        }
    };
    dijkstra();

    cout << d[n] << ' ' << dis[1];
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

G. A Xor B Problem again

思路

如果两个数 \(a,\ b\) 满足 \(a\oplus b = a + b\)，则这两个数在二进制表示下没有位同时为 \(1\)

对于一个数 \(10110_{(2)}\) 可知满足条件的数有 \(01001_{(2)},\ 01000_{(2)},\ 00001_{(2)}\)，而后面两个数都是前一个数的子集

故我们只需找出 \(11111_{(2)} \oplus 10110_{(2)}\) 的子集的大小即可

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
    int n;
    cin >> n;
    vector<int> dp(200000);
    vector<int> a(n);

    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        dp[a[i]]++;
    }

    for (int i = 0; i < 17; i++)
    {
        for (int j = 0; j < (1 << 17); j++)
        {
            if (j & (1 << i))
                dp[j] += dp[j ^ (1 << i)];
        }
    }

    ll ans = 0;
    for (int i = 0; i < n; i++)
    {
        ans += dp[((1 << 17) - 1) ^ a[i]];
    }
    cout << ans;
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

H. 摘苹果

思路

线段树

  • \(num\) 表示当前节点有多少苹果
  • \(cnt\) 表示当前节点有多少课树的苹果数量小于 \(100\)
  • \(flag\) 表示当前节点下没有可以采摘的苹果数

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;

struct node
{
    ll num, cnt;
    bool flag;
} seg[N * 4];
vector<int> a(N);

void update(int id)
{
    seg[id].num = seg[id * 2].num + seg[id * 2 + 1].num;
    seg[id].cnt = seg[id * 2].cnt + seg[id * 2 + 1].cnt;
    seg[id].flag = seg[id * 2].flag & seg[id * 2 + 1].flag;
}

void build(int id, int l, int r)
{
    if (l == r)
    {
        seg[id].num = a[l];
        if (seg[id].num < 100)
            seg[id].cnt = 1;
        if (seg[id].num < 10)
            seg[id].flag = 1;
        return;
    }

    int mid = (l + r) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    update(id);
}

void modify(int id, int l, int r, int ql, int qr)
{
    if (seg[id].flag)
        return;

    if (l == r)
    {
        seg[id].num = seg[id].num - (seg[id].num + 2) / 3;
        if (seg[id].num < 100)
            seg[id].cnt = 1;
        if (seg[id].num < 10)
            seg[id].flag = 1;
        return;
    }

    int mid = (l + r) / 2;
    if (qr <= mid)
        modify(id * 2, l, mid, ql, qr);
    else if (ql > mid)
        modify(id * 2 + 1, mid + 1, r, ql, qr);
    else
    {
        modify(id * 2, l, mid, ql, mid);
        modify(id * 2 + 1, mid + 1, r, mid + 1, qr);
    }
    update(id);
}

int querycnt(int id, int l, int r, int ql, int qr)
{
    if (l == ql && r == qr)
        return seg[id].cnt;

    int mid = (l + r) / 2;
    if (qr <= mid)
        return querycnt(id * 2, l, mid, ql, qr);
    else if (ql > mid)
        return querycnt(id * 2 + 1, mid + 1, r, ql, qr);
    else
        return querycnt(id * 2, l, mid, ql, mid) + querycnt(id * 2 + 1, mid + 1, r, mid + 1, qr);
}

ll querynum(int id, int l, int r, int ql, int qr)
{
    if (l == ql && r == qr)
        return seg[id].num;

    int mid = (l + r) / 2;
    if (qr <= mid)
        return querynum(id * 2, l, mid, ql, qr);
    else if (ql > mid)
        return querynum(id * 2 + 1, mid + 1, r, ql, qr);
    else
        return querynum(id * 2, l, mid, ql, mid) + querynum(id * 2 + 1, mid + 1, r, mid + 1, qr);
}

void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    build(1, 1, n);
    while (m--)
    {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1)
            modify(1, 1, n, l, r);
        else if (op == 2)
            cout << querycnt(1, 1, n, l, r) << endl;
        else if (op == 3)
            cout << querynum(1, 1, n, l, r) << endl;
    }
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}
ACM > 题解
#算法
2023年中国高校计算机大赛-团队程序设计天梯赛（GPLT）上海理工大学校内选拔赛
http://xiaowhang.github.io/archives/3300329301/
作者
Xiaowhang
发布于
2024年3月25日
许可协议