# # AtCoder Beginner Contest 188 题解

## # Problem A - Three-Point Shot (opens new window)

x, y = map(int, input().split())
print('Yes' if abs(x - y) <= 2 else 'No')

1
2

## # Problem B - Orthogonality (opens new window)

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
print('Yes' if sum(ai * bi for ai, bi in zip(a, b)) == 0 else 'No')

1
2
3
4

## # Problem C - ABC Tournament (opens new window)

n = int(input())
a = list(map(int, input().split()))
half = 1 << (n - 1)
left_win = 0
for i in range(half):
if a[i] > a[left_win]:
left_win = i
right_win = half
for i in range(half, 1 << n):
if a[i] > a[right_win]:
right_win = i
if a[left_win] > a[right_win]:
print(right_win + 1)
else:
print(left_win + 1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

## # Problem D - Snuke Prime (opens new window)

$[1,2],[3,4],[5,8],[9,+\infty)$

$[1,3),[3,5),[5,9),[9,+\infty)$

1. （麻烦）我们可以对区间端点进行离散化，然后用差分数组求和的方式计算出每一区间内的花费。
2. （简单）我们可以用一个map来存储每个关键时间点（$a_i$$b_i+1$，也即区间起点）上的费用变化，然后按顺序处理区间，对这些变化进行累加。

#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;
typedef long long ll;

int main() {
int N;
ll C;
cin >> N >> C;
vector<int> a(N), b(N), c(N);
set<int> s;
for (int i = 0; i < N; ++i) {
cin >> a[i] >> b[i] >> c[i];

// We only need a[i] and b[i]+1 to represent the final segments.
// For example, [1, 4] and [3, 8] will make
// [1, 2], [3, 4], [5, 8] and [9, +inf].
// We need 1, 3, 5, and 9 to represent these segments.
s.insert(a[i]), s.insert(b[i] + 1);
}

// Discretize the endpoints.
int idx = 0;
map<int, int> mp;
for (int si : s)
mp[si] = idx++;
int M = s.size();
vector<int> v(s.begin(), s.end());

// Use a difference array to handle the services.
vector<ll> diff(M);
for (int i = 0; i < N; ++i)
diff[mp[a[i]]] += c[i], diff[mp[b[i] + 1]] -= c[i];

// Accumulate the difference array to get the value of each segment.
// At the same time, add to the total cost.
vector<ll> acc(M);
acc[0] = diff[0];
ll ans = 0;
for (int i = 0; i < M - 1; ++i) {
if (i >= 1)
acc[i] = acc[i - 1] + diff[i];
int span = v[i + 1] - v[i];
ans += min(C, acc[i]) * span;
}
cout << ans;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;
typedef long long ll;

int main() {
int N;
ll C;
cin >> N >> C;
vector<int> a(N), b(N), c(N);
set<int> s;
map<int, ll> changes;
for (int i = 0; i < N; ++i) {
cin >> a[i] >> b[i] >> c[i];

// We only need a[i] and b[i]+1 to represent the final segments.
// For example, [1, 4] and [3, 8] will make
// [1, 2], [3, 4], [5, 8] and [9, +inf).
// They can also be seen as [1, 3), [3, 5), [5, 9) and [9, +inf].
// We need 1, 3, 5, and 9 to represent these segments.
s.insert(a[i]), s.insert(b[i] + 1);

// We use a map to store the change of cost on each critical day.
changes[a[i]] += c[i];
changes[b[i] + 1] -= c[i];
}

vector<int> v(s.begin(), s.end());
int M = v.size();

ll ans = 0, acc = 0;
for (int i = 0; i < M - 1; ++i) {
// Deal with the starting and ending of segments.
acc += changes[v[i]];

// Add to the total cost.
ans += min(C, acc) * (v[i + 1] - v[i]);
}
cout << ans;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

## # Problem E - Peddler (opens new window)

$N$开始倒序进行动态规划即可。

#include <iostream>
#include <vector>
#define MAXN 200005

using namespace std;

int main() {
int N, M;
cin >> N >> M;

vector<int> A(N + 1);
for (int i = 1; i <= N; ++i)
cin >> A[i];

for (int i = 0; i < M; ++i) {
int u, v;
cin >> u >> v;
}

vector<int> hi(N + 1, -1e9);
int ans = -1e9;
for (int i = N; i >= 1; --i) {
hi[i] = max(hi[i], hi[v]);
ans = max(ans, hi[i] - A[i]);
hi[i] = max(hi[i], A[i]);
}
cout << ans;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

## # Problem F - +1-1x2 (opens new window)

• 如果$X\geq Y$，答案为$X-Y$
• 如果$X，采用BFS求解。为了减少状态分支数，从$Y$而非$X$开始。对于每一个当前值$Y'$，首先尝试用$d+|Y'-X|$更新最优解。然后，如果$Y'>X$，再进一步考虑使用三种操作：
• 如果$Y'$为偶数，则$\div2$$\times2$的逆操作）
• 如果$Y'$为奇数，考虑$+1$$-1$。 特别地，如果当前队首元素的操作步数已经大于等于最优解，则提前结束搜索。

from collections import deque

X, Y = map(int, input().split())
if X >= Y:
print(X - Y)
else:
ans = Y - X
dq = deque([(Y, 0)])
vis = set([Y])
while dq:
u, d = dq.popleft()
if d >= ans:
break
ans = min(ans, d + abs(u - X))
if u <= X:
continue
if u % 2 == 0:
if u // 2 not in vis:
dq.append((u // 2, d + 1))
else:
if u + 1 not in vis:
dq.append((u + 1, d + 1))
if u - 1 not in vis:
dq.append((u - 1, d + 1))
print(ans)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28