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

A. Letter Home

算法：

    模拟。

思路：

    分类讨论，判断是在全部点的左、右或中间即可。

关键代码：

void solve()
{
    int n, s;
    cin >> n >> s;
    vector<int> a(n + 10);
    cin >> a;

    sort(a.begin(), a.begin() + n);

    ll ans;

    if (s <= a[0])
    {
        ans = a[n - 1] - s;
    }
    else if (s >= a[n - 1])
    {
        ans = s - a[0];
    }
    else
    {
        ll cnt = min(s - a[0], a[n - 1] - s);
        ans = cnt * 2 + max(s - a[0], a[n - 1] - s);
    }

    cout << ans << endl;
}

B. Above the Clouds

算法：

    模拟。

思路：

    无。

关键代码：

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

    map<char, int> m;
    for (int i = 0; i < n; ++i)
        ++m[s[i]];

    for (int i = 1; i < n - 1; ++i)
    {
        if (m[s[i]] > 1)
        {
            cout << "YES" << endl;
            return;
        }
    }

    cout << "NO" << endl;
}

C. Those Who Are With Us

算法：

    模拟。

思路：

    判断 max (最大值) 是否出现在一个十字上即可，成立答案为 max - 1，否则为 max。

关键代码：

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n + 10, vector<int>(m + 10));

    ll maxx = LLONG_MIN;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            cin >> a[i][j];
            maxx = max(maxx, 1ll * a[i][j]);
        }
    }

    map<int, int> mx, my;
    vector<pii> xx, yy;
    ll ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (a[i][j] == maxx)
            {
                ++mx[i], ++my[j];
                ++ans;
            }
        }
    }

    if (ans == 2)
    {
        cout << maxx - 1 << endl;
        return;
    }

    for (auto [x, cnt] : mx)
        xx.push_back({cnt, x});
    for (auto [y, cnt] : my)
        yy.push_back({cnt, y});

    sort(all(xx));
    sort(all(yy));

    auto [cntx, fx] = (*xx.rbegin());
    auto [cnty, fy] = (*yy.rbegin());

    if ((cntx == 1 && cnty == ans - 1) || (cnty == 1 && cntx == ans - 1))
    {
        cout << maxx - 1 << endl;
        return;
    }

    ll cnt = 0;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (a[i][j] == maxx)
            {
                if (i == fx || j == fy)
                    ++cnt;
            }
        }
    }

    if (cnt >= ans)
        cout << maxx - 1 << endl;
    else
        cout << maxx << endl;
}

D. 1709

算法：

    模拟，排序。

思路：

    无。

关键代码：

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

    vector<int> a(n + 10);
    vector<int> b(n + 10);

    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= n; ++i)
        cin >> b[i];

    vector<pii> op;
    for (int i = 1; i <= n - 1; ++i)
    {
        for (int j = 1; j <= n - 1; ++j)
        {
            if (a[j] > a[j + 1])
            {
                swap(a[j], a[j + 1]);
                op.push_back({1, j});
            }
        }
    }
    for (int i = 1; i <= n - 1; ++i)
    {
        for (int j = 1; j <= n - 1; ++j)
        {
            if (b[j] > b[j + 1])
            {
                swap(b[j], b[j + 1]);
                op.push_back({2, j});
            }
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        if (a[i] > b[i])
        {
            swap(a[i], b[i]);
            op.push_back({3, i});
        }
    }

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

E. Sponsor of Your Problems

算法：

    贪心，模拟。

思路：

    当 l = r 时，区间中只有一个数 x，此时 f(l, x) + f(x, r) = f(l, l) + f(l, l) = 数字长度 × 2，直接输出即可。

    当 l ≠ r 时，从高位开始逐位比较，找到它们从前往后最长相同的前缀，记作前 k 位相同。对于任意 l ≤ x ≤ r，如果我们选的 x 也保留这 k 位不变，则 f(l, x) 和 f(x, r) 至少都能获得 k 分，总共贡献 2k。

    关键在于从第 k+1 位开始的处理。分两种情况讨论：

1. 如果第 k+1 位上，l[k] 和 r[k] 差值大于 1，说明在这一位我们可以自由选择一个既不等于 l[k] 也不等于 r[k] 的数，这样 f(l, x) 和 f(x, r) 在这一位上都不会增加，也就不会产生额外贡献。因此，此时的最小值就是 2k，后面的位我们完全可以绕开 l 和 r，避免任何重复。
2. 如果第 k+1 位上，l[k] 和 r[k] 差值等于 1，说明 x[k] 只能取 l[k] 或 r[k]，这一位无论怎么选都会对 f(l, x) 或 f(x, r) 产生 1 分的贡献，答案因此增加 1 分。我们继续向后看，若存在某一位 i，使得 l[i] = 9 且 r[i] = 0，这样该位 x[i] 也只能选 9 或 0，无法绕开，也必须产生 1 分的贡献，所以每出现一次这种情况就再加 1。

    最终答案就是 2k，加上后面无法绕开的每一位的必要贡献。

关键代码：

void solve()
{
    string l, r;
    cin >> l >> r;

    if (l == r)
    {
        cout << l.size() * 2 << endl;
        return;
    }

    int n = l.size();

    int pos = -1;
    for (int i = 0; i < n; ++i)
    {
        if (l[i] != r[i])
        {
            pos = i;
            break;
        }
    }

    if (abs(l[pos] - r[pos]) > 1)
    {
        cout << pos * 2 << endl;
        return;
    }

    ll ans = 2 * pos + 1;
    for (int i = pos + 1; i < n; ++i)
    {
        if (l[i] == '9' && r[i] == '0')
            ++ans;
        else
            break;
    }

    cout << ans << endl;
}

F. Yamakasi

算法：

    贪心，双指针，前缀和，哈希表。

思路：

    前置问题：怎么在 O(n) 的时间内求出数组中和为 s 的子数组个数。

        定义前缀和 \(sum_i\) 表示数组中前 i 个数组的和( 1base )，那么一段数组的和就可以表示为 \(sum_r – sum_{l – 1}\)，那么要求和为 s 的子数组就是在求 \(sum_r – sum_{l – 1} = s\) 的子数组，该式子就可变形为 \(sum_{l – 1} = sum_r – s\)，此时就可以只用遍历一遍前缀和数组，使用 i 当作当前点再用一个哈希表存储当前点前所有的 \(1 \text{ ~ } i – 1\) 的子数组和，判断哈希表内是否存在 \(sum_i – s\) 的值累加起来即可。

    此时就可以找出最大值为 x 的区间，再在累加哈希表中的值即可。

    怎么在 O(n) 的时间找出所有最大值为 x 的区间呢？

    定义一个 pos 代表区间左端点，初始时 pos = 1，遍历所有数组，i 为当前点，当：

• \(a[i] < x\) 时，继续移动 i 即可。
• \(a[i] = x\) 时，这个点可以当作区间内的点。
• \(a[i] > x\) 时，这个点不能作为任何区间内的点，令 \(pos = i + 1\) 即可。

    此时就可以找出区间所有点最大值是 x 的区间。

    将以上两个混合之后的操作就为：

• 定义 \(sum_i\) 为前缀和数组，hash 为哈希表，pos 代表为加入还未加入哈希表的最小左边界，i 为当前点。
• \(a[i] < x\) 时，继续移动 i 即可。
• \(a[i] = x\) 时，将 pos 到 i 的所有 \(1 \text{~} pos – 1\) 的 sum 值加入到哈希表中。
• \(a[i] > x\) 时，这个点不能作为任何区间内的点，令 \(pos = i + 1\) ，清空哈希表即可。
• 每次循环都判断一下哈希表内有没有 \(sum_i – s\) ，存在就用累加答案即可。

关键代码：

void solve()
{
    ll n, s, x;
    cin >> n >> s >> x;
    vector<int> a(n + 10);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

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

    map<ll, int> m;
    int pos = 1;
    ll ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (a[i] > x)
        {
            m.clear();
            pos = i + 1;
        }
        else if (a[i] == x)
        {
            while (pos <= i)
            {
                ++m[sum[pos - 1]];
                ++pos;
            }
        }

        ans += m[sum[i] - s];
    }

    cout << ans << endl;
}

G. Gangsta

算法：

    前缀和，推公式，排序。

思路：

    定义 \(f(s[l..r]) = \max(cnt_0, cnt_1)\)，而实际的子串长度为 \(len = r – l + 1\)，
所以有：

\(f = \frac{len + |cnt_1 – cnt_0|}{2}​ = \frac{s_0 + s_1}{2}\)

    题目要求我们求出所有区间的 f 的和，通过以上公式我们可以分别求出 \(s_0\) 和 \(s_1\) 再对结果除二即可。

    对于 \(s_0 = len\)，只需求出所有区间的长度，可以发现最长区间长度为 n 且出现 1 次，最短区间长度为 1 且出现 n 次，通过此规律只需通过以下代码求得：

for (ll i = 1; i <= n; ++i)
    ans += i * (n - i + 1ll);

    接下来我们处理 \(s_1\)​，即所有区间中 \(|cnt_1 – cnt_0|\) 的总和。

    我们设字符 '1' 的权值为 +1，字符 '0' 的权值为 -1，构造前缀和数组 \(pre\)，其中 \(pre[i]\) 表示前 i 个字符中 '1' 的数量减去 '0' 的数量，即： \(pre[i] = pre[i-1] + (s[i] == ‘1’ ? 1 : -1)\)

    对于任意区间 \([l, r]\)，有： \(cnt_1 – cnt_0 = pre[r] – pre[l – 1]\)

    我们需要对所有这样的区间差值取绝对值并求和，即统计所有 \(|pre[r] – pre[l – 1]|\) 的总和，转换成经典问题：求一个数组中所有前缀和的两两差值的绝对值之和。

    我们将前缀和数组 \(pre[0], pre[1], \ldots, pre[n]\) 排序，记排序后的数组仍为 \(pre\)，那么对于第 i 个元素，它对答案的贡献为： \(pre[i] \times (2i – n)\)

    因此我们可以通过以下代码计算这一部分贡献：

sort(pre.begin(), pre.begin() + n + 1);
for (ll i = 0; i <= n; ++i)
    ans += pre[i] * (i - (n - i));

最后，\(f = \frac{s_0 + s_1}{2}\)，我们已经分别求出了 \(s_0\)​ 和 \(s_1\)​，将总和除以 2 即为最终答案。

关键代码：

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

    s = ' ' + s;

    vector<ll> pre(n + 10, 0);
    for (int i = 1; i <= n; ++i)
        pre[i] = pre[i - 1] + (s[i] == '1' ? 1 : -1);

    ll ans = 0;
    for (ll i = 1; i <= n; ++i)
        ans += i * (n - i + 1ll);

    sort(pre.begin(), pre.begin() + n + 1);
    for (ll i = 0; i <= n; ++i)
        ans += pre[i] * (i - (n - i));

    cout << ans / 2 << endl;
}

H. Ice Baby

    还没补。