Codeforces Round #775 (Div. 2, based on Moscow Open Olympiad in Informatics)

有一段时间不写题了，再加上脑子本来就不好用，哎，用了一个小时的时间找一个爆int的bug，我***直接炸了

Weird Sum

一个以后用到必须直接秒出的trick。
x坐标和y坐标分别处理。
给定 $n$ 个数，$O(nlogn)$求 ${\sum }_{i=1}^n{\sum }_{j=i+1}^n|a_i-a_j|$
容易证明: 将交换原序列任意两个相邻元素，原式结果不变。
所以先将 $a$ 数组从小到大排序，然后考虑去掉绝对值。
令$S={\sum }_{i=1}^n{a}_i$。

法一:

$$\begin{gathered} a_1的贡献：(S-a_1)-(n-1)a_1 \\ {a}_2的贡献：(S-a_1-a_2)-(n-2)a_2 \\ {a}_3的贡献：(S-a_1-a_2-a_3)-(n-3)a_3 \\ ...... \\ {a}_{n-1}的贡献：S-a_1-a_2-...-a_{n-1}-(1)a_{n-1} \end{gathered}$$
将上边的式子求和:
$ans=(n-1)S-2[(n-1)a_1+(n-2)a_2+(n-3)a_3+...+...a_{n-1}]$
如果用accumulate求和记得加 0ll ,否则会WA的很惨。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <vector>
#include <map>
#define pb push_back
using namespace std;
typedef unsigned long long ll;
int n,m,idx;
vector<ll>x[110000],y[110000];
map<int,int>mp;
int Map(int x){
    if(mp.count(x))return mp[x];
    return mp[x] = ++idx;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            ll t;cin>>t;
            t = Map(t);
            x[t].pb(i);
            y[t].pb(j);
        }
    }
    ll ans=0;
    for(ll i=1;i<=idx;i++){
        vector<ll>X(x[i]),Y(y[i]);
        sort(X.begin(),X.end());
        sort(Y.begin(),Y.end());
        ll num=X.size();
        ll tmp=0;
        for(ll j=0;j<X.size();j++){
            tmp += (num-j-1)*X[j];
        }
        ans += -2 * tmp;
        ans += (num-1)*accumulate(X.begin(),X.end(),0ll);
        tmp = 0;
        for(ll j=0;j<Y.size();j++){
            tmp += (num-j-1)*Y[j];
        }
        ans += (-2 * tmp);
        ans += (num-1)*accumulate(Y.begin(),Y.end(),0ll);
    }
    cout<<ans<<endl;
    return 0;
}

法二：

每一项分别计算，使用前缀和优化。其实就是上边的式子分开算

    ll ans=0;
    for(ll i=1;i<=idx;i++){
        if(x[i].size()==0)continue;
        vector<ll>X(x[i]),Y(y[i]);
        sort(X.begin(),X.end());
        sort(Y.begin(),Y.end());
        ll num=X.size()-1,sum;
        sum=accumulate(X.begin(),X.end(),0ll);
        for(ll j=0;j<X.size();j++){
            ans += sum-X[j];
            ans -= (num-j)*X[j];
            sum-= X[j];
        }
        num=Y.size()-1;
        sum=accumulate(Y.begin(),Y.end(),0ll);
        for(ll j=0;j<Y.size();j++){
            ans += sum-Y[j];
            ans -= (num-j)*Y[j];
            sum -= Y[j];
        }
    }

accumulate 还可以对字符串进行累加

string sum = accumulate(s.begin(),s.end(),string(""));

B. Game of Ball Passing

题意：

有n个人传球，给出每个人需要传球的次数，问最少需要使用几个球能让所有人的传球次数都用完。
当传球次数为1的可以给传球次数为0的人传球。
我各种分类讨论，还是过不了哭了啊
学下题解。
让传球次数减少的最快的操作就是让某个人传球，然后再传回来。可以发现一个临界，当$2\ast max(a_i)==\sum a_i$。 一个足刚好够用，合理外推，假设最大值时无穷，那么1个求肯定是不够用的，那是不是说$2\ast max(a_i)<\sum a_i$ 时1个球就可以了呢？答案是肯定的，因为足球从次数最多的人传出去再传回来，不等式依然成立，每次都动态的让传球次数最多的那个人传球就行了，当不等式取大于号时，可以发现猜 ans = $2\ast max(a_i)-\sum a_i$