2023年第十四届蓝桥杯大赛软件类省赛Python大学B组真题

发表于 更新于 分类于 阅读次数： 本文字数： 393 阅读时长 ≈ 1 分钟
Our job is improving the quality of life, not just delaying death. — Patch Adams

C. 松散子序列

思路：

  • \(dp\) 状态分两种
  • \(dp[i][0]\) 表示不选当前这字符，当前的这个状态只能由上一个状态(选或不选)决定，即 \(dp[i][0]=max(dp[i-1][0],dp[i-1][1])\)
  • \(dp[i][1]\) 表示选当前这个字符就不能选前一个字符，即 \(dp[i][1]=dp[i-1][0]+w_i\)

时间复杂度：\(O(n)\)

注：\(w_i\)​ 为当前这个字符的价值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::string s;
    std::cin >> s;

    int n = s.size();

    std::vector dp(n, std::vector<int>(2));
    dp[0][1] = s[0] - 'a' + 1;
    for (int i = 1; i < n; i++) {
        dp[i][0] = std::max(dp[i - 1][0], dp[i - 1][1]);
        dp[i][1] = dp[i - 1][0] + s[i] - 'a' + 1;
    }
    std::cout << std::max(dp[n - 1][0], dp[n - 1][1]) << "\n";

    return 0;
}

D. 管道

思路：

  • 二分答案
  • 我们发现对于 \(L_i\) 有单调性，我们只需要判断每两个端点之间的距离是否可以互相抵达即可
  • 注意爆 \(int\)​

时间复杂度：\(O(nlogn)\)

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, len;
    std::cin >> n >> len;

    std::vector<std::array<i64, 2>> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i][0] >> a[i][1];
    }

    i64 l = 0, r = 2E9;
    while (l < r) {
        i64 mid = l + r >> 1;
        auto check = [&](i64 x) {
            std::vector<std::array<i64, 2>> seg;
            for (int i = 0; i < n; i++) {
                if (x >= a[i][1]) {
                    i64 t = x - a[i][1];
                    seg.push_back({a[i][0] - t, a[i][0] + t});
                }
            }
            std::sort(seg.begin(), seg.end());
            if (seg.empty() || seg[0][0] > 1) {
                return false;
            }
            i64 right = seg[0][1];
            for (int i = 1; i < seg.size(); i++) {
                if (right + 1 < seg[i][0]) {
                    return false;
                }
                right = std::max(right, seg[i][1]);
            }
            return right >= len;
        };
        if (!check(mid)) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    std::cout << l << "\n";
    
    return 0;
}