A.

判断数位严格递减。

1
2
3
4
5
6
7
8
9
10
11
12
void solve() {
  string s;
  cin >> s;
  auto t = s;
  sort(all(t), greater<char>());
  t.resize(unique(all(t)) - t.begin());
  if (t == s) {
    cout << "Yes";
  } else {
    cout << "No";
  }
}

B.

其实可以做到 $O(N)$，但是写了 $O(NX)$ 的做法。

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
void solve() {
  int N, X;
  cin >> N >> X;
  N -= 1;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  for (int Y = 0; Y <= X; Y++) {
    auto B = A;
    B.pb(Y);
    debug(B);
    sort(all(B));
    int S = 0;
    for (int i = 1; i < N; i++) {
      S += B[i];
    }
    debug(S, X);
    if (S >= X) {
      cout << Y << "\n";
      return;
    }
  }
  cout << -1 << "\n";
}

C.

考虑每个数最多出现一次，也就是一共 $2^{10}$ 种数字。注意开 ll 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ll b[1000000], c;
void dfs(int x, ll v) {
  if (x == -1) {
    b[c++] = v;
    return;
  }
  dfs(x - 1, v * 10 + x);
  dfs(x - 1, v);
}

void solve() {
  int K;
  cin >> K;
  dfs(9, 0);
  sort(b, b + c);
  cout << b[K + 1] << "\n";
}

D.

求 $\sum \min(P, x_i + y_j)$。

考虑对 $y$ 排序，然后求前缀和二分即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve() {
  int N, M, K;
  cin >> N >> M >> K;
  vi a(N), b(M);
  read(a, b);
  vector<long long> B(M + 1);
  sort(all(b));
  B[0] = 0;
  for (int i = 0; i < M; i++) {
    B[i + 1] = B[i] + b[i];
  }

  ll ans = 0;
  for (int i = 0; i < N; i++) {
    int p = lower_bound(all(b), K - a[i]) - b.begin();
    ans += 1ll * a[i] * p + B[p] + 1ll * K * (M - p);
  }

  cout << ans << "\n";
}

F.

带删减背包计数。

答案是 $\prod (1+x)$

所以每次删除的时候考虑乘上一个 $\frac{1}{1+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
const int P = 998244353;
void solve() {
  int Q, K;
  cin >> Q >> K;
  vector<int> dp(K + 1);
  dp[0] = 1;
  while (Q--) {
    char c;
    cin >> c;
    int x;
    cin >> x;
    if (c == '+') {
      for (int i = K; i >= x; i--) {
        dp[i] += dp[i - x];
        if (dp[i] >= P) {
          dp[i] -= P;
        }
      }
    } else {
      for (int i = x; i <= K; i++) {
        dp[i] += P - dp[i - x];
        if (dp[i] >= P) {
          dp[i] -= P;
        }
      }
    }
    cout << dp.back() << "\n";
  }
}

G.

有 $N \leq 17$ 个点，$M$ 个 $R, B$，$R_i$ 和 $B_{p_i}$ 构成 $M$ 条边，共有 $M!$ 种方案，求连通块个数的期望。

考虑我们可以先不关心顺序，只需要知道 ${R_i}$ 里面每个节点出现了多少次，同理 $B_i$ 也是。

记录 $X[S]$ 表示 $R$ 里有多少个在 $S$ 里的元素，$Y[S]$ 同理。

容易设计出状态 $A[S]$ 表示 $S$ 联通的概率，最后答案就是 $\sum A[S]$。

对于一个集合 $S$ 来说，不能直接计算方案，考虑容斥。

若 $X_S = Y_S$，说明这个 $S$ 内可以一一配对，否则 $A_S$ 为 0，$S$ 内部这些 $(R, B)$ 一一配对的概率就是 $\frac{1}{\binom{X_S}{M}}$，但这里显然有多余的部分，也就是可能 $S$ 可以拆成俩集合 $S_1$ 和 $S_2$，这俩集合之间不连通，所以我们要先计算出 $A_{S_1}$ 和 $A_{S_2}$。

考虑枚举 $S_1 \subset S$，然后枚举子集更新 $S$，容斥即可。

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
const int P = 998244353;
const int INV2 = (P + 1) / 2;

void solve() {
  int N, M;
  cin >> N >> M;
  vector<int> R(M), B(M);
  for (int i = 0; i < M; i++) {
    cin >> R[i];
    --R[i];
  }
  for (int i = 0; i < M; i++) {
    cin >> B[i];
    --B[i];
  }
  vector<long long> inv(M + 1);
  inv[1] = 1;
  for (int i = 2; i <= M; i++) {
    inv[i] = P - inv[P % i] * (P / i) % P;
  }
  vector<long long> fact(M + 1), invf(M + 1);
  fact[0] = invf[0] = 1;
  for (int i = 1; i <= M; i++) {
    fact[i] = fact[i - 1] * i % P;
    invf[i] = invf[i - 1] * inv[i] % P;
  }

  vector<int> X(N, 0);
  vector<int> Y(N, 0);
  for (int i = 0; i < M; i++) {
    X[R[i]] += 1;
    Y[B[i]] += 1;
  }

  vector<int> SX(1 << N, 0), SY(1 << N, 0);
  for (int i = 0; i < 1 << N; i++) {
    for (int j = 0; j < N; j++) {
      if (i >> j & 1) {
        SX[i] += X[j];
        SY[i] += Y[j];
      }
    }
  }

  vector<int> A(1 << N, 0);
  rep(i, 1, 1 << N) {
    if (SX[i] == SY[i]) {
      A[i] = fact[SX[i]] * fact[M - SX[i]] % P * invf[M] % P;
    }
  }

  rep(i, 1, 1 << N) {
    if (SX[i] == SY[i]) {
      for (int j = i - 1 & i; j > 0; --j &= i) {
        int k = i ^ j;
        if (j < k) {
          break;
        }
        int a = SX[k];
        int b = SX[(1 << N) - 1 - i];
        A[i] += P - A[j] * fact[a] % P * fact[b] % P * invf[a + b] % P;
        if (A[i] >= P) {
          A[i] -= P;
        }
      }
    }
  }

  int ans = 0;
  rep(i, 1, 1 << N) {
    ans += A[i];
    if (ans >= P) {
      ans -= P;
    }
  }

  cout << ans << "\n";
}