VP 记录 - 2022 CCPC 广州站

发表于 更新于 分类于 ， ， 合著者：Foi 本文字数： 858 阅读时长 ≈ 3 分钟

比赛链接

进度: 7 / 13

题目概览

题号 1 标题 2 做法
*A Alice and Her Lost Cat
*B Ayano and sequences
C Customs Controls 2 图论，构造，缩点，并查集 / 差分约束
*D Digits
E Elevator 签到 (前缀和)
*F Equations
*G Game
H GameX 签到 (博弈论)
I Infection 树上背包，概率 DP
J Math Exam 容斥，前缀和，折线计数
K Middle Point Graph 图论 -> 无向图三元环 & 四元环计数
L Station of Fate 签到 (组合数学)
*M XOR Sum

官方题解

A - Alice and Her Lost Cat

解题思路

复杂度

代码参考

Show code

B - Ayano and sequences

解题思路

复杂度

代码参考

Show code

C - Customs Controls 2

解题思路

设从 \(1\) 到 \(i\) 的答案为 \(d_i\)

显然若对任意点 \(v\), 若有弧 \(u_1\to v\), \(u_2\to v\), 则 \(d_{u_1}=d_{u_2}\)

我们用并查集将 \(d\) 相同的点缩成一个点，因为点权是正的，所以缩点后的图应该也是个 DAG, 否则不满足要求

设点 \(i\) 在缩点后的图中对应的点编号为 \(s_i\), 之后我们对缩点后的图跑一遍 BFS 求一下每个点的拓扑序 \(b_{s_i}\)

最后我们只需让所有路径的点权和为 \(b_{s_n}\) 即可

要做到这一点，若有弧 \(u\to v\), 我们只需令 \(w_v=b_{s_v}-b_{s_u}\) 即可

有一个小技巧：我们可以将判环和 BFS 合起来，我们记录一下缩点后的图的每个点的入度 \(\deg_{in}(s_i)\), 若 \(\deg_{in}(s_1)>0\), 则显然不满足要求，之后我们 BFS 时遍历到一个点时将这个点的入度减 \(1\) (相当于删去刚刚走过的这条弧), 若这个点入度为 \(0\) 了则入队，这样图中没有环当且仅当每个点都被恰好遍历一次

复杂度

\(O(m\alpha(n)+n)\)

代码参考

Show code

C.cppview raw
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
#include <bits/stdc++.h>
using namespace std;
class DsuBasic {
protected:
  std::vector<size_t> fa;

public:
  explicit DsuBasic(size_t size): fa(size) {
    std::iota(fa.begin(), fa.end(), 0);
  }
  size_t find(size_t x) { return x == fa[x] ? fa[x] : fa[x] = find(fa[x]); }
  bool merge(size_t x, size_t y) {
    size_t fx = find(x), fy = find(y);
    return fx == fy ? false : (fa[fx] = fy, true);
  }
};
void solve(int t_ = 0) {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> ng(n + 1);
  for (int i = 1, u, v; i <= m; ++i) {
    cin >> u >> v;
    ng[v].push_back(u);
  }
  vector<int> id(n + 1);
  int cnt = 0;
  {
    DsuBasic dsu(n + 1);
    for (int i = 1; i <= n; ++i)
      for (auto j : ng[i]) dsu.merge(ng[i].front(), j);
    for (int i = 1; i <= n; ++i)
      if (dsu.find(i) == i) id[i] = cnt++;
    for (int i = 1; i <= n; ++i) id[i] = id[dsu.find(i)];
  }
  vector<int> w_(n + 1);
  {
    vector<vector<int>> g(cnt);
    vector<int> indeg(n + 1);
    for (int v = 1; v <= n; ++v)
      for (auto u : ng[v]) {
        g[id[u]].emplace_back(id[v]);
        ++indeg[id[v]];
      }
    if (indeg[id[1]]) {
      cout << "No\n";
      return;
    }
    queue<int> q;
    q.push(id[1]);
    int cnt2 = 0;
    while (!q.empty()) {
      auto now = q.front();
      q.pop();
      w_[now] = cnt2++;
      for (auto to : g[now])
        if (!--indeg[to]) q.push(to);
    }
    if (cnt2 != cnt) {
      cout << "No\n";
      return;
    }
  }
  vector<int> w(n + 1);
  w[1] = 1;
  for (int v = 2; v <= n; ++v) w[v] = w_[id[v]] - w_[id[ng[v].front()]];
  cout << "Yes\n";
  for (int i = 1; i <= n; ++i) cout << w[i] << " \n"[i == n];
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cerr << std::fixed << std::setprecision(6);
  int i_ = 0;
  int t_ = 0;
  std::cin >> t_;
  for (i_ = 0; i_ < t_; ++i_) solve(i_);
  return 0;
}

D - Digits

解题思路

复杂度

代码参考

Show code

E - Elevator

代码参考

Show code

E.cppview raw
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
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
struct Node {
  int x, id;
  Node(int x = 0, int id = 0): x(x), id(id) {}
};
struct Fenwick {
  vector<i64> v;
  explicit Fenwick(i64 x): v(x) {}
  constexpr static i64 lowbit(i64 x) { return x & (-x); }
  void update(i64 pos, i64 x) {
    for (i64 i = pos; i < v.size(); i += lowbit(i)) v[i] += x;
  }
  i64 sum(i64 pos) const {
    i64 ans = 0;
    for (i64 i = pos; i; i -= lowbit(i)) ans += v[i];
    return ans;
  }
};
const int N = 500000 + 7;
i64 A[N], B[N], C[N], Ans[N];
void solve() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> A[i], B[i] = A[i];
  sort(B + 1, B + 1 + n);
  int Sz = unique(B + 1, B + 1 + n) - B - 1;
  for (int i = 1; i <= n; ++i) C[i] = lower_bound(B + 1, B + 1 + Sz, A[i]) - B;
  Fenwick T1(n + 1), T2(n + 1);
  for (int i = 1; i <= n; ++i) {
    Ans[i] += T1.sum(C[i]);
    Ans[i] += T1.sum(C[i]) * A[i] - T2.sum(C[i]);
    T1.update(C[i], 1);
    T2.update(C[i], A[i]);
  }
  Fenwick T3(n + 1), T4(n + 1);
  for (int i = n; i >= 1; --i) {
    Ans[i] += T3.sum(C[i]) * A[i] - T4.sum(C[i]);
    T3.update(C[i], 1);
    T4.update(C[i], A[i]);
  }
  for (int i = 1; i <= n; ++i) cout << (Ans[i] <= m - 2 ? Ans[i] : -1) << '\n';
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int i_ = 0;
  int t_ = 0;
  cin >> t_;
  solve();
  return 0;
}

F - Equations

解题思路

复杂度

代码参考

Show code

G - Game

解题思路

复杂度

代码参考

Show code

H - GameX

代码参考

Show code

H.cppview raw
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
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
const string AB_[2] = {"Bob", "Alice"};
void solve() {
  i64 n, k;
  cin >> n >> k;
  vector<bool> vis(1000000 + 1);
  for (int i = 0, x; i < n; ++i) {
    cin >> x;
    vis[x] = 1;
  }
  int even = 0, odd = 1;
  int cnt_even = 0, cnt_odd = 0;
  for (int i = 0; i <= 1000000; ++i) {
    if (cnt_odd > k && cnt_even > k) break;
    if (vis[i]) continue;
    if (i & 1) {
      if (cnt_odd > k) continue;
      ++cnt_odd;
      odd = i;
    } else {
      if (cnt_even > k) continue;
      ++cnt_even;
      even = i;
    }
  }
  cout << AB_[even < odd] << '\n';
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int i_ = 0;
  int t_ = 0;
  cin >> t_;
  for (i_ = 0; i_ < t_; ++i_) solve();
  return 0;
}

I - Infection

解题思路

复杂度

代码参考

Show code

I.cppview raw
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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2000 + 7, Mod = 1000000000 + 7;
vector<int> E[N];
int A[N], B[N], C[N], P[N], Q[N], Fa[N], S, sz[N];
int f[N][N][2];
int KSM(int x, int p) {
  int Ret = 1;
  while (p) {
    if (p & 1) (Ret *= x) %= Mod;
    p >>= 1, (x *= x) %= Mod;
  }
  return Ret;
}
void DP(int u, int fa) {
  sz[u] = 1;
  f[u][1][0] = 1;
  Fa[u] = fa;
  f[u][1][1] = A[u] * KSM(S, Mod - 2) % Mod;
  for (auto v : E[u]) {
    if (v == fa) continue;
    DP(v, u);
    for (int i = sz[u]; i; --i) {
      for (int j = sz[v]; j; --j) {
        f[u][i + j][0] =
          (f[u][i + j][0] + f[u][i][0] * f[v][j][0] % Mod * P[v] % Mod) % Mod;
        f[u][i + j][1] =
          (f[u][i + j][1] + (f[u][i][0] * f[v][j][1] % Mod * P[u] % Mod +
                             f[u][i][1] * f[v][j][0] % Mod * P[v] % Mod) %
                              Mod) %
          Mod;
      }
      f[u][i][0] = f[u][i][0] * (1 - P[v] + Mod) % Mod;
      f[u][i][1] = f[u][i][1] * (1 - P[v] + Mod) % Mod;
    }
    sz[u] += sz[v];
  }
}
void solve() {
  int n;
  cin >> n;
  for (int i = 1, u, v; i < n; ++i) {
    cin >> u >> v;
    E[u].push_back(v), E[v].push_back(u);
  }
  for (int i = 1; i <= n; ++i) {
    cin >> A[i] >> B[i] >> C[i];
    S += A[i], P[i] = B[i] * KSM(C[i], Mod - 2) % Mod;
  }
  DP(1, 0);
  for (int i = 2; i <= n; ++i)
    for (int j = 1; j <= n; ++j) {
      f[1][j][1] = (f[1][j][1] + f[i][j][1] * (1 - P[Fa[i]] + Mod) % Mod) % Mod;
    }
  for (int i = 1; i <= n; ++i) cout << f[1][i][1] << endl;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int i_ = 0;
  int t_ = 0;
  cin >> t_;
  solve();
  return 0;
}

J - Math Exam

解题思路

复杂度

代码参考

Show code

J.cppview raw
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
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
const int MOD = 998244353;
const int N = 1e7 + 5;
int inv[N], combs[N];
int n, m;
int sum_c(int l, int r) {
  return ((r <= n ? combs[r] : 0) + MOD - (l > 0 ? combs[l - 1] : 0)) % MOD;
}
#define FLIP1(l, r) (n - 1) - r, (n - 1) - l
#define FLIP2(l, r) (n + (m + 1) / 2 + 1) - r, (n + (m + 1) / 2 + 1) - l
int g(int, int);
int f(int l, int r) {
  if (r < 0) return 0;
  l = max(l, 0);
  r = min(r, (n - 1) / 2);
  return (sum_c(l, r) + MOD - g(FLIP2(l, r))) % MOD;
}
int g(int l, int r) {
  if (l > n) return 0;
  l = max(l, (n + 1 + (m + 1) / 2 + 1) / 2);
  r = min(r, n);
  return (sum_c(l, r) + MOD - f(FLIP1(l, r))) % MOD;
}
auto solve([[maybe_unused]] int t_ = 0) -> void {
  cin >> n >> m;
  inv[0] = inv[1] = combs[0] = 1;
  for (int i = 2; i <= n; ++i)
    inv[i] = (i64)(MOD - MOD / i) * inv[MOD % i] % MOD;
  for (int i = 1; i <= n; ++i)
    combs[i] = (i64)combs[i - 1] * inv[i] % MOD * (n - i + 1) % MOD;
  for (int i = 1; i <= n; ++i) (combs[i] += combs[i - 1]) %= MOD;
  int l = (n + 1) / 2, r = (n + 1 + (m + 1) / 2) / 2;
  i64 ans = sum_c(l, r);
  (ans += MOD - f(FLIP1(l, r))) %= MOD;
  (ans += MOD - g(FLIP2(l, r))) %= MOD;
  cout << ans << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int i_ = 0;
  solve(i_);
  return 0;
}

K - Middle Point Graph

解题思路

带讨论，具体可以参照题解

三元环和四元环的求法可参照 笔记 - 无向图连通子图 & 环计数 相关章节

复杂度

代码参考

Show code

K.cppview raw
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
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
const int MOD = 1e9 + 7;
auto solve([[maybe_unused]] int t_ = 0) -> void {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> g(n + 1), dg(n + 1);
  vector<int> deg(n + 1);
  auto comp = [&](int u, int v) -> bool {
    return deg[u] > deg[v] || (deg[u] == deg[v] && u > v);
  };
  {
    vector<pair<int, int>> e;
    e.reserve(m);
    for (int i = 1, u, v; i <= m; ++i) {
      cin >> u >> v;
      e.emplace_back(u, v);
      ++deg[u];
      ++deg[v];
    }
    for (auto [u, v] : e) {
      if (!comp(u, v)) swap(u, v);
      dg[u].push_back(v);
      g[u].push_back(v);
      g[v].push_back(u);
    }
  }
  i64 ans = 0;
  if (n >= 4) {
    i64 c4 = 0;
    vector<int> pre(n + 1), cnt(n + 1);
    for (int i = 1; i <= n; ++i)
      for (auto &&to1 : dg[i])
        for (auto &&to2 : g[to1]) {
          if (i == to2 || !comp(i, to2)) continue;
          if (pre[to2] != i) cnt[to2] = 0;
          c4 += cnt[to2]++;
          pre[to2] = i;
        }
    (ans += c4 % MOD) %= MOD;
  }
  if (n >= 3) {
    i64 c3 = 0;
    vector<int> pre(n + 1);
    for (int i = 1; i <= n; ++i) {
      for (auto &&to : dg[i]) pre[to] = i;
      for (auto &&to1 : dg[i])
        for (auto &&to2 : dg[to1]) c3 += pre[to2] == i;
    }
    (ans += c3 % MOD * 3) %= MOD;
  }
  (ans += (i64)m * (m - 1)) %= MOD;
  for (int i = 1; i <= n; ++i) ans += (i64)deg[i] * (deg[i] - 1) / 2 % MOD;
  ans %= MOD;
  (ans += (i64)m * (n - 2)) %= MOD;
  cout << ans << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int i_ = 0;
  int t_ = 0;
  std::cin >> t_;
  for (i_ = 0; i_ < t_; ++i_) solve(i_);
  return 0;
}

L - Station of Fate

代码参考

Show code

L.cppview raw
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
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
const i64 MOD = 998244353;
constexpr i64 qpow(i64 a, i64 b, i64 mod) {
  i64 ret = 1;
  for (; b; b >>= 1, a = a * a % mod)
    if (b & 1) ret = ret * a % mod;
  return ret;
}
const int N = 2e5 + 5;
i64 fact[N];
i64 comb(i64 n, i64 m) {
  if (n < m) return 0;
  return fact[n] * qpow(fact[n - m], MOD - 2, MOD) % MOD *
         qpow(fact[m], MOD - 2, MOD) % MOD;
}
void solve() {
  i64 n, m;
  cin >> n >> m;
  cout << fact[n] * comb(n - 1, m - 1) % MOD << '\n';
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int i_ = 0;
  fact[0] = 1;
  for (int i = 1; i < N; ++i) fact[i] = fact[i - 1] * i % MOD;
  int t_ = 0;
  cin >> t_;
  for (i_ = 0; i_ < t_; ++i_) solve();
  return 0;
}

M - XOR Sum

解题思路

复杂度

代码参考

Show code

  1. 打 * 的是还没写的题↩︎

  2. 带超链接的是找到了原题或原型↩︎