AtCoder Beginner Contest 302 解题报告

LINK TO CONTEST

A - Attack

知识点：模拟
效率：$O(1)$

#include <iostream>
#include <queue>
#define pr pair<ll, ll>
#define ll long long
using namespace std;
int main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    ll A,B;
    cin >> A >> B;
    cout << A/B+int(A%B != 0);
}

B - Find snuke

知识点：搜索
效率：$O(n)$
按照题目往各个方向搜就行

#include <iostream>
#include <queue>
#include <list>
#include <stack>
#define pr pair<ll, ll>
#define ll long long
#define str string
using namespace std;
int main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    ll H,W;
    cin >> H >> W;
    vector<str> v(H);
    str target = "snuke";
    for(int i = 0;i < H;i++ ) cin >> v[i];
    auto flg = false;
    int dirs[8][2] = {
            0,1,1,0,-1,0,0,-1,
            1,1,-1,-1,1,-1,-1,1
                      };
    stack<pair<ll,ll>> res;
    std::function<bool(int,int,int,int)> dfs = [&](int x, int y, int now, int i) {
        //cout << x << " " << y  << v[y][x] << endl;
        if(now==4){
            res.push({x,y});
            flg = true;
            return true;
        }
            auto nx = x + dirs[i][0], ny = y + dirs[i][1];
            if(nx >= 0 && ny >= 0 && nx < W && ny < H
            && v[ny][nx] == target[now+1]) {
                if(dfs(nx,ny,now+1,i)){
                    res.push({x,y});
                    return true;
                }
            }
        return false;
    };
    for(int i = 0;i < H;i++) {
        for (int j = 0;j < W;j++) {
            if (v[i][j]=='s') for (int k = 0;k < 8;k++) {
                    dfs(j,i,0,k);
                    if (flg) break;
            }
            if (flg) break;
        }
        if (flg) break;
    }
    if(flg) {
        while(!res.empty()) {
            auto now = res.top();
            cout << now.second + 1 << " " << now.first + 1 << "\n";
            res.pop();
        }
    }
}

C - Find snuke

知识点：搜索
效率：$O(n)$

#include <iostream>
#include <queue>
#include <list>
#include <stack>
#define pr pair<ll, ll>
#define ll long long
#define str string
using namespace std;
vector<vector<bool>> dis;
vector<bool> vis;
ll H,W;
bool dfs(int now, int cnt) {
    //cout << now << " " << cnt << endl;
    if(cnt == H - 1) return true;
    vis[now] = true;
    bool res = false;
    for(int i = 0;i < H;i++) {
        //cout << i << " " << dis[now][i]  << " " << vis[i] << ";";
        if(!res && dis[now][i] && !vis[i]) {
            res |= dfs(i,cnt+1);
        }
    }
    vis[now] = false;
    return res;
}
int main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cin >> H >> W;
    vector<str> v(H);
    for(int i = 0;i < H;i++ ) cin >> v[i];
    dis = vector(H, vector<bool>(H, false));
    vis = vector<bool>(H, false);
    auto getF = [&](int a, int b)->bool {
        if(a==b) return false;
        int cnt = 0;
        for(int i = 0;i < v[a].size();i++)  {
            if(v[a][i] != v[b][i]) cnt += 1;
        }
        return cnt == 1;
    };
    for(int i = 0;i < H;i++) {
        for(int j = i + 1;j < H;j++) {
            dis[i][j] = dis[j][i] = getF(i,j);
            //cout << i << " " << j << " " << dis[i][j] << endl;
        }
    }
    for(int i = 0;i < H;i++) {
        if(dfs(i,0)) {
            cout << "Yes";
            return 0;
        }
    }
    cout << "No";
    return 0;


}

D - Impartial Gift

知识点：双指针
效率：$O(n)$

#include <iostream>
#include <queue>
#include <list>
#include <stack>
#include <algorithm>
#define pr pair<ll, ll>
#define ll long long
#define f(i,a,b) for(ll i = a;i <= b;i++)
#define abs(a,b) (a>b?a-b:b-a)
#define str string
using namespace std;
int main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    ll N,M,D;
    cin >> N >> M >> D;
    vector<ll> A(N);
    vector<ll> B(M);
    f(i,0,N-1) cin >> A[i];
    f(i,0,M-1) cin >> B[i];
    sort(A.begin(),A.end(), greater<ll>());
    sort(B.begin(),B.end(),greater<ll>());
    ll L=0,R=0;
    for(int L = 0;L < N;L++) {
        //cout << L << " " << R << endl;
        ll va = A[L], vb = B[R];
        //cout << va << " " << vb << endl;
        if(abs(va,vb) <= D) {
            cout << va+vb;
            return 0;
        }else{
            //L大了
            if(va > vb) continue;
            else{
                //R大了，找最近的R
                while(R<M-1&&vb>va) {
                    R++;
                    vb = B[R];
                    if(abs(va,vb) <= D) {
                        cout << va + vb;
                        return 0;
                    }
                }
            }
        }
    }
    cout << -1;
    return 0;


}

E - Isolation

知识点：图、缓存
效率：$O(nlogn)$

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, Q;
    cin >> N >> Q;
    vector<unordered_set<int>> graph(N + 1);
    vector<int> in_degree(N + 1, 0);

    int isolated = N; // Initially, all nodes are isolated

    while(Q--) {
        int type;
        cin >> type;
        if(type == 1) {
            int u, v;
            cin >> u >> v;
            if(!in_degree[u]) isolated--;
            if(!in_degree[v]) isolated--;
            graph[u].insert(v);
            graph[v].insert(u);
            in_degree[u]++;
            in_degree[v]++;
        } else {
            int v;
            cin >> v;
            if(in_degree[v]) {
                isolated++;
                for(auto u : graph[v]) {
                    in_degree[u]--;
                    if(!in_degree[u]) isolated++;
                    graph[u].erase(v); // Remove the edge from the adjacency set of the connected vertex
                }
                graph[v].clear();
                in_degree[v] = 0;
            }
        }
        cout << isolated << "\n";
    }
    return 0;
}