专栏文章

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

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

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minjnb37
此快照首次捕获于
2025/12/02 03:30
3 个月前
此快照最后确认于
2025/12/02 03:30
3 个月前
查看原文
闪击战+线段树战
预期：100 + 100 + 100 + 20
实际：100 + 100 + 100 + 20

T1

哈哈这次史没有跟上我，做完T1T2它就走了。
原题
一眼题，先手显然选两个奇数，后手选一奇一偶，所以记一个 cntcnt 表示奇数个数，一个 sumsum 表示总和，答案就是 sum−⌊cnt3⌋−[cnt mod 3=1]sum - \lfloor \frac{cnt}{3} \rfloor - [cnt \bmod 3 = 1]。
写了15min。
CPP
#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、ba、b 塞进一个数组里从大到小排个序，是 aa 的就直接选，同时把原数组中的编号打个标记，是 bb 的就看它是否被标记，如果是，剩下的就全选它后退出，否则就选个对应的 aa 再全选它，选完和答案取最大值，然后放弃这个继续选。
CPP
#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

原题
这个想的有点久了。
首先我想到了按 hh 排序，然后dp，用可持久化线段树维护每个数是否已经被选过。
但是这样显然是会死的，于是想直接dp，看怎么优化。
设 fif_i 表示前 ii 个数的最大总价值，v(x,y)v(x, y) 为 xx 到 yy 中最矮建筑的 bb 值，fi=max⁡j=0i−1fj+v(j+1,i)f_i = \max_{j = 0}^{i - 1} f_j + v(j + 1, i)
那么就可以用一个线段树维护 ff，用 tftf 表示，一个线段树维护 f+vf + v，用 tt 表示。
同时，我们需要求出每个位置 xx 最大的满足 y<xy < x 且 hy<hxh_y < h_x 的 yy，记为 lxl_x。
然后做dp，每次先在 tt 的区间 [li+1,i][l_i + 1, i] 上进行一个类似于区间覆盖的操作，也就是 tx=tfx+bit_x = tf_x + b_i。
接下来直接询问最大值，存入 fif_i。
然后对 tftf 单点修改。
由于我不会树状数组，所以我用线段树。
总共三个线段树，也是成功的写出了超级神人做法，用了1.5h。
CPP
#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，只能 O(n3)\mathcal{O(n^3)} 遗憾离场。

总结

线段树好玩😋
dp太难了，我太菜了，只能多练🙌

评论

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

正在加载评论...