2025 CCH非专业级软件能力认证提高级第九轮总结

DFbd · 2025-10-11 16:14:18 · 个人记录

前两题由同学搬出（看来同学们都喜欢数学题😋）

超爽无算法场，拼尽全力终于AK。

预期：100 + 100 + 100 + 100

实际：100 + 100 + 100 + 100

T1

看了一下题，感觉好写但是史到临头去上个厕所，回来直接写完，总共30min。

题意：给定一个长度为 n 数字密码，我们需要将其猜出。对于每一位都有一个集合，表示该位可能尝试的数。同时，有 k 个长度为 n 的已经试过的密码（保证没有正确密码，不一定都符合上文中可能尝试的数），求最多还需要尝试多少次才可以试出宝箱的密码，如果永远试不出输出 -1。

显然，如果给定密码有任何一位不包含与对应集合中，就无解。

否则次数就是所有集合大小的乘积减去每一位都包含于集合中的尝试过的密码的数量。

#include <bits/stdc++.h>

#define int long long

using namespace std;

int n, k, v[20], f[20][10];
string a, s[20], d;

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> k >> a;
  int ans = 1;
  for (int i = 1; i <= n; i++) {
    cin >> v[i] >> s[i];
    int x = 1;
    for (int j = 0; j < v[i]; j++) {
      f[i][s[i][j] - '0'] = 1;
      if (s[i][j] == a[i - 1])
        x = 0;
    }
    if (x) {
      cout << "-1";
      return 0;
    }
    ans *= v[i];
  }
  while (k--) {
    cin >> d;
    int x = 1;
    for (int i = 0; i < n; i++)
      if (!f[i + 1][d[i] - '0'])
        x = 0;
    ans -= x;
  }
  cout << ans;
  return 0;
}

T2

又是推公式题。

题意：

求 F_{n,m} \bmod (10^9 + 7)。

一开始没看数据范围，但是不可能让我 \mathcal{O(nm)}，于是我开始推式子。

到这就可以 \mathcal{O(n)}，一看范围 n,m \le 10^{10^6} 直接去世，只能继续。

令 f_i = F_{i,m}，x = a^{m - 1}，y = b(1 + a + \dots + a^{m - 2})，则

令 p = cx，q = dx + y，则

用等比数列求和，这时我们就只剩下一个指数过大的问题了。

可以想到使用快速幂，但是每次除 2 太慢，可以每次除 10，这样我们的复杂度就变成了 \mathcal{O(\log_{10} n)}。

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int P = 1e9 + 7;

string n, m;
int a, b, c, d;

int fpow2(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1)
      res = res * a % P;
    a = a * a % P;
    b >>= 1;
  }
  return res;
}

int fpow10(int a, string b) { \\每次除10的快速幂
  int res = 1;
  for (int i = b.size() - 1; i >= 0; i--) {
    if (b[i] != '0')
      res = res * fpow2(a, b[i] - '0') % P;
    a = fpow2(a, 10);
  }
  return res;
}

string operator - (string s, int x) {
  for (int i = s.size() - 1; i >= 0; i--) {
    if (s[i] != '0') {
      s[i] = s[i] - 1;
      break;
    }
    s[i] = '9';
  }
  return s;
}

int operator % (string s, int x) {
  int p = 1, ans = 0;
  for (int i = s.size() - 1; i >= 0; i--, p = p * 10 % x)
    ans = (ans + p * (s[i] - '0') % x) % x;
  return ans;
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> m >> a >> b >> c >> d;
  int x = fpow10(a, m - 1), y = b * (a == 1 ? (m - 1) % P : (x - 1 + P) % P * fpow2(a - 1, P - 2) % P) % P;
  int p = c * x % P, q = (d * x % P + y) % P, t = fpow10(p, n - 1);
  cout << ((x + y) % P * t % P + q * (p == 1 ? (n - 1) % P : (t - 1 + P) % P * fpow2(p - 1, P - 2) % P) % P) % P;
  return 0;
}

用时1h写完，还剩2.5h，打暴力肯定是够了，但是机房里有人T3、4都会了，突然又感觉时间不够了。

T4

狂想T31h没想到，决定先放放T3看看T4，感觉可做。

题意：有 m 个数，第 i 个数为 g_i。可以对 g 进行任意次交换，设交换后第 i 个数为 h_i。如果 g_i \ne h_i，总值加 1。但是题目不会直接给出 g，而是给出 n 个序列 s_1,s_2,\dots,s_n，且 g = s_n。每个序 列 s_i 以如下两种格式之一给出：

• 1 k s_{i,1..k}。

• 2 x y：s_i = s_x + s_y，其中 + 表示序列拼接。保证：1 \le x, y \le i − 1。

求 g 的最大总值。

首先想想求最大总值的求法。

显然，若 g 中存在一个出现次数超过长度的一半，那么总值就是除了该数以外的数的个数的两倍，否则总值就是长度。

于是我们要求每个数的出现次数。

一开始以为是一棵二叉树，可以直接搜索，但是其实这是一个有向无环图，所以自然想到拓扑排序，并求出每一个 s 会被计算多少次。

求完之后，统计每个形式 1 给出的序列中的值的出现次数乘上该序列计算次数，就能拿到 g 中的值的出现次数了。

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int kMaxN = 1e6 + 5;

int t, n, ls[kMaxN], rs[kMaxN], v[kMaxN], cnt[kMaxN], in[kMaxN], id[kMaxN];

void topsort() {
  queue<int> q;
  for (int i = 1; i <= n; i++)
    if (!in[i])
      q.push(i);
  cnt[n] = 1; \\cnt[i]为序列i计算次数
  while (q.size()) {
    int x = q.front();
    q.pop();
    if (v[x])
      continue;
    in[ls[x]]--;
    if (!in[ls[x]])
      q.push(ls[x]);
    cnt[ls[x]] += cnt[x];
    in[rs[x]]--;
    if (!in[rs[x]])
      q.push(rs[x]);
    cnt[rs[x]] += cnt[x];
  }
}

void solve() {
  cin >> n;
  for (int i = 1; i <= n; i++)
    cnt[i] = in[i] = v[i] = 0;
  int tot = 0; \\以形式1给出的序列个数
  vector<unordered_map<int, int>> s(n + 1);
  for (int i = 1; i <= n; i++) {
    int op, x, y, k;
    cin >> op;
    if (op == 1) {
      cin >> k;
      v[i] = ++tot;
      id[tot] = i;
      for (int j = 1; j <= k; j++) {
        cin >> x;
        s[tot][x]++; \\该序列出现次数
      }
    } else {
      cin >> x >> y;
      ls[i] = x, rs[i] = y;
      in[x]++, in[y]++;
    }
  }
  topsort();
  map<int, int> mp;
  for (int i = 1; i <= tot; i++)
    if (cnt[id[i]])
      for (auto j : s[i])
        mp[j.first] += j.second * cnt[id[i]];
  int mx = 0, sum = 0;
  for (auto i : mp) {
    mx = max(mx, i.second);
    sum += i.second;
  }
  cout << (mx > sum - mx ? 2 * (sum - mx) : sum) << '\n';
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  for (cin >> t; t; t--)
    solve();
  return 0;
}

耗时1h。

T3

写完T4只有30min，有点紧迫了，没想到我刚写完就灵机一动，顺着之前想的就会了。

题意：一个长度为 n 的排列 a，并定义 h 为前缀最大值减去前缀最小值的数组。给定 h，求有多少种可能的 a，对 10^9 + 7 取模。

前1h我想到的是若 h_i > h_{i - 1}，则 a_i 要么比最大值大 h_i - h_{i - 1}，要么比最小值小 h_i - h_{i - 1}，共两种选法。同时会产生 h_i - h_{i - 1} - 1 个没有被选的，但是不会影响最大最小值的数。

若 h_i = h_{i - 1}，则 a_i 就有不影响最大最小值的数的个数种选法。

但是当时我发现，若一直都是将最大值抬升，那么最大值将会超过 n，同理最小值有可能小于 1。而且，第一个数可能有多种选法。

而写完T4回来后，我发现以上两种情况是不会出现的。

若某个数超过 n，我就可以将第一个值减小，这样就不会超出了。而为了保证最大值不超过 n，最小值不低于 1，第一个值显然只有一种选法。

所以，情况数按照这个计算方式是不会错的。

前提是我们要判掉无解。

只有三种情况无解：第一个数不为0，有数不小于 n，出现严格的逆序对。

接下来就很好写了。

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int kMaxN = 2e6 + 5, P = 1e9 + 7;

int t, n, h[kMaxN];

void solve() {
  cin >> n;
  int ans = 1, sum = 0;
  for (int i = 1; i <= n; i++) {
    cin >> h[i];
    if (h[i] > h[i - 1]) {
      ans = ans * 2 % P;
      sum += h[i] - h[i - 1] - 1;
    }
    if (i > 1 && h[i] == h[i - 1]) {
      ans = ans * sum % P;
      sum--;
    }
  }
  if (h[1]) {
    cout << "0\n";
    return;
  }
  for (int i = 1; i <= n; i++)
    if (h[i] < h[i - 1] || h[i] >= n) {
      cout << "0\n";
      return;
    }
  cout << ans << '\n';
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  for (cin >> t; t; t--) 
    solve();
  return 0;
}

10min写完，然后去外面吹15min风就结束了。

总结

这次真的算简单的，难得AK一回啊。