1 条题解
-
0
题意
已知一条链,每个节点 与节点 之间有一条边。
每个点有一个点权 ,。
定义 表示只保留点权为 的点,其余点全部删去,所得到的图的联通块个数。
求 。
题解
考虑分解总和,进行分开求解。
对于一组 ,如果有一个 满足 且 ,那么联通块个数加一。
所以枚举每个 统计答案即可,时间复杂度 。
#include<bits/stdc++.h> using namespace std; const int N=1e5+5; int n,a[N]; long long ans; int main(){ std::ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++){ if(a[i]>a[i-1])ans+=1ll*(a[i]-a[i-1])*(n-a[i]+1); else ans+=1ll*a[i]*(a[i-1]-a[i]); } cout<<ans; }
- 1
信息
- ID
- 2051
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 6
- 已通过
- 2
- 上传者