2022 China Collegiate Programming Contest (CCPC) Guangzhou Onsite

A.

令 $f_{u,k,0/1}$ 表示 $u$ 的子树里面有 $k$ 个叶子结点需要搜查，是否有一个另外的叶子结点需要通过修复 $u$ 的祖先结点的监控确定。

初始叶子结点: $f_{u,0,0}=a_u, f_{u,1,0}=f_{u,1,1}=f_{u,0,1}=0$。

$f_{u,k,0} = \min(\sum_{k_i} f_{v,k_i,0}, a_u + \sum_{k_i} \min(f_{v,k_i,0}, f_{v,k_i, 1}))$

$f_{u,k,1} = \min(\sum_{k_i} f_{v,k_i,0/1})$，1 最多只能有一个，不然无法确定。

$ans = \min(t_i + \min(f_{1,i,0}, f_{1,i,1}))$.

代码鸽了。

偷了个 mwh 的。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 7;
long long F[2][N][N], G[2][N], E[N], R[N], a[N], b[N];
int t, n, siz[N];
vector<int> v[N];
void dfs(int u, int fa) {
  siz[u] = 1;
  bool flag = 0;
  F[0][u][0] = F[1][u][0] = 0;
  for (int i = 0; i < v[u].size(); i++) {
    int x = v[u][i];
    if (x == fa)
      continue;
    dfs(x, u), flag = 1;
  }
  E[0] = 0;
  for (int i = 0; i < v[u].size(); i++) {
    int x = v[u][i];
    if (x == fa)
      continue;
    for (int t = 0; t <= siz[u] + siz[x]; t++)
      G[0][t] = G[1][t] = 1e18, R[t] = 1e18;
    for (int f1 = 0; f1 <= siz[u]; f1++)
      for (int f2 = 0; f2 <= siz[x]; f2++) {
        G[0][f1 + f2] = min(G[0][f1 + f2], F[0][u][f1] + F[0][x][f2]);
        G[1][f1 + f2] = min(G[1][f1 + f2], F[1][u][f1] + F[0][x][f2]);
        G[1][f1 + f2] = min(G[1][f1 + f2], F[0][u][f1] + F[1][x][f2]);
        R[f1 + f2] = min(R[f1 + f2], E[f1] + min(F[1][x][f2], F[0][x][f2]));
      }
    siz[u] += siz[x];
    for (int t = 0; t <= siz[u]; t++)
      F[0][u][t] = G[0][t], F[1][u][t] = G[1][t], E[t] = R[t];
  }
  if (!flag) {
    F[0][u][0] = a[u];
    F[1][u][0] = 0;
    F[0][u][1] = 0;
  }
  for (int i = 0; i <= siz[u]; i++)
    F[0][u][i] = min(F[0][u][i], E[i] + a[u]);
}
signed main() {
  cin >> t;
  while (t--) {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
      v[i].resize(0), siz[i] = 0;
    for (int i = 1; i <= n; i++)
      scanf("%lld", &a[i]);
    for (int i = 1; i <= n; i++)
      scanf("%lld", &b[i]);
    for (int i = 1; i < n; i++) {
      int x, y;
      scanf("%d%d", &x, &y);
      v[x].push_back(y);
      v[y].push_back(x);
    }
    for (int i = 1; i <= n; i++)
      for (int j = 0; j <= n; j++)
        F[0][i][j] = F[1][i][j] = 1e18;
    dfs(1, 0);
    long long ans = 1e18;
    for (int i = 0; i <= n; i++)
      ans = min(ans, b[i] + min(F[0][1][i], F[1][1][i]));
    cout << ans << endl;
  }
  return 0;
}

B.

犯蠢了。

先不考虑 1 操作，只考虑 2 操作。

2 操作其实是 $[l,r]$ 在时间 $\geq t$ 的一个矩形加，那么如果没有 1 操作，就已经做完了。

1 操作是一个区间覆盖，覆盖的范围和时间也是一个矩形，矩形求和就可以了。

所以可以对时间用扫描线，线段树就可以做完了。

C.

考虑拆个点 $2\times i,2\times i+1$。

$2\times i$ 表示到 $i$ 的权值但是没有算上 $w_i$。

$2\times i+1$ 表示到 $i$ 的权值，并且算上 $w_i$。

显然如果有一条边 $(u,v)$，应该把 $(2\times u+1,2\times v)$ 塞到一个集合里面。

然后建图的话只需要将 $find(2\times i)$ 和 $find(2 \times i+1)$ 连边，跑一个拓扑就好了。

无解条件就是有环，因为权值一定要为正数。

最后显然 $w_u = val[find(2\times u+1)] - val[find(2\times u)]$。

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
103
104
105
#include <algorithm>
#include <bits/stdc++.h>
#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
struct unionfind {
  vector<int> p;
  unionfind(int N) { p = vector<int>(N, -1); }
  int root(int x) { return p[x] < 0 ? x : p[x] = root(p[x]); }
  bool same(int x, int y) { return root(x) == root(y); }
  void unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x != y) {
      if (p[x] < p[y]) {
        swap(x, y);
      }
      p[y] += p[x];
      p[x] = y;
    }
  }
  int size(int x) { return -p[root(x)]; }
};

void solve() {
  int n, m;
  cin >> n >> m;
  unionfind f(n * 2);
  rep(i, m) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    f.unite(u * 2 + 1, v * 2);
    debug("unite", u * 2 + 1, v * 2);
  }
  vi deg(n * 2);
  vc<vi> g(n * 2);
  rep(i, n) {
    int u = f.root(i * 2);
    int v = f.root(i * 2 + 1);
    debug(u,v);
    deg[v] += 1;
    g[u].pb(v);
  }
  vi val(n * 2, -1);
  queue<int> q;
  int c = 0;
  rep(i, n * 2) if (deg[i] == 0) q.emplace(i);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    val[u] = c++;
    for (auto v : g[u])
      if (--deg[v] == 0)
        q.emplace(v);
  }
  if (*min_element(all(val)) == -1) {
    cout << "No\n";
    return;
  }
  cout << "Yes\n";
  rep(i, n) cout << val[f.root(i * 2 + 1)] - val[f.root(i * 2)]
                 << " \n"[i + 1 == n];
}

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

E.

每次可以让最大值减一，使得第 $i$ 个是编号最小且值最大的需要的 -1 次数。从大到小记录前缀和用线段树即可。

H.

考虑太多容易想假。

Alice 希望最后的 mex 是偶数，所以她加的数字必然都是奇数。

Bob 加的都是偶数，所以都网上加 k 个就可以了。

最后检查 mex。

L.

题目意思:给定 N 个人，M 个不同的车站，排队方案数。

简单数学题，先分配然后再乘上 $N!$。

M.

数位 dp。

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
#include <bits/stdc++.h>
#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 P = 1e9 + 7;
ll C[40][40];
ll dp[51][220][20];
void md(ll &x) {
  if (x >= P)
    x -= P;
}
void solve() {
  ll N, M, K;
  cin >> N >> M >> K;
  dp[50][0][K] = 1;
  for (int i = 49; i >= 0; i--) {
    ll lim = M >> i;
    rep(a, 200) { // exceed from higher bit
      ll s = (N >> i) - a;
      rep(b, K + 1) {
        rep(c, b + 1) {
          rep(d, K - b + 1) {
            ll x1 = c + d, x0 = K - x1;
            ll x = x1 * x0;
            if (lim == 0 && c > 0)
              continue;
            if (lim <= 1 && d > 0)
              continue;
            if (x > s)
              continue;
            if (s - x & 1)
              continue;
            ll a1 = (N >> i + 1) - (s - x) / 2;
            ll b1 = lim % 2 == 0 ? b - c : K - d;
            md(dp[i][a][b] +=
               dp[i + 1][a1][b1] * C[b][c] % P * C[K - b][d] % P);
          }
        }
      }
    }
  }
  cout << dp[0][0][K] << "\n";
}

int main() {
  rep(i, 40) {
    C[i][0] = C[i][i] = 1;
    rep(j, 1, i) { md(C[i][j] = C[i - 1][j - 1] + C[i - 1][j]); }
  }
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t = 1;
  // cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}