Codeforces #364 B. Mishka and trip
传送门:http://www.codeforces.com/contest/703/problem/B
题目翻译
一个N点的图,其中有K个点是重要点。
首先这个图中,1与2连接,2与3连接……N-1与N,N与1都连接(这是一个大环)
然后所有的重要点K,它与其他所有的点有一条边连接
每个点具有一个权值c,每一条边的“魅力值”是它所连接的两个c的乘积,求所有边魅力值之和
题解
乘法分配律
我们统计每个点所连接的点的魅力值之和,然后用其乘自己的魅力值。如此求和再/2就是答案。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
/* Author : WNJXYK Problem : B Blog : http://wnjxyk.cn Date : 2016 */ #include<cstdio> #include<cstdlib> #include<ctime> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<set> #include<vector> #include<map> using namespace std; #define LL long long const int Maxn=100000; int n,k; LL C[Maxn+5]; bool inK[Maxn+5]; LL SumK=0; LL SumAll=0; LL Ans=0; int main(){ //freopen("in.txt","r",stdin); scanf("%d%d",&n,&k); for (int i=1;i<=n;i++) scanf("%I64d",&C[i]); for (int i=1;i<=k;i++){ int x; scanf("%d",&x); inK[x]=true; SumK+=C[x]; } for (int i=1;i<=n;i++) SumAll+=C[i]; for (int i=1;i<=n;i++){ int px=i-1,ax=i+1; if (px<=0) px=n; if (ax>n) ax=1; if (!inK[i]) Ans += C[i]*(LL)(SumK + (inK[px]?0:C[px]) + (inK[ax]?0:C[ax]) - (inK[i]?C[i]:0) ); else Ans += C[i]*(LL)(SumAll - C[i]); //cout<<"#"<<i<<" : "<<(SumK + (inK[px]?0:C[px]) + (inK[ax]?0:C[ax]) - (inK[i]?C[i]:0) )<<endl; } Ans/=(LL)2; printf("%I64d\n",Ans); return 0; } |

原文链接:Codeforces #364 B. Mishka and trip
WNJXYKの博客 版权所有,转载请注明出处。
还没有任何评论,你来说两句吧!