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

· · 个人记录

搬题人：帅气的cch

样例解释数量：2

正确样例解释数量：0

T2没和0取max，我不玩了😭

预期：100 + 100 + 100 + 20

实际：100 + 50 + 100 + 0

T1

签到题。

一开始看题看不懂，然后发现样例解释错了，就过了。

原题没找到，题意就是有 n 类点，每类有两个点，求依次走过第 1,2,\dots,n 类点，然后再依次走过第 n,n - 1,\dots,1 类点的最短曼哈顿距离。

由题可知，编号相邻的两类会有两条连边分别连接两个点。

而这两条边总共就两种情况，第一个连第一个，第二个连第二个，或第一个连第二个，第二个连第一个。

求最小值后加入答案，最后再加上第 n 类的两个点的连边。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int kMaxN = 1e5 + 5;

ll n, m, ans, a[kMaxN << 1], b[kMaxN << 1];

ll dis(ll a, ll b, ll c, ll d) {
  return abs(a - c) + abs(b - d);
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i * 2 - 1] >> b[i * 2 - 1] >> a[i * 2] >> b[i * 2];
    int nx1 = a[i * 2 - 1], ny1 = b[i * 2 - 1], nx2 = a[i * 2], ny2 = b[i * 2];
    int lx1 = a[(i - 1) * 2 - 1], ly1 = b[(i - 1) * 2 - 1], lx2 = a[(i - 1) * 2], ly2 = b[(i - 1) * 2];
    if (i > 1) 
      ans += min(dis(nx1, ny1, lx1, ly1) + dis(nx2, ny2, lx2, ly2), dis(nx1, ny1, lx2, ly2) + dis(nx2, ny2, lx1, ly1));
  }
  cout << ans + dis(a[n * 2 - 1], b[n * 2 - 1], a[n * 2], b[n * 2]);
  return 0;
}

T2

纯最短路板子，但是我没考虑负数，没有和0取max，痛失50pts。

依旧没找到原题，题意是有 n 个点，m 条无向带权边和一个数 k，每个点有一个值 h，经过该点时会将 k 减 h 再加 h，初始时在 1 号点，且不会减 h_1。可以花费 x ^ 2 的代价将任何一个点的 h 减 x，且同一个点不能减多次。令总花费为代价 + 路径长度，求到 n 号点的最小花费。

第 i 个点的点权就是 \max(0, h_i - (k + h_1))^2，然后跑一个带点权的最短路就可以了。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int kMaxN = 2e5 + 5;

struct node {
  ll to, v;
  bool operator < (const node &a) const {return v > a.v;}
};

ll n, m, k, h[kMaxN], val[kMaxN], dis[kMaxN], vis[kMaxN];
vector<node> e[kMaxN];

void Dijkstra() {
  memset(dis, 0x3f, sizeof(dis));
  priority_queue<node> q;
  q.push({1, 0});
  dis[1] = 0;
  while (q.size()) {
    int x = q.top().to;
    q.pop();
    if (vis[x])
      continue;
    vis[x] = 1;
    for (int i = 0; i < e[x].size(); i++) {
      int t = e[x][i].to;
      if (dis[t] > dis[x] + e[x][i].v + val[t]) {
        dis[t] = dis[x] + e[x][i].v + val[t];
        q.push({t, dis[t]});
      }
    }
  }
}

int main() {
  cin >> n >> m >> k;
  for (int i = 1; i <= n; i++) {
    cin >> h[i];
    val[i] = max(0ll, h[i] - k - h[1]) * max(0ll, h[i] - k - h[1]); //这里一定要记得取max
  }
  for (int i = 1; i <= m; i++) {
    ll x, y, z;
    cin >> x >> y >> z;
    e[x].push_back({y, z});
    e[y].push_back({x, z});
  }
  Dijkstra();
  cout << dis[n];
  return 0;
}

T3

抽象找规律，找了2.5h。

题意就是求有多少个 1,2,\dots,n 的排列满足以下条件：

对于所有的 i（2\le i\le n）：

答案对 10^9 + 7 取模

设 f_i 为长度 i 的答案数，然后我们分情况看看。

情况一

这时，答案就是把条件反过来的长度为 n - 1 的排列数。

不难发现，把条件反过来与不反过来的答案是相同的，所以这时答案就是 f_{n - 1}。

情况二

设 n 左边有 l 个点，则右边有 n - 1 - l 个点，那么这时答案应为 f_l \times f_{n - l + 1} \times \binom nl。

情况三

这种情况只有 n 为奇数时有，答案同样为 f_{n - 1}。

然后 n^2 dp即可。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll p = 1e9 + 7;

ll n, f[10005], fact[10005], ifa[10005];

ll fpow(ll a, ll b) {
  ll res = 1;
  while (b) {
    if (b % 2)
      res = res * a % p;
    a = a * a % p;
    b >>= 1;
  }
  return res;
}

ll C(ll x, ll y) {
  return fact[x] * ifa[y] % p * ifa[x - y] % p;
}

int main() {
  cin >> n;
  fact[0] = 1;
  for (int i = 1; i <= n; i++) {
    fact[i] = fact[i - 1] * i % p;
    ifa[i] = fpow(fact[i], p - 2);
  }
  f[1] = 1;
  for (ll i = 1; i <= n; i++) {
    for (ll j = 2; j <= i - 1; j += 2)
      f[i] = (f[j] * f[i - 1 - j] % p * C(i - 1, j) % p + f[i]) % p;
    f[i] = (f[i] + f[i - 1] * (1 + (i % 2)) % p) % p;
  }
  cout << f[n];
  return 0;
}

T4

写完T3没时间了，赶紧随便写了个20pts，然后预料之中地挂了。

总结

本次比赛出现的最大问题：时间分配不均。

我是这样打的：

前20min没看懂T1，看懂后10min过了。

然后30min把T2、3、4看了一下，然后20min写完T2。

然后开始手玩T3，玩了2h20min才发现规律，然后10min过掉。

这时才开始写T4，然后没拿到分。

所以不如先把能写暴力写了，再去过T3，能获得更高分。