Hrbust ACM练习 2024级第5周题单 题解分享 (A-C,F-H)
相关文章链接
前言
题单链接: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)