Codeforces Round #365 (Div. 2) Mishka and trip

Mishka and trip

题意：

有n个城市，第i个城市与第i+1个城市相连，他们边的权值等于i的美丽度*i+1的美丽度，有k个首都城市，一个首都城市与每个城市都相连，求所有边的权值。

题解：

先把n个城市存下来，之后开一个标记数组，来标记k个首都（这题这块很巧妙，正因为开了标记首都的数组，所以才把O(N^2)的算法降到了O(N)） 把所有城市的美丽值都加起来，遍历首都，每次遍历完就sum-首都，这样，最后求环的剩下的边就好了，环的剩下的边就是i不是首都，i+1也不是首都，那么就i*i+1

还有这题的输入都是从1开始的，如果你从0输入的要注意下，但如果从1输入的话，取模的时候更难弄，所以建议从0开始读入。

这题还有一个转化，就是乘积相加变为和乘乘积

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF=0x3f3f3f3f;

const ll LINF=0x3f3f3f3f3f3f3f3f;

#define PI(A) cout<<(A)<<endl

#define SI(N) cin>>(N)

#define SII(N,M) cin>>(N)>>(M)

#define cle(a,val) memset(a,(val),sizeof(a))

#define rep(i,b) for(int i=0;i<(b);i++)

#define Rep(i,a,b) for(int i=(a);i<=(b);i++)

#define reRep(i,a,b) for(int i=(a);i>=(b);i--)

#define dbg(x) cout <<#x<<" = "<<(x)<<endl

#define PIar(a,n) rep(i,n)cout<<a[i]<<" ";cout<<endl;

#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<" ";cout<<endl;}

const double EPS= 1e-9 ;

/*  /////////////////////////     C o d i n g  S p a c e     /////////////////////////  */

const int MAXN= 100000+ 9 ;

int a[MAXN];

bool used[MAXN];

int n,k;

int main()

{

    while(SII(n,k))

    {

        ll sum=0,ans=0,x;

        cle(used,0);

        rep(i,n)SI(a[i]),sum+=a[i];

        rep(i,k)SI(x),used[x]=1;

        rep(i,n)

        {

            if (used[i+1])

            {

                sum-=a[i];

                ans+=a[i]*sum;

            }

        }

        rep(i,n-1) if (!used[i+1]&&!used[i+2]) {ans+=a[i]*a[i+1];}

        if (!used[n]&&!used[1]) ans+=a[n-1]*a[0];

        PI(ans);

    }

    return 0;

}