本文主要是介绍Hitachi Vantara Programming Contest 2024（AtCoder Beginner Contest 368）ABCDEF，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
前言
F比E简单多了，难评
A题：Cut
题意
给定n张卡片，将后m张卡片按顺序放置到顶部，按顺序输出卡片id
思路
更改输出方式即可
代码
inline void solve() {int n, m; cin >> n >> m;vector<int> a(n + 1);for (int i = 1; i <= n; i ++ ) cin >> a[i];for (int i = n - m + 1; i <= n; i ++ ) cout << a[i] << ' ';for (int i = 1; i <= n - m; i ++ ) cout << a[i] << ' ';return;
}
B题： Decrease 2 max elements
题意
对于一次操作，将整个数组降序sort一遍，并且将第一个和第二个元素的值减去一，问使得数组最多存在一个正整数的最小操作次数
思路
数据很小，并且是B题，不要多想，直接暴力
代码
inline void solve() {int n; cin >> n;vector<int> a(n + 1);for (int i = 1; i <= n; i ++ ) cin >> a[i];sort(a.begin() + 1, a.end(), greater<>());int cnt = 0;while (a[2] > 0) {a[1] -= 1, a[2] -= 1;sort(a.begin() + 1, a.end(), greater<>());cnt += 1;}cout << cnt << endl;return;
}C题：Triple Attack
题意
有n名敌人，我们每次攻击最前面那一个，定义T一开始为0，每进行一次攻击，会使得T值加一，当T是3的倍数的时候，攻击伤害为3，否则为1。问击败所有敌人所需的T
思路
这肯定跟周期有关了，在周期5的条件下，我们一共可以攻击5滴血。这个可以直接用除和模进行计算。
然后会剩下%5后的血量，我们直接进行模拟即可
代码
inline void solve() {int n; cin >> n;vector<int> a(n + 1);int cur = 1;ll ans = 0;for (int i = 1; i <= n; i ++ ) {int x; cin >> x;ans += x / 5 * 3;x %= 5;while (x) {int at = cur % 3 == 0 ? 3 : 1;int minv = min(at, x);x -= minv;cur += 1, ans += 1;}}cout << ans << endl;return;
}D题：Minimum Steiner Tree
题意
每次可以删去一个叶节点，问包含k个给定节点的最小树的大小是多少
思路
直接dfs，我们以一个给定的节点作为起点进行dfs，如果遇到了给定的节点，那么我们就要将这条路上的所有节点都进行“染色”（因为这些节点是到达此节点的必要条件）。最后输出染色的节点数量即可
代码
inline void solve() {int n, k; cin >> n >> k;vector<vector<int>> e(n + 1);for (int i = 1; i < n; i ++ ) {int a, b; cin >> a >> b;e[a].push_back(b), e[b].push_back(a);}map<int, int> vis;int st;for (int i = 1; i <= k; i ++ ) {int x; cin >> x;vis[x] = 1;st = x;}int ans = 0;vector<int> used(n + 1);function<void(int, int, vector<int>&)> dfs = [&](int u, int pre, vector<int>& path) {if (vis[u]) {for (int i = path.size() - 1; i >= 0; i -- ) {if (!used[path[i]]) used[path[i]] = 1, ans += 1;else break;}}for (int v : e[u]) {if (v == pre) continue;path.push_back(v);dfs(v, u, path);path.pop_back();}};vector<int> p;p.push_back(st);dfs(st, -1, p);cout << ans << endl;return;
}E题：Train Delay
题意
建议直接看原题进行理解
思路
模拟
首先我们将时间sort一遍，然后进行遍历
对于遍历到的点，要将其前面所有到达时间小于等于其出发时间的点对目的地的最低下限进行更新
什么意思呢？
10 20 1 2
30 40 2 3
四个信息分别为出发时间，到达时间，起点，终点
我们注意到30>20，那么对于终点2来说，其下限时间为20+它的推迟时间
此后遍历到的2的点的出发时间都要大于等于20+它的推迟时间
这个过程可以用优先队列进行模拟
代码
inline void solve() {int n, m, x; cin >> n >> m >> x;vector<ll> ans(m + 1);ans[1] = x;vector<array<int, 5>> p(m + 1);for (int i = 1; i <= m; i ++ ) {int a, b, s, t; cin >> a >> b >> s >> t;p[i] = {s, t, a, b, i};}sort(p.begin() + 1, p.end());using P = array<ll, 3>;priority_queue<P, vector<P>, greater<P>> q;vector<ll> d(n + 1);for (int i = 1; i <= m; i ++ ) {auto [s, t, a, b, id] = p[i];while (q.size() && q.top()[0] <= s) {auto [t1, t2, pos] = q.top();q.pop();d[pos] = max(d[pos], t2);}ans[id] = max(ans[id], d[a] - s);q.push({t, t + ans[id], b});}for (int i = 2; i <= m; i ++ ) cout << ans[i] << ' ';return;
}F题：Dividing Game
题意
见题目
思路
像，太像了。之前cf上也做过一道sg函数的，不过那个是猜的，这个可以明显计算
因为它进行的改变是将x变成小于其的任意正因数
所以我们预处理1e5的sg函数的时候，复杂度为1e5*sqrt（a）
这就直接处理出来了，秒了，比E简单100倍
你可能会注意到，下面用了一个while求sg函数
因为我打表前1000个，它的sg值就没有超过10，所以可以直接while遍历
代码
const int N = 1e5 + 9;
int sg[N];
inline void solve() {int n; cin >> n;int ans = 0;for (int i = 1; i <= n; i ++ ) {int x; cin >> x;ans ^= sg[x];}cout << (ans ? "Anna" : "Bruno") << endl;return;
}inline void pre_work() {sg[1] = 0;for (int i = 2; i <= 100000; i ++ ) {set<int> s;s.insert(0);for (int j = 2; j * j <= i; j ++ ) {if (i % j == 0) {s.insert(sg[j]);s.insert(sg[i / j]);}}int cur = 0;while (true) {if (!s.count(cur)) {sg[i] = cur;break;}cur += 1;}}
}
这篇关于Hitachi Vantara Programming Contest 2024（AtCoder Beginner Contest 368）ABCDEF的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
