首页 > 其他 > 详细

Codeforces Round #553 (Div. 2) E 贡献

时间:2019-05-05 13:01:25      阅读:144      评论:0      收藏:0      [点我收藏+]

https://codeforces.com/contest/1151/problem/E

题意

一条长n的链,每个点上有值\(a[i]\),定义\(f(l,r)\)为该区间的\(值\)所代表的点留下来后的联通块数量,求\(\sum^n_{l=1} \sum^n_{r=1} f(l,r)\)

题解

  • 计算贡献,计算每个点留下后作为联通块的第一个点的情况数就是这个点的贡献

代码

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
ll n,a[100005],ans,r;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        if(a[i]>a[i-1]){
            r=n;
            ans+=(r-a[i]+1)*(a[i]-a[i-1]);
        }else if(a[i]<a[i-1]){
            r=a[i-1]-1;
            ans+=(a[i])*(a[i-1]-a[i]);
        }
        //cout<<ans<<endl;
    }
    cout<<ans;
}

Codeforces Round #553 (Div. 2) E 贡献

原文:https://www.cnblogs.com/VIrtu0s0/p/10812205.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!