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

A – Count .

算法：

模拟。

思路：

无。

关键代码：

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

    ll ans = 0;
    for (auto c : s)
        if (c == 'i' || c == 'j')
            ++ans;

    cout << ans << endl;
}

B – Music Player

算法：

模拟。

思路：

无。

关键代码：

void miyan()
{
    int Q;
    cin >> Q;

    int cnt = 0;
    bool ok = 0;
    while (Q--)
    {
        int op;
        cin >> op;
        if (op == 1)
            ++cnt;
        else if (op == 2)
            cnt = max(0, cnt - 1);
        else
            ok = !ok;

        if (ok && cnt >= 3)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}

C – Peer Review

算法：

图论，组合数。

思路：

定义 \(u\) 点的 \(cur = n – cnt(u) – 1\)，每个点 \(u\) 的答案为 \(C_{cur}^{3}\)。

关键代码：

void miyan()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n + 1);
    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for (int i = 1; i <= n; ++i)
    {
        ll cur = n - g[i].size() - 1;

        if (cur < 3)
            cout << 0 << ' ';
        else
            cout << (cur * (cur - 1) * (cur - 2) / 6) << ' ';
    }

    cout << endl;
}

D – Swap and Range Sum

算法：

树状数组。

思路：

无。

关键代码：

struct BIT
{
    int n;
    vector<ll> tr;
    BIT(int _N)
    {
        n = _N;
        tr.resize(n + 1, 0);
    }

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

    ll query(int l, int r)
    {
        auto ask = [&](int x)
        {
            ll ans = 0;
            for (; x; x -= x & -x)
                ans += tr[x];
            return ans;
        };

        return ask(r) - ask(l - 1);
    }
};

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

    BIT bit(n);
    for (int i = 1; i <= n; ++i)
        bit.add(i, a[i]);

    while (q--)
    {
        int op;
        cin >> op;

        if (op == 1)
        {
            int x;
            cin >> x;

            int val1 = a[x];
            int val2 = a[x + 1];
            swap(a[x], a[x + 1]);
            bit.add(x, -val1);
            bit.add(x + 1, -val2);
            bit.add(x, val2);
            bit.add(x + 1, val1);
        }
        else
        {
            int l, r;
            cin >> l >> r;

            cout << bit.query(l, r) << endl;
        }
    }
}

E – Laser Takahashi

极角排序，还没补。

F – Diagonal Separation 2

算法：

\(dp\)，前缀和优化。

思路：

通过手玩样例不难发现，最后满足题目要求的网格，其每行白色格子的数量一定是非严格单调递减的且白色格子都在前 \(k\) 个位置，即第 \(i\) 行白色格子数量一定小于等于第 \(i – 1\) 行的白色格子数量。

考虑动态规划。

定义 \(dp[i][j]\) 为第 \(i\) 行只有前 \(j\) 个格子为白色的最少操作次数。

初始化第 \(1\) 行：

• \(dp[1][i]_{i = 0}^{n} = i – cnt(1, 1, i) + cnt(1, i + 1, n)\)
• 其中 \(cnt(row, l, r)\) 为第 \(row\) 行第 \(l\) 列到 \(r\) 列的白色格子数量。

状态转移：

• \(dp[i][j]_{j = 0}^n = dp[i – 1][k]_{k = j}^{n} + i – cnt(i, 1, j) + cnt(i, j + 1, n)\)

其中 \(cnt\) 函数可以定义并预处理 \(pre[i][j]\) 和 \(suf[i][j]\) 前缀后缀数组，使其可以在 \(O(1)\) 时间内获得白色格子数量。

初始化与状态转移：

for (int i = 0; i <= n; ++i)
    dp[1][i] = i - pre[1][i] + suf[1][i + 1];

for (int i = 2; i <= n; ++i)
    for (int j = 0; j <= n; ++j)
        for (int k = j; k <= n; ++k)
            dp[i][j] = min(dp[i][j], dp[i - 1][k] + j - pre[i][j] + suf[i][j + 1]);

此时状态转移时间复杂度为 \(O(n ^ 3)\)，而 \(n = 5000\)，会超时，考虑优化掉一层循环。

不难想到优化 \(dp[i – 1][k]_{k = j}^{n}\)，其只是获取前一层状态的后缀最小值，可以开一个数组存储后缀最小值，或者在转移第 \(i\) 层时逆序转移并定义 \(minn\) 为前一层的后缀最小值，跟随着转移共同更新。

此时状态转移代码为：

for (int i = 2; i <= n; ++i)
{
    int minn = INT_MAX;
    for (int j = n; j >= 0; --j)
    {
        minn = min(minn, dp[i - 1][j]);
        dp[i][j] = minn + j - pre[i][j] + suf[i][j + 1];
    }
}

由于只会用到上一层的状态，可以开滚动数组优化内存。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector a(n + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= n; ++i)
    {
        string s;
        cin >> s;

        s = ' ' + s;
        for (int j = 1; j <= n; ++j)
            if (s[j] == '.')
                a[i][j] = 1;
    }

    vector pre(n + 1, vector<int>(n + 2, 0));
    vector suf(n + 1, vector<int>(n + 2, 0));
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
            pre[i][j] = pre[i][j - 1] + a[i][j];

        for (int j = n; j >= 1; --j)
            suf[i][j] = suf[i][j + 1] + a[i][j];
    }

    vector dp(2, vector<int>(n + 1, INT_MAX));
    for (int i = 0; i <= n; ++i)
        dp[1 & 1][i] = i - pre[1][i] + suf[1][i + 1];

    for (int i = 2; i <= n; ++i)
    {
        int minn = INT_MAX;
        for (int j = n; j >= 0; --j)
        {
            minn = min(minn, dp[(i - 1) & 1][j]);
            dp[i & 1][j] = minn + j - pre[i][j] + suf[i][j + 1];
        }
    }

    int ans = INT_MAX;
    for (int i = 0; i <= n; ++i)
        ans = min(ans, dp[n & 1][i]);

    cout << ans << endl;
}

G – Lightweight Knapsack

    还没补。