526互联

AtCoder Beginner Contest 305 题解 A - F

发布时间 2023-06-14 23:44:46作者: 叁纔

A - Water Station

题目大意

找到离给定的数最近的一个 \(5\) 的倍数输出即可。

解题思路

我们取这个数对 \(5\) 的上下界，也就是整数除以 \(5\) 再乘以 \(5\)，以及这个数再加上一个 \(5\)，比较这两数和给定数的距离即可。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 1e5 + 10;
const int MOD = 1e9 + 7;

void solve() {
    int x;
    cin >> x;
    int a = x / 5 * 5, b = a + 5;
    if (b - x < x - a) {
        cout << b << endl;
    } else {
        cout << a << endl;
    }
}

signed main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}

B - ABCDEFG

题目大意

题图给定数轴，表示这七个字符的相对位置关系，求任意两者的距离。

解题思路

人脑预处理出前缀和，直接相减即可。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 1e5 + 10;
const int MOD = 1e9 + 7;

int s[] = {0, 3, 4, 8, 9, 14, 23};

void solve() {
    char a, b;
    cin >> a >> b;
    if (a > b) swap(a, b);
    cout << s[b - 'A'] - s[a - 'A'] << endl;
}

signed main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}

C - Snuke the Cookie Picker

题目大意

给定一个图，由.和#组成，其中的#理应组成一个矩形区域，但是现在缺了一块，需要我们找出缺的这一块。

解题思路

我们通过扫描整个图中的#，通过坐标最值可以找到矩形的边界，那么扫描矩形区域，出现.就是缺的地方了。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 1010;
const int MOD = 1e9 + 7;

string g[N];

void solve() {
    int h, w;
    cin >> h >> w;
    for (int i = 1; i <= h; ++i) {
        cin >> g[i];
        g[i] = '0' + g[i];
    }
    int x1 = 0, x2 = h, y1 = 0, y2 = w;
    for (int i = 1; i <= h; ++i) {
        for (int j = 1; j <= w; ++j) {
            if (g[i][j] == '#') {
                y1 = max(y1, j);
                y2 = min(y2, j);
                x1 = max(x1, i);
                x2 = min(x2, i);
            }
        }
    }
    for (int i = x2; i <= x1; ++i) {
        for (int j = y2; j <= y1; ++j) {
            if (g[i][j] == '.') {
                cout << i << ' ' << j << endl;
            }
        }
    }
}

signed main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}

D - Sleep Log

题目大意

给出高橋さん的睡眠时间表，奇数项是起床时间，偶数是睡觉时间，有 \(q\) 次询问，每次给出一个区间，问这段时间高橋さん睡了多长时间。

解题思路

一维区间询问，可以使用前缀和，考虑到给定的区间会把原来的睡眠时间分割开，使用二分找到第一个不小于区间端点的元素位置，修正分割量即可。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 4e5 + 10;
const int MOD = 1e9 + 7;

int a[N], s[N];

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        s[i] = s[i - 1] + (a[i] - a[i - 1]) * (i & 1);
    }
    int q;
    cin >> q;
    for (int i = 1; i <= q; ++i) {
        int l, r;
        cin >> l >> r;
        int idl = lower_bound(a + 1, a + n + 1, l) - a;
        int idr = lower_bound(a + 1, a + n + 1, r) - a;
        LL cnt = 0;
        if (idr & 1) {
            cnt += a[idr] - r;
        }
        if (idl & 1) {
            cnt += l - a[idl - 1];
        }
        cout << s[idr] - s[idl - 1] - cnt << endl;
    }
}

signed main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}

E - Art Gallery on Graph

题目大意

给定一个无权无向图，其上有 \(k\) 个卫士，每个卫士有保卫范围 \(h_i\)，距离卫士距离不超过 \(h_i\) 的点都可以被保卫，现在求被保卫的点。

解题思路

实际上就是让我们去dijkstra以卫士为中心的最短路，并且标记所有经过的点，最后汇总输出即可。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 4e5 + 10;
const int MOD = 1e9 + 7;

struct Guard{
    int p;
    int h;
    bool operator< (const Guard& t) const{
        return h < t.h;
    }
};

bool vis[N];
int res[N];
int n, m, k, idx;
int H[N], e[N], ne[N];

void add(int a, int b) {
    e[idx] = b;
    ne[idx] = H[a];
    H[a] = idx++;
}

void dijkstra() {
    priority_queue<Guard> heap;
    for (int i = 1; i <= k; ++i) {
        int p, h;
        cin >> p >> h;
        heap.push({p, h});
    }
    for (int i = 1; i <= n; ++i) {
        while (!heap.empty()) {
            auto top = heap.top();
            heap.pop();
            if (vis[top.p]) continue;
            vis[top.p] = true;
            if (top.h) {
                for (int j = H[top.p]; ~j; j = ne[j]) {
                    if (!vis[e[j]]) {
                        heap.push({e[j], top.h - 1});
                    }
                }
            }
        }
    }
}

void solve() {
    cin >> n >> m >> k;
    memset(H, -1, sizeof H);
    for (int i = 1; i <= m; ++i) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    dijkstra();
    LL cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (vis[i]) {
            res[++cnt] = i;
        }
    }
    cout << cnt << endl;
    for (int i = 1; i <= cnt; ++i) {
        cout << res[i] << ' ';
    }
}

signed main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}

F - Dungeon Explore

题目大意

给定一个 \(n\) 点 \(m\) 边无权连通无向图，起始时位于 \(1\) 点，允许我们移动最多 \(2n\) 次到达 \(n\) 点。每次走向一个新的结点，都会得知该点附近链接点的信息。

解题思路

我们需要从 \(1\) 走到 \(n\)，同时，每次只能直到自己当前所在位置的临接点，这个过程很类似于dfs的过程，如果我们dfs，实际上是将每个点都遍历一遍，那么除去头尾两点，其他点至多入一次出一次，所以最后的移动次数会略小于 \(2n\) 可解。

另：交互题一定要关ios，忘记关了TLE了5次qwq。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
//#define endl '\n'
//#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 110;
const int MOD = 1e9 + 7;

bool vis[N];
int n, m;

void dfs(int u) {
    vis[u] = true;
    if (u == n) exit(0);
    int num;
    cin >> num;
    int ne[N];
    for (int i = 1; i <= num; ++i) {
        cin >> ne[i];
    }
    for (int i = 1; i <= num; ++i) {
        if (!vis[ne[i]]) {
            cout << ne[i] << endl;
            dfs(ne[i]);
            cout << u << endl;
            for (int j = 0; j <= num; ++j) {
                int xxcwasdfad;
                cin >> xxcwasdfad;
            }
        }
    }
}

void solve() {
    cin >> n >> m;
    dfs(1);
}

signed main() {
//    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}