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)
題目大意
<++>
解題思路
<++>
神奇的代碼
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/552388.html
標籤：其他
上一篇：內網滲透基礎知識
下一篇：返回列表