链接：https://codeforces.com/contest/2140

A. Shift Sort

算法：

    贪心。

思路：

    手玩几组样例后发现每次只能将一个 \(1\) 换到正确位置，直接找有几个 \(1\) 不在正确地方即可。

关键代码：

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

    cout << count(s.begin(), s.begin() + ranges::count(s, '0'), '1') << endl;
}

B. Another Divisibility Problem

算法：

    数学。

思路：

    通过题目可知需求的 \(y\) 需要满足( \(k\) 为 \(y\) 的位数 )：

\(x\cdot 10^{k}+y\equiv 0\ (\mathrm{mod}\ x+y)\)

    其中：

\(x\cdot 10^{k}+y = x \cdot (10 ^ k – 1) + x + y\)

    代入原式得：

\(x \cdot (10 ^ k – 1) + x + y\equiv 0\ (\mathrm{mod}\ x+y) \Rightarrow x \cdot (10 ^ k – 1) \equiv 0\ (\mathrm{mod}\ x+y) \)

    通过上式可知要想让式子成立，必须有 \(x \cdot (10 ^ k – 1)\) 是 \(x+y\) 的倍数，既后者是前者的因子，令 \(k = 1\) 得 \(3 \cdot x\) 就是前者的一个因子，那么令 \(3 \cdot x = x + y\)，得 \(y = 2 \cdot x\)。

关键代码：

void solve()
{
    ll x;
    cin >> x;

    cout << (x << 1) << endl;
}

C. Ultimate Value

算法：

    贪心，博弈论。

思路：

    不难猜到游戏只会进行一轮，既：

• 如果某对元素交换会增加答案，那么爱丽丝会交换这对元素，否则她会直接结束游戏。
• 鲍勃必然会直接结束游戏，因为鲍勃交换了某对减小答案的元素后，爱丽丝可以交换回来，既怎么交换对他都没好处，直接结束便是最优策略。

关键代码：

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

    if (n == 1)
    {
        cout << a[0] << endl;
        return;
    }

    ll sum = 0;
    for (int i = 0; i < n; ++i)
    {
        if (i & 1)
            sum -= a[i];
        else
            sum += a[i];
    }

    ll ans = sum;
    for (int i = 0; i < n; ++i)
        ans = max(ans, sum + i - (i & 1));

    ll minn1 = 1e15, minn2 = 1e15;
    for (int i = 0; i < n; ++i)
    {
        if (i & 1)
        {
            ans = max(ans, sum + i + 2 * a[i] - minn2);
            minn1 = min(minn1, i - 2 * a[i]);
        }
        else
        {
            ans = max(ans, sum + i - 2 * a[i] - minn1);
            minn2 = min(minn2, i + 2 * a[i]);
        }
    }

    cout << ans << endl;
}

D. A Cruel Segment’s Thesis

算法：

    排序，贪心。

思路：

    因为每条线段都会取到，所以每条线段都会对答案贡献 \(r – l\)。

    每次配对两条线段会产生一条额外的线段 \([x, y]\)，长度为 \(y – x\)。

    为了让这条线段尽可能的长，必然是选择配对线段中更小的那个 \(l\) 和配对线段中更大的那个 \(r\)。

    怎么选更优？

    可以发现每个线段如果选择其左端点那么他的贡献为 \(-l\), 如果选择其右端点那么他的贡献为 \(+r\)。

    那么一条线段从选择左端点换为选择右端点其增量为 \(d = +r – (-l) = r + l\)。

    也就是说：

• 默认选择所有线段左端点，贡献都为 \(-l\)。

• 然后选择 \(k\) 条，将他们翻转为选择右端点，既 \(-l\) 变成 \(+r\)，此时贡献变化为 \(r + l\)

• 那么我们就可以选择 \(k\) 条 \(l + r\) 值最大的线段去当右端点。

    对于 \(n\) 为奇数时，会空出来一条线段 \(R\)，那么这条线段除了本身外，还有可能对答案做出增量：

• 如果 \(R\) 的左端点比较小，他就可以代替选择当作左端点的线段，直接贪心的选择一条最大当作左端点的线段的左端点
• 如果 \(R\) 的右端点比较大，他就可以代替选择当作右端点的线段，直接贪心的选择一条最小当作右端点的线段的右端点

关键代码：

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

    ll ans = 0;
    vector<pii> range(n + 1);
    for (auto &[x, y] : range | views::drop(1))
    {
        cin >> x >> y;
        ans += y - x;
    }

    sort(range.begin() + 1, range.end(), [&](pii a, pii b) -> bool
         { return (a.first + a.second) < (b.first + b.second); });

    if (n % 2 == 0)
    {
        for (int i = 1; i <= n; ++i)
        {
            if (i <= n / 2)
                ans -= range[i].first;
            else
                ans += range[i].second;
        }
    }
    else
    {
        ll minn = 1e9, maxx = -1e9;
        for (int i = 1; i <= n; i++)
        {
            if (i <= n / 2)
                ans -= range[i].first, maxx = max(maxx, 1ll * range[i].first);
            else if (i > n / 2 + 1)
                ans += range[i].second, minn = min(minn, 1ll * range[i].second);
        }

        ans = max({ans, ans + maxx - range[n / 2 + 1].first, ans + range[n / 2 + 1].second - minn});
    }

    cout << ans << endl;
}

E1. Prime Gaming (Easy Version)

    还没补。