ABC 436 题解

A

根据题目可知，我们只需要输出 $\lvert n - |s| \lvert$ 个 o 后再输出当选字符串即可，但是要特判如果 $n = |s|$ 时直接输出字符串。

#include <bits/stdc++.h>
using namespace std;
int n;
string s;

int main() {
    cin >> n >> s;
    if (s.size() == n)cout << s;
    else {
        for (int i = s.size();i < n;i++) {
            cout << "o";
        }
        cout << s;
    }
    return 0;
}

B

初看题目很复杂，但是其实只用直接模拟即可我们使用两个变量 $l,\ r$ 来循环填充即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, l, r, a[N][N];

int main() {
    cin >> n;
    l = 0, r = n / 2;
    for (int i = 1;i <= n * n;i++) {
        a[l][r] = i;
        int ll = l, lr = r, nl = (l - 1 + n) % n, nr = (r + 1) % n;
        if (a[nl][nr] != 0) {
            nl = (ll + 1) % n;
            nr = lr;
        }   
        l = nl, r = nr;
    }
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            cout << a[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}

其中的 $l,\ r$ 为当前填充的坐标，$ll,\ rr$ 为当前坐标的备份，$nl,\ nr$ 则不断直接向右上移动。

C

题目大意

在一个 $n \times n$ 的网格上从左上角开始，放置 $m$ 个小正方形，每次都放置一个面积为 $2 \times 2$ 的小正方形，但是每个正方形不能重叠，求最后防止的正方形数量。

思路

由于 $n,\ m$ 的值都很大 ($1 \leq n,\ m \leq 10^{9}$)，所以我们不能直接模拟，但是我们对于每一个放置检查只需要检查相邻的 $9$ 个位置，每次复杂度为 $O(\log m)$。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
int n, m;
set<int>id;

struct node {
    int x, y;
}a[N];

signed main() {
    cin >> n >> m;
    for (int i = 1;i <= m;i++) {
        cin >> a[i].x >> a[i].y;
    }
    for (int i = 1;i <= m;i++) {
        bool pan = 1;
        for (int dx = -1;dx <= 1;dx++) {
            for (int dy = -1;dy <= 1;dy++) {
                int nx = a[i].x + dx, ny = a[i].y + dy;
                if (nx >= 1 && nx <= n - 1 && ny >= 1 && ny <= n - 1) {
                    if (id.count((nx * (n + 1) + ny))) {
                        pan = 0;
                        break;
                    }
                }
            }if (!pan)break;
        }
        if (pan) {
            id.insert((a[i].x * (n + 1)) + a[i].y);
        }
    }
    cout << id.size();
    return 0;
}

D

题目大意

在一个 $n \times m$ 的迷宫中，求出从 $(1,\ 1)$ 走到 $(n,\ m)$ 的最小时间，走不到输出 $-1$。每个格子可能为：

• . 花费 $1$ 单位时间通过
• # 不能通过
• a-z 可以传送到相同字母处

思路

直接 BFS 就行了

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, m;
int d[4][2] = { 0,1,0,-1,1,0,-1,0 };
char a[N][N];
bool vis[N][N], vvis[N];
vector<pair<int, int>>mp[N];

struct node {
    int x, y, dis;
};

void init(int i, int j) {
    if (a[i][j] >= 'a' && a[i][j] <= 'z') {
        mp[a[i][j] - 'a'].push_back({ i, j });
    }
}

void bfs() {
    queue<node>q;
    vis[1][1] = 1;
    q.push({ 1,1,0 });
    for (;!q.empty();) {
        node now = q.front();
        if (now.x == n && now.y == m) {
            cout << now.dis;
            exit(0);
        }
        q.pop();
        for (int i = 0;i < 4;i++) {
            int nx = now.x + d[i][0], ny = now.y + d[i][1];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] != '#' && vis[nx][ny] == 0) {
                vis[nx][ny] = 1;
                q.push({ nx,ny,now.dis + 1 });
            }
        }
        if (a[now.x][now.y] >= 'a' && a[now.x][now.y] <= 'z') {
            if (vvis[a[now.x][now.y] - 'a'] == 0) {
                vvis[a[now.x][now.y] - 'a'] = 1;
                for (auto i : mp[a[now.x][now.y] - 'a']) {
                    if (vis[i.first][i.second] == 0) {
                        vis[i.first][i.second] = 1;
                        q.push({ i.first,i.second,now.dis + 1 });
                    }
                }
            }
        }
    }
    cout << -1;
}

int main() {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> a[i][j];
            init(i, j);
        }
    }
    bfs();
    return 0;
}

E

题目大意

给定一个长度为 $n$ 的序列 $a$，每次选择 $(i,\ j)$，交换 $a_i$ 与 $a_j$，求出将序列 $a$ 交换为对于每一个 $a_i$ 都有 $a_i = i$ 的最小操作次数

思路

找置换环时，将加入新置换环数量的步骤改为前置换环可合法交换的操作次数即可，想出来的时候只有 $20\ s$ 了，没写出来。