Codeforces Round #553 (Div. 2) E 贡献
2024-09-11 10:43:01
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;
}
最新文章
- 在nginx中配置如何防止直接用ip访问服务器web server及server_name特性讲解
- CMake安装(linux)
- Android自定义相机拍照、图片裁剪的实现
- html5 大幅度地增加和改良input元素的种类
- 关于windows程序的学习及思考系列之一
- log4j详细配置说明
- 转:Android模拟器连接电脑网络
- jQuery UI 之 Bootstrap 快速入门
- centos下pg_dump的服务器版本不匹配问题
- DSO分类及应用
- Wpf中鼠标样式的修改,作用点修改
- java 解析xml文档---通过XmlPullParser解析方式
- MongoDB固定集合(Capped Collections)
- (转)关于docker的15个小tip
- Angular20 nginx安装,angular项目部署
- java使用POI将数据导出放入Excel
- 26.Odoo产品分析 (三) – 人力资源板块(6) – 工资表(2)
- vi怎么统计查找字符串的个数
- PPT文件流转为图片,并压缩成ZIP文件输出到指定目录
- cocos2d JS 自定义事件分发器(接收与传递数据) eventManager