edu 打烂了。

A.

检查 $w_1$。

B.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve() {
  int N;
  cin >> N;
  vector<int> A(N);
  vector<int> B(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  for (int i = 0; i < N; i++) {
    cin >> B[i];
  }
 
  long long ans = 1ll * *min_element(A.begin(), A.end()) * N + accumulate(B.begin(), B.end(), 0LL);
  long long ans2 = 1ll * *min_element(B.begin(), B.end()) * N + accumulate(A.begin(), A.end(), 0LL);
  cout << min(ans, ans2) << "\n";
}

C.

考虑最后一个连续段只会剩下一个，也就是每个连续段里面选出来一个的方案数有 $\prod len_i$，擦除字符的方案数为 $n-cnt$，其中 cnt 为连续段个数。

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
void solve() {
  vector<int> seg;
  string s;
  cin >> s;
  int N = (int) s.size();
  for (int i = 0, j = 0; i < N; i = j) {
    j = i;
    while (j < N && s[i] == s[j]) {
      j += 1;
    }
    seg.push_back(j - i);
  }
  // debug(seg);
  cout << N - sz(seg) << " ";
  vector<long long> fac(N + 1);
  fac[0] = 1;
  for (int i = 1; i <= N; i++) {
    fac[i] = fac[i - 1] * i % P;
  }
  ll ans = 1;
  for (int i : seg) {
    ans = ans * i % P;
  }
  ans = ans * fac[N - sz(seg)] % P;
  cout << ans << "\n";

D.

拆位计算。

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
const int P = 998244353;
void solve() {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  vector<int> B(N + 1);
  for (int i = 0; i < N; i++) {
    B[i + 1] = B[i] ^ A[i];
  }
  vector<long long> cnt1(30);
  vector<long long> cnt2(30);
  vector<long long> cnt3(30);
  vector<long long> cnt4(30);
  long long ans = 0;
  long long res = 0;
  for (int i = 0; i <= N; i++) {
    for (int j = 0; j < i; j++) {
      res += 1ll * (B[i] ^ B[j]) * (i - j) % P;
    }
    for (int j = 0; j < 30; j++) {
      if (B[i] >> j & 1) {
        long long w = cnt2[j];
        long long v = cnt4[j];
        ans += 1ll * (w * i - v) % P * (1LL << j) % P;
        if (ans >= P) {
          ans -= P;
        }
      } else {
        long long w = cnt1[j];
        long long v = cnt3[j];
        ans += 1ll * (w * i - v) % P * (1LL << j) % P;
        if (ans >= P) {
          ans -= P;
        }
      }
    }
    debug(ans, res);
    for (int j = 0; j < 30; j++) {
      if (B[i] >> j & 1) {
        cnt1[j]++;
        cnt3[j] += i;
      } else {
        cnt2[j]++;
        cnt4[j] += i;
      }
    }
  }
 
  cout << ans << "\n";
}

E.

被狠狠的演了。

首先可以发现三种颜色一定可以。$dep%3$ 来染色。

  • 如果树的深度为 1，只需要一种颜色。
  • 如果深度大于 1，那么父边的颜色必须唯一，因此至少需要两种颜色。

那么只需要判定颜色数为 2 的合法性就可以了。

那就需要让每个点除了父边的颜色相同，实际上是根的每个子树独立，每个子树中的边按照奇偶染色，但是如果有两个点，度数等于 2，但是父边颜色不同，则无法区分。所以我们必须避免这种情况，而根的同一子树如果有两个深度奇偶性不同的 2 度点则无解。剩余的情况通过调整第一层的边的颜色一定有解。

如果 2 不合法，直接输出 3 和方案即可。

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
void solve() {
  int n;
  cin >> n;
  vi p(n, -1);
  rep(i, 1, n) cin >> p[i], --p[i];
  vi dep(n, 0), deg(n, 0);
  rep(i, 1, n) {
    dep[i] = dep[p[i]] + 1;
    deg[p[i]] += 1;
  }
  int k;
  vi col(n);
  if (*max_element(all(dep)) == 1) {
    k = 1;
  } else {
    vc<vi> adj(n);
    rep(i, 1, n) { adj[p[i]].pb(i); }
    bool ok = true;
    rep(i, n) {
      if (p[i] == 0) {
        int cnt[2]{};
        auto dfs = [&](auto self, int u) -> void {
          if (deg[u] == 1) {
            cnt[dep[u] % 2] += 1;
          }
          for (auto v : adj[u]) {
            col[v] = !col[u];
            self(self, v);
          }
        };
        dfs(dfs, i);
        if (cnt[0] && cnt[1]) {
          ok = false;
          break;
        } else {
          col[i] = cnt[0] ? 1 : 0;
          dfs(dfs, i);
        }
      }
    }
    if (ok) {
      k = 2;
    } else {
      k = 3;
      for (int i = 1; i < n; i++) {
        col[i] = dep[i] % 3;
      }
    }
  }

  cout << k << "\n";
  rep(i, 1, n) {
    cout << col[i] + 1 << " \n"[i + 1 == n];
  }

  cout.flush();

  while (true) {
    int x;
    cin >> x;
    if (x == 1) {
      break;
    }
    vi u;
    rep(i, k) {
      int c;
      cin >> c;
      if (c == 1) {
        u.pb(i);
      }
    }
    if (sz(u) > 1) {
      if (k == 2) {
        u[0] = 0;
      } else {
        if ((u[0] + 1) % 3 != u[1]) {
          swap(u[0], u[1]);
        }
      }
    }
    cout << u[0] + 1 << endl;
  }
}

F.

首先一个人的存活轮数是 $h \times \lceil\frac{a}{x} \rceil$。

所以只需要考虑 $x \leq A = \max a$ 的情况。枚举 $x$，然后枚举 $\lceil \frac{a}{x} \rceil$，最大值一定是取 $a$ 的区间中最大的 $h$，然后通过预处理 $f_{i, 0/1}$ 表示在 $a_j \geq i$ 时候 $h_j$ 的最大值和次大值，也只需要更新 $h_j$ 对应的下标即可，其他都是 0。

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <bits/stdc++.h>
#include <cmath>
#ifndef LOCAL
#define debug(...) 42
#else
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#endif
#define rep1(a) for (int i = 0; i < a; i++)
#define rep2(i, a) for (int i = 0; i < a; i++)
#define rep3(i, a, b) for (int i = a; i < b; i++)
#define rep4(i, a, b, c) for (int i = a; i < b; i += c)
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)

#define pb emplace_back
using namespace std;
template <typename T, typename T2> void cmin(T &x, const T2 &y) {
  x = x < y ? x : y;
}
template <typename T, typename T2> void cmax(T &x, const T2 &y) {
  x = x > y ? x : y;
}
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
template <class T> using vc = vector<T>;
template <class T> using pq = priority_queue<T>;
template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
mt19937 rng(time(NULL));
const int inf = 1000000000;
const ll lnf = 1000000000000000000;
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define fi first
#define se second

const int V = 2e5;
void solve() {
  int n;
  cin >> n;
  vi h(n), a(n);
  rep(i, n) cin >> h[i];
  rep(i, n) cin >> a[i];

  map<pii, int> id;
  rep(i, n) id[{h[i], a[i]}] = i;
  vc<array<pii, 2>> f(V + 1);
  rep(i, n) {
    auto v = make_pair(h[i], a[i]);
    for (auto &y : f[a[i]]) {
      if (v > y) {
        swap(v, y);
      }
    }
  }
  for (int i = V - 1; i >= 0; i--) {
    for (auto v : f[i + 1]) {
      for (auto &y : f[i]) {
        if (v > y) {
          swap(v, y);
        }
      }
    }
  }

  vc<ll> ans(n);
  rep(x, 1, V + 1) {
    ll mx = 0;
    int l = 0;
    for (int i = 1; i <= V; i += x) {
      ll res = 1ll * (i + x - 1) / x * f[i][0].fi;
      if (res > mx) {
        mx = res;
        l = i;
      }
    }
    auto v = f[l][0];
    ll sec = 0;
    for (int i = 1; i <= V; i += x) {
      ll res = 1ll * (i + x - 1) / x * f[i][f[i][0] == v].fi;
      if (res > sec) {
        sec = res;
      }
    }
    if (sec < mx) {
      cmax(ans[id[v]], mx - sec);
    }
  }

  rep(i, n) cout << ans[i] << " \n"[i + 1 == n];
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}