Back to Blog

AtCoder Beginner Contest 436题解

这道题就是将字符串s长度增加到n增加的元素是$o$ 这道题是一道模拟题，将$n$行$n$列的网格，按照规则填满。 在单元格 $(0,\frac{N - 1}{2})$ 中写入 1 。 重复以下操作 $N^2−1 $次： 令 $(r,c)$ 为上次写入整数的单元格， $k$为写入的整数。如果单元格 $((r−1)\...

Type 题解

Created May 21, 2026, 17:00:00 / Updated May 21, 2026, 17:00:00

Views — / Comments — / Words 1,048

AtCoder Beginner Contest 436题解

o-padding

这道题就是将字符串s长度增加到n增加的元素是oo

void solve() {
    string str;
    cin >> n >> str;
    str = string(n - str.size(), 'o') + str;
    cout << str << endl;
}

Magic Square

这道题是一道模拟题，将nn行nn列的网格，按照规则填满。

  1. 在单元格 (0,N−12)(0,\frac{N - 1}{2}) 中写入 1 。
  2. 重复以下操作 N2−1N^2−1 次：
    • 令 (r,c)(r,c) 为上次写入整数的单元格， kk为写入的整数。如果单元格 ((r−1)mod  N,(c+1)mod  N)((r−1)\mod N,(c+1) \mod N) 为空，请在该单元格中写入 k+1k+1 ；否则，请在单元格 ((r+1)mod  N,c)((r+1)\mod N,c) 中写入k+1 k+1 。这里， xmod  Nx\mod N表示 xx 除以 NN 时的余数。
void solve() {
    read(n);
    vector arr(n, vector<int>(n, 0));
    arr[0][(n - 1) / 2] = 1;
    int cnt = n * n - 1;
    int r = 0, c = (n - 1) / 2, k = 1;
    while (cnt --) {
        int x = ((r - 1) % n + n) % n, y = (c + 1) % n;
        if (arr[x][y])
            arr[(r + 1) % n][c] = k + 1, r = (r + 1) % n, c = c, k++;
        else
            arr[x][y] = k + 1, r = x, c = y, k++;
    }
    for (auto& a: arr) {
        for (int x: a)
            cout << x << ' ';
        cout << endl;
    }
}

2x2 Placing

这个题和上面的题差不多。都是模拟题，但是这个题的NN很大。需要用map<int,map<int,int>>map<int, map<int,int>>来存储

unordered_map<int,unordered_map<int,int>>unordered\_map<int, unordered\_map<int, int>> 也行能放置的条件是这个周围4个块没有被占。

用map$$unordered\_map自带的count()count()函数判断是否占有，就行了

void solve() {
    read(n, m);
    unordered_map<int, unordered_map<int, int8_t>> arr;
    int cnt = 0;
    while (m--) {
        int r, c;
        read(r, c);
        if (!arr[r].count(c) && !arr[r + 1].count(c) && !arr[r].count(c + 1) && !arr[r + 1].count(c + 1)) {
            arr[r][c] = arr[r + 1][c] = arr[r][c + 1] = arr[r + 1][c + 1] = ++cnt;
        }
    }
    cout << cnt << endl;
}

Teleport Maze

这道题就是bfsbfs求最小路。中间有几个小插曲就是能瞬移。遇到相同的字母。都能取到另一个字母的地方。与普通的最小路就这些区别。唯一需要强调的点是。不要让点重复进入队列。具体操作看我的题解

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

void solve() {
    int h, w;
    // read(h, w);
    cin >> h >> w;
    vector<string> str(h);
    vector<pii> arr[26];
    for (int i = 0; i < h; i ++) {
        cin >> str[i];
        for (int j = 0; j < w; j ++) {
            if (str[i][j] >= 'a' && str[i][j] <= 'z')
                arr[str[i][j] - 'a'].emplace_back(i, j);
        }
    }
    queue<tpii> q; // x, y, cnt
    vector<vector<int8_t>> st(h + 1, vector<int8_t>(w + 1, false));
    q.emplace(0, 0, 0);
    while (!q.empty()) {
        auto [x, y, cnt] = q.front();
        if (x == h - 1 && y == w - 1)
            return cout << cnt << endl, void();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int px = x + dx[i], py = y + dy[i];
            if (px < 0 || py < 0 || px >= h || py >= w)
                continue;
            if (st[px][py] || str[px][py] == '#')
                continue;
            st[px][py] = true;
            q.emplace(px, py, cnt + 1);
        }
        if (str[x][y] == '.') {
            continue;
        } else {
            for (auto [px, py]: arr[str[x][y] - 'a']) {
                if (st[px][py])
                    continue;
                st[px][py] = true;
                q.emplace(px, py, cnt + 1);
            }
        }
    }
    cout << -1 << endl;
}

Minimum Swap

这道题就是一个置换环的知识点，需要将它转换为并查集的知识进行解题

我们可以发现w[i]!=iw[i] != i时能进行的操作是将他与w[w[i]]w[w[i]]交换

另一个点我用图

3 1 4 2 5
1 2 3 4 5
3 -> 4 、 3 -> 2

3能和4交换也能和2交换。这个能交换的都在同一个置换环中。大家可以画画图看看。只要知道这一点了，那贡献就知道了。

int p[N];
int siz[N];

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

void merge(int a, int b) {
    a = find(a), b = find(b);
    if (a == b)
        return;
    siz[b] += siz[a];
    p[a] = b;
}

void solve() {
    read(n);
    fill(siz, siz + n + 1, 1);
    iota(p, p + n + 1, 0);
    vector<int> res;
    for (int i = 1; i <= n; i++) {
        read(w[i]);
    }
    for (int i = 1; i <= n; i++) {
        if (w[i] != i) {
            merge(w[i], i);
        }
    }
    i64 ans = 0;
    for (int i = 1; i <= n; i++) {
        if (p[i] == i && siz[i] != 1) {
            ans += (i64)siz[i] * (siz[i] - 1) / 2;
        }
    }
    cout << ans << endl;
}

Starry Landscape Photo

这道题我赛时没写出来。看了看ai的题解也算是写出来了吧。。。

换句话说，一个合法的集合 S 必须满足：存在参数 l，r，bl，r，b，使得 S 恰好由位置在 [l，r][l，r] 之间且亮度排名 ≤b 的所有星星组成。而且 SS 不能是空集。

关键思路： 为了避免重复计数（即同一个集合被不同的l，r，b l，r，b 组合生成），我们需要为每一个合法的集合找到一个“唯一标识”。 对于任何一个合法的星星集合 S，其中必定包含一颗“最暗”的星星（即亮度排名数值最大的那颗）。设这颗星星的亮度排名为 bmaxb_{max}。 那么，这个集合 S 第一次被生成的时刻，一定是我们把相机亮度阈值 bb 设定为bmax b_{max} 的时候。 如果 b<bmax{b<b_{max}}，这个集合里的那颗最暗星星就看不到了，集合就不完整。 如果 b>bmaxb>b_{max}，我们可能会引入更暗的星星；即便没有引入，按照计数规则，我们规定在 b=bmax 时统计该集合。

因此，我们可以把问题转化为： 枚举亮度阈值 b 从 1 到 N。当阈值为 b 时，有多少个合法的集合 S 满足“集合中亮度最暗的星星恰好是亮度为 b 的这颗星”？

算法推导

  1. 我们将亮度从1 1 到NN依次“点亮”星星。
  2. 当轮到亮度为 bb 的星星（设其位置为Pb P_b）被点亮时，天空中已经点亮了所有亮度小于等于 b 的星星（共 b 颗）。
  3. 此时，所有可能的“合法集合”都是当前这些已点亮星星在位置上的连续子段。
  4. 我们要计数的集合，必须包含这颗刚刚被点亮的星星（位置为 PbP_b）。如果不包含它，那么这个集合的最大亮度肯定小于 bb，说明它在之前的步骤（bb 更小的时候）已经被统计过了。
  5. 所以问题简化为：在当前所有已点亮的 bb 颗星星中，按位置排序后，有多少个连续子段包含了位置为 PbP_b 的这颗星？

数学计算： 假设当前已点亮的 bb 颗星星，按位置从左到右排序后，刚刚加入的那颗星星（位置 Pb）排在第 k 位。 那么，包含这第 kk 颗星的连续子段，其：

  • 左端点可以是第 11 到第k k 颗星中的任意一个（共 kk 种选择）。
  • 右端点可以是第 kk 到第 bb 颗星中的任意一个（共 b−k+1b−k+1 种选择）。

因此，新增的合法集合数量为： count=k×(b−k+1)\text{count} = k \times (b - k + 1)

struct Fenwick {
    int n;
    vector<i64> tr;
    Fenwick(int n = 0) {
        init(n);
    }

    void init(int n) {
        this->n = n;
        tr.resize(n + 1);
    }

#define lowbit(x) ((x) & (-x))
    Fenwick(vector<int> a) {
        n = a.size();
        tr.resize(n + 1);
        for (int i = 1; i <= n; i++)
            tr[i] = a[i];
        for (int x = 1; x <= n; x++)
            for (int i = x - 1; i >= x - lowbit(x) + 1; i -= lowbit(i))
                tr[x] += tr[i];
    }

    void add(int x, const i64 &c) {
        for (int i = x; i <= n; i += lowbit(i))
            tr[i] += c;
    }

    i64 sum(int x) {
        i64 res = 0;
        for (int i = x; i; i -= lowbit(i))
            res += tr[i];
        return res;
    }
    i64 query(int l, int r) {
        return sum(r) - sum(l - 1);
    }
#undef lowbit
};

void solve() {
    read(n);
    Fenwick tr(n + 1);
    for (int i = 1; i <= n; i++) {
        read(w[i]);
        t[w[i]] = i;
    }
    i64 ret = 0;
    for (int i = 1; i <= n; i++) {
        tr.add(t[i], 1);
        int cnt = tr.sum(t[i]);
        ret += (i64)(i - cnt + 1) * cnt;
    }
    cout << ret << endl;
}
商业转载请联系站长获得授权，非商业转载请注明本文出处及文章链接，您可以自由地在任何媒体以任何形式复制和分发作品，也可以修改和创作，但是分发衍生作品时必须采用相同的许可协议。本文采用 CC BY-NC-SA 4.0 - 非商业性使用 - 相同方式共享 4.0 国际 进行许可。

Comments

Notes, questions, and follow-ups are welcome here.

Comments are temporarily unavailable because WALINE_SERVER_URL or PUBLIC_WALINE_SERVER_URL is not configured.