牛客周赛 round 110

alisa为了督促自己学习所以写点题解，如果能帮到补题的你就再好不过了。

头文件参考

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define all(x) (x).begin(), (x).end()

A

一个正整数要么是奇数要么是偶数；其中偶数可以用若干个2表示，奇数可以用若干个2外加一个1来表示，本题中没有1 所以选择去掉一个2加一个3。

特别的，如果本来一个2都没有那去2加3 的操作就无法成立此时输出-1。

void solve()
{
    int n;
    cin >> n;
    if (n < 2)
    {
        cout << "NO";
    }
    else
    {
        cout << "YES";
    }
}

B

观察结构发现除了最角落的两个数字外，每一个数字都能作出 $2*v[i]$ 次贡献，这启发我们算出总和 $2*sum$ 然后减去最角落的两个数字即为答案

要使答案最大化，我们应该把最小的两个数字放到角落。

void solve()
{
    int n;
    cin >> n;
	vector<int> v(n + 1);
	for (int i = 1; i <= n; i++)
	{
		cin >> v[i];
	}
	
	sort(all(v));
	cout << accumulate(all(v), 0ll) - v[1] - v[2];
}

C

区间越小，mex的值越有可能变小。所以我们枚举每一个 $r = l + 1$ 的区间手动计算 $max - mex$ 即可，时间复杂度 $O(n)$

void solve()
{
    int n;
    cin >> n;
    vector<int> v(n + 1);

    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
    }

    // 只要遍历一遍就行
    int ans = LLONG_MIN;
    for (int i = 1; i + 1 <= n; i++)
    {
        int n1 = v[i], n2 = v[i + 1];
        int maxnum = max(n1, n2);
        int mex = 0;
        if (n1 == 0 or n2 == 0)
        {
            mex++;
            if (n1 == 1 or n2 == 1)
            {
                mex++;
            }
        }
        ans = max(ans, maxnum - mex);
    }
    cout << ans;
}

D

看到绝对值想到把它展开。

具体来说， $\sum\limits a[i]-m = \sum_{a[i]<m} m-a[i] + \sum_{a[i]>m} a[i] - m$ 这样一拆，我们就能把绝对值转化为线性形式：

左边部分： $v*cnt\_left - sum\_left$
右边部分： $sum\_right-v*cnt\_right$ 这就能用前缀和快速计算，而不用每次循环去算所有差值。复杂度从 $O(n)$ 降低到了 $O(1)$

知道了这个知识，现在让我们来看中位数会如何改变。

假设数组长度 n。删去一个数后，剩下 n−1 个数，新的中位数位置就是：

m=\frac{(n-1)-1}{2}=\frac{n-2}{2}

(0 based)

所以：

新中位数一定是 排序后第 m 个数，不过需要跳过被删掉的那个。换句话说：
删去不同的数，中位数可能是 相邻的两个元素之一。例子：
n=5，原数组排序后中位数是下标 2。删掉一个数后：
- 新长度=4 → 新中位数在下标 1。
- 如果删掉原来排在前半部分的数，中位数候选是原数组的第 2 位；
- 如果删掉后半部分的数，中位数候选是原数组的第 1 位。

因此，中位数的可能性非常有限。

总体思路总结：

sort
枚举删除哪个数（n 次）。
每次确定新的中位数位置（下标 m），并对应到原数组：
- 如果删除点在中位数左边，新中位数要右移一位。
- 否则就是当前位置。
用前缀和在 $O(1)$ 算新平衡度。
取最小值。总体时间复杂度 $O(n \log n)$

void solve()
{
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    sort(all(v));
    vector<int> pre(n + 1, 0);
    for (int i = 0; i < n; i++)
    {
        pre[i + 1] = pre[i] + v[i];
    }
    int m_new = (n - 2) / 2;
    int ans = LLONG_MAX;
    for (int k = 0; k < n; k++)
    {
        int pos = m_new + (m_new >= k ? 1 : 0);
        int cur = v[pos];
        int sum_l = pre[pos] - (k < pos ? v[k] : 0);
        int cnt_l = pos - (k < pos ? 1 : 0);
        int sum_r = (pre[n] - pre[pos + 1]) - (k > pos ? v[k] : 0);
        int cnt_r = (n - pos - 1) - (k > pos ? 1 : 0);
        int tot = cur * cnt_l - sum_l + sum_r - cur * cnt_r;
        ans = min(ans, tot);
    }
    cout << ans;
}

E

如何计算数根

alisa 想了很久，都没有办法很好的展示 $\mod 9$ 是如何得到数根的，为此咕咕到了现在但是我好像找到了一种感性的理解方式：

对于一个数字，各位相加的过程其实等价于减去若干个9的倍数。

譬如 76 要想得到7+6 只需要计算 $76-7*9$ ，这是因为 $76 = 70 + 6$ 而对于每一个10 把它减去9就能得到1。

同样的道理，要计算521的数位之和，应当对每一个100都减去99，对每一个10都减去9

最终我们会得到一个一位数 $r$ ，因为先前的每一步操作都不改变 $\mod 9$ 的余数，所以：

$r≡N (\mod 9)$

这启示我们，要计算一个数的数根，只需要把这个数字对9取模即可。

但是，这个计算公式需要我们知道数字N 还可以如何转化呢

我们不直接计算数字N 而是想办法凑出 $N\%9$

对于一个数字串 $s_{1}s_{2}s_{3}...s_{n-1}s_{n}$ 他对应的十进制数可以被拆解为

$N=s_{1} \cdot 10^{n-1}+s_{2} \cdot 10^{n-2}+s_{3} \cdot 10^{n-3}+...+s_{(n-1)} \cdot 10^{n-(n-1)}+s_{n} \cdot 10^{n-n}$

把等式两侧分别对9取模，可以得到

$N\mod 9 = s_{1}+s_{2}+s_{3}+...+s_{n-1}+s_{n} \mod 9$

(这是因为 $10 \mod 9 = 1$ )

跟上面的结论结合在一起，我们注意到要求521的数根，其实只要5+2+1然后将结果对9取模就好了！

而5+2+1的过程是可以用前缀和来统计的。

问题转化

形式化地说：定义前缀和

$pre[i] = s_{1}+s_{2}+...+s_i$

那么任意子串 $[l, r]$ 的数字和即为

$S(l, r)=pre[r]-pre[l-1]$

那么子串模9 就可以被转化为

$S(l, r) \mod 9=pre[r]-pre[l-1] \mod 9$

这把“子串问题”转成了“两个前缀的差”的问题，不可不谓是质的突破。

接下来我们的任务目标就是在遍历字符串的同时，对前缀和的信息动手脚了。

把“统计所有子串”变成“统计前缀模的配对”

想统计多少子串 $[l, r]$ 满足子串模为t

$(pre[r]-pre[l-1])\mod 9=t$ 等价于 $pre[l-1]=(pre[r]-t)\mod9$ 我们采取外层循环遍历r，内层循环遍历t $t \in [0, 8]$

固定右端 r 后，满足条件的左端数目 = 之前出现过的前缀模等于 $(pre[r]-t)\%9$ 的次数。

所以如果你从左到右遍历 r，并维护一个数组 cnt[t]（记录之前前缀模为 t 的次数），那么对于每个 r、每个目标余数 t，你可以立刻得到贡献 cnt[(P[r]-t) mod 9]。把 t 从 $[0, 8]$ 都加上，就得到了以 r 为右端的所有子串模分布。

配对技巧

上面提供的是一种常见的配对统计技巧，我们可以来打个表看看为什么可以处理所有子串

遍历到 $s[1]$ 记录1的信息
遍历到2 先累加之前1的信息，得到12的信息；接着记录2的信息
遍历到3 先累加之前12,2的信息得到123，23；接着记录3的信息
... 所以，遍历到i位置的时候，我们总能确保前面所有子串的信息都已经被记录。下次遇到形如 $a[l]+a[r]=k$ 的式子的时候，我们也可以尝试采用枚举r和k 然后从预处理信息中找 $a[l]$ 的做法。

统计答案（完整步骤）

维护一个长度 9 的计数数组 cnt[0..8]，cnt[t] 表示已经遇到的前缀（包括空前缀）中模为 t 的个数。
- 初始：cnt[0] = 1（空前缀，代表 l=1 的子串）。
维护当前前缀和模 pref（也就是 pre[r] % 9）。初始化 pref = 0。
维护一个变量 ans（用来累积数字根之和），初始 ans = 0。
从左到右遍历每个位置 r = 1..n（处理字符 s[r]）：
1. 用 pref = (pref + digit(s[r])) % 9 更新当前前缀模（这里 digit(s[r]) 是字符转成的 0..9）。
2. 用历史 cnt 来统计以 r 为右端的新产生的所有子串的数字根之和：
  - 对历史前缀模 t（t = 0..8`）：
    - 该历史前缀与当前 pref 配对会产生模 v = (pref - t + 9) % 9 的若干子串，数量为 cnt[t]（对应所有 l 使得 `pre[l] % 9 = t）。
    - 数字根贡献：
      - 如果 v != 0：这些子串每个的数字根 = v，所以总贡献 v * cnt[t]。
      - 如果 v == 0：这些子串中 非全零 的会贡献 9（数字根 = 9），但全零的子串贡献 0。为了实现简单，在此处统一把 v == 0 的子串暂且当作 9 来加，即加 9 * cnt[t]。（以后统一修正）
    - 所以在遍历 m 时可以执行 ans += (v ? v : 9) * cnt[t]。
3. 完成上述统计后，把当前前缀模记入历史：cnt[pref]++（注意顺序：先统计再更新 cnt，否则会把包含当前 r 的左端错误地计为历史）。
遍历结束后，你已经把每个模为 0 的子串都当作 9 加进去了（包含那些实际为 0 的全零子串）。现在需要修正：
- 计算全零子串的数量 Z：扫描字符串中的每一段连续零段，长度为 L 的零段包含 L*(L+1)/2 个全零子串，累加得到 Z。
- 把多加的 9 * Z 减回：ans -= 9 * Z。
最终 ans 即为所有连续子串（去掉前导零后表示的整数）的数字根之和。

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

    vector<int> cnt(9);
    int pref = 0;
    cnt[0] = 1;
    int ans = 0;
    for (int r = 0; r < n; r++)
    {
        pref = (pref + s[r] - '0') % 9; // 记录 pre[r]

        for (int t = 0; t <= 8; t++)
        {
            // pre[l - 1] % 9 == t
            auto val = (pref + 9 - t) % 9;
            ans += (val ? val : 9) * cnt[t];
        }

        cnt[pref]++;
    }

    int Z = 0;
    int L = 0;
    for (auto c : s)
    {
        if (c - '0' == 0)
        {
            L++;
        }
        else
        {
            Z += (L + 1) * L / 2;
            L = 0;
        }
    }

    Z += (L + 1) * L / 2; // 别忘了最后再算一次！
    ans -= 9 * Z;         // 每一个0多贡献了9
    cout << ans;
}

F

正在写喵...