Codeforces 703B (模拟) Mishka and trip

题目：这里

题意：n个城市，每个城市有个魅力值vi，首先，有n条路将这n个城市连成一个环，1号城市连2号城市，2号连3号****n号连1号城市，每条路的魅力值是其连接的两个城市

的魅力值的乘积，这n个城市其中还有k个是特殊城市，每个特殊城市和任意一条城市都有一条路连接，看题目下面的图，保证每两个城市之间最多只有一条路，问所有路的

魅力值之和是多少？

首先是连接成环的路线魅力值，很好算，然后每个特殊城市的路线，先求出所有城市的魅力值之和sum，依次求特殊城市的时候用sum减去这个特殊城市本身以及两边相邻的城市

魅力值(因为相邻两边的路已经算过了)，再乘这个特殊城市本身魅力值就行，注意这样可能会有路算重复了，而题目显然每条路只能算一次，每次再减去已经出现过的特殊城市

的魅力值之和就行了，注意可能之前出现的特殊城市可能会是现在的特殊城市的左右相邻的城市之一，这样的话就不用减了，因为已经减了，标记一下就行。

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 const int M = 1e5 + ;

 ll a[M];bool has[M];

 int main()

 {

     int n,m;

     ll sum=,ans=;

     scanf("%d%d",&n,&m);

     for (int i= ; i<=n ; i++)

     {

         scanf("%I64d",&a[i]);

         if (i>) ans+=(a[i]*a[i-]);

         sum+=a[i];

     }

     ans+=a[]*a[n];

     memset(has,false,sizeof(has));

     ll cas=;

     while (m--)

     {

         int x,l,r;

         scanf("%d",&x);

         has[x]=true;

         if (x-==) l=n;

         else l=x-;

         if (x+==n+) r=;

         else r=x+;

         ans+=(sum-a[x]-a[l]-a[r])*a[x];

         ll we=cas;

         if (has[l]) we-=a[l];

         if (has[r]) we-=a[r];

         ans-=we*a[x];

         cas+=a[x];

     }

     printf("%I64d\n",ans);

     return ;

 }

巴特西

Codeforces 703B (模拟) Mishka and trip

最新文章

热门文章