「笔记」最值转绝对值｜绝对值求和

Intro.

Prob. A

求 $S=\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{n}\min(a_i,b_j)$ 的值。

Prob. B

求 $S=\displaystyle \sum_{i=1}^n\sum_{j=1}^n \lvert a_i-a_j \rvert$ 的值。

Sol.

Prob. A

显然我们直接求比较难求，但是我们注意到这样的一个数学性质，即 $\min(x,y)=\dfrac{x+y-\lvert x - y \rvert}{2}$。我们就可以把这个最值求和问题转化为绝对值求和（形如 Intro. Prob. B）的问题。

同理，如果我们在这里求的是 $S=\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{n}\max(a_i,b_j)$，我们根据 $\max(x,y)=\dfrac{x+y+\lvert x - y \rvert}{2}$，也能转化为相似的形式。

Prob. B

一个办法是直接暴力 $\mathcal O (n^2)$ 计算，但是对于比较大的 $n$ 是肯定会超时的。

所以我们不妨利用数学性质：把数字 $a$ 排序，然后 $\mathcal O (n)$ 计算 $(i-1) \times a_i-\sum_{j=1}^{i-1}a_j$ 的总和即可。时间复杂度为 $\mathcal O (n \log n)$（排序的时间复杂度），如果范围较小可以使用桶来优化到 $\mathcal O (n)$。

Ex.

CF2121G

题目

给定一个长度为 $n$ 的 $\tt{01}$ 字符串串，定义 $f(x)$ 为字符串 $x$ 中某一字符的最大出现次数。求 $\displaystyle \sum_{l=1}^n\sum_{r=l}^n f(s_ls_{l+1}\ldots s_r)$

我们先用记字符 $c$ 在前缀 $[1, i)$ 的出现次数为 $pre_{c,i}$，因此对于区间 $[l, r]$，其在区间内的出现次数为 $pre_{c,r}-pre_{c,l}$。于是有某一字符的最大出现次数为 $\max_{c~\in~\{\tt{0},\tt{1}\}}(pre_{c,r}-pre_{c,l})=\max(pre_{0,r}-pre_{0,l}, pre_{1,r}-pre_{1,l})$。

考虑到对于给定的 $[l, r]$ 总是有 $pre_{0,r}-pre_{0,l}+pre_{1,r}-pre_{1,l}=r-l+1$，同时根据我们上面的推论，我们可以把上式转化为 $\dfrac{r-l+1+\lvert pre_{0,r}-pre_{0,l}-(pre_{1,r}-pre_{1,l}) \rvert}{2}$，对于 $\dfrac{r-l+1}{2}$，显然易求。所以我们考虑后面的部分，变形有 $(pre_{0,r}-pre_{1,r})-(pre_{0,l}-pre_{1,l})$，记 $d_i=pre_{0,i}-pre_{1,i}$，原式为 $d_r-d_l$，相当于我们要求 $\displaystyle \sum_{l=1}^n\sum_{r=1}^n \lvert d_r - d_l \rvert$，根据 Sol. Prob. B 的办法排序后求值即可。

代码

#define int long long
void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += i * (n - i + 1);
    }
    vector<int> pre(n + 1);
    for (int i = 0; i < n; i++) {
        pre[i + 1] = pre[i] + (s[i] == '0' ? -1 : 1);
    }
    sort(pre.begin(), pre.end());
    int tot = 0;
    int sum = 0;
    for (int i = 0; i <= n; i++) {
        tot += i * pre[i] - sum;
        sum += pre[i];
    }
    ans = (ans + tot) / 2;
    cout << ans << "\n";
}

---

练习

洛谷：P12391 「RiOI-6」帝国少女

CF2131F

相关信息