AtCoder Beginner Contest 304

A - First Player (abc304 a)

题目大意

依次给定每个人的姓名和年龄,排成一圈。从年龄最小的人依次输出姓名。

解题思路

找到年龄最小的,依次输出就好了。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector<pair<int, string>> p(n);
    for(auto &i : p)
        cin >> i.second >> i.first;
    int st = min_element(p.begin(), p.end()) - p.begin();
    for(int i = 0; i < n; ++ i){
        cout << p[st].second << '\n';
        st = (st + 1) % n;
    }

    return 0;
}



B - Subscribers (abc304 b)

题目大意

给定一个数字,如果其超过三位数,则仅保留其最高三位,低位数字全部置为0。

解题思路

读一个string,直接赋值即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    string s;
    cin >> s;
    if (s.size() > 3)
        fill(s.begin() + 3, s.end(), '0');
    cout << s << '\n';

    return 0;
}



C - Virus (abc304 c)

题目大意

给定\(n\)个人的坐标,第一个人阳了,若两人的欧式距离\(\leq d\),其中有一个阳了,则另一个也会阳。然后继续传染。

问最终每个人是否阳了。

解题思路

从第一个人直接\(BFS\)即可。时间复杂度为 \(O(n^2)\)

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n, d;
    cin >> n >> d;
    d *= d;
    vector<array<int, 2>> p(n);
    for(auto &i : p)
        cin >> i[0] >> i[1];
    vector<int> ans(n, 0);
    ans[0] = 1;
    queue<int> team;
    team.push(0);
    auto dis = [&](int x, int y){
        return (p[x][0] - p[y][0]) * (p[x][0] - p[y][0]) + (p[x][1] - p[y][1]) * (p[x][1] - p[y][1]);
    };
    while(!team.empty()){
        int u = team.front();
        team.pop();
        for(int i = 0; i < n; ++ i){
            if (ans[i])
                continue;
            if (dis(i, u) <= d){
                ans[i] = 1;
                team.push(i);
            }
        }
    }
    for(int i = 0; i < n; ++ i)
        if (ans[i])
            cout << "Yes" << '\n';
        else 
            cout << "No" << '\n';

    return 0;
}



D - A Piece of Cake (abc304 d)

题目大意

一个\(h \times w\)的蛋糕,给定 \(n\)个草莓的位置,然后竖切 \(a\)刀,横切 \(b\)刀,给定切的位置,问切出来的 \((a+1)(b+1)\)块蛋糕中,草莓数量最少和最多分别是多少。不会把草莓切成两半。

解题思路

\(a \times b \leq 4e10\),因此不能考虑每块蛋糕。但我们可以考虑每个草莓对蛋糕的贡献。

根据草莓的位置,每个草莓仅对一块蛋糕有贡献,因此我们就遍历每块草莓,令其对应蛋糕的草莓数加一。而求是哪块蛋糕,其实就看它位于哪一刀的右边和上边(左下坐标原点)即可,二分就可以找到。

最后看最大值和最小值即可。因为蛋糕的草莓数量是稀疏的,我们可以用 map记录,最后看map里的元素个数是否等于\((a+1)(b+1)\),不等于说明有的蛋糕没有草莓。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int w, h, n, a, b;
    cin >> w >> h >> n;
    vector<array<int, 2>> s(n);
    for(auto &i : s)
        cin >> i[0] >> i[1];
    cin >> a;
    vector<int> vec(a);
    for(auto &i : vec)
        cin >> i;
    cin >> b;
    vector<int> hor(b);
    for(auto &i : hor)
        cin >> i;
    map<LL, int> cnt;
    int minn = n + 1, maxx = 0;
    auto check = [&](int x, int y){
        int pos1 = upper_bound(vec.begin(), vec.end(), x) - vec.begin();
        int pos2 = upper_bound(hor.begin(), hor.end(), y) - hor.begin();
        return 1ll * (a + 1) * pos2 + pos1;
    };
    for(auto &[x, y]: s){
        LL id = check(x, y);
        cnt[id] ++;
    }
    for(auto &[_, v] : cnt){
        minn = min(minn, v);
        maxx = max(maxx, v);
    }
    if (cnt.size() < 1ull * (a + 1) * (b + 1))
        minn = 0;
    cout << minn << ' ' << maxx << '\n';

    return 0;
}



E - Good Graph (abc304 e)

题目大意

给定一张无向图,有\(k\)个限制,第 \(i\)个限制表示 点\(x_i\)和 点\(y_i\) 不能相互到达。原图满足这\(k\)条限制。

依次回答\(q\)个独立的询问,每个询问添加一条边\((u,v)\)后,是否还满足这 \(k\)个限制。

解题思路

题意相当于给了若干个连通块,然后要求一些连通块之间不能相互到达,然后问增加的边,是否导致两个不该连通的连通块连通。

那就给每个连通块标个号,然后把不能连通的连通块编号用set存起来,每个询问就问这条边的两个点所在的连通块标号是否在这个set里即可。

连通块标号、查点所在的连通块,用并查集即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

class dsu {
    public:
    vector<int> p;
    int n;

    dsu(int _n) : n(_n) {
        p.resize(n);
        iota(p.begin(), p.end(), 0);
    }

    inline int get(int x) {
        return (x == p[x] ? x : (p[x] = get(p[x])));
    }

    inline bool unite(int x, int y) {
        x = get(x);
        y = get(y);
        if (x != y) {
            p[x] = y;
            return true;
        }
        return false;
    }
};

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    dsu d(n);
    for(int i = 0; i < m; ++ i){
        int u, v;
        cin >> u >> v;
        -- u, -- v;
        d.unite(u, v);
    }
    int k;
    cin >> k;
    set<array<int, 2>> forbid;
    for(int i = 0; i < k; ++ i){
        int u, v;
        cin >> u >> v;
        -- u, -- v;
        int fu = d.get(u), fv = d.get(v);
        assert(fu != fv);
        if (fu > fv)
            swap(fu, fv);
        forbid.insert({fu, fv});
    }
    int q;
    cin >> q;
    while(q--){
        int u, v;
        cin >> u >> v;
        -- u, -- v;
        int fu = d.get(u), fv = d.get(v);
        if (fu > fv)
            swap(fu, fv);
        if (forbid.find({fu, fv}) == forbid.end()){
            cout << "Yes" << '\n';
        }else{
            cout << "No" << '\n';
        }
    }

    

    return 0;
}



F - Shift Table (abc304 f)

题目大意

给定高桥的\(n\)天值班情况。

问满足下述条件的青木的\(n\)天值班情况数量,满足每天他俩至少有一人值班,且青木的值班情况是关于\(m | n\)循环的,其中 \(m < n\)

解题思路

<++>

神奇的代码



G - Max of Medians (abc304 g)

题目大意

<++>

解题思路

<++>

神奇的代码



Ex - Constrained Topological Sort (abc304 h)

题目大意

<++>

解题思路

<++>

神奇的代码



热门相关:斗神战帝   特工重生:快穿全能女神         法医娇宠,扑倒傲娇王爷