AtCoder Beginner Contest 302

A - Attack (abc302 a)

题目大意

给定怪物的血量\(a\)和你每次攻击扣除的血量 \(b\),问打多少次怪物才会死。

解题思路

答案即为\(\lceil \frac{a}{b} \rceil = \lfloor \frac{a + b - 1}{b} \rfloor\)

神奇的代码
#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);
    LL a, b;
    cin >> a >> b;
    cout << (a + b - 1) / b << '\n';

    return 0;
}



B - Find snuke (abc302 b)

题目大意

给定一个二维网格,格子上有字母,找到一连串位置,使得其字符串为\(snuke\),要求这一连串位置俩俩相邻,即有共边或共点。这意味着可以横竖对角线。

解题思路

枚举起点,枚举方向(8个方向),依次判断即可。

神奇的代码
#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 h, w;
    cin >> h >> w;
    vector<string> a(h);
    for(auto &i : a)
        cin >> i;
    string target = "snuke";
    vector<array<int, 2>> ans;
    auto check = [&](int x, int y, int dx, int dy){
        vector<array<int, 2>> tmp;
        for(int i = 0; i < target.size(); ++ i){
            if (x >= h || x < 0 || y >= w || y < 0)
                return false;
            if (a[x][y] != target[i])
                return false;
            tmp.push_back({x, y});
            x += dx;
            y += dy;
        }
        ans = tmp;
        return true;
    };
    auto solve = [&](){
        for(int i = 0; i < h; ++ i){
            for(int j = 0; j < w; ++ j){
                for(int x = -1; x <= 1; ++ x)
                    for(int y = -1; y <= 1; ++ y){
                        if (x == 0 && y == 0)
                            continue;
                        if (check(i, j, x, y)){
                            return;
                        }
                    }

            }
        }
    };
    solve();
    for(auto &i : ans)
        cout << i[0] + 1 << ' ' << i[1] + 1 << '\n';

    return 0;
}



C - Almost Equal (abc302 c)

题目大意

给定\(n\)个字符串,问能否排个序,使得俩俩字符串恰好仅一个位置上的字母不同。

解题思路

范围不大,直接\(O(n!)\)枚举排序,再 \(O(nm)\)判断即可。

神奇的代码
#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, m;
    cin >> n >> m;
    vector<string> s(n);
    for(auto &i : s)
        cin >> i;
    vector<int> id(n);
    iota(id.begin(), id.end(), 0);
    auto check = [&](){
        do{
            bool ok = true;
            for(int i = 0; i < n - 1; ++ i){
                int x = id[i], y = id[i + 1];
                int cnt = 0;
                for(int j = 0; j < m; ++ j)
                    cnt += (s[x][j] != s[y][j]);
                if (cnt != 1){
                    ok = false;
                    break;
                }
            }
            if (ok)
                return true;
        }while(next_permutation(id.begin(), id.end()));
        return false;
    };
    if (check())
        cout << "Yes" << '\n';
    else 
        cout << "No" << '\n';

    return 0;
}



D - Impartial Gift (abc302 d)

题目大意

给定两个数组\(a,b\),要求从中各选一个数,使得俩数的差值不超过 \(d\),问俩数和的最大值。

解题思路

先排个序,然后枚举\(a\)的每个数,在\(b\)中找到第一个不大于 \(a+d\)的值 ,然后取最大值即可。因为排了序,可以二分找,也可以因为枚举的\(a\)是递增的,一个指针从\(b\)中一路扫过去。

神奇的代码
#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, m;
    LL d;
    cin >> n >> m >> d;
    vector<LL> a(n), b(m);
    for(auto &i : a)
        cin >> i;
    for(auto &i : b)
        cin >> i;
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    int pos = 0;
    LL ans = -1;
    for(int i = 0; i < n; ++ i){
        while(pos < m && b[pos] - a[i] <= d){
            ++ pos;
        }
        if (pos != 0 && abs(a[i] - b[pos - 1]) <= d){
            ans = max(ans, a[i] + b[pos - 1]);
        }
    }
    cout << ans << '\n';

    return 0;
}



E - Isolation (abc302 e)

题目大意

给定一张图,\(n\)个点,无边。有以下两种操作:

  • 1 u v,为\(u, v\)连一条边
  • 2 u,删除与\(u\)相连的每条边

对于每个操作,输出孤立点数量,即度数为 \(0\)的数量。

解题思路

按照上述题意模拟即可,每条边只会添加一次,删除一次,因此复杂度为\(O(q)\)

因为存的是双向边,删\(u\)的边时,比如删除的边是 \((u,v)\),要避免在删 \(v\)的边时将 \((u,v)\)再删一次,因此用了一个 \(set\)记录当前的边,其中规定了编号小的在前。

神奇的代码
#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, q;
    cin >> n >> q;
    vector<int> du(n, 0);
    vector<vector<int>> edge(n);
    int ans = n;
    auto add = [&](int x){
        if (du[x] == 0)
            -- ans;
        du[x] ++;
    };
    auto mine = [&](int x){
        if (du[x] == 1)
            ++ ans;
        du[x] --;
    };
    set<array<int, 2>> edges;
    while(q--){
        int op;
        cin >> op;
        if (op == 1){
            int u, v;
            cin >> u >> v;
            -- u, -- v;
            edge[u].push_back(v);
            edge[v].push_back(u);
            add(u);
            add(v);
            int minn = min(u, v), maxx = u + v - minn;
            edges.insert({minn, maxx});
        }else{
            int u;
            cin >> u;
            -- u;
            for(auto &v : edge[u]){
                int minn = min(u, v), maxx = u + v - minn;
                auto it = edges.find({minn, maxx});
                if (it != edges.end()){
                    edges.erase(it);
                    mine(u);
                    mine(v);
                }
                edge[u].clear();
            }
        }
        cout << ans << '\n';
    }

    return 0;
}



F - Merge Set (abc302 f)

题目大意

给定\(n\)个集合,每个集合包含了 \(1 \sim m\)的一些数。可以进行一种操作,选择两个交集不为空的集合,得到它们的并集。

问最少进行多少次操作,可以得到一个包含 \(1\)\(m\)的集合。

解题思路

集合与集合之间,根据交集不为空的关系,有连边。但由于\(n\)\(10^5\)的大小,因此不能 \(O(n^2)\)建边。

但由于所有集合的所有数加起来只有 \(5e5\),如果一个集合 \(i\)有数字 \(j\),我们可以 连一条\(i \to j\)的边,让数字 \(j\)充当集合与集合之间的中介。这样边数只有 \(5e5\)条。

即有两类点,一类是表示集合的点,一类是表示数字的点,集合\(\to\)数字的边权为 \(0\),数字\(\to\)集合的边权为 \(1\)

答案就是从\(1\)号点到 \(m\)号点的最短路距离减一。

因为边权只有 \(0\)\(1\),且在搜索时边权是交替出现的,所以直接 \(BFS\)即可。

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

const int inf = 1e9 + 7;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<array<int, 2>>> edge(n + m);
    for(int i = 0; i < n; ++ i){
        int x;
        cin >> x;
        while(x--){
            int v;
            cin >> v;
            -- v;
            edge[v].push_back({m + i, 1});
            edge[m + i].push_back({v, 0});
        }
    }
    vector<int> dis(n + m, inf);
    dis[0] = 0;
    queue<array<int, 2>> team;
    team.push({dis[0], 0});
    while(!team.empty()){
        auto [expect, u] = team.front();
        team.pop();
        for(auto &[v, w] : edge[u]){
            if (dis[u] + w < dis[v]){
                dis[v] = dis[u] + w;
                team.push({dis[v], v});
            }
        }
    }
    if (dis[m - 1] == inf)
        dis[m - 1] = 0;
    cout << dis[m - 1] - 1 << '\n';

    return 0;
}



G - Sort from 1 to 4 (abc302 g)

题目大意

给定一个仅包含\(1,2,3,4\)的数组,一次操作可以交换任意两个数。

问最少进行多少次交换,使得数组不严格升序。

解题思路

<++>

神奇的代码



Ex - Ball Collector (abc302 h)

题目大意

给定一棵树,每个点有两个值。

对于\(v = 2,3,...,n\) ,问从点\(1\)到点 \(v\)的最短路径途径的每个点中,各选一个数,其不同数的个数的最大值。

解题思路

<++>

神奇的代码



热门相关:地球第一剑   法医娇宠,扑倒傲娇王爷   最强装逼打脸系统   名门天后:重生国民千金   姊妹战争