原题链接：
http://codeforces.com/problemset/problem/703/B
题意：
有n个城市，1-n形成一个环，其中有k个省会，每个省会应该和每个城市都连起来。每个城市有一个美丽值，两城市之间的连路的美丽值为两城市美丽值的乘积，要求所有连路的美丽值的总和。
分析：
首先想到的是先把所有情况加起来，再减去会重复的。但是写起来比较麻烦而且重复的难以理清，而且感觉怎么写都会超时。所以我们可以先不考虑省会的城市，连把环路的美丽值加起来，得ans=∑(n < i<=0)beauty[i]*beauty[(i+1)%n]，并且记录所有城市美丽值的和sum（因为后面考虑首都的时候都是要乘其他的城市的美丽值然后求和）。在考虑首都的时候，只需要减去在sum中减去自己，并且把自己标记，用tmp暂存对于当前首都的sum值，标记是为了证明当前省会已经和其他所有城市连接过了，并且在sum值中已经减过，然后在处理后面的省会的时候，当相邻的没被标记【说明不是省会】，就需要把tmp减掉相邻的美丽值，因为在环路中已经计算过，接下来就是ans+=tmp×beauty[cap[i]]。跑完循环就是答案。复杂度O(n)
代码：
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<vector> 5 #include<set> 6 #include<map> 7 #include<algorithm> 8 #include<string> 9 #include<queue> 10 #include<cmath> 11 #include<stack> 12 #include<cctype> 13 #include<list> 14 15 16 #define ll long long 17 #define ull unsigned long long 18 19 using namespace std; 20 21 const int maxn=100010; 22 const int inf=1<<30; 23 24 ll be[maxn]; 25 ll ci[maxn]; 26 bool flag[maxn]; 27 28 int main() 29 { 30 //#define DEBUG 31 32 #ifdef DEBUG 33 freopen("in.txt","r",stdin); 34 //freopen("out.txt","w",stdout); 35 #endif 36 37 int n,k; 38 scanf("%d%d",&n,&k); 39 ll sum=0; 40 ll ans=0; 41 for(int i=0;i<n;i++){ 42 scanf("%I64d",&be[i]); 43 sum+=be[i]; 44 } 45 for(int i=0;i<n;i++){ 46 ans+=be[i]*be[(i+1)%n]; 47 } 48 for(int i=0;i<k;i++){ 49 scanf("%I64d",&ci[i]); 50 } 51 ll tmp; 52 for(int i=0;i<k;i++){ 53 if(!flag[ci[i]-1]){ 54 sum-=be[ci[i]-1]; 55 flag[ci[i]-1]=1; 56 } 57 tmp=sum; 58 if(!flag[(ci[i]-2+n)%n]){ 59 tmp-=be[(ci[i]-2+n)%n]; 60 } 61 if(!flag[(ci[i])%n]){ 62 tmp-=be[(ci[i])%n]; 63 } 64 ans+=tmp*be[ci[i]-1]; 65 } 66 printf("%I64d ",ans); 67 return 0; 68 }