AtCoder Beginner Contest 303 题解 A - E

A - Similar String

题目大意

忽略0和o的差别以及1和l的差别比较两个字符串。

解题思路

1. 可以硬求，直接写个超长的if判断一下。
2. 可以对两个字符串进行修改，0都换成o，1都换成l，然后直接比较两个字符串。

AC Code

硬求

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <map>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 1e5 + 10;
const int MOD = 1e9 + 7;

void solve() {
    int n;
    string s1, s2;
    cin >> n >> s1 >> s2;
    for (int i = 0; i < n; ++i) {
        if (s1[i] != s2[i] && !(s1[i] == '1' && s2[i] == 'l') && !(s1[i] == 'l' && s2[i] == '1') && !(s1[i] == '0' && s2[i] == 'o') && !(s1[i] == 'o' && s2[i] == '0')) {
            cout << "No" << endl;
            return;
        }
    }
    cout << "Yes" << endl;
}

signed main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}

替换

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <map>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 1e5 + 10;
const int MOD = 1e9 + 7;

void solve() {
    int n;
    string s1, s2;
    cin >> n >> s1 >> s2;
    for (int i = 0; i < n; ++i) {
        if (s1[i] == '0') {
            s1[i] = 'o';
        } else if (s1[i] == '1') {
            s1[i] = 'l';
        }
        if (s2[i] == '0') {
            s2[i] = 'o';
        } else if (s2[i] == '1') {
            s2[i] = 'l';
        }
    }
    cout << (s1 == s2 ? "Yes" : "No") << endl;
}

signed main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}

B - Discord

题目大意

给定 \(n\) 个人在一起拍的 \(m\) 张照片，如果两个人没有挨在一起过就会生气。问生气的两人组的组数。

解题思路

这种说法很像图论中的无向边，考虑到数据范围很小，我们可以使用一个邻接矩阵存放每两人之间的关系，遍历找出没有挨在一起的组数即可。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <map>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 60;
const int MOD = 1e9 + 7;

bool a[N][N];

void solve() {
    int n, m;
    cin >> n >> m;
    int tmp = 0;
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            int x;
            cin >> x;
            a[x][tmp] = true;
            a[tmp][x] = true;
            tmp = x;
        }
        tmp = 0;
    }
    LL cnt = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            if (!a[i][j]) cnt++;
        }
    }
    cout << cnt << endl;
}

signed main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}

C - Dash

题目大意

高橋社长在二维平面上按照给出的指令行动，图上有 \(m\) 个回血道具，如果血量低于 \(k\) 就回到 \(k\)，同时消耗掉这个道具。每走一步就会扣一点血，问最终高橋社长能否走完指令。

解题思路

按照题目意思模拟即可，但是本题的范围由绝对值确定，所有需要开两倍大小的数组，然后将原点设在中心，不过显然我们不能开一个巨大无比的二维数组，所以可以使用一个map数组代替。不过我赛时交了个错的代码因为数据不够强过了，我把二维映射到了一维，居然数据没有卡掉这个bug。

AC Code

学长的正解

#include<functional>
#include<iostream>
#include<map>
#include<string>
#include<unordered_map>
#include<vector>
#include<stack>
using namespace std;
typedef long long ll;
#pragma G++ optimize (3)
#define int ll
#define inc(i, l, r) for(ll i=l;i<=r;i++)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl "\n"

ll inf;
map<int,int>mpp[400200];

signed main() {
    inf = 998244353;
    IOS;
    inf = 1e9 + 7;
    int _ = 1;
    //cin >> _;
    while (_--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        string s;
        cin >> s;

        inc(i, 1, b) {
            int x, y;
            cin >> x >> y;
            mpp[x + 200000][y + 200000]++;
        }
        int x = 0, y = 0;
        int pd = 1;
        inc(i, 0, a - 1) {
            c--;
            if (c < 0) {
                pd = 0;
                break;
            }
            if (s[i] == 'U')y++;
            else if (s[i] == 'D')y--;
            else if (s[i] == 'L')x--;
            else x++;
            if (mpp[x + 200000][y + 200000] && c < d) {
                mpp[x + 200000][y + 200000]--;
                c = d;
            }
        }
        if (pd)cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

蒟蒻的错解

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <map>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 4e5 + 10;
const int MOD = 1e9 + 7;

int g[N];

void solve() {
    int n, m, h, k;
    string s;
    cin >> n >> m >> h >> k >> s;
    for (int i = 1; i <= m; ++i) {
        int x, y;
        cin >> x >> y;
        g[x + 200000] = y;
    }
    int xx = 0, yy = 0;
    for (int i = 0; i < n; ++i) {
        h--;
        if (h < 0) {
            cout << "No" << endl;
            return;
        }
        if (s[i] == 'R') {
            xx++;
        } else if (s[i] == 'L') {
            xx--;
        } else if (s[i] == 'U') {
            yy++;
        } else if (s[i] == 'D') {
            yy--;
        }
        if (g[xx + 200000] == yy && h < k) {
            h = k;
            g[xx + 200000] = -0x3f3f3f3f;
        }

    }
    cout << "Yes" << endl;
}

signed main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}

D - Shift vs. CapsLock

题目大意

我们需要输入一个只有A和a的字符串，有以下三种操作：

• 点一下A键，耗时 \(X\) 秒
• 按住SHIFT键，同时点一下A键，耗时 \(Y\) 秒
• 按一下CAPSLOCK键，耗时 \(Z\) 秒

起始状态下，屏幕没有任何字，大写锁定指示灯熄灭。

解题思路

三种操作方式，两种状态间有相关关系，具有无后效性，感觉就很像一个线性dp。

我们可以按照输入第 \(i\) 位，大写锁定状态为 \(j(0或1)\) 进行dp，注意单独输入 a 时，有两种可能，第一种是按下A键，第二种是先按CAPSLOCK，再按SHIFT + A，再根据当前dp状态决定是否需要再按一次CAPSLOCK。

最后记得取两种大写锁定状态的最小值。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <map>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 3e5 + 10;
const int MOD = 1e9 + 7;

LL dp[N][2];

void solve() {
    LL x, y, z;
    string s;
    cin >> x >> y >> z >> s;
    if (s[0] == 'a') {
        dp[0][0] = min(x, 2 * z + y);
        dp[0][1] = z + min(x, y);
    } else {
        dp[0][0] = min(y, 2 * z + x);
        dp[0][1] = z + min(x, y);
    }
    for (int i = 1; i < s.length(); ++i) {
        if (s[i] == 'A') {
            dp[i][1] = min(dp[i - 1][1] + min(x, 2 * z + y), dp[i - 1][0] + z + min(x, y));
            dp[i][0] = min(dp[i - 1][0] + min(y, 2 * z + x), dp[i - 1][1] + z + min(x, y));
        } else {
            dp[i][1] = min(dp[i - 1][0] + z + min(x, y), dp[i - 1][1] + min(y, 2 * z + x));
            dp[i][0] = min(dp[i - 1][1] + z + min(x, y), dp[i - 1][0] + min(2 * z + y, x));
        }
    }
    cout << min(dp[s.length() - 1][0], dp[s.length() - 1][1]);
}

signed main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}

E - A Gift From the Stars

题目大意

定义星星表示一个除了中间结点外的结点都连在中间结点上且度数为 \(1\) 的无向图，给定一个无向图，是将多个星星连接起来的，问给定的无向图删去加的边后，能找到的每个星星的大小（中心结点的度数）。

解题思路

首先我们使用一个邻接矩阵获取每个点的度数，随后遍历每个结点，找到度数为 \(1\) 的点，这个点就肯定是某个星星的枝，由这个结点出发，搜索对它连通的区域，使用一个计数变量op来记录我们走的步骤，考虑到：枝—中心—枝是一个三元组，计数变量在\((0\sim2)\)之间循环。每当计数变量取到 \(1\) 的时候，就是我们的中间结点，将这个星星的大小压到答案数组里，如此往复一次遍历每一个结点情况即可。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 2e5 + 10;
const int MOD = 1e9 + 7;

vector<vector<int>> g(N);
vector<int> res;

void dfs(int cur, int lst, int op) {
    if (op == 1) {
        res.push_back(g[cur].size());
    }
    for (auto i : g[cur]) {
        if (i != lst) {
            dfs(i, cur, (op + 1) % 3);
        }
    }
}

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i = 1; i <= n; ++i) {
        if (g[i].size() == 1) {
            dfs(i, 0, 0);
            break;
        }
    }
    sort(res.begin(), res.end());
    for (int i : res) {
        cout << i << ' ';
    }
    cout << endl;
}

signed main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}

本栏目推荐文章
• AT_arc125_c [ARC125C] LIS to Original Sequence 题解
• P5321 [BJOI2019] 送别 题解--zhengjun
• AtCoder World Tour 2022 B The Greatest Two
• 2021-2022 ICPC Northwestern European Regional Programming Contest (NWERC 2021)
• AtCoder Beginner Contest 335 G Discrete Logarithm Problems
• P9007 [入门赛 #9] 最澄澈的空与海 (Hard Version) 题解
• P2198 杀蚂蚁 题解
• P3243 [HNOI2015] 菜肴制作 题解
• AT_abc243_g [ABC243G] Sqrt题解
• AT_abc243_g [ABC243G] Sqrt题解

题解 Beginner AtCoder Contest 303beginner atcoder contest 303 题解beginner atcoder contest contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334