AtCoder Beginner Contest 368

A.Cut（模拟）

题意：

有一叠 $N$张扑克牌，最上面的 $i$张扑克牌上写着一个整数 $A\_i$。

你从牌堆底部取出 $K$张牌，将它们放在牌堆顶部，并保持它们的顺序。

操作后从上到下输出写在卡片上的整数。

分析：

我们先从$n-k+1$输出到$n$，再从$1$输出到$n-k$。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define endl '\n'
#define PII pair<LL, LL>
const int maxn = 2e5 + 10;
const int INF = 2e9 + 5;
const int mod = 998244353;
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n, k;cin >> n >> k;vector<int> a(n + 1);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; i++)cout << a[i] << " ";cout << endl;return 0;
}

B.Decrease 2 max elements（模拟）

题意：

给你一个由 $N$个正整数 $A=(A\_1,A\_2,\dots ,A\_N)$组成的序列。高桥重复下面的操作，直到 $A$包含的正整数元素不超过一个：

• 按降序排列 $A$。然后将 $A\_1$和 $A\_2$减少 $1$。

询问他执行此操作的次数。

分析：

我们用优先队列进行模拟，每次取出两个最小的，分别减$1$，再加回到队列。直到第二小的不为正数。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define endl '\n'
#define PII pair<LL, LL>
const int maxn = 2e5 + 10;
const int INF = 2e9 + 5;
const int mod = 998244353;
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin >> n;priority_queue<int> tmp;for (int i = 1; i <= n; i++){int x;cin >> x;tmp.push(x);}int ans = 0;while (1){int a = tmp.top();tmp.pop();int b = tmp.top();tmp.pop();if (b <= 0)break;a--;b--;ans++;tmp.push(a), tmp.push(b);}cout << ans << endl;return 0;
}

C.Triple Attack（思维）

题意：

你正在玩一个游戏。

有 $N$个敌人排成一排，最前面的 $i$个敌人的健康值是 $H\_i$。

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

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

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

分析：

我们发现每三次攻击敌人都会扣$5$滴血，对于敌人剩下小于$5$滴血的情况，我们特判攻击次数是否是三的倍数即可。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define endl '\n'
#define PII pair<LL, LL>
const int maxn = 2e5 + 10;
const int INF = 2e9 + 5;
const int mod = 998244353;
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin >> n;LL ans = 0;for (int i = 0; i < n; i++){int h;cin >> h;ans += (h / 5) * 3;h %= 5;while (h > 0){ans++;if (ans % 3 == 0){h -= 3;}else{h--;}}}cout << ans << endl;return 0;
}

D.Minimum Steiner Tree（DFS）

题意：

给你一棵树，树上有 $N$个顶点，编号为 $1$到 $N$。第$i$条边连接顶点 $A\_i$和 $B\_i$。

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

分析：

我们以第一个保留的点为根，进行$dfs$。在$dfs$过程中的当前点$u$，判断其是否需要保留，那么我们就需要知道其子树是否有需要保留的点，有则当前点$u$需要保留。因此$DFS$返回的东西即为该子树是否有需要保留的点。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define endl '\n'
#define PII pair<LL, LL>
const int maxn = 2e5 + 10;
const int INF = 2e9 + 5;
const int mod = 998244353;
vector<int> e[maxn];
int tmp[maxn], ans;
void dfs(int u, int fa)
{for (auto v : e[u]){if (v == fa)continue;dfs(v, u);if (tmp[v])tmp[u] = 1;}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n, k;cin >> n >> k;for (int i = 1; i < n; i++){int u, v;cin >> u >> v;e[u].push_back(v), e[v].push_back(u);}int x;for (int i = 1; i <= k; i++){cin >> x;tmp[x] = 1;}dfs(x, -1);for (int i = 1; i <= n; i++)ans += tmp[i];cout << ans << endl;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,\dots ,X\_M$，使得他们的和 $X\_2+\dots +X\_M$最小。

• 条件对于所有满足 $1\le i,j\le M$的一对 $(i,j)$，如果 $B\_i=A\_j$和 $T\_i\le S\_j$，那么 $T\_i+X\_i\le S\_j+X\_j$。

  • 换句话说，对于任何一对原本可以换乘的列车，即使将每列列车 $i$的出发和到达时间延迟 $X\_i$，仍然可以换乘。

可以证明，满足这样条件的 ，且和 $X\_2+\dots +X\_M$最小的序列$X\_2,\dots ,X\_M$是唯一的。

分析：

我们需要知道所有列车的最早发车时间。那么$X[i]=$开车时间 - 原始开车时间。所以我们将所有时间从小到大排序，遍历到的每一个出发时间，能赶上他的所有到达时间已经遍历过。那么这辆车的最早开车时间就是：所有能赶上他的车中，到达时间的最大值。这样就能得知所有的$X[i]$。 最后就只需要记录每个车站目前的最晚到达时间即可。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define endl '\n'
#define PII pair<LL, LL>
const int N = 2e5 + 10;
const int INF = 2e9 + 5;
const int mod = 998244353;
int n, m, x;
LL a[N], b[N], s[N], t[N], delay[N], arrival[N];
struct event
{LL type, time, id;
} tmp[N << 1];int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n, m, x;cin >> n >> m >> x;for (int i = 1; i <= m; i++){cin >> a[i] >> b[i] >> s[i] >> t[i];tmp[2 * i - 1] = {0, s[i], i};tmp[2 * i] = {1, t[i], i};}sort(tmp + 1, tmp + 2 * m + 1, [&](event a, event b){if (a.time == b.time) {return a.type > b.type;}return a.time < b.time; });delay[1] = x;for (int i = 1, stat; i <= 2 * m; i++){if (tmp[i].type == 0){stat = a[tmp[i].id];if (tmp[i].id != 1)delay[tmp[i].id] = max(0ll, arrival[stat] - tmp[i].time);}else{stat = b[tmp[i].id];arrival[stat] = max(arrival[stat], tmp[i].time + delay[tmp[i].id]);}}for (int i = 2; i <= m; i++)cout << delay[i] << " ";cout << endl;return 0;
}

F.Rearrange Query （博弈论）

题意：

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

• 自由选择一个整数 $i(1\le i\le N)$。然后，自由选择一个不是 $A\_i$本身的 、$A\_i$的因数 $x$，并用 $x$代替 $A\_i$。

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

分析：

每个$A[i]$可以操作的次数是$A[i]$的质因子个数，设为$B[i]$，那么所有的$B[i]$异或值不为$0$时，则先手必胜；否则，则先手必败。如果异或和为$0$，那么先手无论如何取数，后手都可以通过操作，使得异或和保持为$0$，直到数列$A$全为$0$，先手不能取数，必败。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define endl '\n'
#define PII pair<LL, LL>
const int N = 2e5 + 10;
const int INF = 2e9 + 5;
const int mod = 998244353;
int len[N];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin >> n;for (int i = 1; i <= 1e5; i++){for (int j = i * 2; j <= 1e5; j += i)len[j] = max(len[j], len[i] + 1);}int flag = 0;for (int i = 0; i < n; i++){int x;cin >> x;flag ^= len[x];}if (flag == 0)cout << "Bruno" << endl;elsecout << "Anna" << endl;return 0;
}
s

赛后交流

在比赛结束后，会在交流群中给出比赛题解，同学们可以在赛后查看题解进行补题。

群号： 704572101，赛后大家可以一起交流做题思路，分享做题技巧，欢迎大家的加入。