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

A – Strong Word

算法：

模拟。

思路：

无。

关键代码：

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

    if (s.back() == s.front())
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

B – Center Alignment

算法：

模拟。

思路：

无。

关键代码：

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

    int m = 0;
    for (auto x : s)
        m = max(m, (int)x.size());

    for (auto x : s)
    {
        int d = m - x.size();

        cout << string(d / 2, '.') << x << string(d / 2, '.') << endl;
    }
}

C – Sugoroku Destination

算法：

图论。

思路：

注意到：\(i ≤ a_i ≤ n (1 ≤ i ≤ n)\)，可得 \(a[n] = n\)（不动点），\(a[n]\) 的答案固定为 \(n\)，而 \(a[n – 1] ∈ {n – 1, n}\)，既它为不动点或者为 \(n\)，当取 \(a[n – 1] = a[a[n – 1]]\) 时，\(a[i]\) 到达下一次的位置为 \(a[j]\)，由于 \(a[j](j \ge i)\)，可知 \(a[j]\) 的值已经为答案，因此每个 \(i\) 都取 \(a[i – 1] = a[a[i – 1]]\) 即可。

关键代码：

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

    for (int i = n; i >= 1; --i)
        a[i] = a[a[i]];

    for (int i = 1; i <= n; ++i)
        cout << a[i] << ' ';
    cout << endl;
}

D – Reconstruct Chocolate

算法：

大模拟。

思路：

定义 \(cur_h\) 为当前巧克力的高，\(cur_w\) 为当前巧克力的宽。

还原分割过程：

• 初始时，\(cur_h = H, cur_w = W\)，巧克力数量为 \(1\)；
• 由于巧克力是沿格子边界分割成且分割后的两块均为矩形，那么分割后必然存在一块巧克力的 \(h_i = cur_h\)，或者 \(w_i = cur_w\)；
• 当存在巧克力 \(h_i = cur_h\) 时，将 \(i\) 分割掉后，剩余巧克力大小为 \(cur_h * (cur_w – w_i)\)，使 \(cur_h := cur_h\)，\(cur_w := cur_w – w_i\)；
• 存在巧克力 \(w_i = cur_w\) 时同理；
• 以此类推即可将一块巧克力分割为 \(n\) 块巧克力，具体实现看代码。

关键代码：

void miyan()
{
    int H, W, n;
    cin >> H >> W >> n;
    vector<pii> a(n);
    for (auto &[x, y] : a)
        cin >> x >> y;

    map<int, multiset<pii, greater<>>> X, Y;
    for (int i = 0; i < n; ++i)
    {
        auto [x, y] = a[i];
        X[x].insert({y, i});
        Y[y].insert({x, i});
    }

    vector<pii> ans(n);
    int x1 = 1, y1 = 1, x2 = H, y2 = W;
    int nowh = H, noww = W;
    for (int i = 0; i < n; ++i)
    {
        if (X[nowh].size())
        {
            auto it = X[nowh].begin();
            auto [y, p] = *it;

            int x = nowh;
            ans[p] = {x1, y1};

            X[x].erase(it);
            Y[y].erase(Y[y].lower_bound({x, p}));

            noww -= y;
            y1 += y;

            continue;
        }

        if (Y[noww].size())
        {
            auto it = Y[noww].begin();
            auto [x, p] = *it;

            int y = noww;
            ans[p] = {x1, y1};

            Y[y].erase(it);
            X[x].erase(X[x].lower_bound({y, p}));

            nowh -= x;
            x1 += x;

            continue;
        }
    }

    for (auto [x, y] : ans)
        cout << x << ' ' << y << endl;
}

E – Many LCMs

算法：

数论，质因数分解，质数筛，\(LCM\)，快速幂，逆元。

思路：

定义：

• \(cnt(p)\) 为质数 \(p\) 在数字 \(x\) 质因数分解后出现的次数；
• \(cmax()\) 为所有数字中次大（第二大）的数字。

设在 \(n\) 个数字中，质数 \(p\) 在每个数分解质因数后出现的次数为 \(e_1, e_2, ….., e_n\)，那么在 \(LCM\) 中 \(p\) 的指数就为 \(max(e_1, e_2, ….., e_n)\)。

因此总的 \(LCM\) 就为：

$$LCM = \prod_{i = 1}^{k} p_i ^ {max(e_{i1}, e_{i2}, ….., e_{in})}$$

数论基础：数论基本概念 – MiyanLog

算术基本定理：算术基本定理 – MiyanLog

当去除的数字 \(a_i\) 的 \(cnt(p_i) = max(e_{i1}, e_{i2}, ….., e_{in})\) 时，最终的 \(LCM\) 消去了 \(max(e_{i1}, e_{i2}, ….., e_{in})\) 的贡献，加上了次大的 \(cmax(e_{i1}, e_{i2}, ….., e_{in})\) 的贡献。

为了快速实现上述操作，需要存储质数 \(p_i\) 在所有 \(a_i\) 中的最大出现次数和次大出现次数。

具体实现看代码。

关键代码：

vector<int> prime, minp, maxp;
void get_prime(int n)
{
    minp.resize(n + 1);
    maxp.resize(n + 1);
    for (int i = 2; i <= n; i++)
    {
        if (!minp[i])
        {
            minp[i] = maxp[i] = i;
            prime.push_back(i);
        }
        for (auto j : prime)
        {
            if (j > minp[i] || j > n / i)
                break;
            minp[i * j] = j;
            maxp[i * j] = maxp[i];
        }
    }
}

vector<pii> factorize(int n)
{
    vector<pii> ans;
    while (n > 1)
    {
        int now = minp[n], cnt = 0;
        while (n % now == 0)
        {
            n /= now;
            cnt++;
        }
        ans.push_back({now, cnt});
    }
    return ans;
}

ll qmi(ll a, ll b, ll p)
{
    ll ans = 1 % p;
    while (b)
    {
        if (b & 1)
            ans = ans * a % p;
        b >>= 1;
        a = a * a % p;
    }

    return ans;
}

ll inv(ll q, ll mod)
{
    return qmi(q, mod - 2, mod);
}

void miyan()
{
    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto &x : a)
        cin >> x;

    map<int, vector<pii>> mp;
    for (auto x : a)
    {
        if (mp.count(x))
            continue;

        mp[x] = factorize(x);
    }

    map<int, int> maxv, cmaxv;
    for (int i = 0; i < n; ++i)
    {
        int val = a[i];
        auto vec = mp[val];

        for (auto [x, y] : vec)
        {
            if (y > maxv[x])
            {
                cmaxv[x] = maxv[x];

                maxv[x] = y;
            }
            else if (y > cmaxv[x])
                cmaxv[x] = y;
        }
    }

    ll lcm = 1;
    for (auto [x, y] : maxv)
        lcm = lcm * qmi(x, y, MOD) % MOD;

    for (int i = 0; i < n; ++i)
    {
        ll ans = lcm;
        ll val = a[i];

        for (auto [x, y] : mp[val])
            if (maxv[x] == y)
                ans = ans * qmi(x, cmaxv[x], MOD) % MOD * inv(qmi(x, y, MOD), MOD) % MOD;

        cout << ans << ' ';
    }

    cout << endl;
}

F – Exactly K Steps 2

算法：

图论，邻接矩阵，矩阵快速幂。

思路：

矩阵快速幂统计定长最短路模板。

不懂的看：矩阵快速幂及其应用 – MiyanLog

关键代码：

// 矩阵大小，记得改初始矩阵大小
const int SIZE = 100;
struct Matrix
{
    int ROW, COL; // 行数, 列数
    ll M[SIZE + 1][SIZE + 1];

    // 构造函数
    Matrix(int _ROW = 0, int _COL = 0)
    {
        ROW = _ROW;
        COL = _COL;
        clear();
    }

    // 清零，生成零矩阵
    void clear() { memset(M, 0x3f, sizeof(M)); }

    // 初始化，生成大小为 n 的单位矩阵 (必须是方阵)
    void init()
    {
        clear();
        for (int i = 1; i <= ROW; ++i)
            M[i][i] = 0;
    }

    // 重载 * 运算符 (A 是 N * K 矩阵，B 是 K * M 矩阵)
    Matrix friend operator*(const Matrix &A, const Matrix &B)
    {
        // 前提：A 的列数必须等于 B 的行数
        // 结果：矩阵 ans 的大小为 A.ROW * B.COL
        Matrix ans(A.ROW, B.COL);
        ans.clear();

        for (int i = 1; i <= A.ROW; ++i)
            for (int k = 1; k <= A.COL; ++k)
                for (int j = 1; j <= B.COL; ++j)
                    ans.M[i][j] = min(ans.M[i][j], A.M[i][k] + B.M[k][j]);

        return ans;
    }

    // 重载 ^ 运算符，实现矩阵快速幂
    Matrix friend operator^(Matrix base, ll exp)
    {
        Matrix ans(base.ROW, base.ROW);
        ans.init(); // 生成与 base 同阶的单位矩阵

        while (exp)
        {
            if (exp & 1)
                ans = ans * base;
            base = base * base;
            exp >>= 1;
        }

        return ans;
    }
};

const ll inf = 0x3f3f3f3f3f3f3f3f;

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

    Matrix base(n, n);
    base.clear();
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            base.M[i][j] = a[i][j];

    base = base ^ k;

    for (int i = 1; i <= n; ++i)
        cout << base.M[i][i] << endl;
}

G – Knight Placement

还没补。