AtCoder Beginner Contest 348 A~F

A. Penalty Kick(循环)

题意

有$n$轮比赛，已知在第$i$轮比赛中，如果$i$是$3$的倍数，那么将会输掉这场比赛，否则将会赢下这场比赛，请你输出一个序列表示每轮比赛的结果（o表示赢，x表示输）。

分析

使用循环进行判断输出即可。

代码

#include<bits/stdc++.h>
using namespace std;void solve() {int n;cin >> n;for (int i = 1; i <= n; i++) {if (i % 3 == 0) {cout << "x";} else {cout << "o";}}
}int main() {solve();return 0;
}

B.Farthest Point(枚举)

题意

给出二维坐标系上的$N$个点，请你输出每个点距离最远的点的编号是什么（只比较与其他$N-1$个点的距离，如果存在多个距离相等的点，输出编号最小的一个）。

分析

对于每个点，枚举其他的$N-1$个点，记录距离最远的点即可。

代码

#include<bits/stdc++.h>
using namespace std;int x[105], y[105];void solve() {int n;cin >> n;for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];for (int i = 1; i <= n; i++) {int len = -1, id = i;for (int j = 1; j <= n; j++) {int l = (x[j] - x[i]) * (x[j] - x[i]) + (y[j] - y[i]) * (y[j] - y[i]);if (l > len) {len = l;id = j;}}cout << id << endl;}
}int main() {solve();return 0;
}

C.Colorful Beans(map)

题意

有$N$种糖豆，每种糖豆都有一个美味值以及一个颜色，由于所有豆子都被混在一起，我们只能根据颜色来分辨出不同的豆子。

请你选出一种颜色的一个豆子，问能获得的最大的最小美味值是多少。

分析

考虑最坏情况，即无论选择哪种颜色的豆子，被选出的豆子均为该颜色豆子中美味值最小的一个，那么可以将所有颜色的豆子均视为只存在美味值最低的那一颗，然后统计所有颜色豆子美味值最低的那一颗中的最大值即可，由于数据规模较大，可以使用map对颜色和美味值进行存储。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;map<ll, ll> P;void solve() {int n;cin >> n;for (int i = 1; i <= n; i++) {ll a, c;cin >> a >> c;if (P.find(c) == P.end()) {P[c] = a;} else {P[c] = min(P[c], a);}}ll maxn = -1;for (auto i : P) {maxn = max(maxn, i.second);}cout << maxn << endl;
}int main() {solve();return 0;
}

D.Medicines on Grid(DFS)

题意

有一个$H\times W$的网格，网格中每个$1\times 1$的小方格中包含以下四种内容之一：

• '.':表示空格子

• '#':表示存在一个障碍物

• 'S':表示起点

• 'T':表示终点

每次移动到四方向上相邻的格子中，均会消耗$1$点能量，当能量为$0$时，将不能再移动。

在网格中，其中$N$个格子中包含着药品，使用第$i$个药品会将能量值设置为$E_i$。他只能在这个药品对应的格子上使用药品，不能将药品带出格子，且药品使用后就会消失。

问：以$0$点初始能量从起点出发，能否到达终点。

分析

本题看上去是一个经典的DFS问题，但数据规模较大，如果想要使用DFS算法通过，需要优化掉很多多余的操作。

优化1：inline关键字

在DFS函数前加上inline关键字，降低函数调用开销

inline void dfs(...) {...
}

优化2：找到答案后就不需要搜索了

由于题目只问是否有解，那么可以使用变量$flag$记录是否找到过答案，到达终点后将$flag$标记为$1$，并在$dfs$开头进行判断，如果$flag=1$，直接return，不需要继续查找。

Tips: 本优化在极限数据下无效

优化3：当前解不可能为最优解的就排除掉

对于多次到达某个点，可以想到，如果之前到达点$(i,j)$的剩余能量更多，那么我们当前继续走下去必然不会比前面方案更优，因此，可以使用一个$maxn$数组，使用$maxn[i][j]$表示曾经到达点$(i,j)$的最大能量，并在dfs开头判断，如果当前走到这个点的能量不如记录的$maxn[i][j]$，直接return。

优化4：去掉多余判断

由于网格上进行搜索需要判断是否出界和点是否为障碍物，因此需要额外的5条判断代码，我们可以想办法把这5条代码优化掉。

将maxn数组初始化为极大值，然后将所有能走的点（'.', 'S'. 'T'）修改为-1，同时将坐标均设置为从$1$开始，即行为$1\sim h$，列为$1\sim w$，那么所有不能走的点的maxn数组记录的值均为极大值，如果走到该点就会直接return，不再需要对边界以及不能走的点进行判断。

代码（可以在C++20下通过）

#include<bits/stdc++.h>
using namespace std;int h, w, fx, fy;
char c[305][305];int e[305][305], vis[305][305];int flag;inline void dfs(int x, int y, int cnt) {if (flag || cnt <= vis[x][y]) return;if (c[x][y] == 'T') {flag = 1;return;}cnt = cnt < e[x][y] ? e[x][y] : cnt;vis[x][y] = cnt;if (!cnt) return;int num = e[x][y];e[x][y] = 0;dfs(x + 1, y, cnt - 1);dfs(x - 1, y, cnt - 1);dfs(x, y - 1, cnt - 1);dfs(x, y + 1, cnt - 1);e[x][y] = num;
}void solve() {cin >> h >> w;memset(vis, 0x3f, sizeof(vis));for (int i = 1; i <= h; i++) {for (int j = 1; j <= w; j++) {cin >> c[i][j];if (c[i][j] == 'S') {fx = i;fy = j;}if (c[i][j] != '#') {vis[i][j] = -1;}}}int n;cin >> n;for (int i = 1; i <= n; i++) {int r, C, E;cin >> r >> C >> E;e[r][C] = max(e[r][C], E);}dfs(fx, fy, 0);if (flag == 1) cout << "Yes" << endl;else cout << "No" << endl;
}int main() {solve();return 0;
}

E.Minimize Sum of Distances(DFS)

题意

给出一个包含$N$个点，$N-1$条边的无向图（保证给出的图是一棵树），图上第$i$条边连接着点$a_i$和$b_i$。

给出一个序列$C=(C_1,C_2,\dots ,C_N)$，$C_i$表示结点$i$的权值。并定义$d(a,b)$为点$a$和$b$之间的距离。并对于每个节点$x(x=1,2,\dots ,N)$，定义$f(x)=\sum _{i=1}^N(C_i\times d(x,i))$，请你找到$\underset{1\le v\le N}{\min }f(v)$。

分析

假设以节点$k$为根节点，那么$f(k)$实际上就是$\sum _{i=1}^N(C_i\times deep[i])$（根节点深度为0），因此每个点到达根节点的距离就等于深度。

然后考虑树上每个节点$x$的$f(x)$是多少，不难想到，当从子树的根节点走向某个子结点时，与走向的子结点中包含的所有结点的距离均会减少$1$，而与树上其他所有结点的距离都会增加$1$，因此，可以使用数组$su{m}_C[i]$记录以$i$为根节点的子树的节点权值之和，而整棵树的权值之和减去该子树的权值之和即为需要加上的部分，即：

• $f(v)=f(u)-su{m}_C[v]+su{m}_C[1]-su{m}_C[v]=f(u)+su{m}_C[1]-2\ast su{m}_C[v];$(这里以结点1作为根节点，v为u的直接子结点)

任选一个结点建树，并维护$su{m}_C$数组，然后再使用一次dfs，枚举所有树上的点，记录最小的$f(i)$即为最后的答案。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5e2;vector<int> G[N];
ll n, deep[N], C[N], sum_C[N], ans;void dfs(int u, int pre) {ans += deep[u] * C[u];sum_C[u] = C[u];for (auto v : G[u]) {if (v == pre) continue;deep[v] = deep[u] + 1;dfs(v, u);sum_C[u] += sum_C[v];}
}void dfs2(int u, int pre, ll sum) {for (auto v : G[u]) {if (v == pre) continue;ll cnt = sum + sum_C[1] - 2 * sum_C[v];ans = min(ans, cnt);dfs2(v, u, cnt);}
}void solve() {cin >> n;for (int i = 2; i <= n; i++) {int a, b;cin >> a >> b;G[a].push_back(b);G[b].push_back(a);}for (int i = 1; i <= n; i++) cin >> C[i];dfs(1, -1);dfs2(1, -1, ans);cout << ans << endl;
}int main() {solve();return 0;
}

F.Oddly Similar(bitset)

题意

给出$N$个包含$M$个元素的序列，如果两个序列$X$和$Y$满足相同下标上相同的数字数量为奇数的话，那么就认为这两个序列是相似的，问：给出的$N$个序列中，有多少对序列是相似的。

分析

考虑使用$bitset$进行优化，使用$bt[i][j][k]$表示第$i$列数字$j$在第$k$行的状态，当$bt[i][j][k]=1$表示第$k$行第$i$列上的数字为$j$。

那么为什么要这么做呢？

首先，要想知道前面的$1\sim k-1$行有多少个数字与当前这一行的第$i$列的数字相同，那么只需要检查$bt[i][j]$表示的二进制串上有多少个$1$即可。

怎么判断前面所有行中多少行相同下标的数字数量为奇数呢？

使用一个$bitset$ $T$表示第$k$行与前面$k-1$行的相似情况，即使用$T[x]=1$表示第$x$行与第$k$行相似。由于奇数个相同才算相似，因此，让每列相同的行状态二进制串$bt[i][j]$与$T$进行异或运算，那么结束运算后，如果某行与第$k$行有奇数个想同下标相同的数字，那么结果的二进制串中对应位置必然为$1$，否则为$0$。

每轮记录$T$中包含多少个$1$，即为当前第$k$行与前面$k-1$行有多少行相似。

代码

#include <bits/stdc++.h>using namespace std;const int N = 2005, M = 1005;int n, m, a[N][N];
bitset<N> T, bt[N][M];void solve() {cin >> n >> m;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> a[i][j];}}int ans = 0;for (int i = 0; i < n; i++) {T.reset();for (int j = 0; j < m; j++) {T ^= bt[j][a[i][j]];bt[j][a[i][j]].set(i);}ans += T.count();}cout << ans << endl;
}int main() {solve();return 0;
}

赛后交流

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

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