A.

模拟题。

B.

考虑两种情况一种是所有 $b_i$ 都选，一种是都不选，最后输出 minmax 即可。

C.

找到最靠前并且大于等于 $a_i$ 的位置，和最靠后并且大于等于 $a_i$ 的位置，就做完了。

D.

考虑在 $i \leq j$ 的时候一定会有 $c_i \leq c_j$，否则 $c_i > c_j$ 肯定选 $j$，所以按照这个思路贪心即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void solve() {
  int n;
  cin >> n;
  vi c(n);
  for (int i = 0; i < n; i++) {
    cin >> c[i];
  }
  ll k;
  cin >> k;
  for (int i = n - 1; i > 0; i--) {
    cmin(c[i - 1], c[i]);
  }
 
  int a = k;
  for (int i = 0; i < n; i++) {
    int add = c[i] - (i == 0 ? 0 : c[i - 1]);
    if (add) {
      cmin(a, k / add);
    }
    k -= a * add;
    cout << a << " \n"[i + 1 == n];
  }
}

E.

赛时随机过了。

  • $O(n^2)$ 的做法，考虑有用的区间很少。记录下来直接转移即可。
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
void solve() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
 
  for (int i = 0; i < n; i++) {
    memset(vis, 0, sizeof vis);
    int mx = 0;
    for (int j = i; j < n; j++) {
      vis[a[j]] = 1;
      while (vis[mx]) {
        mx += 1;
      }
      mex[i][j] = mx;
    }
  }
 
  vc<vi> trans(n);
  for (int i = 0; i < n; i++) {
    trans[i].pb(i);
    for (int j = i + 1; j < n; j++) {
      if (mex[i][j] != mex[i + 1][j] && mex[i][j] != mex[i][j - 1]) {
        trans[i].pb(j);
      }
    }
  }
 
  for (int i = 0; i <= n; i++) {
    memset(ok[i], 0, sizeof ok[i]);
  }
  ok[0][0] = 1;
  for (int i = 0; i < n; i++) {
    for (int v = 0; v < N; v++) {
      ok[i + 1][v] |= ok[i][v];
    }
    for (int j : trans[i]) {
      for (int v = 0; v < N; v++) {
        if (ok[i][v]) {
          ok[j + 1][v ^ mex[i][j]] = 1;
        }
      }
    }
  }
  for (int i = n; i >= 0; i--) {
    if (ok[n][i]) {
      cout << i << "\n";
      return;
    }
  }
}
  • 另外有一种可以做到 $O(nV)$ 的做法。

令 $f_x$ 为构成 $x$ 的最小位置。

然后每次用 $f_x$ 最小的位置来更新，细节看代码。

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
void solve() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
 
  for (int i = 0; i < n; i++) {
    memset(vis, 0, sizeof vis);
    int mx = 0;
    for (int j = i; j < n; j++) {
      vis[a[j]] = 1;
      while (vis[mx]) {
        mx += 1;
      }
      mex[i][j] = mx;
    }
  }
  for (int i = 0; i <= n; i++) {
    pos[i] = 0;
    for (int j = 0; j < n; j++) {
      cnt[i][j] = 0;
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
      cnt[mex[i][j]][j] += 1;
    }
  }
  for (int i = 0; i < N; i++) {
    d[i] = n;
  }
  memset(vis, 0, sizeof vis);
  pqg<pii> q;
  d[0] = -1;
  int l = 0;
  q.emplace(-1, 0);
  while (!q.empty()) {
    auto [dis, u] = q.top();
    q.pop();
    if (vis[u]) {
      continue;
    }
    vis[u] = 1;
    while (l <= dis) {
      for (int r = l; r < n; r++) {
        cnt[mex[l][r]][r] -= 1;
      }
      l += 1;
    }
    for (int i = 0; i <= n; i++) {
      int &p = pos[i];
      while (p < n && !cnt[i][p])
        p += 1;
      if (d[u ^ i] > p) {
        d[u ^ i] = p;
        q.emplace(d[u ^ i], u ^ i);
      }
    }
  }
 
  for (int i = N - 1; i >= 0; i--) {
    if (d[i] < n) {
      cout << i << "\n";
      return;
    }
  }
}

但是好像 maspy 写的比我好.jpg

处理 $pos_i$ 的方法比我高明啊。