首页 > 代码库 > 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;}
Codeforces 703B Mishka and trip
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。