Codeforces 703B. Mishka and trip

题目链接:http://codeforces.com/problemset/problem/703/B

题意：

　　在一个国家有 N 个城市,编号为 1 ～ N, 每个城市有一个漂亮值 C_i.每两个相邻编号的城市之间都有一条路,也就是说第 i 个城市和第 i + 1 个城市之间有一条路,特别的第一个城市和最后一个城市之间有一条路,路的价值为路两端城市的漂亮值的积,即 C_i * C_i+1;除此之外,在这 N 个城市中还有 K 个首都城市,一个首都城市和其他 N - 1 个城市之间都存在路,问这个国家所有路的总价值.

思路:

　　题目中给的N < 100000,显然直接计算会T.这里把所有城市分为首都城市和普通城市分别计算,首先计算首都城市,一个首都城市个其他所有城市之间都存在路,假设 sum 为所有城市的价值总和,则与第一个首都城市相连的所有路的价值为C_k1 * (sum - C_k1),与第二个首都城市相连的所有路的价值为C_k2 * (sum - C_k1 - C_k2),因为第二个城市除了在 sum 中减掉自己的价值之外,也需要减掉之前与K₁之间的价值,因为已经计算过了,之后每计算一个首都城市,就应该把其价值在 sum 中减掉,更新 sum,并计算C_k * sum的值加起来就是所有首都城市的总价值了.然后再计算普通城市,只要第 i 和第 i + 1个城市都不是首都城市那么,它们之间就存在一条未被计算过的路.

代码:

 1 #include <bits/stdc++.h>
 2 
 3 typedef long long LL;
 4 typedef unsigned long long ULL;
 5 using namespace std;
 6 const int MAXN = 100000;
 7 
 8 int main() {
 9     int N, K;
10     scanf("%d%d", &N, &K);
11     int ci[MAXN + 7] = {0};
12     for(int i = 1; i <= N; i++) scanf("%d", &ci[i]);
13     int id[MAXN + 7] = {0};
14     for(int i = 0; i < K; i++) scanf("%d", &id[i]);
15     int flag[MAXN + 7] = {0};
16     for(int i = 0; i < K; i++) flag[id[i]] = 1;
17     int sum = 0;
18     for(int i = 1; i <= N; i++) sum += ci[i];
19     ULL ans = 0;
20     for(int i = 0; i < K; i++) sum -= ci[id[i]], ans += (LL)ci[id[i]] * sum;//这里需要注意下,相乘时会爆int,一记WA!
21     ci[N + 1] = ci[1], flag[N + 1] = flag[1];
22     for(int i = 1; i <= N; i++) if(!flag[i] && !flag[i + 1]) ans += ci[i] * ci[i + 1];
23     printf("%I64u
", ans);
24     return 0;
25 }