雅虎网站收录入口商丘建设网站

题目在这里

大意:
MAD函数返回出现次数$\ge 2$的最大整数
$b_i$ = $MAD(a[1,2,...i])$
每次操作把$a_i$进行上述操作，直到全变为0为止，对每次操作的数组进行求和，记为$sum$,问sum的大小

分析:
经过一次运算总可以得到非递减的序列,因为MAD函数非递减，最大值只会越来越大
只有连续的数段可以向右传递,做一次虽然非递减，但是会有只有单个的情况这是不可以向右传递的
我们可以再做一次计算去除这些数，剩下就是可以向右传递的

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;    
void calc(vector<int>&a,i64 &s){map<int,int> mp;i64 now = 0;vector<int> res(n+1,0);for(int i = 1;i<=n;++i){mp[a[i]]++;if(mp[a[i]]>=2&&a[i]>now){now = a[i];}res[i] = now;}a = res;for(int i = 1;i<=n;++i){//cout<<a[i]<<' ';s+=a[i];}//cout<<s<<"\n";
}
void solve(){cin>>n;vector<int>a(n+1);i64 s = 0;for(int i = 1;i<=n;++i) cin>>a[i],s+=a[i];calc(a,s);calc(a,s);for(int i = 1;i<=n;++i){s+=(n-i)*1LL*a[i];}//cout<<s<<"\n";
}signed main(){ios;int t;cin>>t;while(t--){solve();}return 0;
}

读错题目了好难受qaq