AtCoder Beginner Contest 368 题解思路（A-D，F）

本文主要是介绍AtCoder Beginner Contest 368 题解思路（A-D，F），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

AtCoder Beginner Contest 368 题解&&思路（A-D，F）

A - Cut

题目描述

有 $N$ 个数在一个桶里面，从上往下第 $i$ 个数是 $A_i$ ，从桶下面取出 $K$ 个数，保持原顺序放在桶的上面，从上到下打印写在卡片上的整数。

思路

时间复杂度 $\mathcal{O}(N).$

本质上就是先输出后 $K$ 个数然后再从前面输出。

#include <iostream>
#include <cstdio>
#include <stdlib.h>
#define N 105using namespace std;
int a[N];
signed main(){int n,k;cin >> n >> k;for (int i = 1;i <= n;i ++) cin >> a[i];for (int i = n - k + 1;i <= n;i ++) cout << a[i] << ' ';for (int i = 1;i < n - k + 1;i ++) cout << a[i] << ' ';return 0;
}

B - Decrease 2 max elements

题目描述

问题陈述

给你一个由 $N$ 个正整数 $(A_1, A_2, \dots ,A_N)$ 组成的序列。高桥重复下面的操作，直到 $A$ 包含一个或更少的正整数元素：

按降序排列 $A$ 。然后将 $A_1$ 和 $A_2$ 减少 $1$ 。

求他执行此操作的次数。

思路

直接模拟即可。

用数组或者 $ma p$ 存一下大于 $0$ 的有多少个就行，每次操作后更新。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stdlib.h>
#include <map>
#define N 105
using namespace std;
int n,a[N],ans;
map<bool,int> mp; 
signed main(){cin >> n;for (int i = 1;i <= n;i ++) cin >> a[i];for (int i = 1;i <= n;i ++) {if (a[i] > 0) mp[1] ++;else mp[0] ++;}while(mp[1] > 1) {stable_sort(a + 1,a + 1 + n,[](int x,int y) {return x > y;});a[1] --,a[2] --;if (a[1] == 0) mp[1]--,mp[0] ++;if (a[2] == 0) mp[1]--,mp[0] ++;ans ++;}cout << ans;return 0;
}

C - Triple Attack

题目描述

问题陈述

你正在玩一个游戏。

有 $N$ 个敌人排成一排，最前面的 $i$ 个敌人的生命值是 $H_i$ 。

你将使用初始化为 $0$ 的变量 $T$ 重复以下操作，直到所有敌人的生命值都变为 $0$ 或更少。

将 $T$ 增加 $1$ 。然后，攻击最前方生命值为 $1$ 或更高的敌人。如果 $T$ 是 $3$ 的倍数，敌人的生命值会减少 $3$ ；否则，生命值会减少 $1$ 。

当所有敌人的生命值变为 $0$ 或更少时，求 $T$ 的值。

思路

赛时有细节问题，没打出来，~~呜呜呜呜~~

我们可以发现一个循环节：
$T = 3, 4, 5$
这里攻击对方是 $5$ 的健康值，而只用迭代 $3$ 次 $T .$

对于没有到 $T\%3=0$ 的，暴力枚举即可（我赛时就是因为没有这样，想用 $O (1)$ 解决，导致有一大堆细节问题……）。

其他的就不必多说了。

#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <cstring>
#include <algorithm>
#define N 200005
#define int long long
using namespace std;
int n,a[N],T = 0;
signed main(){cin >> n;for (int i = 1;i <= n;i ++) cin >> a[i];for (int i = 1;i <= n;i ++) {while(a[i] > 0 && T % 3) {T ++;if (T % 3) a[i]--;else a[i] -= 3;}if (a[i] > 0) {int m = a[i] / 5;T += m * 3;a[i] %= 5;if (a[i] >= 1) T ++;if (a[i] >= 2) T ++;if (a[i] >= 3) T ++;}}cout << T;return 0;
}

D - Minimum Steiner Tree

题目描述

问题陈述

给你一棵树，树上有 $N$ 个顶点，编号为 $1$ 至 $N$ 。第 $i$ 条边连接顶点 $A_i$ 和 $B_i$ 。

考虑从这个图中删除一些边和顶点（可能为零）后可以得到一棵树。求这样一棵树中包含所有 $K$ 指定顶点 $V_1,\ldots,V_K$ 的顶点的最小数目。

思路

注意到题目给的是一棵树，也就是说从 $u$ 到 $v$ 有且仅有一条路径，难道这里我们要枚举 $V_i,V_j$ ？其实不用，我们可以从 $V_1$ 为根开始 dfs 图的遍历，碰到节点 $x\in V$ 的，就更新这条路径上的点（表示算作答案），但一定要先遍历再更新（有可能当前节点 $u\in V$ 而 $x\in V$ 且 $x$ 是 $u$ 子树下的一个点，这样就会顺便把 $V_1\rightarrow u$ 的路径也给更新了）。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <stdlib.h>
#include <vector>
#include <set>
#define N 200005using namespace std;
int n,v[N],k;
vector<int> g[N];
bool bj[N];
bool vis[N];
int stk[N],tp;
void dfs(int cur,int fa) {tp ++,stk[tp] = cur;for (auto i : g[cur])if (i != fa){dfs(i,cur);if (bj[i] && !vis[i]) {for (int j = 1;j <= tp;j ++) vis[stk[j]] = 1;vis[i] = 1;}}tp --;
}
signed main(){cin >> n >> k;for (int i = 1;i < n;i ++) {int u,v;cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}for (int i = 1;i <= k;i ++) cin >> v[i],bj[v[i]] = 1;dfs(v[1],0);vis[v[1]] = 1;int ans = 0;for (int i = 1;i <= n;i ++) ans += vis[i];cout << ans;return 0;
}

E - Train Delay

题目描述

问题陈述

在 Atcoder 国家，有 $N$ 座城市，编号为 $1$ 至 $N$ ，以及 $M$ 列火车，编号为 $1$ 至 $M$ 。 $i$ 次列车在 $S_i$ 点从城市 $A_i$ 出发，在 $T_i$ 点到达城市 $B_i$ 。

给定一个正整数 $X_1$ ，求一个非负整数 $X_2,\ldots,X_M$ 的最小值 $X_2+\ldots+X_M$ ，以满足下列条件。

条件对于所有满足 $\leq i,j \leq M$ 的一对 $(i, j)$ ，如果 $B_i=A_j$ 和 $T_i \leq S_j$ ，那么 $T_i+X_i \leq S_j+X_j$ 。
- 换句话说，对于任何一对原本可以换乘的列车，即使将每趟列车 $i$ 的出发和到达时间延迟 $X_i$ ，仍然可以换乘。

可以证明，这种将 $X_2,\ldots,X_M$ 设置为 $X_2+\ldots+X_M$ 的最小值的方法是唯一的。

思路

赛场上没有想出来就先做 $T_6$ 了，后面更。

F - Dividing Game

题目描述

问题陈述

给你一个由 $N$ 个正整数 $(A_1, A_2, \dots ,A_N)$ 组成的序列，其中每个元素至少是 $2$ 。安娜和布鲁诺用这些整数玩一个游戏。他们轮流执行以下操作，安娜先执行。

自由选择一个整数 $\ (1 \leq i \leq N)$ 。然后，自由选择 $A_i$ 的一个不是 $A_i$ 本身的正整除 $x$ ，并将 $A_i$ 替换为 $x$ 。

不能进行操作的一方输，另一方赢。假设两位棋手都以最佳的方式下棋，那么谁会赢呢？

思路

这是道博弈论的题目，不难想出来这题应该和因数有关，考虑时间复杂度 $\mathcal{O}(N\sqrt N)$ 的算法。

看到此题我先求出其因数的个数（除了它本身），然后，观察到现在是不是跟之前做过的题目一样，没错是它！

——Nim 游戏

但交上去，挂了……

现在我考虑这条关于 $A_i$ 的因子链，发现跟它的最长链有关，不过也很好理解，拿最长能够使先手必胜的状态更大，于是就 $A$ 了。

#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 100005
using namespace std;
int n,a[N],cnt;
signed main(){cin >> n;for (int i = 1;i <= n;i ++) {cin >> a[i];int p = 0;for (int j = 2;j * j <= a[i];j ++)while(a[i] % j == 0) a[i] /= j,p ++;if (a[i] > 1) p ++;cnt ^= p;
//		cout << p << endl;}if (cnt == 0) return cout << "Bruno",0;cout << "Anna"; return 0;
}