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 = 0for x in a:c = x // 5t += c * 3x -= c * 5while x > 0:t += 1if t % 3 == 0:x -= 3else:x -= 1print(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;
}