链接：https://ac.nowcoder.com/acm/contest/128672

A – ICPC Time

算法：

模拟。

思路：

无。

关键代码：

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

    cout << (n + 5) % 24 << endl;
}

B – 倍数

算法：

模拟。

思路：

无。

关键代码：

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

    if (s.find('0') != -1 || s.find('5') != -1)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

C – 邻合

算法：

贪心，\(dp\)。

思路1：

贪心。

若 \(x\) 与 \(y\) 互质，那么 \(gcd(x, y) = 1\)。

贪心策略 \(1\)：

容易想到当 \(a_i\) 与 \(a_{i – 1}\) 互质时，将 \(a_{i}\) 修改成 \(a_{i – 1} \times a_{i + 1}\)，此时既满足了与 \(a_{i – 1}\) 不互质，也满足了与 \(a_{i + 1}\) 也不互质。

贪心策略 \(2\)：

又因为 \(gcd(0, x) = |x|\)，当 \(a_i\) 与 \(a_{i – 1}\) 互质时，可以将 \(a_i\) 修改为 \(0\)，此时 \(a[i]\) 与前后元素都满足条件，该策略比上面思路代码更简洁。

代码：

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

    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (gcd(a[i], a[i - 1]) == 1)
        {
            ++ans;
            a[i] = 0;
        }
    }

    cout << ans << endl;
}

思路2：

\(dp\)。

定义 \(dp[i][0/1]\) 为是否保留（\(0\) 不保留，\(1\) 保留）第 \(i\) 个位置时，前 \(i\) 个位置最多保留元素个数。

考虑状态转移。

当不保留 \(a_i\) 时，无需考虑其与 \(a_{i – 1}\) 是否互质，可以直接从 \(i – 1\) 转移而来，既状态转移公式为 \(dp[i][0] = max(dp[i – 1][0], dp[i – 1][1])\)；

当保留时，需分类讨论：

• 如果 \(a_i\) 为 \(1\)，无法保留，必须修改，得 \(dp[i][1] = 0\)；
• 否则，如果 \(gcd(a_i, a_{i – 1}) = 1\)，若要保留 \(a_i\)，只能不选择 \(a_{i – 1}\)，既状态转移公式为 \(dp[i][1] = dp[i – 1][0] + 1\)；
• 如果 \(gcd(a_i, a_{i – 1}) \neq 1\)，可以保留 \(a_i\)，状态转移公式为 \(dp[i][1] = max(dp[i – 1][0] + 1, dp[i – 1][1] + 1)\)；

又因为 \(i\) 只依赖于 \(i – 1\)，遂可以开滚动数组。

代码：

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

    int ans = 0;
    array<int, 2> dp({0, 0});
    for (int i = 1; i <= n; ++i)
    {
        array<int, 2> ndp;

        ndp[0] = max(dp[0], dp[1]);

        if (a[i] == 1)
            ndp[1] = 0;
        else
        {
            if (gcd(a[i], a[i - 1]) == 1)
                ndp[1] = dp[0] + 1;
            else
                ndp[1] = max(dp[0] + 1, dp[1] + 1);
        }

        ans = max({ans, ndp[0], ndp[1]});

        dp.swap(ndp);
    }

    cout << n - ans << endl;
}

D – 对和

算法：

贡献法。

思路：

经典拆贡献。

关键代码：

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

    ll ans = 0;
    ll val1 = 0, val2 = 0;
    ll cnt1 = 0, cnt2 = 0;
    for (int i = 0; i < n; ++i)
    {
        ll cur1 = (a[i] + 1) / 2;
        ll cur2 = a[i] / 2;

        if (a[i] & 1)
        {
            ans += cur1 * cnt1 + val1;
            ans += cur2 * cnt2 + val2;

            ++cnt1;
            val1 += cur2;
        }
        else
        {
            ans += cur1 * cnt2 + val2;
            ans += cur2 * cnt1 + val1;

            ++cnt2;
            val2 += cur2;
        }
    }

    cout << ans << endl;
}

E – 镜像

算法：

搜索。

思路：

跑 \(bfs\)，存储 \((x, cnt)\)，其中 \(x\) 为当前数字，\(cnt\) 为变化为 \(x\) 的（最小）次数。

剪枝：

• 如果当前 \(x\) 的位数已经大于 \(b\) 的位数，直接返回；
• 同理，只有 \(x + k\) 的位数小于等于 \(b\) 的位数，才可以执行操作 \(2\)；
• \(k\) 值最小为 \(k\)，如果 \(a\) 可以变为 \(b\)，操作次数不会大于等于 \(b\)，既当 \(cnt \ge b\) 时，直接返回。

关键代码：

void miyan()
{
    ll a, b, k;
    cin >> a >> b >> k;

    if (k > b && a != b)
    {
        cout << -1 << endl;
        return;
    }

    auto check = [&](int x, int y) -> bool
    {
        if (to_string(x).size() <= to_string(y).size())
            return 1;

        return 0;
    };

    queue<pii> q;
    vector<int> st(b * 10, 0);
    q.push({a, 0});
    st[a] = 1;
    while (q.size())
    {
        auto [x, cnt] = q.front();
        q.pop();

        if (x == b)
        {
            cout << cnt << endl;
            return;
        }

        if (cnt > 2 * b || !check(x, b))
            continue;

        if (x % 10 != 0)
        {
            int num = x;
            int y = 0;
            while (num)
            {
                y = y * 10 + num % 10;
                num /= 10;
            }

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

        if (check(x + k, b) && !st[x + k])
        {
            st[x + k] = 1;
            q.push({x + k, cnt + 1});
        }
    }

    cout << -1 << endl;
}

F – 差异

算法：

最大子数组和。

思路：

考虑翻转 \(s_{i, j}\) 会产生什么代价？

设除 \(s_i\) 外，\(j\) 位置上 \(0\) 的个数为 \(cnt_0\) 个，\(1\) 为 \(cnt_1\) 个。

当 \(s_{i, j}\) 为 \(1\) 时，翻转前的贡献为 \(cnt_0\)，翻转后的贡献为 \(cnt_1\)，差为 \(cnt1 – cnt0\)，要使答案最小，就需要尽量选择翻转后，使贡献更小的位置，定义 \(a_j\) 为 \(cnt_1 – cnt_0\)，\(s_{i, j}\) 为 \(0\) 时同理。

容易想到对 \(a\) 数组跑最小子数组和，既可得到翻转后使答案更优的一段，后续不过多赘述，看代码即可。

关键代码：

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

        s[i] = ' ' + s[i];
    }

    vector<ll> cnt(m + 1, 0);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cnt[j] += s[i][j] == '0';

    for (int i = 1; i <= n; ++i)
    {
        ll ans = 0;
        vector<ll> a(m + 1, 0);
        for (int j = 1; j <= m; ++j)
        {
            ll cnt0 = cnt[j], cnt1 = n - cnt[j];

            if (s[i][j] == '0')
            {
                --cnt0;
                a[j] = cnt0 - cnt1;
                ans += cnt1;
            }
            else
            {
                --cnt1;
                a[j] = cnt1 - cnt0;
                ans += cnt0;
            }
        }

        vector<ll> dp(m + 1, 0);
        ll minn = 0;
        for (int j = 1; j <= m; ++j)
        {
            dp[j] = min({a[j], dp[j - 1] + a[j]});
            minn = min(minn, dp[j]);
        }

        cout << ans + minn << endl;
    }
}