AtCoder Beginner Contest 301

2023-05-13 23:35 由 ~Lanly~ 发表于 #其他

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;
}