https://acm.ecnu.edu.cn/contest/231/problem/D/
题意:给你n个点,且给出n个点的点权,给出特殊点(值为1),特殊点有到其他任何边权。
边权等于两点权值乘积。求所以边权之和。
解法:一边遍历一遍筛除特殊点。
//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string.h>
#include<time.h>
#include <vector>
#define ME(x , y) memset(x , y , sizeof(x))
#define SF(n) scanf("%d" , &n)
#define rep(i , n) for(int i = 0 ; i < n ; i ++)
#define INF 0x3f3f63f3f
#define mod 20191117
#define PI acos(-1)
using namespace std;
typedef long long ll ;
ll a[100009];
ll vis[100009];
ll ans = 0, sum = 0 ;
int main()
{
#ifdef ONLINE_JUDGE
#else
freopen("D:/c++/in.txt", "r", stdin);
freopen("D:/c++/out.txt", "w", stdout);
#endif
ll n ;
scanf("%lld" , &n);
scanf("%lld" , &a[1]);
sum = a[1] ;
for(int i = 2 ; i <= n ; i++)
{
scanf("%lld" , &a[i]);
sum += a[i];
ans += a[i] * a[i-1];
}
ans += a[1] * a[n];
a[0] = a[n] ;
a[n+1] = a[1];
for(int i = 1 ; i <= n ; i++)
{
scanf("%lld" , &vis[i]);
}
for(int i = 1 ; i <= n - 1 ; i++)
{
if(vis[i])
{
ll t = a[i-1] + a[i+1];
if(vis[i-1]) t = a[i+1];
sum -= a[i] ;
ans += a[i] * (sum - t);
}
}
if(vis[n])
{
if(vis[1]) sum += a[1];//以防筛除两次
ll t = a[n-1] + a[n+1];
if(vis[n-1]) t = a[n+1];
sum -= a[n];
ans += a[n] * (sum - t);
}
cout << ans << endl ;
return 0;
}
原文:https://www.cnblogs.com/nonames/p/11961707.html