A - ABC Preparation

排序找出最小值

  1. int main() {
  2.     ios_base::sync_with_stdio(false), cin.tie(0);
  3.     vector<int> a(4);
  4.     for (auto &i : a) cin >> i;
  5.     sort(a.begin(), a.end());
  6.     cout << a[0];
  7.     return 0;
  8. }

B - Smartphone Addiction

模拟

  1. int main() {
  2.     ios_base::sync_with_stdio(false), cin.tie(0);
  3.     int N, M, T, A, B, K = 0, t = 0;
  4.     cin >> N >> M >> T;
  5.     for (M = N; cin >> A >> B; N += B + K - 2 * A, K = B, N = min(N, M))
  6.         if (N - A + K <= 0) t++;
  7.     cout << (N - T + B <= 0 || t ? "No" : "Yes");
  8.     return 0;
  9. }

C - Duodecim Ferra

组合数学问题，裁点有 L-1 个，我们取其中的 11 个，根据组合答案为：AtCoder Beginner Contest 185 题解 - 图1。

然后根据组合数学原来进行化简 ↓

AtCoder Beginner Contest 185 题解 - 图2

  1. int main() {
  2.     ios_base::sync_with_stdio(false), cin.tie(0);
  3.     ll L, i = 0, N = 1;
  4.     for (cin >> L; ++i < 12; N *= (L - i), N /= i)
  5.         ;
  6.     cout << N << "\n";
  7.     return 0;
  8. }

D - Stamp

计算出所有白色区间。最短的区间长度即为 AtCoder Beginner Contest 185 题解 - 图3 的最佳取值，之后计算需要的邮票总数即可。

好题！

  1. int main() {
  2.     ios_base::sync_with_stdio(false), cin.tie(0);
  3.     int N, M, K = 0, cnt = 0, i = 1;
  4.     cin >> N >> M;
  5.     int A[M + 2], B[M + 1];
  6.     A[0] = 0, A[M + 1] = N + 1;
  7.     for (; i <= M; ++i) cin >> A[i];
  8.     sort(A, A + M + 2);
  9.     for (int i = 0; i < M + 1; ++i) B[i] = A[i + 1] - A[i] - 1;
  10.     sort(B, B + M + 1);
  12.     // for (int i = 0; i < M + 1; ++i) cout << B[i] << " ";
  13.     // cout << endl;
  15.     for (i = 0; i < M + 1; ++i) {
  16.         if (!K) K = B[i];
  17.         if (K) cnt += (B[i] + K - 1) / K;
  18.     }
  19.     cout << cnt << "\n";
  20.     return 0;
  21. }

E - Sequence Matching

类似于最长公共子序列。考虑 AtCoder Beginner Contest 185 题解 - 图4三种转移。

时间复杂度AtCoder Beginner Contest 185 题解 - 图5#card=math&code=%5Cmathcal%7BO%7D%28NM%29)。

  1. // 暂无

F - Range Xor Query

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

时间复杂度 AtCoder Beginner Contest 185 题解 - 图6%5Clog%20N)#card=math&code=%5Cmathcal%7BO%7D%28%28N%2BQ%29%5Clog%20N%29)。

  1. #include <bits/stdc++.h>
  3. #include <atcoder/segtree>
  4. using namespace std;
  5. int op(int a, int b) { return a ^ b; }
  6. int e() { return 0; }
  7. int main() {
  8.     int n, q;
  9.     cin >> n >> q;
  10.     vector<int> v(n);
  11.     for (int i = 0; i < n; ++i) cin >> v[i];
  12.     atcoder::segtree<int, op, e> seg(v);
  13.     while (q--) {
  14.         int t, x, y;
  15.         cin >> t >> x >> y;
  16.         if (t == 1) {
  17.             seg.set(x - 1, v[x - 1] ^ y);
  18.             v[x - 1] ^= y;
  19.         } else {
  20.             cout << seg.prod(x - 1, y) << endl;
  21.         }
  22.     }
  23. }