E. Number of Components

方法一：考慮每個點的貢獻，認為一個聯通塊里讓編號最大的點產生貢獻
那么，對于一個點 $i$，如果對答案產生貢獻，一定要點 $i$ 存在，而點 $i+1$ 不存在。

#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr) #pragma GCC optimize(2) #include<iostream> #include<algorithm> using namespace std; using ll=long long; constexpr int N=100010; ll a[N]; int n; int main() {IO;cin>>n;for(int i=1;i<=n;i++) cin>>a[i];ll res=0;for(int i=1;i<n;i++){ll x=a[i],y=a[i+1];if(x>y)res+=1ll*(n-x+1)*(x-y);elseres+=1ll*(y-x)*x;}res+=a[n]*(n-a[n]+1);cout<<res<<'\n';return 0; }

方法二：連通塊數量=點數-邊數于是點數和邊數分開統計
點在連通塊中的情況，對于$(i,i+1)$這條邊要在連通塊中必須要求$i,i+1$同時在于是直接計算即可

#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr) #pragma GCC optimize(2) #include<iostream> #include<algorithm> using namespace std; using ll=long long; constexpr int N=100010; ll a[N]; int n; int main() {IO;cin>>n;ll res=0;for(int i=1;i<=n;i++) {cin>>a[i];res+=a[i]*(n-a[i]+1);}for(int i=1;i<n;i++){ll x=a[i],y=a[i+1];res-=min(x,y)*(n-max(x,y)+1);}cout<<res<<'\n';return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的codeforces1151 E. Number of Components（计数）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。