AtCoder Beginner Contest 185 题解

视频题解 (opens new window)

Problem A - ABC Preparation (opens new window)

直接输出四个数的最小值。

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

参考代码 （Python 3）

print(min(map(int, input().split())))

Problem B - Smartphone Addiction (opens new window)

模拟。

时间复杂度$\mathcal{O}(M)$。

参考代码 （Python 3）

n, m, t = map(int, input().split())
last = 0
now = n
for _ in range(m):
    ai, bi = map(int, input().split())
    now -= ai - last
    if now <= 0:
        print('No')
        exit(0)
    now += bi - ai
    if now > n:
        now = n
    last = bi
now -= t - last
print('Yes' if now > 0 else 'No')

Problem C - Duodecim Ferra (opens new window)

答案为${L-1}\choose11$。

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

参考代码 （Python 3）

from math import comb

l = int(input())
print(comb(l - 1, 11))

Problem D - Stamp (opens new window)

计算出所有白色区间。最短的区间长度即为$k$的最佳取值，之后计算需要的邮票总数即可。

时间复杂度$\mathcal{O}(M)$。

参考代码 （Python 3）

n, m = map(int, input().split())
a = [] if m == 0 else list(map(int, input().split()))
a.sort()
if m == 0:
    print(1)
else:
    seg = []
    if a[0] != 1:
        seg.append(a[0] - 1)
    if a[-1] != n:
        seg.append(n - a[-1])
    for i in range(m - 1):
        if a[i + 1] - a[i] > 1:
            seg.append(a[i + 1] - a[i] - 1)
    if len(seg) == 0:
        print(0)
    else:
        shortest = min(seg)
        print(sum((si - 1) // shortest + 1 for si in seg))

Problem E - Sequence Matching (opens new window)

类似于最长公共子序列。考虑$dp[i-1][j],dp[i][j-1],dp[i-1][j-1]$三种转移。

时间复杂度$\mathcal{O}(NM)$。

参考代码 （Python 3）

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
for i in range(n + 1):
    for j in range(m + 1):
        if i == 0 and j == 0:
            continue
        dp[i][j] = int(1e6)
        if i > 0:
            dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1)
        if j > 0:
            dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1)
        if i > 0 and j > 0:
            extra = -1 if a[i - 1] == b[j - 1] else 0
            dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1 + extra)
print(dp[n][m])

Problem F - Range Xor Query (opens new window)

线段树，单点更新，区间查询。直接用AC-Library模板即可。

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

参考代码 （C++）

#include <atcoder/segtree>
#include <iostream>
#include <vector>

using namespace std;

int op(int a, int b) { return a ^ b; }

int e() { return 0; }

int main() {
  int n, q;
  cin >> n >> q;
  vector<int> v(n);
  for (int i = 0; i < n; ++i)
    cin >> v[i];
  atcoder::segtree<int, op, e> seg(v);
  while (q--) {
    int t, x, y;
    cin >> t >> x >> y;
    if (t == 1) {
      seg.set(x - 1, v[x - 1] ^ y);
      v[x - 1] ^= y;
    } else {
      cout << seg.prod(x - 1, y) << endl;
    }
  }
}