Sequence Pair Weight

題意：

一個數組a，其中兩個一樣的數的貢獻為1，問這個數組的所有子串的貢獻和是多少?

題解：

舉例：
對于[1，2，1，2，1，1，4]
我們考慮第三個1，他會有什么貢獻?
(x表示不選)
第一個1和他配對的情況：
[1,2,1,2,1,x,x]
[1,2,1,2,1,1,x]
[1,2,1,2,1,1,4]
第二個1和他配對的情況：
[x,2,1,2,1,x,x]
[x,2,1,2,1,1,x]
[x,2,1,2,1,1,4]

[x,x,1,2,1,x,x]
[x,x,1,2,1,1,x]
[x,x,1,2,1,1,4]

大家有看出什么規律嗎？
對于第三個1，他的貢獻為在他之前的所有1的長度(這個長度為兩個1之間的長度)，比如第一個1的長度為1（到數組頭），第二個1的長度為2（到第一個1），然后乘以第三個1后面的數量，因為后面數可以順著跟
仔細看看上面的舉例分析就明白了

代碼：

#include<iostream> #include<cstdio> #include<map> using namespace std; int T,a[100050],n; long long ans; map<long long,long long> mp; int main() {scanf("%d",&T);while(T--){ans=0;mp.clear();scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%d",&a[i]);}for (int i=1;i<=n;i++){ans=ans+(n-i+1)*mp[a[i]];mp[a[i]]+=i;}printf("%lld\n",ans);} }

總結

以上是生活随笔為你收集整理的Sequence Pair Weight的全部內容，希望文章能夠幫你解決所遇到的問題。

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