ABC311

V_Melville精進録 / 2023-07-24 / 原文

T1：First ABC

模拟

代码实现

n = int(input())
s = input()

A = B = C = False
for i in range(n):
    if s[i] == 'A': A = True
    if s[i] == 'B': B = True
    if s[i] == 'C': C = True
    if A and B and C: 
        exit(print(i+1))

T2：Vacation Together

暴力

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

int main() {
    int n, d;
    cin >> n >> d;
    
    vector<string> s(n);
    rep(i, n) cin >> s[i];
    
    string t;
    rep(i, d) {
        bool ok = true;
        rep(j, n) if (s[j][i] == 'x') ok = false;
        if (ok) t += 'o'; else t += 'x';
    }
    
    int ans = 0, now = 0;
    rep(i, d) {
        if (t[i] == 'o') now++; else now = 0;
        ans = max(ans, now);
    }
    
    cout << ans << '\n';
    
    return 0;
}

T3：Find it!

注意到无论从哪个点开始搜，最终都会走到环里，所以当第一次走到已经走过的点时可以再走一圈

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<int> a(n+1);
    rep(i, n) cin >> a[i+1];
    
    vector<int> id(n+1);
    int k = 1;
    int v = 1;
    while (id[v] == 0) {
        id[v] = k; k++;
        v = a[v];
    }
    
    vector<int> ans;
    int len = k-id[v];
    rep(i, len) {
        ans.push_back(v);
        v = a[v];
    }
    
    cout << len << '\n';
    for (int v : ans) cout << v << ' ';
    
    return 0;
}

T4：Grid Ice Floor

将 当前停在哪个方格 作为状态，沿着上下左右哪个方向进行 \(\operatorname{bfs}\)，同时记录下滑行途中经过的方格以及最终停在的方格！

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using P = pair<int, int>;

const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, 1, 0, -1};

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<string> s(n);
    rep(i, n) cin >> s[i];
    
    vector used(n, vector<bool>(m));
    vector passed(n, vector<bool>(m));
    queue<P> q;
    q.emplace(1, 1); 
    passed[1][1] = used[1][1] = true;
    while (q.size()) {
        auto [i, j] = q.front(); q.pop();
        rep(v, 4) {
            int ni = i, nj = j;
            while (s[ni][nj] == '.') {
                passed[ni][nj] = true;
                ni += di[v]; nj += dj[v];
            }
            ni -= di[v]; nj -= dj[v];
            if (used[ni][nj]) continue;
            used[ni][nj] = true;
            q.emplace(ni, nj);
        }
    }
    
    int ans = 0;
    rep(i, n)rep(j, m) if (passed[i][j]) ans++;
    
    cout << ans << '\n';
    
    return 0;
}