Codeforces Round (2021-08-01)

A. Gregor and Cryptography

题意

给定一个不小于 5 的质数 $p$ 。找出 $2\le a<b\le p$ ，让 $p\bmod a=p\bmod b$ 。

思路

质数 $p$ 是奇数，所以模 2 余 1，模 $p-1$ 也余 1。直接输出 2 和 $p-1$ 就行。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int mo = 998244353;

int T;

int main () {
    scanf("%d", &T);
    while(T--) {
        int p;
        scanf("%d", &p);
        printf("%d %d\n", 2, p - 1);
    }
    return 0;
}

B. Gregor and the Pawn Game

题目链接

题意

棋盘上有上下两行兵，对手的兵不会移动。自己的兵可以向正前方的空格走，或者斜着吃掉对面的兵，问最多能有多少个兵到达对面一行。

思路

从左往右处理自己的兵，优先吃左边的兵，其次走到正前方的空格，最后才吃右边的兵。

左边的位置后面用不到了，能吃就先吃；正前方的空格也只属于当前这个兵。右边的兵可能还要留给后面的兵，所以最后再用。用 v 标记已经占用的位置即可。

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 17;
int n, ans, T;
int v[maxn];
char s[maxn], t[maxn];


void Init(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) v[i] = 0;
    ans = 0;
    scanf("%s", s + 1);
    scanf("%s", t + 1);
    for(int i = 1; i <= n; i++) {
        if(t[i] == '1') {
            if(i > 1 && s[i - 1] == '1' && !v[i - 1]) {
                v[i - 1] = 1;
                ans++;
            }
            else if(s[i] == '0' && !v[i]) {
                v[i] = 1;
                ans++;
            }
            else if(i < n && s[i + 1] == '1' && !v[i + 1]) {
                v[i + 1] = 1;
                ans++;
            }
        }
    }
}


int main(){
    scanf("%d", &T);
    while(T--) {
        Init();
        printf("%d\n",ans);
    }
    return 0;
}

C. Web of Lies

题目链接

题意

贵族的编号越大，实力越强。如果一个贵族至少有一个朋友，而且所有朋友都比他强，他就会被杀掉；这个过程不断重复。还会动态增加或删除朋友关系，每次询问重新从当前完整关系图开始，求最终活下来的人数。

思路

只要有一个编号更大的朋友，自己最后就会被淘汰。顺着更大的编号往上走，最上面的人会留下来，下面的人则会依次满足被淘汰的条件。

所以只维护每个人比自己强的朋友集合。集合为空的人会留下来，答案就是这些人的数量。加边或删边时，只会影响编号较小的那个人，维护它的集合是否由空变非空、或由非空变空就行。

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 17;
int n, ans, T, m;
set<int> s[maxn];


int main(){
    scanf("%d%d", &n, &m);
    ans = n;
    for(int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        if(u > v) swap(u, v);
        s[u].insert(v);
    }
    for(int i = 1; i <= n; i++) if(s[i].size()) ans--;
    scanf("%d", &T);
    while(T--) {
        int t, u, v;
        scanf("%d", &t);
        if(t == 2) {
            scanf("%d%d", &u, &v);
            if(u > v) swap(u, v);
            s[u].erase(v);
            if(s[u].empty()) ans++;
        }
        else if(t == 1) {
            scanf("%d%d", &u, &v);
            if(u > v) swap(u, v);
            if(s[u].empty()) ans--;
            s[u].insert(v);
        }
        else {
            printf("%d\n",ans);
        }
    }
    return 0;
}

D. Integers Have Friends

题目链接

题意

给定一组互不相同的正整数。找最长的连续子数组，使得存在一个 $m\ge2$ ，让里面所有数模 $m$ 的余数相同。

思路

把相邻两项作差。余数相同，就说明这些差都有同一个大于 1 的公因数，所以直接维护差分区间的 gcd，不用把每个差分的质因数都拆出来。

从左往右加入一个差分，把上一轮各段的 gcd 再和它取 gcd，并加上只含当前差分的新段。同一个 gcd 只留最早的起点，后面的起点不会更优。gcd 大于 1 时，差分长度加一就是原数组长度。

往左扩展时，gcd 每次严格变小至少减半，因此一轮只有 $O(\log A)$ 种状态，空间也只需要这些状态。单个数总是合法，答案从 1 开始。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 2e5 + 17;
ll a[maxn], b[maxn];
int T, n, ans;
vector<pair<ll, int>> s, t;

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
        for(int i = 1; i < n; i++) b[i] = abs(a[i + 1] - a[i]);
        s.clear();
        ans = 1;
        for(int i = 1; i < n; i++) {
            t.clear();
            t.push_back({b[i], i});
            for(auto &it : s) {
                ll g = __gcd(it.first, b[i]);
                if(t.back().first == g) {
                    t.back().second = min(t.back().second, it.second);
                }
                else t.push_back({g, it.second});
            }
            s.swap(t);
            for(auto &it : s) if(it.first > 1) {
                ans = max(ans, i - it.second + 2);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

A. Gregor and Cryptography

题意

思路

代码

B. Gregor and the Pawn Game

题意

思路

代码

C. Web of Lies

题意

思路

代码

D. Integers Have Friends

题意

思路

代码

Random Posts