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

DFbd · 2025-10-21 16:30:26 · 个人记录

闪击战+线段树战

预期：100 + 100 + 100 + 20

实际：100 + 100 + 100 + 20

T1

哈哈这次史没有跟上我，做完T1T2它就走了。

原题

一眼题，先手显然选两个奇数，后手选一奇一偶，所以记一个 cnt 表示奇数个数，一个 sum 表示总和，答案就是 sum - \lfloor \frac{cnt}{3} \rfloor - [cnt \bmod 3 = 1]。

写了15min。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int kMaxN = 1e5 + 5;

ll n, a, cnt, sum;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  for (cin >> n; n; n--) {
    cin >> a;
    cnt += a % 2;
    sum += a;
    cout << (sum == a ? a : sum - cnt / 3 - (cnt % 3 == 1)) << ' ';
  }
  return 0;
}

这个题其实23年我们做过两次，那个时候我甚至两次都WA了一发。

T2

原题

感觉这题2000有点高了，直接把 a、b 塞进一个数组里从大到小排个序，是 a 的就直接选，同时把原数组中的编号打个标记，是 b 的就看它是否被标记，如果是，剩下的就全选它后退出，否则就选个对应的 a 再全选它，选完和答案取最大值，然后放弃这个继续选。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int kMaxN = 2e5 + 5;

struct node {
  ll v, o, id;
} c[kMaxN];

ll t, n, m, a[kMaxN], b[kMaxN], vis[kMaxN];

bool cmp(node a, node b) {
  return a.v > b.v;
}

void solve() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    cin >> a[i] >> b[i];
    vis[i] = 0;
    c[i * 2 - 1] = {a[i], 0, i};
    c[i * 2] = {b[i], 1, i};
  }
  sort(c + 1, c + 2 * m + 1, cmp);
  ll ans = 0, now = 0, cnt = 0;
  for (int i = 1; i <= 2 * m; i++) {
    if (cnt >= n)
      break;
    if (!c[i].o) {
      vis[c[i].id] = 1;
      now += c[i].v;
      cnt++;
    } else {
      if (vis[c[i].id]) {
        ans = max(ans, c[i].v * (n - cnt) + now);
        cout << ans << '\n';
        return;
      } else
        ans = max(ans, c[i].v * (n - cnt - 1) + a[c[i].id] + now);
    }
  }
  cout << max(now, ans) << '\n';
}

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

写了20min，还有3h25min写T3T4，时间充裕。

T3

原题

这个想的有点久了。

首先我想到了按 h 排序，然后dp，用可持久化线段树维护每个数是否已经被选过。

但是这样显然是会死的，于是想直接dp，看怎么优化。

设 f_i 表示前 i 个数的最大总价值，v(x, y) 为 x 到 y 中最矮建筑的 b 值，f_i = \max_{j = 0}^{i - 1} f_j + v(j + 1, i)

那么就可以用一个线段树维护 f，用 tf 表示，一个线段树维护 f + v，用 t 表示。

同时，我们需要求出每个位置 x 最大的满足 y < x 且 h_y < h_x 的 y，记为 l_x。

然后做dp，每次先在 t 的区间 [l_i + 1, i] 上进行一个类似于区间覆盖的操作，也就是 t_x = tf_x + b_i。

接下来直接询问最大值，存入 f_i。

然后对 tf 单点修改。

由于我不会树状数组，所以我用线段树。

总共三个线段树，也是成功的写出了超级神人做法，用了1.5h。

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int kMaxN = 1e5 + 5;

int n, a[kMaxN], f[kMaxN], t[kMaxN << 2], tag[kMaxN << 2], tf[kMaxN << 2], l[kMaxN];

void addtag(int x, int v) {
  tag[x] = v;
  t[x] = tf[x] + v;
}

void pushdown(int x) {
  if (tag[x]) {
    addtag(x << 1, tag[x]);
    addtag(x << 1 | 1, tag[x]);
    tag[x] = 0;
  }
}

int query(int x, int l, int r, int a, int b) {
  if (l > b || r < a)
    return -1e18;
  if (a <= l && r <= b) 
    return t[x];
  pushdown(x);
  int m = l + r >> 1;
  return max(query(x << 1, l, m, a, b), query(x << 1 | 1, m + 1, r, a, b));
}

void update(int x, int l, int r, int a, int v) {
  if (l > a || r < a)
    return;
  if (l == r) {
    t[x] = v;
    return;
  }
  int m = l + r >> 1;
  update(x << 1, l, m, a, v);
  update(x << 1 | 1, m + 1, r, a, v);
  t[x] = max(t[x << 1], t[x << 1 | 1]);
}

void updatef(int x, int l, int r, int a, int v) {
  if (l > a || r < a)
    return;
  if (l == r) {
    tf[x] = v;
    return;
  }
  int m = l + r >> 1;
  updatef(x << 1, l, m, a, v);
  updatef(x << 1 | 1, m + 1, r, a, v);
  tf[x] = max(tf[x << 1], tf[x << 1 | 1]);
}

void modify(int x, int l, int r, int a, int b, int v) {
  if (l > b || r < a)
    return;
  if (a <= l && r <= b) {
    addtag(x, v);
    return;
  }
  pushdown(x);
  int m = l + r >> 1;
  modify(x << 1, l, m, a, b, v);
  modify(x << 1 | 1, m + 1, r, a, b, v);
  t[x] = max(t[x << 1], t[x << 1 | 1]);
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    l[i] = query(1, 1, n, 1, a[i]);
    update(1, 1, n, a[i], i);
  }
  memset(t, 0, sizeof(t));
  for (int i = 1, b; i <= n; i++) {
    cin >> b;
    modify(1, 1, n, l[i] + 1, i, b);
    f[i] = query(1, 1, n, 1, i);
    updatef(1, 1, n, i + 1, f[i]);
  }
  cout << f[n];
  return 0;
}

人类智慧又过了，还好老师最后卡了一下，大快人心。

T4

原题

我真的不会dp，只能 \mathcal{O(n^3)} 遗憾离场。

总结

线段树好玩😋

dp太难了，我太菜了，只能多练🙌