# # AtCoder Beginner Contest 176 题解

## # Problem B - Multiple of 9 (opens new window)

### # 题解

$9$的倍数每一位之和也一定是$9$的倍数。

## # Problem D - Wizard in Maze (opens new window)

### # 题解

#include <deque>
#include <iostream>
#include <vector>
#define INF 0x3f3f3f3f

using namespace std;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
int h, w, sx, sy, ex, ey;

int main() {
cin >> h >> w >> sx >> sy >> ex >> ey;
sx--, sy--, ex--, ey--;
vector<string> a(h);
for (int i = 0; i < h; ++i)
cin >> a[i];
vector<vector<int>> dist(h, vector<int>(w, INF));
vector<vector<bool>> vis(h, vector<bool>(w, false));
deque<pair<int, int>> q;
q.push_back({sx, sy});
dist[sx][sy] = 0;
while (!q.empty()) {
auto f = q.front();
q.pop_front();
int ci = f.first, cj = f.second;
if (ci == ex && cj == ey) {
cout << dist[ci][cj];
return 0;
}
if (vis[ci][cj])
continue;
vis[ci][cj] = true;
for (int k = 0; k < 4; ++k) {
int ni = ci + dy[k], nj = cj + dx[k];
if (ni < 0 || ni >= h || nj < 0 || nj >= w ||
dist[ni][nj] <= dist[ci][cj] || a[ni][nj] == '#')
continue;
dist[ni][nj] = dist[ci][cj];
q.push_front({ni, nj});
}
for (int ni = ci - 2; ni <= ci + 2; ++ni)
for (int nj = cj - 2; nj <= cj + 2; ++nj) {
if (ni < 0 || ni >= h || nj < 0 || nj >= w || a[ni][nj] == '#' ||
dist[ni][nj] <= dist[ci][cj] + 1)
continue;
dist[ni][nj] = dist[ci][cj] + 1;
q.push_back({ni, nj});
}
}
cout << -1;
}

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

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

### # 题解

#include <algorithm>
#include <iostream>
#include <set>
#include <vector>

using namespace std;
int main() {
int h, w, m;
cin >> h >> w >> m;
vector<int> hc(h + 1), wc(w + 1);
vector<pair<int, int>> p(m);
for (int i = 0; i < m; ++i)
cin >> p[i].first >> p[i].second, hc[p[i].first]++, wc[p[i].second]++;
set<pair<int, int>> s(p.begin(), p.end());
int hm = *max_element(hc.begin(), hc.end());
int wm = *max_element(wc.begin(), wc.end());
vector<int> vh, vw;
for (int i = 1; i <= h; ++i)
if (hc[i] == hm)
vh.emplace_back(i);
for (int i = 1; i <= w; ++i)
if (wc[i] == wm)
vw.emplace_back(i);
int sh = vh.size(), sw = vw.size();
if (sh * sw > m) {
cout << hm + wm;
return 0;
}
for (int i : vh)
for (int j : vw)
if (!s.count({i, j})) {
cout << hm + wm;
return 0;
}
cout << hm + wm - 1;
}

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

## # Problem F - Brave CHAIN (opens new window)

### # 题解

• 如果这三个数都相等，我们直接用这三个数组合，$triplets$加一，所有记录的最优状态都不需要改变。
• 将当前保留的两个数替换为这三个数中的任意两个。以$(a,b)$为例，此时我们有两种更进一步的选择：
• 不产生新的三元组，更新$dp[a][b]$到当前的全局最优解$opt$
• 取保留了两个$c$的状态，与$c$一起构成一个三元组，更新$dp[a][b]$$dp[c][c]+1$
• 将当前保留的两个数中的一个替换为这三个数中的某一个数。以$a$为例，此时我们需要遍历另一个保留的数$x$，之后有以下更进一步的选择：
• 不产生新的三元组，更新$dp[a][x]$到当前至少保留了一个$x$的局部最优解$local\_opt[x]$
• 特别的，如果$b=c$，我们可以取保留了$(b,x)$的状态，将$dp[a][x]$更新到$dp[b][x]+1$

• 全局最优$opt$
• 保留至少一个$i$的局部最优$local\_opt[i]$
• 保留至少一个$j$的局部最优$local\_opt[j]$
• 保留$(i,j)$的最优$dp[i][j]$$dp[j][i]$

#include <iostream>
#include <vector>
#define INF 0x3f3f3f3f

using namespace std;
typedef pair<int, int> pii;
int main() {
int n;
cin >> n;
vector<int> a(3 * n);
for (int i = 0; i < 3 * n; ++i)
cin >> a[i];
vector<vector<int>> f(n + 1, vector<int>(n + 1, -INF));
vector<int> local_opt(n + 1, -INF);
f[a[0]][a[1]] = f[a[1]][a[0]] = 0;
local_opt[a[0]] = 0, local_opt[a[1]] = 0;
int triplets = 0, opt = 0;
for (int i = 2; i < 3 * (n - 1); i += 3) {
vector<int> b(3);
for (int j = 0; j < 3; ++j)
b[j] = a[i + j];
if (b[0] == b[1] && b[0] == b[2]) {
triplets++;
continue;
}
for (int p = 0; p <= 2; ++p) {
int q = (p + 1) % 3, s = (p + 2) % 3;
for (int x = 1; x <= n; ++x) {
if (b[q] == b[s])
}
}
for (const auto &u : updates) {
int x = u.first.first, y = u.first.second, val = u.second;
if (f[x][y] < val) {
f[x][y] = f[y][x] = val;
opt = max(opt, val);
local_opt[x] = max(local_opt[x], val);
local_opt[y] = max(local_opt[y], val);
}
}
}
opt = triplets + max(opt, f[a.back()][a.back()] + 1);
printf("%d", opt);
}

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