AtCoder Beginner Contest 299 解题报告

第二次参加，直接比一年以前退化成弱智

A - Treasure Chest

知识点：模拟、状态机
效率：$O(n)$
大意是找有没有||这样的模式，如果有就输出in，否则输出out
于是按题意模拟即可，设计状态机，只要结束的时候状态是1且遇到过即可

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n;
    string s;
    cin >> n >> s;
    int flg = 0;
    int ok = false;
    for(int i = 0;i < n;i++) {
        if (s[i]=='|') {
            flg += 1;
        }
        if (s[i] == '*' && flg == 1) {
            ok = true;
        }
    }
    cout << (ok?"in":"out");
}

B - Trick Taking

知识点：模拟
效率：$O(n)$
给定花色T，找花色T中最大的牌
但如果没有花色T的牌，就将第一个出牌人的花色转换为花色T

#include <iostream>
#include <vector>
#define ll long long
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    ll n, t;
    cin >> n >> t;
    vector<int> c(n+1);
    vector<int> r(n+1);
    for(int i = 0;i < n;i++) cin >> c[i];
    for(int i = 0;i < n;i++) cin >> r[i];
    ll mxn = -1,mxi = -1;
    for(int i = 0;i < n;i++) {
        if(c[i]==t) {
            if(r[i] > mxn) {
                mxn = r[i];
                mxi = i;
            }
        }
    }
    if(mxn!=-1) {
        cout << mxi + 1;
        return 0;
    }
    t = c[0];
    mxn = r[0], mxi = 0;
    for(int i = 0;i < n;i++) {
        if(c[i]==t) {
            if(r[i] > mxn) {
                mxn = r[i];
                mxi = i;
            }
        }
    }
    cout << mxi + 1;
    return 0;
}

C - Dango

知识点：模拟、状态机
效率：$O(n)$
找-、-之间o的数量

#include <iostream>
#include <vector>
#define ll long long
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    ll n;
    string s;
    cin >> n >> s;
    int a=0,b=0;
    int ans = -1;
    for(int i = 0; i < n; i++) {
        if(s[i]=='o') {
            a++;
            if(b>0) ans = max(ans,a);
        }
        if(s[i]=='-'){
            b++;
            ans = max(ans,a);
            a=0;
        }
    }
    cout << (ans==0?-1:ans);
    return 0;
}

D - Find by Query

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

首先确定第0位和第n位是1，找一个位置$p$，$S_{p}!=S_{p+1}$
假如中间有1，那么必然存在01，因为第一位是0
所以找01就行，不需要找10
也就是说，如果找到1，那么左边必然存在一个0
如果找到0，右边必然存在一个1

#include <iostream>
#define ll long long
using namespace std;
int main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    ll N;
    cin >> N;
    ll l = 1,r = N, mid, ans;
    while(l+1 < r) {
        mid = (l+r) >> 1;
        cout << "? " << mid << endl;
        cin >> ans;
        if(ans) r = mid;
        else l = mid;
    }
    cout << "! " << l << endl;
}

E - Nearest Black Vertex

知识点：图、BFS、染色
效率：$O(2*n)$

1. 整张图必须有一个黑点
2. 给定K个条件，必须满足至少存在一个满足条件黑点，使黑点到当前点的最小距离为x

思路：

1. 第一轮BFS：先把路径小于目标点和目标距离x的点刷成白的
2. 第二轮BFS：然后对于所有约束条件，找距离恰好为x的点，假如不是白的，则刷成黑的（这时候就会出现已经被别的点刷成白的情况，假如所有距离为x的点全部被别的点刷成白的了，那么就没有符合题意的点，即没有答案）

#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 N, M, K;
    ll a,b;
    cin >> N >> M;
    vector<vector<ll>> vec(N+1);
    for(int i = 0; i < M;i++) {
        cin >> a >> b;
        vec[a].push_back(b);
        vec[b].push_back(a);
    }
    cin >> K;
    vector<ll> mark(N+1, 0);
    vector<pr> tmp;
    for(int i = 0; i < K; i++) {
        cin >> a >> b;
        tmp.push_back({a,b});
        vector<bool> vis(N+1, 0);
        queue<pr> q;
        q.push({a,0});
        while(!q.empty()){
            auto top = q.front();
            q.pop();
            ll nv = top.first, t = top.second;
            if (vis[nv]) continue;
            vis[nv] = true;
            if (t >= b) break;
            mark[nv] = -1;
            for(auto target: vec[nv]) {
                q.push({target, t + 1});
            }
        }
    }

    for(auto &[a,b]: tmp) {
        queue<pr> q;
        q.push({a,0});
        bool flg = false;
        vector<bool> vis(N+1, 0);
        while(!q.empty()){
            auto top = q.front();
            q.pop();
            ll nv = top.first, t = top.second;
            if (vis[nv]) continue;
            vis[nv] = true;
            if (t > b) break;
            if (t==b) {
                if(mark[nv]!=-1) {
                    mark[nv] = 1;
                    flg = true;
                }
            }
            for(auto target: vec[nv]) {
                q.push({target, t + 1});
            }
        }
        if(!flg) {
            cout << "No\n";
            return 0;
        }
    }
    cout << "Yes\n";

    for(int i = 1;i <= N;i++ ) {
        if(K==0) mark[1] = 1;
        cout << (mark[i]==1?1:0);
    }

}

F

知识点：DP、子序列问题
该题目是动态规划里面子序列问题的扩展版，因此需要先补充一下子序列的题库和做题思路
首先是子序列个数，传统单独问子序列个数的是要使用后缀计数来去重

G

知识点：模拟/线段树
构造题，要学习一下如何构造

解法1

知识点：模拟
复杂度：$O(n)$
主要掌握题中“构造序列不会重复”的题意，只要当前遍历到的答案能够覆盖之前的答案，
而且覆盖后还至少存在一个可行序列，那么就可行
说起来很简单，但是我想明白花了非常长的时间

#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 N, M, K;

    cin >> N >> M;
    vector<ll> d(N+1, 0);
    vector<ll> cnt(M+1, 0);
    vector<ll> ans(M+1, 0);
    vector<bool> use(M+1, false);
    for(int i = 0;i < N;i++) {
        cin >> d[i];
        cnt[d[i]]++;
    }

    ll now = -1;
    for(int i = 0;i < N;i++) {
        //cout << " i" << i << " d[i]" << d[i] << endl;
        cnt[d[i]]--;
        if(use[d[i]]) continue;
        //cout << (ans[now] >= d[i]);
        while(now >= 0 && cnt[ans[now]] && ans[now] >= d[i]) {
            //cout << "ansnow" << ans[now] << "d[i]" << d[i] << endl;
            use[ans[now]] = false;
            now--;
        }
        now += 1;
        ans[now] = d[i];
        //cout << now << " " << ans[now]<< endl;
        use[d[i]] = true;
    }

    for(int i = 0; i < M; ++ i)
        cout << ans[i] << " \n"[i == M];
    return 0;

}

解法2 线段树

留坑