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

· · 个人记录

每日爆炸（5/1）

T3数据爆炸，std爆炸，T4数据爆炸，心态爆炸，pts爆炸

预期：100 + 100 + 看运气 + 50

实际：100 + 100 + 5 + 50

T1

题意：有一个数字 m，每时刻可以将 m 加一、减一或不变。有 n 个时刻 t_i，要求在 t_i 时 l_i \le m \le r_i，若有方案能满足所有要求，输出 YES，否则输出 NO。

依旧先拉屎，回来再写。

发现只要记录当前可能温度最大值和最小值，如果与当前的范围不相交，就无解。否则就取个交集然后继续。

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int kMaxN = 1e5 + 5;

struct node {
  int t, l, h;
} p[kMaxN];

int T, n, m;

bool cmp(node a, node b) {
  return a.t < b.t;
}

void solve() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
    cin >> p[i].t >> p[i].l >> p[i].h;
  sort(p + 1, p + n + 1, cmp);
  int tl = m, tr = m;
  for (int i = 1; i <= n; i++) {
    tl -= (p[i].t - p[i - 1].t), tr += (p[i].t - p[i - 1].t);
    if (tr < p[i].l || tl > p[i].h) {
      cout << "NO\n";
      return;
    }
    tl = max(tl, p[i].l), tr = min(tr, p[i].h);
  }
  cout << "YES\n";
}

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

又是30min，不知道为什么每一次一会T1就拉屎。

T2

题意：有一棵树，每个点上有一个数集，q 次询问，每次求 x 到根节点经过的最早的数集中包含 y 的点的编号，没有的话输出 -1。

看到范围感觉这题是 \mathcal{O(q \log n)} 的，然后就想 \log 算法，感觉不是很可做。

于是就想把询问离线处理。

我们可以存下每个点的询问的 y 和是第几个询问，存完后直接暴搜，同时维护一个每个数出现的位置（只要记最后一个），然后把每个点的询问都处理了就可以了，不要忘了回溯。

#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 1e5 + 5;

struct node {
  int v, id;
};

int n, fa[kMaxN], Q, ans[kMaxN], now[kMaxN];
vector<int> e[kMaxN], a[kMaxN];
vector<node> q[kMaxN];

void dfs(int x) {
  vector<int> v;
  for (int i = 0; i < a[x].size(); i++) {
    v.push_back(now[a[x][i]]);
    now[a[x][i]] = x;
  }
  for (int i = 0; i < q[x].size(); i++)
    ans[q[x][i].id] = now[q[x][i].v];
  for (int i = 0; i < e[x].size(); i++)
    dfs(e[x][i]);
  for (int i = 0; i < a[x].size(); i++)
    now[a[x][i]] = v[i];
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 2; i <= n; i++) {
    cin >> fa[i];
    e[fa[i]].push_back(i);
  }
  for (int i = 1, k; i <= n; i++) {
    for (cin >> k; k; k--) {
      int x;  
      cin >> x;
      a[i].push_back(x);
    }
  }
  cin >> Q;
  for (int i = 1; i <= Q; i++) {
    int x, y;
    cin >> x >> y;
    q[x].push_back({y, i});
  }
  memset(now, -1, sizeof(now));
  dfs(1);
  for (int i = 1; i <= Q; i++)
    cout << ans[i] << '\n';
  return 0;
}

竟然有人用数剖+倍增再加线段树过了，太恐怖了。

T4

题意：有一棵以 1 为根的树，每个节点有两个值 a_i,b_i，你可以从节点 x 跳到它的子树内任意一个节点 y 上，花费为 a_x \times b_y。跳跃多次走过一条路径的总费用为每次跳跃的费用之和。请分别计算出每个节点到达它子树中叶子节点的费用中的最小值。不能从一个节点跳到它自己。

暴力 \mathcal{O(n^2)} dp很好做，于是在此基础上开始想转移优化。

想了1h想到了，兴奋地开始写的时候发现有 (10^5)^{10^5} 的乘法于是去世了，气炸了。

最后只能暴力遗憾离场。

T3

赛时写不动了，写完T4才来的。

后来发现是个广搜，直接死掉了。