专栏文章

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

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

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minh3v7z
此快照首次捕获于
2025/12/02 02:19
3 个月前
此快照最后确认于
2025/12/02 02:19
3 个月前
查看原文
今天没过T3，呜呜呜我太菜了。
预期：100 + 100 + 70 + (60 + 看运气)
实际：85 + 100 + 70 + 70

T1

挂了15分，炸了。
原题
可以想到枚举公差，就可以算出每个数对应的首项，这个首项的修改次数就会减一。
于是可以用一个umap记录每个首项减的次数，每次修改和答案取更优值。
于是我就写出了考场代码，用了25min。
CPP
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 3e5 + 5;

int n, w, a[kMaxN], ans = 1e9;

int main() {
  freopen("queue.in", "r", stdin);
  freopen("queue.out", "w", stdout);
  cin >> n >> w;
  for (int i = 1; i <= n; i++)
    cin >> a[i];
  for (int i = 0; 1 + i * (n - 1) <= w; i++) {
    unordered_map<int, int> mp;
    for (int j = 1; j <= n; j++) {
      mp[a[j] - i * (j - 1)]++;
      ans = min(ans, n - mp[a[j] - i * (j - 1)]);
    }
  }
  cout << ans;
  return 0;
}
我拿到了85pts，原因是没有判断上界，如果末项超过 ww 这个就是不合法的，同时首项还要大于一。当 n=1n = 1 时，枚举公差会死循环，需要特判。
CPP
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 3e5 + 5;

int n, w, a[kMaxN], ans = 1e9;

int main() {
  cin >> n >> w;
  if (n == 1) {
    cout << 0;
    return 0;
  }
  for (int i = 1; i <= n; i++)
    cin >> a[i];
  for (int i = 0; 1 + i * (n - 1) <= w; i++) {
    unordered_map<int, int> mp;
    for (int j = 1; j <= n; j++)
      if (a[j] - i * (j - 1) + i * (n - 1) <= w && a[j] - i * (j - 1) > 0) {
        mp[a[j] - i * (j - 1)]++;
        ans = min(ans, n - mp[a[j] - i * (j - 1)]);
      }
  }
  cout << ans;
  return 0;
}

T2

这个绝对比T1简单。
原题
显然只要一个点没有与他相邻且编号比他大的点，那么他就不会被删。
所以记录与他相邻且编号比他大的点的数量，答案就是数量为0的点数。
CPP
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 1e5 + 5;

int n, m, q, op, cnt[kMaxN], ans;

void addedge() {
  int u, v;
  cin >> u >> v;
  if (v > u) {
    ans -= (!cnt[u]);
    cnt[u]++;
  } else {
    ans -= (!cnt[v]);
    cnt[v]++;
  }
}

void deledge() {
  int u, v;
  cin >> u >> v;
  if (v > u) {
    cnt[u]--;
    ans += (!cnt[u]);
  } else {
    cnt[v]--;
    ans += (!cnt[v]);
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> m;
  ans = n;
  for (int i = 1; i <= m; i++) 
    addedge();
  for (cin >> q; q; q--) {
    cin >> op;
    if (op == 1) 
      addedge();
    if (op == 2)
      deledge();
    if (op == 3)
      cout << ans << '\n';
  }
  return 0;
}
15min写完，比T1快10min。

T3

哎呀没有观察到美丽性质，气炸了。
原题
显然这题最多合并两个区间，只要存在 mm 使得 sm⊕sl−1>sr⊕sms_m \oplus s_{l - 1} > s_r \oplus s_m（ss 为异或前缀和）。
于是可以写出 O(n3)\mathcal{O(n^3)} 的暴力，再加上两个性质可以拿到70pts。
可以观察到，总共只有30多个二进制位，而数组又是递增的，所以长度大于60时，答案必然是1。
CPP
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int kMaxN = 1e5 + 5;

int T, n, a[kMaxN];

void solve() {
  cin >> n;
  int f = 1, F = 1;
  for (int i = 1; i <= n; i++)
    cin >> a[i];
  if (n > 60) {
    cout << "1\n";
    return;
  }
  if (n <= 2) {
    cout << "-1\n";
    return;
  }
  int ans = 1e9;
  for (int i = 1; i <= n; i++)
    a[i] ^= a[i - 1];
  for (int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++)
      for (int k = i; k < j; k++)
        if ((a[k] ^ a[j]) < (a[k] ^ a[i - 1]))
          ans = min(ans, j - i - 1);
  cout << (ans == 1e9 ? -1 : ans) << '\n';
}

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

T4

直接暴力，60pts拿满，再加上无解，总共70pts。

总结

我是傻子，我怎么没做出T3。

评论

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

正在加载评论...