# AtCoder Beginner Contest 183 题解

视频题解 (opens new window)

# Problem A - ReLU (opens new window)

直接输出max(0,N)\max(0,N)即可,时间复杂度O(1)\mathcal{O}(1)

参考代码 (Python 3)
print(max(int(input()), 0))
1

# Problem B - Billiards (opens new window)

简单的几何计算,令GG'GG关于xx轴的对称点,连接SGSG,计算其与xx轴交点的横坐标

x=Sx+(GxSx)Sy0Sy(Gy)x=S_x+(G_x-S_x)\frac{S_y-0}{S_y-(-G_y)}

即为答案。

时间复杂度O(1)\mathcal{O}(1)

参考代码 (Python 3)
sx, sy, gx, gy = map(int, input().split())
print("{:.12f}".format(sx + (gx - sx) * sy / (sy + gy)))
1
2

# Problem C - Travel (opens new window)

NN很小,枚举所有路线即可。

时间复杂度O(N!)\mathcal{O}(N!)

参考代码 (Python 3)
from itertools import permutations

n, k = map(int, input().split())
t = []
for _ in range(n):
    t.append(list(map(int, input().split())))
rem = list(permutations(range(1, n)))
ans = 0
for perm in rem:
    dist = 0
    perm = [0] + list(perm) + [0]
    for i in range(n):
        dist += t[perm[i]][perm[i + 1]]
    if dist == k:
        ans += 1
print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# Problem D - Water Heater (opens new window)

扫描线算法。

对于第ii个人,给SiS_i增加PiP_i,同时给TiT_i减少PiP_i

从第一分钟开始扫描,如果在某一时刻总需求超过了总供给,则无解。

时间复杂度O(N+T)\mathcal{O}(N+T)

参考代码 (C++)
#include <iostream>
#include <vector>
#define MAXN 200005

using namespace std;
typedef long long ll;
int main() {
  int n, w;
  cin >> n >> w;
  vector<ll> delta(MAXN);
  for (int i = 0; i < n; ++i) {
    int s, t, p;
    cin >> s >> t >> p;
    delta[s] += p;
    delta[t] -= p;
  }
  ll curr = 0;
  for (int i = 0; i < MAXN; ++i) {
    curr += delta[i];
    if (curr > w) {
      cout << "No";
      return 0;
    }
  }
  cout << "Yes";
}
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

# Problem E - Queen on Grid (opens new window)

动态规划。记录每行、每列和每条对角线当前的前缀方法总和即可。

到达(i,j)(i,j)的方法总数为dp[i][j]=row[i]+col[j]+diag[ij+w]dp[i][j]=row[i]+col[j]+diag[i-j+w]。之后,再用dp[i][j]dp[i][j]去更新row[i]row[i]col[j]col[j]diag[ij+w]diag[i-j+w]

如果(i,j)(i,j)是墙,需要把row[i]row[i]col[j]col[j]diag[ij+w]diag[i-j+w]都清零。

时间复杂度O(HW)\mathcal{O}(HW)

参考代码 (C++)
#include <iostream>
#include <vector>
#define MOD 1000000007

using namespace std;
typedef long long ll;
int main() {
  int h, w;
  cin >> h >> w;
  vector<string> a(h);
  for (int i = 0; i < h; ++i)
    cin >> a[i];
  vector<vector<ll>> dp(h, vector<ll>(w));
  dp[0][0] = 1;
  vector<ll> row(h), col(w), diag(h + w);
  for (int i = 0; i < h; ++i)
    for (int j = 0; j < w; ++j) {
      if (a[i][j] == '#') {
        row[i] = 0;
        col[j] = 0;
        diag[i - j + w] = 0;
        continue;
      }
      if (i > 0)
        dp[i][j] += col[j];
      if (j > 0)
        dp[i][j] += row[i];
      if (i > 0 && j > 0)
        dp[i][j] += diag[i - j + w];
      dp[i][j] %= MOD;
      col[j] = (col[j] + dp[i][j]) % MOD;
      row[i] = (row[i] + dp[i][j]) % MOD;
      diag[i - j + w] = (diag[i - j + w] + dp[i][j]) % MOD;
    }
  cout << dp[h - 1][w - 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

# Problem F - Confluence (opens new window)

并查集,合并时把包含不同班级较少的合并到较多的里面去。

时间复杂度O(NlogN+Q)\mathcal{O}(N\log N+Q)

参考代码 (C++)
#include <iostream>
#include <unordered_map>
#include <vector>
#define MOD 1000000007

using namespace std;
typedef long long ll;
int main() {
  int n, q;
  cin >> n >> q;
  vector<int> c(n);
  for (int i = 0; i < n; ++i)
    cin >> c[i];
  vector<int> parent(n);
  vector<unordered_map<int, int>> mem(n);
  for (int i = 0; i < n; ++i) {
    parent[i] = i;
    mem[i][c[i]]++;
  }
  auto find = [&](auto self, int u) {
    if (parent[u] == u)
      return u;
    return parent[u] = self(self, parent[u]);
  };

  auto merge = [&](int u, int v) {
    int pu = find(find, u), pv = find(find, v);
    if (pu == pv)
      return;
    if (mem[pu].size() >= mem[pv].size()) {
      for (auto [t, f] : mem[pv])
        mem[pu][t] += f;
      parent[pv] = pu;
    } else {
      for (auto [t, f] : mem[pu])
        mem[pv][t] += f;
      parent[pu] = pv;
    }
  };

  while (q--) {
    int t, x, y;
    cin >> t >> x >> y;
    if (t == 1) {
      merge(x - 1, y - 1);
    } else {
      int root = find(find, x - 1);
      if (mem[root].count(y))
        cout << mem[root][y] << endl;
      else
        cout << 0 << endl;
    }
  }
}
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