title: AtCoder Beginner Contest 301categories: 算法题解description: 咕咕咕tags:  - Atcoder  - 贪心  - BFS  - DPcover: /img/chino/vec/chino17.jpgkatex: truedate: 2023-05-13 22:47:31

A – Overall Winner (abc301 a)题目大意

给定一个字符串表示高桥和青木每局的获胜情况。

如果高桥获胜局数多，或者两个胜局相等，但高桥率先取得那么多胜场，则高桥获胜，否则青木获胜。

问谁获胜。

解题思路

按照题意，统计两者的获胜局数比较即可。

如果两者局数相等，可以看最后一局谁胜，青木胜则意味着高桥率先取得那么多胜场，即高桥胜，反之青木胜。

神奇的代码
#include 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 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 > 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 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 cnt[2];    for(int j = 0; j <= 1; ++ j)        for(auto &i : s[j])            cnt[j][i] ++;    set target{'a', 't', 'c', 'o', 'd', 'e', 'r'};    auto ok1 = [&](){        for(int i = 'a'; i = 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 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 >= 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 using namespace std;using LL = long long;const int inf = 1e9 + 7;const array 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 tu(h);    for(auto &i : tu)        cin >> i;    int candy = 0;    for(auto &i : tu)        candy += count(i.begin(), i.end(), 'o');    vector<vector> dis(candy, vector(candy, 0));    map<array, int> tr;    map<int, array> invtr;    vector<vector> tmpdis(h, vector(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> 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 = 0 && 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> dp((1 << candy), vector(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 > j) & 1){                    for(int k = 0; k > 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)题目大意

解题思路

神奇的代码