专栏文章

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

DDFbd
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mintllw7
此快照首次捕获于
2025/12/02 08:08
3 个月前
此快照最后确认于
2025/12/02 08:08
3 个月前
查看原文
搬题人：帅气的cch
样例解释数量：2
正确样例解释数量：0
T2没和0取max，我不玩了😭
预期：100 + 100 + 100 + 20
实际：100 + 50 + 100 + 0

T1

签到题。
一开始看题看不懂，然后发现样例解释错了，就过了。
原题没找到，题意就是有 nn 类点，每类有两个点，求依次走过第 1,2,…,n1,2,\dots,n 类点，然后再依次走过第 n,n−1,…,1n,n - 1,\dots,1 类点的最短曼哈顿距离。
由题可知，编号相邻的两类会有两条连边分别连接两个点。
而这两条边总共就两种情况，第一个连第一个，第二个连第二个，或第一个连第二个，第二个连第一个。
求最小值后加入答案，最后再加上第 nn 类的两个点的连边。
CPP
#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。
依旧没找到原题，题意是有 nn 个点，mm 条无向带权边和一个数 kk，每个点有一个值 hh，经过该点时会将 kk 减 hh 再加 hh，初始时在 11 号点，且不会减 h1h_1。可以花费 x2x ^ 2 的代价将任何一个点的 hh 减 xx，且同一个点不能减多次。令总花费为代价 ++ 路径长度，求到 nn 号点的最小花费。
第 ii 个点的点权就是 max⁡(0,hi−(k+h1))2\max(0, h_i - (k + h_1))^2，然后跑一个带点权的最短路就可以了。
CPP
#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,…,n1,2,\dots,n 的排列满足以下条件：
对于所有的 i（2≤i≤n）i（2\le i\le n）：
  • 若i为奇数，则 ai−1<aia_{i−1} < a_i；
  • 若i为偶数，则 ai−1>aia_{i−1} > a_i。
答案对 109+710^9 + 7 取模
设 fif_i 为长度 ii 的答案数，然后我们分情况看看。

情况一

这时，答案就是把条件反过来的长度为 n−1n - 1 的排列数。
不难发现，把条件反过来与不反过来的答案是相同的，所以这时答案就是 fn−1f_{n - 1}。

情况二

设 nn 左边有 ll 个点，则右边有 n−1−ln - 1 - l 个点，那么这时答案应为 fl×fn−l+1×(nl)f_l \times f_{n - l + 1} \times \binom nl。

情况三

这种情况只有 nn 为奇数时有，答案同样为 fn−1f_{n - 1}。
然后 n2n^2 dp即可。
CPP
#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，能获得更高分。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...