数据结构作业题解01

数据结构作业题解01

exdoubled Lv4
  2025-09-18 17:00 2025-09-18 17:00 Created   2025-12-27 20:24:01 2025-12-27 20:24:01 Updated    3.8k Words  17 Mins  

A. 最大子段和

题目背景

给出一个长度为 \(n\) 的整数序列 \(a_1, a_2, \cdots, a_n\)。

你需要找一个子区间 \([l, r]\) \((1 \leq l \leq r \leq n)\)，使得 \(\sum_{i=l}^r a_i\) 尽可能大。

你只需要输出这个最大值即可。

输入格式

第一行输入一个整数 \(n\)，表示序列长度。

第二行有 \(n\) 个整数，\(a_1, a_2, \cdots, a_n\)。

输出格式

输出一行，一个整数，表示答案。

样例输入 1

1
2
9
3 -1 -4 1 -5 9 -2 6 -5

样例输出 1

1
13

数据范围与提示

对于 100% 的测试数据满足 \(1 \leq n \leq 10^5,\ -10^9 \leq a_i \leq 10^9\)。

思路和题解

一开始没思考，直接暴力用前缀和做，然后样例7爆了，时间复杂度 \(O(n^{2})\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    vector<ll> sum(n+1, 0);
    for(int i = 0; i < n; i++) sum[i+1] = sum[i] + a[i];
    ll ans = LLONG_MIN;
    for(int i = 0; i < n; i++){
        for(int j = i; j < n; j++){
            ans = max(ans, sum[j+1] - sum[i]);
        }
    }
    cout << ans;

发现这是 \(dp\) 经典老题，改用 \(dp\)，\(dp[i]\) 表示区间以第 \(i\) 个元素结尾的最大子区间和，得到状态转移方程 \[ dp[i+1] = max(a[i], dp[i] + a[i]) \]

1
2
3
4
5
6
7
8
9
10
11
12
int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    vector<ll> dp(n+1, 0);
    ll ans = LLONG_MIN;
    for(int i = 0; i < n; i++){
        dp[i+1] = max((ll)a[i], dp[i] + a[i]);
        ans = max(ans, dp[i+1]);
    }
    cout << ans;

B. 最小乘积

题目描述

给定四个数 \(a, b, x, y, n\)，满足 \(a \geq x, b \geq y\)。
你可以依次不超过 \(n\) 次操作，每次可选择如下两种方式进行操作：

  • 使 \(a\) 减少 1，减少之后不得小于 \(x\)；
  • 使 \(b\) 减少 1，减少之后不得小于 \(y\)。

你的任务是通过在这 \(n\) 次操作后，使 \(a \times b\) 尽可能小。

输入格式

输入五个整数 \(a, b, x, y, n\)。

输出格式

输出值 \(a \times b\)。

样例输入 1

1
10 10 8 5 3

样例输出 1

1
70

样例输入 2

1
12 8 8 7 2

样例输出 2

1
77

样例输入 3

1
12343 43 4543 39 123212

样例输出 3

1
177177

样例输入 4

1
1000000000 1000000000 1 1 1

样例输出 4

1
999999999000000000

样例输入 5

1
1000000000 1000000000 1 1 1000000000

样例输出 5

1
999999999

样例输入 6

1
10 11 2 1 5

样例输出 6

1
55

样例输入 7

1
10 11 9 1 10

样例输出 7

1
10

数据范围

\(1 \leq a, b, x, y, n \leq 10^9\)。

思路和题解

前两题都不喜欢动脑子导致的，暴力写了 \(\frac{1}{4}\) 的 \(dfs\) ，猛然发现这题暴力绝对会超时， \(dp\) 算上最极致的压缩空间估计也不够，于是想了想，发现这两个数和是一定的，两个数相差越远积越小，采用贪心的思想，先减到一个数不能再减为止。

后面又完善了 \(dfs\) 的解法（喜欢暴力解法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int a, b, x, y, n;
    cin >> a >> b >> x >> y >> n;
    ll ans1 = LLONG_MAX, ans2 = LLONG_MAX;
    {
        int tempa = a, tempb = b, tempn = n;
        int cnta = min(tempn, tempa - x);
        tempa -= cnta;
        tempn -= cnta;
        int cntb = min(tempn, tempb - y);
        tempb -= cntb;
        ans1 = (ll)tempa * tempb;
    }
    {
        int tempa = a, tempb = b, tempn = n;
        int cntb = min(tempn, tempb - y);
        tempb -= cntb;
        tempn -= cntb;
        int cnta = min(tempn, tempa - x);
        tempa -= cnta;
        ans2 = (ll)tempa * tempb;
    }

    cout << min(ans1, ans2) << endl;
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
// dfs 暴力
ll dfs(int a, int b, int x, int y, int &n, int& cnt, ll& ans){
    if(a <= x && b <= x) return ans;
    if(cnt == n) return ans;
    if(a > x){
        ll temp = (ll)(--a) * b;
        cnt++;
        ans = min(ans, temp);
        dfs(a, b, x, y, n, cnt, ans);
        a++;
        cnt--;
    }
    if(b > y){
        ll temp = (ll)a * (--b);
        cnt++;
        ans = min(ans, temp);
        dfs(a, b, x, y, n, cnt, ans);
        b++;
        cnt--;
    }
    return ans;
}
int main() {
    int a,b,x,y,n;
    cin >> a >> b >> x >> y >> n;
    ll ans = LLONG_MAX;
    int cnt = 0;
    ans = dfs(a, b, x, y, n, cnt, ans);
    cout << ans;
    return 0;
}

C. 打牌

题目描述

假设有 \(m\) 个人，一共有 \(n \times m\) 张牌，每个人有 \(n\) 张牌，每张牌编号为正整数且两两不同，最大为 \(n \times m\)。 每一轮大家各出一张牌，点数最大的玩家获胜得到此轮胜利，然后进入下一轮。当所有人牌打完之后，游戏结束。

现在你知道你的 \(n\) 张牌，问你最少能够获胜几轮。

输入格式

第一行两个正整数 \(m\) 和 \(n\)，分别表示有 \(m\) 个人，每个人有 \(n\) 张牌。

接下来有 \(n\) 个整数，分别是你手中的 \(n\) 张牌上的点数。

输出格式

一个整数，表示你最少获胜的轮数。

样例输入 1

1
2
2 5
1 7 2 10 9

样例输出 1

1
2

样例输入 2

1
2
6 11
62 63 54 66 65 61 57 56 50 53 48

样例输出 2

1
4

数据范围

\(m \leq 20, n \leq 50\)。

样例 1 解释：一共有 \(10\) 张牌分别为 \(1 \sim 10\)，而你的牌为 \(1, 7, 2, 10, 9\)。
最坏情况下，你按照 \(1, 7, 2, 10, 9\) 打出五张牌，对方按照 \(3, 8, 4, 5, 6\) 打出五张牌，那么你最少只能获胜 \(2\) 次。

思路和题解

小模拟，采用贪心的思想，考虑最坏的情况，从大到小出牌，其他人如果有大牌只有一个人出比我大的牌，其他人都出比我小的，记录输的局数，最后用总局数减去输的局数就是答案

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
int m, n;
    cin >> m >> n;
    int tot = n * m;
    vector<int> v(n);
    for(int i = 0; i < n; ++i) cin >> v[i];
    sort(v.begin(), v.end(), greater<int>());
    int ans = 0;

    vector<bool> visited(tot+1, false);
    for(int i = 0; i < n; ++i) visited[v[i]] = true;
    
    for(int i = 0, find = 0; i < n; ++i, find = 0){
    
        for(int j = tot; j > v[i]; --j){
            if(!visited[j]){
                ans++;
                visited[j] = true;
                find = 1;
                break;
            }
        }
        if(find){
            for(int j = 1, cnt = 0; j <= tot && cnt < m-2; ++j, ++cnt){
                if(!visited[j]) visited[j] = true;
            }
        } else{
            for(int j = 1, cnt = 0; j <= tot && cnt < m-1; ++j, ++cnt) {
                if (!visited[j]) visited[j] = true;
            }
        }
    
    }
    cout << n-ans;

D. 看番

题目描述

众所周知，ZZR 住在 B 站。

这一天，L 老师来找 ZZR 玩，ZZR 决定向 L 老师展现一下自己快速看器的本领。

ZZR 让 L 老师任意挑选了一部器，L 老师一眼看中了《辉夜大小姐想让我告白》，已知这部器一共有 \(N\) 个精彩片段，每个精彩片段用 \((L_i, R_i)\) 来表示。

ZZR 从第 1 分钟开始看，每次可以按下快进键，快进 \(X\) 分钟，但 ZZR 不想因为快进而错过任何精彩片段，问 ZZR 最快需要多久可以看到这部器。

输入格式

第一行给出两个整数 \(N\) 和 \(X\)。

接下来 \(N\) 行，每行给出两个整数 \(L_i\) 和 \(R_i\)，保证 \(R_{i-1} < L_i\)。

输出格式

输出一个整数，表示 ZZR 最快看完这部器的时间。

样例输入 1

1
2
3
2 3
5 6
10 12

样例输出 1

1
6

样例输入 2

1
2
1 1
1 100000

样例输出 2

1
100000

数据范围

\(1 \leq N \leq 50, 1 \leq X \leq 10^5, 1 \leq L_i \leq R_i \leq 10^5\)

在第一个样例中，ZZR 从第 1 分钟开始看，由于 \([1, 3]\) 区间内没有精彩片段，因此 ZZR 快进到了第 4 分钟。

观看完 \([4, 6]\) 区间内的内容后，时间来到了第 7 分钟，由于 \([7, 9]\) 区间内没有精彩片段，因此 ZZR 快进到了第 10 分钟。

观看完 \([10, 12]\) 区间内的内容后，看器结束。

一共耗时 \(3 + 3 = 6\) 分钟。

思路与题解

简单题，每个空闲时间段能跳就跳，遍历一遍即可

1
2
3
4
5
6
7
8
9
10
11
12
13
int n,x;
    cin >> n >> x;;
    int l,r;
    int ans = 0;
    int lastr = 0;
    for(int i = 0; i < n; i++){
        cin >> l >> r;
        ans += (l - lastr) % x;
        ans += r - l;
        lastr = r;
    }
    cout << ans;
    return 0;

E.SA. 2进制高精度乘法

题目背景

输入两个很大的整数，你需要输出它们的乘积。

特别的，你需要完成 2 进制下的这个问题，而非我们常用的 10 进制。

输入格式

第一行输入一个二进制串，保证最高位为 1。

第二行输入一个二进制串，保证最高位为 1。

输出格式

输出一行，一个二进制串，表示输入的两个二进制串相乘后的答案。

样例输入 1

1
2
10
11

样例输出 1

1
110

样例输入 2

1
2
101
111

样例输出 2

1
100011

数据范围与提示

对于 100% 的测试数据满足输入的二进制串长度不超过 5000。

思路与题解

经典模板题，这里采用数组的思想解（链表也是一样的），先逆向，选一个位数少的做被乘数，列竖式计算，空位补零，注意加法进位，最后再逆向

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
string add(string &a, string &b){
    int n = a.size();
    int m = b.size();
    string maxnum = n > m ? a : b;
    string minnum = n > m ? b : a;
    string ans(maxnum.size(), '0');
    int carry = 0;
    for(int i = 0; i < minnum.size();++i){
        ans[i] = (char)(((minnum[i] - '0') ^ (maxnum[i] - '0') ^ carry) + '0');
        carry = (minnum[i] - '0') + (maxnum[i] - '0') + carry > 1 ? 1 : 0;
    }
    for(int i = minnum.size(); i < maxnum.size(); ++i){
        ans[i] = (char)(((maxnum[i] - '0') ^ carry) + '0');
        carry = (maxnum[i] - '0') + carry > 1 ? 1 : 0;
    }
    if(carry == 1) ans.push_back('1');
    return ans;
}

int main() {
    string str1, str2;
    cin >> str1 >> str2;

    reverse(str1.begin(), str1.end());
    reverse(str2.begin(), str2.end());
    int n = str1.size();
    int m = str2.size();

    string ans;
    for(int i = 0; i < m; ++i){
        string temp;
        if(str2[i] == '0'){
            temp.resize(n,'0');
        } else{
            temp = str1;
        }
        for(int j = 0; j < i; ++j){
            temp.insert(temp.begin(), '0');
        }
        ans = add(ans, temp);
    }
    reverse(ans.begin(), ans.end());
    for(auto c : ans) cout << c;
    return 0;
}

SB. 1·2·3=6

题目背景

某一天，George在12306抢票的时候想到了这么一个问题：

给出一个长度为 \(n\) 的排列 \(p_1, p_2, \cdots, p_n\)。

（\(1 \leq p_i \leq n\)，且 \(1,2,\cdots,n\) 每个数字出现恰好一次）

你需要统计满足条件的四元组 \((a, b, c, d)\) 的数量。

合法四元组的条件为：

\[1 \leq a < b < c < d \leq n \tag{1}\]

且 \(p_a < p_b < p_c < p_d \tag{2}\)

且 \(p_a \cdot p_b \cdot p_c = p_d \tag{3}\)

输入格式

第一行，一个整数 \(n\)。

第二行，\(n\) 个整数，保证为一个排列。

输出格式

输出一个整数，表示合法四元组的数量。

样例输入 #1

1
2
6
1 2 3 4 5 6

样例输出 #1

1
1

样例输入 #2

1
2
10
1 3 2 4 5 6 8 7 9 10

样例输出 #2

1
2

数据范围与提示

对于 100% 的测试数据满足 \(n \leq 10^6\)。

提示：通常 cin/cout 的输入/输出速度慢于 scanf/printf，尤其对于 \(10^6\) 或更大输入/输出级别来说，差异会更加明显。如果要提升 cin/cout 的速度，可以采用关闭同步的方法（关闭后，cin/cout 不能和其它输入/输出函数混用）:

1
2
3
4
5
6
7
8
#include <iostream>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    /*       your 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
#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

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

    int n;
    cin >> n;
    unordered_map<int, int> pos;
    for (int i = 0; i < n; ++i) {
        int val;
        cin >> val;
        pos[val] = i;
    }
    long long count = 0;
    for (int x = 1; x <= n; ++x) {
        if ((long long)x * x * x > n) {
            break;
        }
        for (int y = x + 1; y <= n; ++y) {
            if ((long long)x * y * y > n) {
                break;
            }
            for (int z = y + 1; z <= n; ++z) {
                long long w = (long long)x * y * z;
                if (w > n) {
                    break;
                }
                if (pos.at(x) < pos.at(y) && pos.at(y) < pos.at(z) && pos.at(z) < pos.at(w)) {
                    count++;
                }
            }
        }
    }
    cout << count << endl;
    return 0;
}

C. 拍照

题目背景

某个班级有 \(n\) 位同学，每个同学都有一个唯一的学号，分别是 \(p_1, p_2, \cdots, p_n\ (1 \leq p_i \leq n)\)。

除此之外，每个同学有一个整数身高，分别为 \(h_1, h_2, \cdots, h_n\)。

也就是说，第 \(i\) 个同学的学号是 \(p_i\)，身高是 \(h_i\)。

现在，一共要拍 \(n\) 次照片。

  • 第 \(1\) 次拍照，只有学号为 \(p_1\) 的同学参加。
  • 第 \(2\) 次拍照，学号为 \(p_1, p_2\) 的同学参加。
  • 第 \(3\) 次拍照，学号为 \(p_1, p_2, p_3\) 的同学参加。
  • ……
  • 第 \(n\) 次拍照，所有同学参加。

每次拍照的时候，参与拍照的同学会按照学号从小到大的顺序排成一排。

每次拍照的照片有一个美观度，定义为相邻两个同学身高差的平方和。例如，假设排成一排的同学从左到右的身高依次为 \((1, 4, 1, 2)\)，则美观度是 \((1-4)^2+(4-1)^2+(1-2)^2=19\)。

现在，老师希望你算出这 \(n\) 次拍照的照片的美观度分别是多少。

输入格式

第一行，一个整数 \(n\)，表示班级人数。

第二行，\(n\) 个整数 \(p_1, p_2, \cdots, p_n\)，表示同学的学号。

第三行，\(n\) 个整数 \(h_1, h_2, \cdots, h_n\)，表示同学的身高。

输出格式

输出 \(n\) 行，每行一个整数，第 \(i\) 行表示第 \(i\) 次拍照的照片美观度。

样例输入 1

1
2
3
5
1 3 2 4 5
3 1 4 1 5

样例输出 1

1
2
3
4
5
0
4
10
10
26

数据范围与提示

对于 100% 的测试数据满足 \(n \leq 10^6,\ 1 \leq p_i \leq n,\ 1 \leq h_i \leq 10^6\)。

（输入输出量比较大，请选择较快的输入输出方式）

思路与题解

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
#include <bits/stdc++.h>

using namespace std;

long long square(long long x) {
    return x * x;
}

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

    int n;
    cin >> n;
    vector<int> p(n);
    vector<int> h(n);
    vector<int> h_by_id(n + 1);
    for (int i = 0; i < n; ++i) cin >> p[i];
    for (int i = 0; i < n; ++i) cin >> h[i];
    for (int i = 0; i < n; ++i) h_by_id[p[i]] = h[i];

    map<int, int> students;

    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        int newId = p[i];
        int newH = h_by_id[newId];
        students[newId] = newH;

        auto it = students.find(newId);
        auto prevIt = (it == students.begin()) ? students.end() : prev(it);
        auto next_it = next(it);

        if (prevIt != students.end() && next_it != students.end()) {
            ans -= square(prevIt->second - next_it->second);
            ans += square(prevIt->second - newH);
            ans += square(newH - next_it->second);
        } else if (prevIt != students.end()) {
            ans += square(prevIt->second - newH);
        } else if (next_it != students.end()) {
            ans += square(newH - next_it->second);
        }
        cout << ans << "\n";
    }
    return 0;
}
  • Title: 数据结构作业题解01
  • Author: exdoubled
  • Created at : 2025-09-18 17:00:00
  • Updated at : 2025-12-27 20:24:01
  • Link: https://github.com/exdoubled/exdoubled.github.io.git/sjjg/homework01/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
数据结构作业题解01
  1. A. 最大子段和
    1. 题目背景
      1. 输入格式
      2. 输出格式
      3. 数据范围与提示
    2. 思路和题解
  2. B. 最小乘积
    1. 题目描述
      1. 输入格式
      2. 输出格式
      3. 数据范围
    2. 思路和题解
  3. C. 打牌
    1. 题目描述
      1. 输入格式
      2. 输出格式
      3. 数据范围
    2. 思路和题解
  4. D. 看番
    1. 题目描述
      1. 输入格式
      2. 输出格式
      3. 数据范围
    2. 思路与题解
  5. E.SA. 2进制高精度乘法
    1. 题目背景
      1. 输入格式
      2. 输出格式
      3. 数据范围与提示
    2. 思路与题解
  6. SB. 1·2·3=6
    1. 题目背景
      1. 输入格式
    2. 输出格式
      1. 数据范围与提示
    3. 思路与题解
  7. C. 拍照
    1. 题目背景
      1. 输入格式
      2. 输出格式
      3. 数据范围与提示
    2. 思路与题解