首页 > 代码库 > CodeForces 703B Mishka and trip
CodeForces 703B Mishka and trip
简单题。
先把环上的贡献都计算好。然后再计算每一个$capital$ $city$额外做出的贡献值。
假设$A$城市为$capital$ $city$，那么$A$城市做出的额外贡献：$A$城市左边城市$L$和右边城市$R$都不能和$A$做出贡献，之前存在的$capital$ $city$和$A$城市不能做出贡献，要注意的是$L$和$R$中存在$capital$ $city$的情况。剩下的城市都可以和$A$做出贡献。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-8;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}const int maxn=100010;int n,k;LL c[maxn],sum,y,p;bool f[maxn];int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%lld",&c[i]); LL ans=0; c[n+1]=c[1]; for(int i=1;i<=n;i++) ans=ans+c[i]*c[i+1],y=y+c[i]; for(int i=1;i<=k;i++) { int x; scanf("%d",&x); sum=y; int L=x-1,R=x+1; if(L==0) L=n; if(R==n+1) R=1; sum=sum-c[L]-c[R]-c[x]; sum=sum-p; if(f[L]) sum=sum+c[L]; if(f[R]) sum=sum+c[R]; ans=ans+c[x]*sum; f[x]=1; p=p+c[x]; } printf("%lld\n",ans); return 0;}
CodeForces 703B Mishka and trip
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。