AtCoder Beginner Contest(abc) 305-526互联

A - Water Station

题目大意

给定一个0~100之间的数, 输出离它最近的5的倍数

解题思路

签到题不多嗦了;

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=1e6+10,mod= 998244353;
int n, m;
signed main() {
    cin >> n;
    m = n % 5;
    if (m > 2) n = n + (5 - m);
    else n = n - m;
    cout << n;
    return 0;
}

B - ABCDEFG

题目大意

给出A~G七个字母, 以及每个字母之间的权值, 输入两个字母, 输出两个字母之间的权重总和;

解题思路

前缀和签到题不多嗦了;

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N = 10;
int n, m, k;
int d[] = { 0,3,1,4,1,5,9 };
int s[N];
signed main() {
    for (int i = 1; i <= 6; i++) s[i] = s[i - 1] + d[i];
    char a, b;
    cin >> a >> b;
    n = min(a - 'A', b - 'A');
    m = max(a - 'A', b - 'A');
    cout << s[m] - s[n];
    return 0;
}

题目大意

给定一个由' . '组成的矩阵, 这个矩阵内部有个由'#'组成的小矩阵, 但是这个小矩阵有一个位置仍是' . ', 找出这个位置;

解题思路

签到题不多嗦了

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N = 510;
int n, m, k;
char g[N][N];
signed main() {
    cin >> n >> m;
    int l=N, r=0, u=N, d=0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> g[i][j];
            if (g[i][j] == '#') {
                l = min(l, i);
                r = max(r, i);
                u = min(u, j);
                d = max(d, j);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (g[i][j] == '.') {
                if (i >= l && i <= r && j >= u && j <= d) {
                    cout << i << ' ' << j;
                    return 0;
                }
            }
        }
    }
    return 0;
}

D - Sleep Log

题目大意

小莫展示了他一天的作息时间, 给出了n个时间点, 第1个时间点为0, 都2i个时间点和第(2i+1)个时间点之间是小莫的睡眠时间, 其余时间为清醒时间, 给出m组询问, 每组询问是输入两个时间点, 问这个时间段内小莫的睡眠时间;

解题思路

这个题看着简单, 实际做起来其实还是有许多需要思考的点; 因为时间最多到1e9级别, 而n只有1e5级别, 所以我们可以对时间段进行处理; 对于n个时间点就有(n-1)个时间段, 我们对每个时间段进行编号, 睡眠时间段的值就是时间差, 而清醒时间段为0, 然后求时间段的前缀和; 此外我们可以让两个时间点中较大的那个代表整个时间段 (这个可以用map进行映射), 从而判断询问给出的时间点位于哪个时间段内; 然后在询问中, 对于两个时间点, 我们可以先用二分找到第一个大于等于它的时间点, 这样就可以找到包围询问时间段的两个时间段, 用前缀和得到大致答案后, 再对首尾的两个时间段进行具体的减补;

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m, k,z;
vector<int>v;
map<int, int> mp;
int g[N];
bool st[N];
signed main() {
    cin >> n;
    int maxn = 0;
    cin >> z;
    for (int i = 1; i < n; i++) {
        int x;
        cin >> x;
        if (i % 2 == 0) {
            g[i] = x - z;
            st[i] = true;
        }
        else st[i] = false;
        z = x;
        v.push_back(x);
        mp[x] = i;
    }
    for (int i = 1; i < n; i++) g[i] += g[i - 1];
    cin >> m;
    for (int i = 1; i <= m; i++) {
        int res = 0;
        int a, b;
        cin >> a >> b;
        auto l = lower_bound(v.begin(), v.end(), a) - v.begin();
        auto r = lower_bound(v.begin(), v.end(), b) - v.begin();
        int l1 = mp[v[l]];
        int r1 = mp[v[r]];
        res += g[r1] - g[l1];
        if (st[l1]) res += v[l] - a;
        if (st[r1]) res -= v[r] - b;
        cout << res << endl;
    }
    return 0;
}

E - Art Gallery on Graph

题目大意

给定一个图, 有n个点和m条边, 每条边的权值为1; 然后又给出k个保安, 每个保安都位于不同的点上, 我们乘这些点为监视点, 每个保安都有一个视野范围h, 凡是与监视点距离小于等于h的点都会被监视, 问都有哪些点被监视了(包括监视点), 升序输出;

解题思路

因为n, m, k, 都是1e5级别的, 所以不能用bfs, 所以我想着只能从边入手, 但是一直没有思路; 然后看了看佬的题解, 发现了一个炒鸡牛逼的做法; 我们先找出所有视野范围h中的最大值max, 我们可以另外创建一个点x, 让x连接所有监视点, 然后最牛逼的来了, 我们让x到监视点之间的权值为max-hi (hi为各自的视野范围); 这样我们从x点出发, 找到所有与x距离小于等于max的点就是被监视的点了; 于是这个题就变成了最短路问题;(真的太强了 Orz); 为了防止监视点通过x到达其他点, 我们可以让监视点到x的权值为无穷;

神秘代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m, k, ini, idx;
int h[N], w[N], e[N], ne[N], d[N];
bool st[N];
set<int> s;
vector<PII> v;
void add(int a, int b,int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c; h[a] = idx++;
}
void dijkstra() {
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({ 0,ini });
    memset(d, 0x3f, sizeof d);
    d[ini] = 0;
    while (q.size()) {
        auto t = q.top();
        q.pop();
        int x = t.second;
        if (st[x]) continue;
        st[x] = true;
        for (int i = h[x]; i != -1; i = ne[i]) {
            int j = e[i];
            if (d[j] > d[x] + w[i]) {
                d[j] = d[x] + w[i];
                q.push({ d[j],j });
            }
        }
    }
}
signed main() {
    memset(h, -1,sizeof h);
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b,1);
        add(b, a,1);
    }
    ini = n + 1;
    int maxn = 0;
    for (int i = 1; i <= k; i++) {
        int a, b;
        cin >> a >> b;
        maxn = max(maxn, b);
        v.push_back({ a,b });
        s.insert(a);
    }
    for (auto t : v) {
        int a = t.first;
        int b = t.second;
        add(ini, a, maxn - b);
        add(a, ini, 0x3f3f3f3f);
    }
    dijkstra();
    for (int i = 1; i <= n; i++) {
        if (d[i] <= maxn) s.insert(i);
    }
    cout << s.size() << endl;
    for (int x : s) {
        cout << x << ' ';
    }
    return 0;
}

F - Art Gallery on Graph

题目大意

小莫和安姐在同一家便利店打工, 给定一个长度为n的字符串代表小莫有一个n天的日程表, 第i个字符为'#'表示小莫第i天要值班, 如果是' . '则是休息; 而安姐也要指定一个日程表, 有如下要求
一是小莫休息的日期, 安姐必须要去值班;
二是安姐会取n的一个因数m(不包括n), 并且让这n天的日程表是以m为周期循环的;
问安姐的日程表一共有多少种可能, 结果对998244353取模;

解题思路

一开始我们可以先把n的所有因数m存起来作为循环节的长度; 然后把字符串里所有' . '的位置p也存起来, 这是已经固定的安排, 在后续操作中我们可以把所有的p通过对m取余来聚集到同一个循环节里进行操作; 在一个长度为a的循环节里, 如果已经有b个' . '; 那么对于剩下的(a-b)个日期里我们有2的(a-b)次方个选择方案;
注意, 对于我们选择的循环节长度a, 它的所有方案中也包括了a的因数作为循环节长度时的方案; 比如a=6时的方案里面就存在a=1, a=2和a=3的所有方案, 所以为了避免重复必须要减去所有a的因数的方案; 对此我们可以用map来存储所有长度的方案;
二是注意对减法运算进行取模时记得要+mod之后再取模, 防止有负数; 因为这个debug了好久...
后来才知道这其实是容斥原理的思想: 求满足s1, s2, s3三个条件其中一个的方案数, 那么就可以求s1 + s2 + s3 - s1∩s2 - s1∩s3 - s2∩s3 + s1∪s2∪s3;

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=1e6+10,mod= 998244353;
int n, m;
vector<int> v1;
vector<int> v2;
set<int> s1;
map<int, int>mp;
char str[N];
int qmid(int a, int b, int c) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % c;
        a = a * a %c;
        b >>= 1;
    }
    return res;
}
void ini() {
    for (int i = 1; i <= n / i; i++) {
        if (n % i == 0) {
            v2.push_back(i);
            if (i == 1) continue;
            if (i * i != n) v2.push_back(n / i);
        }
    }
}
int check(int x,int y) {
    int a = (qmid(2, x, mod)+mod)%mod;
    for (int i = 1; i <= y / i; i++) {
        if (y % i == 0) {
            a = (a - mp[i]+mod) % mod;
            if (i == 1) continue;
            if (i * i != y) a = (a - mp[y/i]+mod) % mod;
        }
    }
    return a;
}
signed main() {
    cin >> n >> str+1;
    for (int i = 1; i <= n; i++) {
        if (str[i] == '.') v1.push_back(i);
    }
    ini();
    sort(v2.begin(), v2.end());
    int res = 0;
    for (int i = 0; i < v2.size(); i++) {
        int x = v2[i];
        s1.clear();
        for (int j = 0; j < v1.size(); j++) {
            int y = v1[j];
            if (y > x) {
                if (y % x == 0) y = x;
                else y = y % x;
            }
            s1.insert(y);
        }
        int idx = (x - s1.size())%mod;
        mp[x] = check(idx,x);
        res = (res +mp[x]) % mod;
    }
    cout << res;
    return 0;
}