AtCoder Beginner Contest 368 题ABCD详细题解(C++,Python)
前言:
第一次参加atc的比赛，总体来说比codeforces好，至少不会in queue我也尝试了一下用go写，体验还不错，这个beginner感觉跟cf的div3难度差不多，思维难度不高，感觉主要考察基础的编码能力。这次比赛E难度不合理，E通过的数量比G还少
本文为此比赛题ABCDF的详细题解，包含C++,Python语言描述，如果觉得有帮助或者写的不错可以点个赞，之后我会更新cf, atc, 洛谷比赛的某些题目题解(本人能力不够无法AK只能写某些题目的题解了，之后能力够了会写的)
比赛题目链接：
Tasks - Hitachi Vantara Programming Contest 2024（AtCoder Beginner Contest 368）
目录
题A:
题目大意和思路:
代码(C++):
代码(Python):
题B:
题目大意和思路:
代码(C++):
代码(Python):
题C:
题目大意和思路:
代码(C++):
代码(Python):
题D:
题目大意和思路:
代码(C++):
题A:
A - Cut (atcoder.jp)
题目大意和思路:
有一堆N张卡片,从顶部数起第i张卡片上写着整数Ai。
你从底部取出K张卡片,并将它们按原来的顺序放到堆顶。
请按从上到下的顺序输出操作后卡片上的整数
输入：
5 3 1 2 3 4 5
输出：
3 4 5 1 2
就是把数组后面k个数字放在前面，直接输出就可以了，先输出数组后面k，再输出前面的n - k个
代码(C++):
int main() {
int n, k;
std::cin >> n >> k;
std::vector<int> a(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
for (int i = n - k; i < n; i++) {
std::cout << a[i] << " ";
}
for (int i = 0; i < n - k; i++) {
std::cout << a[i] << " ";
}
std::cout << std::endl;
}代码(Python):
def main():
n, k = map(int, input().split())
arr = list(map(int, input().split()))
print(*arr[n - k:], *arr[:n - k], end = " ")题B:
B - Decrease 2 max elements (atcoder.jp)
题目大意和思路:
一个正整数数组，进行下面操作：
降序排列，然后前两个元素减一
问需要多少次才能使得数组只剩下一个或者0个元素
数据量不大，可以直接暴力模拟做，每次排序后，当最大的数字小于等于0的时候，也就输无法再减的时候退出循环即可
暴力模拟代码:
int main() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
int res = 0;
while (1) {
std::sort(a.begin(), a.end());
if (a[n - 2] <= 0) {
break;
}
a[n - 1]--;
a[n - 2]--;
res++;
}
std::cout << res << std::endl;
}但是有个更好的思路，(当时比赛想了一会，看到数据不大就暴力模拟了)，参考jiangly的代码(前排貌似就他用的不是暴力模拟)
题目的意思就是，每次操作将数组中最大的两个数字减一，要使整个数组只剩一个或零个正整数
那么关注剩下的那个数字即可
有两种情况，第一种是保留的数字为第二小的数字，第二种是保留的数字是最大的数字，一种是数字大小比较接近，操作次数就是数字的和除以2，一种就是最大值保存到最后，此时最大值满足大于sum的一半即可
代码(C++):
int main() {
int n;
std::cin >> n;
int mx = 0, sum = 0;
for (int i = 0; i < n; i++) {
int x;
std::cin >> x;
sum += x;
mx = std::max(x, mx);
}
int res = std::min(sum / 2, sum - mx);
std::cout << res << std::endl;
}代码(Python):
def main():
n = int(input())
arr = list(map(int, input().split()))
sum_val = sum(arr)
mx = max(arr)
res = min(sum_val // 2, sum_val - mx)
print(res)题C:
C - Triple Attack (atcoder.jp)
题目大意和思路:
这题可以这么理解
就是一些怪，从前往后攻击，第一刀伤害1，第二刀伤害1，第三刀伤害3
然后问需要多少刀可以全部杀完
这个数据量肯定不能用暴力做的
3刀一循环，总共会造成5伤害
那么对于每一个元素，可以对5进行取余然后关注余数的就可以了
然后关注当前是哪一刀，再对这个元素剩余的进行“砍”就可以了
注意数据，要用long long
代码(C++):
int main() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
long long t = 0;
for (auto& x : a) {
int c = x / 5;
t += c * 3;
x -= c * 5;
//当此时这个怪还有剩余的血量后
//此时t++,然后看此时是哪一刀对x剩余进行减即可
while (x > 0) {
t++;
if (t % 3 == 0) {
x -= 3;
} else {
x -= 1;
}
}
}
std::cout << t << std::endl;
}代码(Python):
def main():
n = int(input())
a = list(map(int, input().split()))
t = 0
for x in a:
c = x // 5
t += c * 3
x -= c * 5
while x > 0:
t += 1
if t % 3 == 0:
x -= 3
else:
x -= 1
print(t)题D:
D - Minimum Steiner Tree (atcoder.jp)
题目大意和思路:
就是给你一个树，然后再给你k个点，让你求这个树中包含这k个点的最小节点数
板子题，贴个板子(其实我也不算太理解)
代码(C++):
#include <iostream>
#include <vector>
std::vector<std::vector<int>> adj;
std::vector<int> f, sum;
int n, k;
int res = 0;
void dfs(int x, int p) {
sum[x] = f[x];
int cnt = (f[x] == 1) ? 2 : 0;
for (int y : adj[x]) {
if (y == p) continue;
dfs(y, x);
sum[x] += sum[y];
if (sum[y] > 0) cnt++;
}
if (sum[x] < k) cnt++;
if (cnt >= 2) res++;
}
int main() {
std::cin >> n >> k;
adj.resize(n);
for (int i = 0; i < n - 1; i++) {
int x, y;
std::cin >> x >> y;
x--; y--;
adj[x].push_back(y);
adj[y].push_back(x);
}
f.resize(n, 0);
for (int i = 0; i < k; i++) {
int v;
std::cin >> v;
v--;
f[v] = 1;
}
sum.resize(n, 0);
dfs(0, -1);
std::cout << res << std::endl;
return 0;
}