首页 > 代码库 > Codeforces 703B Mishka and trip

Codeforces 703B Mishka and trip

题目大意:有n个城市,k个省会,每个城市有一个魅力值,两个城市之间的连线的价值等于两个城市魅力值的乘积。省会城市和每个城市相连,城市i和城市i+1相连,城市n与城市1相连。求所有连线的和。

题目思路:v[k]*v[1]+v[k]*v[2]+……v[k]*v[n]=v[k]*(v[1]+v[2]+……v[n])。为了节省时间预处理城市魅力值的和。

技术分享
#include<iostream>#include<algorithm>#include<cstring>#include<vector>#include<stdio.h>#include<stdlib.h>#include<queue>#include<math.h>#include<map>#define INF 0x3f3f3f3f#define MAX 1000005#define Temp 1000000000using namespace std;int v[MAX],vis[MAX],a[MAX],n,k,len;int main(){    int num,i,j;    long long sum1,sum2,ans;    while(scanf("%d%d",&n,&k)!=EOF)    {        sum1=0;        sum2=0;        ans=0;        memset(vis,0,sizeof(vis));        for(i=1;i<=n;i++)        {            scanf("%d",&v[i]);            sum1+=v[i];//sum1记录城市魅力值的和        }        for(i=1;i<=k;i++)        {            scanf("%d",&a[i]);            sum2+=(v[a[i]]);//sum2记录未处理的省会城市魅力值的和        }        for(i=1;i<=k;i++)        {            num=a[i];            ans+=(sum1-v[num])*v[num];//算出该省会城市与其他城市连线的和            ans-=(sum2-v[num])*v[num];//减去重复计算的值(省会之间的连线)            sum2-=v[num];            vis[num]=1;        }        for(int i=1;i<=n;i++)//计算非省会城市之间的连线        {            if(!vis[i]&&!vis[i+1])                ans+=(v[i]*v[i+1]);        }        if(!vis[1]&&!vis[n])            ans+=(v[1]*v[n]);        printf("%lld\n",ans);    }    return 0;}
View Code

 

Codeforces 703B Mishka and trip