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;
}
On this page76
数据结构作业题解01
  1. A. 最大子段和
    1. 题目背景
      1. 输入格式
      2. 输出格式
        1. 样例输入 1
        2. 样例输出 1
      3. 数据范围与提示
    2. 思路和题解
  2. B. 最小乘积
    1. 题目描述
      1. 输入格式
      2. 输出格式
        1. 样例输入 1
        2. 样例输出 1
        3. 样例输入 2
        4. 样例输出 2
        5. 样例输入 3
        6. 样例输出 3
        7. 样例输入 4
        8. 样例输出 4
        9. 样例输入 5
        10. 样例输出 5
        11. 样例输入 6
        12. 样例输出 6
        13. 样例输入 7
        14. 样例输出 7
      3. 数据范围
    2. 思路和题解
  3. C. 打牌
    1. 题目描述
      1. 输入格式
      2. 输出格式
        1. 样例输入 1
        2. 样例输出 1
        3. 样例输入 2
        4. 样例输出 2
      3. 数据范围
    2. 思路和题解
  4. D. 看番
    1. 题目描述
      1. 输入格式
      2. 输出格式
        1. 样例输入 1
        2. 样例输出 1
        3. 样例输入 2
        4. 样例输出 2
      3. 数据范围
    2. 思路与题解
  5. E.SA. 2进制高精度乘法
    1. 题目背景
      1. 输入格式
      2. 输出格式
        1. 样例输入 1
        2. 样例输出 1
        3. 样例输入 2
        4. 样例输出 2
      3. 数据范围与提示
    2. 思路与题解
  6. SB. 1·2·3=6
    1. 题目背景
      1. 输入格式
    2. 输出格式
      1. 样例输入 #1
      2. 样例输出 #1
      3. 样例输入 #2
      4. 样例输出 #2
      5. 数据范围与提示
    3. 思路与题解
  7. C. 拍照
    1. 题目背景
      1. 输入格式
      2. 输出格式
        1. 样例输入 1
        2. 样例输出 1
      3. 数据范围与提示
    2. 思路与题解