链接：https://atcoder.jp/contests/abc436

A – o-padding 

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int n;
    string s;
    cin >> n >> s;

    cout << string(n - s.size(), 'o') << s << endl;
}

B – Magic Square 

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n, 0));

    a[0][(n - 1) / 2] = 1;

    int last = 1;
    int x = 0, y = (n - 1) / 2;
    for (int i = 0; i < n * n - 1; ++i)
    {
        if (a[(x - 1 + n) % n][(y + 1) % n] == 0)
        {
            x = (x - 1 + n) % n;
            y = (y + 1) % n;

            a[x][y] = ++last;
        }
        else
        {
            x = (x + 1) % n;
            a[x][y] = ++last;
        }
    }

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
            cout << a[i][j] << ' ';

        cout << endl;
    }
}

C – 2×2 Placing 

算法：

    模拟，\(stl\)。

思路：

    将放置了方块的点加入到 \(set\) 或者 \(map\) 中，每次放置只需在 \(set\) 或者 \(map\) 中查找四个点上是否有方块即可。

关键代码：

void miyan()
{
    int n, m;
    cin >> n >> m;

    ll ans = 0;

    map<pii, int> hash;
    for (int i = 0; i < m; ++i)
    {
        int x, y;
        cin >> x >> y;

        if (!hash.count({x, y}) && !hash.count({x, y + 1}) && !hash.count({x + 1, y}) && !hash.count({x + 1, y + 1}))
        {
            ++ans;
            hash[{x, y}] = 1;
            hash[{x, y + 1}] = 1;
            hash[{x + 1, y}] = 1;
            hash[{x + 1, y + 1}] = 1;
        }
    }

    cout << ans << endl;
}

D – Teleport Maze 

算法：

    \(bfs\)。

思路：

    每个传送点只到达一次。

关键代码：

void miyan()
{
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (auto &x : g)
        cin >> x;

    vector<vector<pii>> c(26);
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (g[i][j] >= 'a' && g[i][j] <= 'z')
            {
                c[g[i][j] - 'a'].push_back({i, j});
            }
        }
    }

    vector<int> st(26, 0);
    vector<vector<int>> dist(n, vector<int>(m, 1e9));
    queue<pii> q;
    q.push({0, 0});
    dist[0][0] = 0;

    while (q.size())
    {
        auto [x, y] = q.front();
        q.pop();

        if (x == n - 1 && y == m - 1)
        {
            cout << dist[x][y] << endl;
            return;
        }

        if (g[x][y] >= 'a' && g[x][y] <= 'z' && !st[g[x][y] - 'a'])
        {
            st[g[x][y] - 'a'] = 1;

            for (auto [a, b] : c[g[x][y] - 'a'])
            {
                if (dist[a][b] > dist[x][y] + 1)
                {
                    dist[a][b] = dist[x][y] + 1;
                    q.push({a, b});
                }
            }
        }

        for (int i = 0; i < 4; ++i)
        {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m || g[a][b] == '#')
                continue;

            if (dist[a][b] > dist[x][y] + 1)
            {
                dist[a][b] = dist[x][y] + 1;
                q.push({a, b});
            }
        }
    }

    cout << -1 << endl;
}

E – Minimum Swap 

算法：

    \(dsu\)。

思路：

    猜的。

    将 \(i\) 和 \(a[i]\) 所在集合合并，对于一个集合中可以作为第一次交换的次数为 \(C_{size}^{2}\)。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    vector<ll> p(n + 1), siz(n + 1, 1);
    for (int i = 1; i <= n; ++i)
        p[i] = i;

    auto find = [&](auto &&self, int x) -> int
    {
        if (x != p[x])
            p[x] = self(self, p[x]);
        return p[x];
    };

    for (int i = 1; i <= n; ++i)
    {
        int x = i, y = a[i];

        x = find(find, x), y = find(find, y);
        if (x != y)
        {
            siz[x] += siz[y];
            p[y] = x;
        }
    }

    ll ans = 0;
    for (int i = 1; i <= n; ++i)
        if (i == find(find, i) && siz[i] > 1)
            ans += siz[i] * (siz[i] - 1) / 2;

    cout << ans << endl;
}

F – Starry Landscape Photo 

算法：

    树状数组。

思路：

    首先肯定不能暴力求出所有 \([l, r, b]\)。

    考虑升序枚举 \(b\)，找到所有满足条件的 \(l, r\)。

    根据乘法原理，对于一个 \(b\) 满足条件的区间个数为 \(l * r\) 个。

    使用树状数组动态维护坐标点上是否有值。

关键代码：

int n;
vector<int> tr;

void add(int x)
{
    for (; x <= n; x += x & -x)
        ++tr[x];
}

ll query(int x)
{
    ll ans = 0;
    for (; x; x -= x & -x)
        ans += tr[x];

    return ans;
}

void miyan()
{
    cin >> n;
    vector<int> a(n + 1), pos(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        pos[a[i]] = i;
    }

    tr.resize(n + 1, 0);

    ll ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        add(pos[i]);

        ll L = query(pos[i]);
        ll R = i - L + 1;

        ans += L * R;
    }

    cout << ans << endl;
}

G – Linear Inequation 

    还没补。