# AtCoder Beginner Contest 178 题解

# Problem A - Not (opens new window)

Code (Python 3)
x = int(input())
print(1 - x)

1
2

# Problem B - Product Max (opens new window)

Code (Python 3)
a, b, c, d = map(int, input().split())
x = [a * c, a * d, b * c, b * d]
print(max(x))

1
2
3

# Problem C - Ubiquity (opens new window)

$\text{有0有9的序列}=\text{所有序列}-\text{没有0的序列}-\text{没有9的序列}+\text{既没有0也没有9的序列}$

Code (Python 3)
mod = 1000000007

def fexp(x, y):
ans = 1
while y > 0:
if y % 2 == 1:
ans = ans * x % mod
x = x * x % mod
y //= 2
return ans

n = int(input())
ans = fexp(10, n) - 2 * fexp(9, n) + fexp(8, n)
ans %= mod
if ans < 0:
ans += mod
print(ans)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# Problem D - Redistribution (opens new window)

Code (Python 3)
mod = 1000000007

def fexp(x, y):
ans = 1
while y > 0:
if y % 2 == 1:
ans = ans * x % mod
x = x * x % mod
y //= 2
return ans

fac = [1]
rev = [1]

for i in range(1, 2006):
fac.append(fac[-1] * i % mod)
rev.append(fexp(fac[-1], mod - 2))

def C(n, k):
if n < k:
return 0
return fac[n] * rev[k] % mod * rev[n - k] % mod

def distribute(n, m):
return C(n - 1, m - 1)

n = int(input())
if n < 3:
print(0)
else:
ans = 0
parts = 1
while n - parts * 2 >= 0:
rest = n - parts * 2
ans += distribute(rest, parts)
ans %= mod
parts += 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

# Problem E - Dist Max (opens new window)

$|x_i-x_j|+|y_i-y_j|=\max\{x_i-x_j+y_i-y_j,x_i-x_j+y_j-y_i,x_j-x_i+y_i-y_j,x_j-x_i+y_j-y_i\}$

$|x_i-x_j|+|y_i-y_j|=\max\{x_i+y_i-(x_j+y_j),x_i-y_i-(x_j-y_j),-x_i+y_i-(-x_j+y_j),-x_i-y_i-(-x_j-y_j)\}$

$\max|x_i-x_j|+|y_i-y_j|=\max\{\max(x_i+y_i-(x_j+y_j)),\max(x_i-y_i-(x_j-y_j)),\max(-x_i+y_i-(-x_j+y_j)),\max(-x_i-y_i-(-x_j-y_j))\}$

Code (C++)
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;
const int d[4][2] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
int main() {
int n;
cin >> n;
vector<ll> lo(4, 1e12), hi(4, -1e12);
for (int i = 0; i < n; ++i) {
ll x, y;
cin >> x >> y;
for (int k = 0; k < 4; ++k) {
ll result = x * d[k][0] + y * d[k][1];
lo[k] = min(lo[k], result);
hi[k] = max(hi[k], result);
}
}
ll ans = 0;
for (int k = 0; k < 4; ++k)
ans = max(ans, hi[k] - lo[k]);
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

# Problem F - Contrast (opens new window)

Code (C++)
#include <iostream>
#include <queue>
#include <vector>

using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n), b(n), cb(n + 1);
vector<bool> taken(n);
vector<vector<int>> ca(n + 1);
for (int i = 0; i < n; ++i) {
cin >> a[i];
ca[a[i]].emplace_back(i);
}
for (int i = 0; i < n; ++i) {
cin >> b[i];
cb[b[i]]++;
}
priority_queue<pair<int, int>> pq;
for (int i = 1; i <= n; ++i) {
int lo = min((int)ca[i].size(), cb[i]);
if (lo)
pq.emplace(lo, i);
}
while (pq.size() >= 2) {
auto [cx, x] = pq.top();
pq.pop();
auto [cy, y] = pq.top();
pq.pop();
if (cx == 1 && pq.size() == 1) {
auto [cz, z] = pq.top();
pq.pop();
int px = ca[x].back();
int py = ca[y].back();
int pz = ca[z].back();
taken[px] = taken[py] = taken[pz] = true;
b[px] = y;
b[py] = z;
b[pz] = x;
ca[x].pop_back();
ca[y].pop_back();
ca[z].pop_back();
cb[x]--;
cb[y]--;
cb[z]--;
} else {
int px = ca[x].back();
int py = ca[y].back();
taken[px] = taken[py] = true;
b[px] = y;
b[py] = x;
ca[x].pop_back();
ca[y].pop_back();
cb[x]--;
cb[y]--;
if (cx > 1)
pq.emplace(cx - 1, x);
if (cy > 1)
pq.emplace(cy - 1, y);
}
}
int idx = 0;
if (!pq.empty()) {
auto [cx, x] = pq.top();
pq.pop();
while (cb[x]) {
while (idx < n && (taken[idx] || a[idx] == x))
idx++;
if (idx >= n)
break;
b[idx] = x;
cb[x]--;
taken[idx] = true;
}
if (cb[x]) {
cout << "No" << flush;
return 0;
}
}
vector<int> rest;
for (int i = 1; i <= n; ++i)
if (cb[i]) {
for (int j = 0; j < cb[i]; ++j)
rest.emplace_back(i);
}
idx = 0;
for (int i : rest) {
while (taken[idx])
idx++;
b[idx] = i;
taken[idx] = true;
}
cout << "Yes" << endl;
for (int i : b)
cout << i << " ";
cout << flush;
}
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97