[数据结构与算法]Codeforces Round #736 (Div. 2)题解

A

题意：找到a,b两个数这两个数满足$amodn=bmodn$
思路：
看上去是个同余方程其实不用这样麻烦
$a=2,b=n/2$就可以啦

B

题意：
这是个象棋的题目$n?n$的矩阵分为我方和敌方
我分棋子可以斜着吃敌方的士兵到达敌方或者对面没有敌方棋子直接到达敌方，打印到达敌方棋子的个数。
思路：
模拟

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, t;
char a[N], b[N];
int main()
{
    cin >> t;
    while (t -- )
    {
        cin >> n;
        cin >> a + 1;
        cin >> b + 1;
        a[n + 1] = '2', b[n + 1] = '2';
        int ans = 0;
        for (int i = 1; i <= n; i ++ ){
            if (a[i] == '0'){
                if (b[i] == '1') ans ++, b[i] = '2';
            }
            else if (a[i] == '1'){
                if (b[i - 1] == '1') ans ++, b[i - 1] = '2';
                else if (b[i + 1] == '1') ans ++, b[i + 1] = '2';
            }
        }
        cout << ans << endl;
    }
    return 0;
}

C

题意：一共有n个点有m条边，这条边上较小的数会被杀死，问最后剩下几个数，还有q次询问，1是添加v到u的一条边，2是删除v到u的一条边，3是打印结果。
思路：
看着这道题像个并查集的题目，但是就是思维，这条边上较小的数会被杀死，我们就看看谁会被杀死，死了多少回就可以了，最后死过0回的$ans++$。

#include <bits/stdc++.h> 
using namespace std;
const int N = 2e5 + 10;
int st[N];
int n, m, u, v, q, x;
int main()
{
    cin >> n >> m;
    memset(st, 0, sizeof st);
    for (int i = 1; i <= m; i ++ ){
        cin >> u >> v;
        if (u > v) st[v] ++;
        else st[u] ++;
    }
    int ans = 0;
    for (int i = 1; i <= n; i ++ ){
            if (st[i] == 0) ans ++;
    }
    cin >> q;
    while (q -- ){
        cin >> x;
        if (x == 3) cout << ans << endl;
        else{
            cin >> u >> v;
            if (x == 1){
                if (u > v){
                    if (st[v] == 0) ans --;
                    st[v] ++;
                }
                else if (v > u){
                    if (st[u] == 0) ans --;
                    st[u] ++;
                }
            }
            else if (x == 2){
                if (v < u){
                    st[v]--;
                    if (st[v] == 0) ans ++;
                }
                else{
                    st[u] --;
                    if (st[u] == 0) ans ++;
                }
            }
        }
    }
    return 0;
}

D

题意：在数组a里面找到一个序列$a_i,a_{i+1},a_{i+2},...,a_j$ 满足有一个数x,$a_{i}modx=a_{i+1}modx=a_{i+2}modx=a_{j}modx$求这个序列的最大长度
思路：
$a_{i}modx=a_{j}modx$可以变形为$a_i?a_j=x?y$所以看见这个我们想到了差分，是的st表维护差分数组的gcd，二分差分数组的长度，最后的长度是$l+1$.

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
long long a[N];
long long Logn[N], f[N][21];
int t, n;
void pre(){
    Logn[1] = 0;
    Logn[2] = 1;
    for (int i = 3; i < N; i ++ )
        Logn[i] = Logn[i / 2] + 1;
}
bool check(int mid){
    int s = Logn[mid];
    for (int i = 1; i + mid - 1 < n; i ++ ){
        int x = i, y = i + mid - 1;
        if (__gcd(f[x][s], f[y - (1 << s) + 1][s]) >= 2) return true;
    }
    return false;
}
int main()
{
    cin >> t;
    pre();
    while (t -- ){
        cin >> n;
        for (int i = 1; i <= n; i ++ ) cin >> a[i];
        for (int i = 1; i < n; i ++ )
            f[i][0] = abs(a[i + 1] - a[i]);
        for (int j = 1; j < 20; j ++ )
            for (int i = 1; i + (1 << j) - 1 < n; i ++ )
                f[i][j] = __gcd(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        int l = 0, r = n;
        int ans = 0;
        while(l < r)//二分差分数组的长度
        {
            int mid = l + r + 1 >> 1;
            if (check(mid))l = mid;
            else r = mid - 1;
        }
        cout << l + 1 << endl;
    }
    return 0;
}