AtCoder Beginner Contest 348
A - Penalty Kick (abc348 A)
题目大意
给定\(n\)，输出 \(ooxooxoox...\)，长度为 \(n\)。
解题思路
按题意模拟即可。
神奇的代码
n = int(input())
ans = "oox" * (n // 3) + "o" * (n % 3)
print(ans)
B - Farthest Point (abc348 B)
题目大意
给定\(n\)个点，对每个点，求出与其距离最远的点的下标。
解题思路
\(n\)只有 \(100\)，对于每个点，花 \(O(n)\)遍历每个点最大化距离，时间复杂度为 \(O(n^2)\)。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<array<int, 2>> p(n);
for (auto& i : p)
cin >> i[0] >> i[1];
for (int i = 0; i < n; ++i) {
int dis = 0, ans = 0;
for (int j = 0; j < n; ++j) {
if (i == j)
continue;
int dis1 = (p[i][0] - p[j][0]) * (p[i][0] - p[j][0]) +
(p[i][1] - p[j][1]) * (p[i][1] - p[j][1]);
if (dis1 > dis) {
dis = dis1;
ans = j;
} else if (dis1 == dis) {
ans = min(ans, j);
}
}
cout << ans + 1 << '\n';
}
return 0;
}
C - Colorful Beans (abc348 C)
题目大意
\(n\)个豌豆，每个豌豆有美味值 \(a\)和颜色值 \(c\)。
豌豆之间只有颜色区别。
现在你会从一种颜色的豌豆里选一个豌豆出来。
最大化选出来的豌豆美味值的最小值。
解题思路
选定一个颜色，最坏情况就是选出了这个颜色中美味值最小的豌豆。
因此对每种颜色求出美味值最小的豌豆，然后所有颜色（决策）的美味值取个最大值即为答案。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
map<int, int> minn;
for (int i = 0; i < n; i++) {
int a, c;
cin >> a >> c;
if (minn.find(c) == minn.end()) {
minn[c] = a;
} else
minn[c] = min(minn[c], a);
}
int ans = minn.begin()->second;
for (auto& [c, a] : minn) {
ans = max(ans, a);
}
cout << ans << '\n';
return 0;
}
D - Medicines on Grid (abc348 D)
题目大意
二维网格，起点终点，有障碍物，有药，药的作用是将体力值变为\(c_i\)。
初始起点，体力值为 \(0\)，问能否走到终点。
解题思路
考虑朴素搜索，记录状态\((i,j,k)\)，表示位于 \((i,j)\)，当前体力值为 \(k\)，然后枚举四个方向搜索后继情况。
考虑总情况数，即 \(O(200^2 \times 200^2)\)，有点危险，可以加一些剪枝，比如设 \(dis[i][j]\)表示到达 \((i,j)\)时的最大体力，采用 \(SPFA\)式的搜索即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int h, w;
cin >> h >> w;
vector<string> tu(h);
for (auto& i : tu)
cin >> i;
vector<vector<int>> dp(h, vector<int>(w, -1));
vector<vector<int>> med(h, vector<int>(w, -1));
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int r, c, e;
cin >> r >> c >> e;
--r, --c;
med[r][c] = e;
}
queue<pair<int, int>> q;
vector<vector<int>> inq(h, vector<int>(w, 0));
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (tu[i][j] == 'S') {
dp[i][j] = med[i][j];
q.push({i, j});
inq[i][j] = 1;
}
}
}
const array<int, 4> dx = {0, 0, 1, -1};
const array<int, 4> dy = {1, -1, 0, 0};
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
inq[x][y] = 0;
if (dp[x][y] <= 0)
continue;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx >= h || ny < 0 || ny >= w || tu[nx][ny] == '#')
continue;
if (dp[nx][ny] < dp[x][y] - 1) {
dp[nx][ny] = max(dp[x][y] - 1, med[nx][ny]);
if (tu[nx][ny] == 'T')
break;
if (!inq[nx][ny]) {
q.push({nx, ny});
inq[nx][ny] = 1;
}
}
}
}
int ok = false;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (tu[i][j] == 'T' && dp[i][j] >= 0) {
ok = true;
break;
}
}
}
if (ok) {
cout << "Yes\n";
} else {
cout << "No\n";
}
return 0;
}
E - Minimize Sum of Distances (abc348 E)
题目大意
给定一棵树，点有点权\(c_i\)，边权为\(1\)。
定义 \(f(x) = \sum_{i}c_i dis(x, i)\)，其中\(dis(x,i)\)表示点 \(x\)到点 \(i\)的最小距离。
求\(f(x)\)的最小值。
解题思路
朴素求法即\(O(n^2)\)。枚举每个点\(x\)，然后求一遍 \(dis(x,i)\) ，然后计算\(f(x)\)，取最小值。枚举每个点耗时 \(O(n)\)，计算 \(f(x)\)耗时 \(O(n)\)。
考虑优化 \(f(x)\)的计算。注意到是棵树，我们一般考虑先枚举根 \(0\)，计算 \(f(0)\)，然后考虑枚举 \(0\)的儿子 \(x\)，看看 \(f(x)\)能否从 \(f(0)\)得到。
枚举的点从 \(0 \to x\)，考虑\(f(0) \to f(x)\)的计算变化，只有\(dis(0,i)\)变成 \(dis(x,i)\)， 其中\(i \in x\)的子树的 \(dis(x,i) = dis(0,i) - 1\)，其余的 \(i\)的 \(dis(x, i) = dis(0,i) + 1\)。
即 \(f(0) = \sum_{i}c_i dis(0, i)\)，这是我们已经算出来的。
当\(0 \to x\)时，\(f(x) = \sum_{i}c_i dis(x, i) = \sum_{i \in x\text{子树}}c_i (dis(0, i) - 1) + \sum_{i \notin x\text{子树}}c_i (dis(0, i) + 1) = \sum_{i}c_i dis(0, i) - \sum_{i \in x\text{子树}} c_i + \sum_{i \notin x\text{子树}}c_i\)
代入\(f(0) = \sum_{i}c_i dis(0, i)\)得，\(f(x)= f(0) - \sum_{i \in x\text{子树}} c_i + \sum_{i \notin x\text{子树}}c_i\)
因此我们预处理\(sum_x\)表示以 \(x\)为子树的 \(c_i\)的和， \(sum\)是所有的 \(c_i\)的和，那不在 \(x\)的子树的 \(c_i\)的和可以表示成 \(sum - sum_x\)。这样当 \(0 \to x\)时， \(f(x)\)就可以通过 \(f(0),sum_x,sum\)在 \(O(1)\)内算出来了。
总的时间复杂度变为 \(O(n)\)。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<vector<int>> edge(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u--;
v--;
edge[u].push_back(v);
edge[v].push_back(u);
}
vector<int> c(n);
for (auto& x : c)
cin >> x;
LL sum = accumulate(c.begin(), c.end(), 0ll);
vector<LL> csum(n);
LL f = 0;
auto dfs = [&](auto self, int u, int fa, int deep) -> void {
for (auto v : edge[u]) {
if (v == fa)
continue;
self(self, v, u, deep + 1);
csum[u] += csum[v];
}
f += 1ll * c[u] * deep;
csum[u] += c[u];
};
dfs(dfs, 0, 0, 0);
LL ans = f;
auto dfs2 = [&](auto self, int u, int fa) -> void {
ans = min(ans, f);
for (auto v : edge[u]) {
if (v == fa)
continue;
f -= csum[v];
f += sum - csum[v];
self(self, v, u);
f -= sum - csum[v];
f += csum[v];
}
};
dfs2(dfs2, 0, 0);
cout << ans << '\n';
return 0;
}
F - Oddly Similar (abc348 F)
题目大意
给定\(n\)个序列\(a_i\)，长度为\(m\)，问俩俩序列相似的对数。
俩序列相似，说明有奇数个位置，其数相同。
解题思路
考虑朴素做法，枚举两个序列，然后枚举下标，记录数相同的个数，其时间复杂度是\(O(n^2m)\)。判断数相同如果不用 \(if\)的话，在 \(clang\)下能跑过（吸氧太猛了。
n3方过2e3
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m, 0));
for (auto& x : a)
for (auto& y : x)
cin >> y;
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int sum = 0;
for (int k = 0; k < m; k++) {
sum ^= (a[i][k] == a[j][k]);
}
ans += sum;
}
}
cout << ans << '\n';
return 0;
}
朴素做法是\(O(nnm)\)，分别是枚举\(j\)（一行），枚举 \(i\)（另一行），再枚举 \(k\)（列）。考虑对其中一个因素优化。经过尝试，我们可以对枚举\(i\)优化。
其实\(O(nnm)\)是非常接近 \(10^9\)的，一般是可以采用 \(bitset\)优化，总复杂度可以除以 \(64\)。
我们记\(cnt[k][l]\)表示第 \(k\)列值为 \(l\)的那些行的情况，即一个 \(bitset\)， \(cnt[k][l][i]=1\)表示第\(i\)行 第\(k\)列的值为\(l\)， \(=0\)则不为 \(l\)。
枚举一行 \(j\)，然后枚举一列 \(k\)，我们将所有的 \(cnt[k][a_{j,k}]\)（这些都是 \(bitset\)）异或起来，最后得到的就是第 \(j\)行与其余行的相似度情况（同下标数相等的个数的奇偶性），统计其为 \(1\)的个数即为 \((i,j)\)相似的 \(i\)的数量。注意要把 \(i=j\)的情况去掉。
时间复杂度是\(O(\frac{n^2m}{64})\)
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
vector<vector<bitset<2000>>> cnt(m, vector<bitset<2000>>(1000));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
--a[i][j];
cnt[j][a[i][j]][i] = 1;
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
bitset<2000> s{};
for (int j = 0; j < m; j++) {
s ^= cnt[j][a[i][j]];
}
s[i] = 0;
ans += s.count();
}
ans /= 2;
cout << ans << '\n';
return 0;
}
G - Max (Sum - Max) (abc348 G)
题目大意
给定长度为\(n\)的数组 \(a,b\)，对 \(k = 1,2,...,n\)，求解以下答案。
选择\(k\)个下标，使得 \(\sum_{k} a_k - \max_{k} b_k\) 最大。
解题思路
<++>
神奇的代码