本站在允许 JavaScript 运行的环境下浏览效果更佳


Hrbust ACM练习 2024级第5周题单 题解分享 (A-C,F-H)

37

相关文章链接

前言

题单链接:2024级第5周题单 - Virtual Judge (vjudge.net)

A 题

原题链接:ABC 339C

Python Code

from itertools import accumulate

input()
min_number = 0
last_number = 0

for n in accumulate(map(int, input().split())):
    if n < min_number:
        min_number = n
    last_number = n

if min_number < 0:
    min_number = -min_number
    print(min_number + last_number)
else:
    print(last_number)

B 题

原题链接:P3397

Python Code

from itertools import accumulate


n, m = map(int, input().split())
l = []
for _m in range(n):
    l.append([])
    for _ in range(n + 1):
        l[_m].append(0)

while m > 0:
    m -= 1
    x1, y1, x2, y2 = map(int, input().split())
    for x in range(x1 - 1, x2):
        l[x][y1 - 1] += 1
        l[x][y2] -= 1

for sl in l:
    print(*list(accumulate(sl[:-1])))

C 题

原题链接:P2280 [HNOI2003] 激光炸弹 - 洛谷

Cpp Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int o[5010][5010];

void add(int x, int y, int v) { o[x][y] += v; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, r, x, y, v;
    cin >> n >> r;
    int max_x = r, max_y = r;

    for (int i = 0; i < n; i++) {
        cin >> x >> y >> v;
        x++;    // x 和 y 索引都加一,避免越界
        y++;
        if (x > max_x) {
            max_x = x;
        }
        if (y > max_y) {
            max_y = y;
        }
        add(x, y, v);
    }
    for (int _x = 1; _x <= max_x; _x++) {
        for (int _y = 1; _y <= max_y; _y++) {
            o[_x][_y] =
                o[_x][_y] + o[_x - 1][_y] + o[_x][_y - 1] - o[_x - 1][_y - 1];
        }
    }
    int rt = 0;
    for (int _x = r; _x <= max_x; _x++) {
        for (int _y = r; _y <= max_y; _y++) {
            rt = max(rt, o[_x][_y] - o[_x - r][_y] - o[_x][_y - r] +
                             o[_x - r][_y - r]);
        }
    }
    cout << rt;
    return 0;
}

Cpp Code 另一种实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int o[5010][5010];

void add(int x, int y, int v) { o[x][y] += v; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, r, x, y, v;
    cin >> n >> r;
    int max_x = r, max_y = r;

    for (int i = 0; i < n; i++) {
        cin >> x >> y >> v;
        if (x > max_x) {
            max_x = x;
        }
        if (y > max_y) {
            max_y = y;
        }
        add(x, y, v);
    }

    // 计算 y=0 这一列上的前缀和
    for (int i = 1; i <= max_x; i++) {
        o[i][0] += o[i - 1][0];
    }
    // 计算 x=0 这一行上的前缀和
    for (int j = 1; j <= max_y; j++) {
        o[0][j] += o[0][j - 1];
    }
    // 从 (1,1) 开始计算前缀和
    for (int _x = 1; _x <= max_x; _x++) {
        for (int _y = 1; _y <= max_y; _y++) {
            o[_x][_y] =
                o[_x][_y] + o[_x - 1][_y] + o[_x][_y - 1] - o[_x - 1][_y - 1];
        }
    }

    int rt = 0;
    // 从 索引 (r-1,r-1) 开始计算矩阵内数字和(索引 0 到 r-1 长度为 r)
    for (int _x = r - 1; _x <= max_x; _x++) {
        for (int _y = r - 1; _y <= max_y; _y++) {
            int v1, v2, v3, v4;
            v1 = o[_x][_y];

            // 越界判定,防止索引小于 0
            if (_x - r < 0) {
                // 说明:负索引前缀和都是 0
                // 举个例子原数组 1,0,2,3
                // 对应前缀和 1,1,3,6
                // 现在问索引 -1 的前缀和
                // 那原数组其实就变成了 0,1,0,2,3
                // 对应前缀和 0,1,1,3,6(对应索引 -1,0,1,2,3)
                v2 = 0;
            } else {
                v2 = o[_x - r][_y];
            }

            if (_y - r < 0) {
                v3 = 0;
            } else {
                v3 = o[_x][_y - r];
            }

            if (_y - r < 0 or _x - r < 0) {
                v4 = 0;
            } else {
                v4 = o[_x - r][_y - r];
            }

            rt = max(rt, v1 - v2 - v3 + v4);
        }
    }
    cout << rt;
    return 0;
}

D 题

Python Code


E 题

Python Code


F 题

原题链接:CF670C

Cpp Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const long long N = 200000 + 10;
ll scientist_language[N], moive_voice[N], moive_subtitle[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;
    cin >> n;                        // n = 科学家的数量
    map<ll, ll> scientist_language;  // language_index -> scientist_number
    for (ll i = 1; i <= n; i++) {
        ll language_index;
        cin >> language_index;
        scientist_language[language_index] += 1;
    }
    ll m;
    cin >> m;  // m = 电影院里的电影数量
    for (ll i = 1; i <= m; i++) {
        ll vocie_language;
        cin >> vocie_language;
        moive_voice[i] = vocie_language;  // index 用 1 到 m
    }
    for (ll i = 1; i <= m; i++) {
        ll subtitle_language;
        cin >> subtitle_language;
        moive_subtitle[i] = subtitle_language;  // index 用 1 到 m
    }

    ll very_satisfied = 0;
    ll almost_satisfied = 0;
    ll movie_index = 1;  //  默认值为 1
    for (ll i = 1; i <= m; i++) {
        ll temp_almost_satisfied = scientist_language[moive_subtitle[i]];
        ll temp_very_satisfied = scientist_language[moive_voice[i]];
        if (temp_very_satisfied > very_satisfied) {
            movie_index = i;
            very_satisfied = temp_very_satisfied;
            // almost_satisfied 也要记得更新,否则会错
            almost_satisfied = temp_almost_satisfied;
        } else if (temp_very_satisfied == very_satisfied &&
                   temp_almost_satisfied > almost_satisfied) {
            movie_index = i;
            almost_satisfied = temp_almost_satisfied;
        }
    }

    cout << movie_index << endl;
    return 0;
}

Cpp Code 另一种实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const long long N = 200000 + 10;
ll scientist_language[N], moive_voice[N], moive_subtitle[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;
    cin >> n;                        // n = 科学家的数量
    map<ll, ll> scientist_language;  // language_index -> scientist_number
    for (ll i = 1; i <= n; i++) {
        ll language_index;
        cin >> language_index;
        scientist_language[language_index] += 1;
    }
    ll m;
    cin >> m;  // m = 电影院里的电影数量
    for (ll i = 1; i <= m; i++) {
        ll vocie_language;
        cin >> vocie_language;
        moive_voice[i] = vocie_language;  // index 用 1 到 m
    }
    for (ll i = 1; i <= m; i++) {
        ll subtitle_language;
        cin >> subtitle_language;
        moive_subtitle[i] = subtitle_language;  // index 用 1 到 m
    }

    ll very_satisfied = 0;
    ll movie_index = 1;  //  默认值为 1
    for (ll i = 1; i <= m; i++) {
        ll temp = scientist_language[moive_voice[i]];
        if (temp > very_satisfied) {
            very_satisfied = temp;
            movie_index = i;  // 记录电影编号
        }
    }
    ll almost_satisfied = 0;
    for (ll i = 1; i <= m; i++) {
        ll temp_voice = scientist_language[moive_voice[i]];
        ll temp_subtitle = scientist_language[moive_subtitle[i]];
        if (very_satisfied == temp_voice && almost_satisfied < temp_subtitle) {
            almost_satisfied = temp_subtitle;
            movie_index = i;
        }
    }

    cout << movie_index << endl;
    return 0;
}

G 题

原题链接:ABC 014C

Python Code

from itertools import accumulate

n = int(input())
l = [0] * (1000000 + 2)
while n > 0:
    n -= 1
    a, b = map(int, input().split())
    l[a] += 1
    l[b + 1] -= 1
print(max(accumulate(l)))

H 题

原题链接:ABC 035C

试了一下 AtCoder,这个判题机是很奇葩的。之前用 print(rt, end="") 会 WA。看了别人的博客才知道这个网站的老题有 bug,在程序输出结束后不进行换行是会 WA 的。新题目已修复。

from itertools import accumulate


n, q = map(int, input().split())
l = []
for _ in range(0, n + 2):
    l.append(1)

while q > 0:
    q -= 1
    li, ri = map(int, input().split())
    l[li - 1] *= -1
    l[ri] *= -1
_n = 0
last_one = 0
rt = ""
for i in range(0, n):
    if _n == n:
        break
    if l[i] == -1:  # 和前一个不一样
        if i == 0 or last_one == 0:
            last_one = 1
        else:
            last_one = 0
        rt += str(last_one)
    else:  # 和前一个一样
        rt += str(last_one)
    _n += 1
print(rt)