AtCoder Beginner Contest 301
title: AtCoder Beginner Contest 301
categories: 算法题解
description: 咕咕咕
tags:
- Atcoder
- 贪心
- BFS
- DP
cover: /img/chino/vec/chino17.jpg
katex: true
date: 2023-05-13 22:47:31
A - Overall Winner (abc301 a)
题目大意
给定一个字符串表示高桥和青木每局的获胜情况。
如果高桥获胜局数多，或者两个胜局相等，但高桥率先取得那么多胜场，则高桥获胜，否则青木获胜。
问谁获胜。
解题思路
按照题意，统计两者的获胜局数比较即可。
如果两者局数相等，可以看最后一局谁胜，青木胜则意味着高桥率先取得那么多胜场，即高桥胜，反之青木胜。
神奇的代码
#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;
string s;
cin >> n >> s;
int t = count(s.begin(), s.end(), 'T'), a = n - t;
if (t > a || (t == a && s.back() == 'A'))
cout << "T" << '\n';
else
cout << "A" << '\n';
return 0;
}
B - Fill the Gaps (abc301 b)
题目大意
给定一个序列，对于两个相邻元素，若其值不是相邻的，则补充之间的值。
问最终的序列。
解题思路
按照题意模拟即可。
神奇的代码
#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, la;
cin >> n >> la;
cout << la;
for(int i = 1; i < n; ++ i){
int x;
cin >> x;
for(int d = (x - la) / abs(x - la), cur = la + d; cur != x; cur += d)
cout << ' ' << cur;
cout << ' ' << x;
la = x;
}
cout << '\n';
return 0;
}
C - AtCoder Cards (abc301 c)
题目大意
给定两个长度相等的字符串\(s_1, s_2\)，包含小写字母和@，问能否将@替换成atcoder中的一个字母，可以通过对其中一个字符串排序，使得两者相同。
解题思路
由于可以排序，我们只考虑两者的每个字母个数相同。
因为?只能替换成atcoder中的一个字母，因此这些字母之外的字母的数量必须相等。
然后考虑\(s_1\)相对于 \(s_2\)，缺少的 atcoder的字母，如果其数量\(cnt\)小于 \(s_1\)的@数量，则可以通过 @替换满足缺少的字母。反之也考虑\(s_2\)相对于\(s_1\)的情况。
如果两者都满足，那么两个就只剩下@了，这个肯定可以满足题意要求的。
神奇的代码
#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);
string s[2];
cin >> s[0] >> s[1];
map<char, int> cnt[2];
for(int j = 0; j <= 1; ++ j)
for(auto &i : s[j])
cnt[j][i] ++;
set<char> target{'a', 't', 'c', 'o', 'd', 'e', 'r'};
auto ok1 = [&](){
for(int i = 'a'; i <= 'z'; ++ i){
if (target.find(i) != target.end())
continue;
if (cnt[0][i] != cnt[1][i])
return false;
}
return true;
};
auto ok2 = [&](int x, int y){
int at = count(s[x].begin(), s[x].end(), '@'), tot = 0;
for(auto &i : target){
tot += max(cnt[y][i] - cnt[x][i], 0);
}
return at >= tot;
};
if (!ok1() || !ok2(0, 1) || !ok2(1, 0))
cout << "No" << '\n';
else
cout << "Yes" << '\n';
return 0;
}
D - Bitmask (abc301 d)
题目大意
给定一个包含\(01\)和 ?的字符串，将?替换成\(0\)或 \(1\)，使得其表示的二进制是最大的，且不大于\(t\)的。问这个的最大值。
解题思路
由于二进制下，任意个数的低位的\(1\)加起来都不如一个高位的 \(1\)。因此我们就从高位考虑每个 ?，如果替换成\(1\)之后不超过 \(t\)，就换成 \(1\)，否则就换成 \(0\)。
神奇的代码
#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);
string s;
LL n;
cin >> s >> n;
LL cur = 0;
for(auto &i : s){
cur <<= 1;
if (i != '?')
cur |= (i - '0');
}
LL ji = (1ll << (s.size() - 1));
for(auto &i : s){
if (i == '?' && cur + ji <= n)
cur += ji;
ji >>= 1;
}
if (cur > n)
cur = -1;
cout << cur << '\n';
return 0;
}
E - Pac-Takahashi (abc301 e)
题目大意
二维迷宫，有一个起点和一个终点，有墙，有最多\(18\)个糖果。问从起点到终点，移动距离不超过 \(t\)的情况下，能获得的糖果数量的最大值。
解题思路
考虑搜索，虽然可移动的范围挺大的，但是我们可以进行压缩，即可以只考虑从起点到糖果、糖果到糖果、糖果到终点，这三类关键操作。
首先通过多次\(BFS\)获得糖果之间的移动距离。
由于糖果只能获得一次，因此当我们抵达某个位置时，需要判断这个位置是否曾经抵达过，需要一个\(01\)状态 \(s\)表示我们获得了哪些糖果。
既然是搜索，肯定还有个状态是我们当前所在的位置，然后转移就是寻找下一个未获得的糖果位置或者终点。
记忆化一下就可以了。
即设 \(dp[i][j]\)表示当前糖果的获得状态是 \(i\)，当前在第 \(j\)个糖果的位置时，移动距离的最小值。
取抵达终点的移动距离不大于 \(t\)的所有 \(i\)中二进制下 \(1\)的最大值即为答案。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int inf = 1e9 + 7;
const array<int, 2> dir[4]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int h, w, t;
cin >> h >> w >> t;
vector<string> tu(h);
for(auto &i : tu)
cin >> i;
int candy = 0;
for(auto &i : tu)
candy += count(i.begin(), i.end(), 'o');
vector<vector<int>> dis(candy, vector<int>(candy, 0));
map<array<int, 2>, int> tr;
map<int, array<int, 2>> invtr;
vector<vector<int>> tmpdis(h, vector<int>(w));
int cnt = 0, sx, sy, ex, ey;
for(int i = 0; i < h; ++ i)
for(int j = 0; j < w; ++ j)
if (tu[i][j] == 'o'){
tr[{i, j}] = cnt;
invtr[cnt] = {i, j};
cnt ++;
}else if (tu[i][j] == 'S'){
sx = i;
sy = j;
}else if (tu[i][j] == 'G'){
ex = i;
ey = j;
}
auto BFS = [&](int x, int y){
for(auto &i : tmpdis)
fill(i.begin(), i.end(), inf);
tmpdis[x][y] = 0;
queue<array<int, 2>> team;
team.push({x, y});
while(!team.empty()){
auto [u, v] = team.front();
team.pop();
for(const auto& [dx, dy] : dir){
int nx = u + dx, ny = v + dy;
if (nx >= 0 && nx < h && ny >= 0 && ny < w && tu[nx][ny] != '#' && tmpdis[nx][ny] > tmpdis[u][v] + 1){
tmpdis[nx][ny] = tmpdis[u][v] + 1;
team.push({nx, ny});
}
}
}
};
for(auto &[key, value] : tr){
BFS(key[0], key[1]);
for(auto &[pos, id] : tr){
dis[value][id] = tmpdis[pos[0]][pos[1]];
}
}
vector<vector<int>> dp((1 << candy), vector<int>(candy, inf));
BFS(sx, sy);
if (tmpdis[ex][ey] > t)
cout << -1 << '\n';
else{
for(auto &[pos, id] : tr)
dp[(1 << id)][id] = tmpdis[pos[0]][pos[1]];
BFS(ex, ey);
int ans = 0;
for(int i = 1, up = (1 << candy); i < up; ++ i){
for(int j = 0; j < candy; ++ j){
if ((i >> j) & 1){
for(int k = 0; k < candy; ++ k){
if (((~i >> k) & 1) && dp[i][j] + dis[j][k] <= t){
dp[i | (1 << k)][k] = min(dp[i | (1 << k)][k], dp[i][j] + dis[j][k]);
}
}
if (dp[i][j] + tmpdis[invtr[j][0]][invtr[j][1]] <= t)
ans = max(ans, __builtin_popcount(i));
}
}
}
cout << ans << '\n';
}
return 0;
}
F - Anti-DDoS (abc301 f)
题目大意
给定一个包含大小写字母和?的字符串\(s\)，将 ?替换成大小写字母。问有多少种替换情况，使得替换后的字符串不包含DDoS类型的子序列。
DDoS类型的字符串满足，长度为\(4\)，第 \(1,2,4\)字母是大写，第 \(3\)字母是小写，且第 \(1,2\)字母相同。
解题思路
<++>
神奇的代码
G - Worst Picture (abc301 g)
题目大意
<++>
解题思路
<++>
神奇的代码
Ex - Difference of Distance (abc301 h)
题目大意
<++>
解题思路
<++>
神奇的代码