freee Programming Contest 2022（AtCoder Beginner Contest 264）

https://atcoder.jp/contests/abc264
FG待补

A - "atcoder".substr()

输出atcoder第L位和第R位上的字符

#include <bits/stdc++.h>

using namespace std;

int main () {
    string s = "atcoder";
    int x, y;
    cin >> x >> y;
    x --, y --;
    for (int i = x; i <= y; i ++)   cout << s[i];
}

B - Nice Grid

我是直接嗯模拟的
也可以找规律，看奇偶性

#include <bits/stdc++.h>

using namespace std;
int a[17][17];  //黑0白1

int main () {
    int x, y;
    cin >> x >> y;
    for (int i = 2; i <= 14; i ++)  a[2][i] = a[i][2] = a[i][14] = a[14][i] = 1;
    for (int i = 4; i <= 12; i ++)   a[4][i] = a[i][4] = a[i][12] = a[12][i] = 1;
    for (int i = 6; i <= 10; i ++)   a[6][i] = a[i][6] = a[i][10] = a[10][i] = 1;
    a[8][8] = 1;
    // for (int i = 1; i <= 15; i ++) {
    //     for (int j = 1; j <= 15; j ++)
    //         cout << a[i][j] << ' ';
    //     cout << endl;
    // }
    if (a[x][y])    cout << "white";
    else    cout << "black";
}

C - Matrix Reducing

题意：可以任选A矩阵的某行或某列删去，问能否构成B矩阵

分别按行和按列看能否凑齐B矩阵
也可以暴力枚举删行 / 列

#include <bits/stdc++.h>

using namespace std;
int a[15][15], b[15][15], x, y; 

int main () {

    int n1, m1, n2, m2;

    cin >> n1 >> m1;    
    for (int i = 0; i < n1; i ++) {
        for (int j = 0; j < m1; j ++)
            cin >> a[i][j];
    }

    cin >> n2 >> m2;    
    for (int i = 0; i < n2; i ++) {
        for (int j = 0; j < m2; j ++) 
            cin >> b[i][j];
    }
    if (n2 > n1 || m2 > m1) {
        cout << "No";
        return 0;
    }

    bool suc = false;
    for (int i = 0; i < (1<<n1); i++)
        for (int j = 0; j < (1<<m1); j++) {
            vector <int> v1, v2;
            for(int k = 0; k < n1; k++) if((i & (1<<k)) == 0) v1.push_back(k);
            for(int k = 0; k < m1; k++) if((j & (1<<k)) == 0) v2.push_back(k);   
            if (v1.size() != n2 || v2.size() != m2)     continue;

            //确保没有偏移
            bool match = true;
            for (int ii = 0; ii < n2; ii++)
                for (int jj = 0; jj < m2; jj++) {
                    if (a[v1[ii]][v2[jj]] != b[ii][jj]) {
                        match = false;
                        break;
                    }
                }  

            if (match) {
                cout << "Yes";
                return 0;
            }       
        }
    
    cout << "No";
}
//能否去掉A的某行或某列，使得AB相等
//二进制暴力枚举

D - "redocta".swap(i,i+1)

题意：给一个串，每次能交换相邻的两个字符，问最少要多少次能把他变成"atcoder"

每个字符对应一个数字，不难得出，就是把现有序列变为有序的操作次数。
那么就是经典的求逆序对问题，直接上模板

#include <bits/stdc++.h>

using namespace std;
int a[10], tmp[10];

int merge_sort (int l, int r) {
    if (l >= r)
        return 0;
    int mid = l + r >> 1;
    int res = merge_sort (l, mid) + merge_sort (mid + 1, r);

    int k = 0, i = l, j = mid + 1; //计数,左半段起点,右半段起点
    while (i <= mid && j <= r) {
        if (a[i] <= a[j])
            tmp[k ++] = a[i ++]; //有序
        else {
            tmp[k ++] = a[j ++];
            res += mid - i + 1; //夹着的那段就是逆序对的数量
        }
    }

    while (i <= mid)    tmp[k ++] = a[i ++];
    while (j <= r)  tmp[k ++] = a[j ++];

    for (int i = l, j = 0; i <= r; i ++, j ++)
        a[i] = tmp[j];
    return res;

}

int main () {
    string s;
    cin >> s;
    for (int i = 0; i < 7; i ++) {
        if (s[i] == 'a')    a[i] = 1;
        else if (s[i] == 't')   a[i] = 2;
        else if (s[i] == 'c')   a[i] = 3;
        else if (s[i] == 'o')   a[i] = 4;
        else if (s[i] == 'd')   a[i] = 5;
        else if (s[i] == 'e')   a[i] = 6;
        else if (s[i] == 'r')   a[i] = 7;
    }

    int ans = 0;
    if (is_sorted(a, a + 7))   ans = 0;
    else {
        ans = merge_sort (0, 6);
    } 
    cout << ans << endl;
}


//1234567
//求逆序对数量

E - Blackout 2

题意：\(1--n\) 的点为城市，\(n+1--n+m\)的点为供电站，城市能实现供电的条件是至少连了一个发电站。现连了E条边，有q次操作，每次操作删去一条边，问此时有多少个城市能供上电

删边等于反向加边，然后把所有供电站都连接到超级源点0上（因为所有供电站都是等价的），用并查集维护连通性，以及连通块内编号即可，每次 \(cnt_0\) 就是所需答案

#include <bits/stdc++.h>

using namespace std;
const int M = 5e5 + 5, N = 2e5 + 5;
int n, m, E, q;
bool vis[M]; //表示这边需要删
int fa[N], cnt[N]; //dsu
int query[M];
vector <int> ans;

struct Node {
    int u, v;
}e[M];

int find (int x) {
    if (x != fa[x]) {
        fa[x] = find (fa[x]);
    }
    return fa[x];
}

int main () {
    scanf ("%d%d%d", &n, &m, &E);

    for (int i = 1; i <= n; i++)      fa[i] = i, cnt[i] = 1; //连通块内点的个数
    for (int i = n+1; i <= n+m; i++)    fa[i] = 0; //发电站均看成连到0点  

    for (int i = 1; i <= E; i++) {
        int u, v;
        scanf ("%d%d", &u, &v);
        e[i] = {u, v};
    }
    scanf ("%d", &q);
    for (int i = 0; i < q; i++)     scanf ("%d", &query[i]), vis[query[i]] = true;

    //最终态，也就是反向增边时的最初态
    for (int i = 1; i <= E; i ++) {
        if (vis[i])     continue;
        int a = e[i].u, b = e[i].v;
        int pa = find (a), pb = find (b);
        if (pa != pb) {
            if (pa == 0)    swap (pa, pb); //保证cnt累加到超级源点上
            fa[pa] = pb;
            cnt[pb] += cnt[pa];
        }
    }

    for (int i = q-1; i >= 0; i--) {
        int j = query[i];
        int a = e[j].u, b = e[j].v;
        ans.push_back (cnt[0]);
        int pa = find (a), pb = find (b);
        if (pa != pb) {
            if (pa == 0)    swap (pa, pb);
            fa[pa] = pb;
            cnt[pb] += cnt[pa];
        }               
    }

    reverse (ans.begin(), ans.end());
    for (auto i : ans)  printf ("%d\n", i);
}

//删边=反向加边

F - Monochromatic Path

G - String Fair