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

A – Sigma Cubes

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    ll ans = 0;
    for (int i = 1; i <= n; ++i)
        ans += pow(-1, i) * pow(i, 3);

    cout << ans << endl;
}

B – Find Permutation 2

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (auto &x : a | views::drop(1))
        cin >> x;

    vector<int> ans(n + 1, 0);
    vector<int> st(n + 1, 0);
    for (int i = 1; i <= n; ++i)
    {
        if (a[i] != -1 && st[a[i]])
        {
            cout << "No" << endl;
            return;
        }

        if (a[i] != -1)
        {
            ans[i] = a[i];
            st[a[i]] = 1;
        }
    }

    cout << "Yes" << endl;

    int now = 1;
    for (int i = 1; i <= n; ++i)
    {
        if (!ans[i])
        {
            while (st[now])
                ++now;

            ans[i] = now++;
        }
    }

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

C – Rotate and Sum Query

算法：

    前缀和。

思路：

    移动存在周期且移动最大为 \(n – 1\) 次，再多 \(1\) 就移回来了，所以开 \(2 * n\) 大小的前缀和数组即可。

关键代码：

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

    vector<ll> s(n + n + 1, 0);
    for (int i = 1; i <= n + n; ++i)
        s[i] = s[i - 1] + a[i];

    ll cnt = 0;
    while (q--)
    {
        int op, l, r;
        cin >> op;
        if (op == 1)
        {
            cin >> l;
            cnt = (cnt + l) % n;
        }
        else
        {
            cin >> l >> r;

            cout << s[r + cnt] - s[l + cnt - 1] << endl;
        }
    }
}

D – Ulam-Warburton Automaton

算法：

    模拟。

思路：

    队列模拟即可。

关键代码：

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

    vector cnt(n, vector<int>(m, 0));
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (g[i][j] == '#')
            {
                cnt[i][j] = 2;
                for (int k = 0; k < 4; ++k)
                {
                    int a = i + dx[k], b = j + dy[k];
                    if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] == '.')
                        ++cnt[a][b];
                }
            }
        }
    }

    queue<pii> q;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (cnt[i][j] == 1)
                q.push({i, j});

    while (q.size())
    {
        queue<pii> qq;
        while (q.size())
        {
            auto [x, y] = q.front();
            q.pop();

            g[x][y] = '#';

            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] == '.')
                {
                    if (++cnt[a][b] == 1)
                        qq.push({a, b});
                }
            }
        }

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

            if (cnt[x][y] == 1)
                q.push({x, y});
        }
    }

    ll ans = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            ans += g[i][j] == '#';

    cout << ans << endl;
}

E – Count Sequences 2

    组合数以后再补。