专栏文章

251021cch模拟赛总结

wwendywu
个人记录参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@minjpfpa
此快照首次捕获于
2025/12/02 03:31
3 个月前
此快照最后确认于
2025/12/02 03:31
3 个月前
查看原文
100 + 100 + 100 + 30 = 330
2h2h不到过T1-T3，然后T4考长链剖分不会：（

A - makise

30min30min才过，我太菜了
首先只有奇数会有贡献，而且操作完之后都是偶数，所以每次先手操作的时候都会选两个奇数，让它们不产生贡献
后手因为先手操作之后一定能有偶数，所以会用一奇一偶产生11的贡献
然后就可以做了
CPP
#include <bits/stdc++.h>
#define LL long long

using namespace std;

LL n;

int main () {
  // freopen("makise.in", "r", stdin);
  // freopen("makise.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  LL s = 0, sum = 0;
  for (LL i = 1, x; i <= n; i++) {
    cin >> x;
    s += x & 1;
    sum += x;
    if (i == 1) {
      cout << x << ' ';
      continue;
    }
    LL tmp = s / 3, tmp1 = s % 3;
    if (tmp1 != 1) {
      cout << sum - tmp << ' ';
      continue;
    }
    cout << sum - tmp - 1 << ' ';
  }
  return 0;
}

B - shop

我居然能在考场上写出贪心：）
首先我们发现，用aa的限制是只能用一次，用bb的限制是必须用了它对应的aa
然后想到bb一定是反复的用同一个，所以考虑枚举这个bb，那么aa就只会贪心的选比这个bb大的，和这个bb对应的aa
然后大样例就WA了，应为nn会比mm小，就把ansans初始化一下，然后枚举bb的时候如果要选的aa比nn多就跳过
CPP
#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 3e5 + 5;

LL t, n, m, aa[N], s[N];
struct zs {
  LL a, b;
} a[N];

bool cmp (zs x, zs y) {
  return x.b > y.b;
}

int main () {
  // freopen("shop.in", "r", stdin);
  // freopen("shop.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  for (cin >> t; t--;) {
    cin >> m >> n;
    for (int i = 1; i <= n; i++) {
      cin >> a[i].a >> a[i].b;
      aa[i] = a[i].a;
    }
    sort(a + 1, a + n + 1, cmp);
    sort(aa + 1, aa + n + 1);
    s[n + 1] = 0;
    for (int i = n; i >= 1; i--) {
      s[i] = s[i + 1] + aa[i];
    }
    LL ans = s[max(0ll, n - m + 1)];
    for (int i = 1; i <= n; i++) {
      LL k = lower_bound(aa + 1, aa + n + 1, a[i].b) - aa;
      if (k <= n - m + 1) continue;
      ans = max(ans, s[k] + (a[i].a >= a[i].b ? a[i].b * (m - (n - k + 1)) : a[i].a + a[i].b * (m - (n - k + 2))));
    }
    cout << ans << '\n';
  }
  return 0;
}

C - divide

卡掉人类智慧！！！卡掉人类智慧！！！卡掉人类智慧！！！卡掉人类智慧！！！卡掉人类智慧！！！卡掉人类智慧！！！
卡掉人类祝睿
看完题第一反应是dpdp，设f[i]f[i]表示1−i1-i的答案
转移：f[i]=maxj=0i−1f[j]+v(j+1,i)f[i] = max_{j = 0}^{i - 1}{f[j] + v(j + 1, i)}
v(i,j)v(i, j)就是ii到jj这一段的权值
然后想到线段树优化dpdp，单点修改，区间查询，ii每次往右一个，就把它到它前面第一个比它小的位置到它的vv改成它
可以用单调栈处理出在每个数前面的第一个比它小的位置
然后就好做了：）
然而有人的人类智慧过了！qwq 卡掉他们qwq
真的卡掉了！！好耶：）
CPP
#include <bits/stdc++.h>
#define LL long long
#define ls k << 1
#define rs k << 1 | 1

using namespace std;

const LL N = 1e5 + 5, inf = 1e18;

LL n, f[N], nxt[N], s[N], t;
struct aa {
  LL a, b;
} a[N];
struct node {
  LL mx, mxf, tag;
} tree[N * 4];

void push_down (int k) {
  if (tree[k].tag == -inf) return;
  tree[ls].mx = tree[ls].mxf + tree[k].tag;
  tree[rs].mx = tree[rs].mxf + tree[k].tag;
  tree[ls].tag = tree[k].tag;
  tree[rs].tag = tree[k].tag;
  tree[k].tag = -inf;
}

void push_up (int k) {
  tree[k].mx = max(tree[ls].mx, tree[rs].mx);
  tree[k].mxf = max(tree[ls].mxf, tree[rs].mxf);
}

void update1 (int k, int l, int r, int l1, int r1, LL x) {
  if (l >= l1 && r <= r1) {
    tree[k].mx = tree[k].mxf + x;
    tree[k].tag = x;
    return;
  }
  push_down(k);
  int mid = l + r >> 1;
  if (mid >= l1) {
    update1(ls, l, mid, l1, r1, x);
  }
  if (mid < r1) {
    update1(rs, mid + 1, r, l1, r1, x);
  }
  push_up(k);
}

void build (int k, int l, int r) {
  tree[k].mx = tree[k].mxf = tree[k].tag = -inf;
  if (l == r) return;
  int mid = l + r >> 1;
  build(ls, l, mid);
  build(rs, mid + 1, r);
}

LL query (int k, int l, int r, int l1, int r1) {
  if (l >= l1 && r <= r1) {
    return tree[k].mx;
  }
  push_down(k);
  LL mid = l + r >> 1, ret = -inf;
  if (mid >= l1) {
    ret = query(ls, l, mid, l1, r1);
  }
  if (mid < r1) {
    ret = max(ret, query(rs, mid + 1, r, l1, r1));
  }
  return ret;
}

void update2 (int k, int l, int r, int k1, LL x) {
  if (l == r) {
    tree[k].mxf = x;
    tree[k].mx += x;
    return;
  }
  push_down(k);
  int mid = l + r >> 1;
  if (mid >= k1) {
    update2(ls, l, mid, k1, x);
  } else {
    update2(rs, mid + 1, r, k1, x);
  }
  push_up(k);
}

int main () {
  // freopen("divide.in", "r", stdin);
  // freopen("divide.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].a;
  }
  for (int i = 1; i <= n; i++) {
    cin >> a[i].b;
  }
  s[t = 1] = 0;
  for (int i = 1; i <= n; i++) {
    for (; a[s[t]].a > a[i].a; t--);
    nxt[i] = s[t];
    s[++t] = i;
  }
  build(1, 1, n);
  update2(1, 1, n, 1, 0);
  fill(f + 1, f + n + 1, -inf);
  for (int i = 1; i <= n; i++) {
    update1(1, 1, n, nxt[i] + 1, i, a[i].b);
    f[i] = query(1, 1, n, 1, i);
    if (i == n) break;
    update2(1, 1, n, i + 1, f[i]);
  }
  cout << f[n];
  return 0;
}
/*
yang li tai shui le
zhe me shit dou neng guo
*/

D - tree

cch果然喜欢tree
还剩2h2h，心态直接崩飞
想过了树形dpdp，换根，淀粉质，树剖，最终决定打暴力：）
赛后看到hhc的正解是我不会的算法，题解的长链剖分我也不会：）
炸掉了：）
CPP
#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 1e5 + 5;

LL n, ans;
vector <LL> v[N], f[N];

void dfs1 (int x, int fa) {
  f[x].emplace_back(v[x].size() - (x != 1));
  for (int i : v[x]) {
    if (i == fa) continue;
    dfs1(i, x);
    for (int j = 0; j < f[i].size(); j++) {
      if (f[x].size() <= j + 1) {
        f[x].emplace_back(f[i][j]);
      } else {
        f[x][j + 1] += f[i][j];
      }
    }
  }
}

void qwq (int x, int y) {
  for (int i = 0; i < min(f[x].size(), f[y].size() + 1); i++) {
    if (i == 0) {
      f[x][i]--;
    } else {
      f[x][i] -= f[y][i - 1];
    }
  }
  for (int i = 0; i < f[x].size(); i++) {
    if (f[y].size() <= i + 1) {
      f[y].emplace_back(f[x][i]);
    } else {
      f[y][i + 1] += f[x][i];
    }
  }
  if (!f[y].size()) f[y].emplace_back(0);
  f[y][0]++;
}

void dfs2 (int x, int fa) {
  if (v[x].size() >= 3) {
    ans += 1ll * v[x].size() * (v[x].size() - 1) * (v[x].size() - 2) / 6;
    // cout << ans << '\n';
    for (int i = 0; i < f[x].size(); i++) {
      LL s = 0, s1 = 0;
      for (int j : v[x]) {
        if (f[j].size() <= i) continue;
        ans += f[j][i] * s1;
        s1 += f[j][i] * s;
        s += f[j][i];
        // cout << ans << ' ' << s << ' ' << s1 << ' ' << f[j][i] << ' ' << j << ' ' << i << '\n';
      }
    }
  }
  // cout << x << '\n';
  // for (int i : f[x]) {
  //   cout << i << ' ';
  // }
  // cout << '\n';
  // for (int i : v[x]) {
  //   for (int j : f[i]) {
  //     cout << j << ' ';
  //   }
  //   cout << '\n';
  // }
  // cout << ' ' << ans << '\n';
  for (int i : v[x]) {
    if (i == fa) continue;
    qwq(x, i);
    dfs2(i, x);
    qwq(i, x);
  }
}

int main () {
  // freopen("tree.in", "r", stdin);
  // freopen("tree.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for (int i = 1, x, y; i < n; i++) {
    cin >> x >> y;
    v[x].emplace_back(y);
    v[y].emplace_back(x);
  }
  dfs1(1, 1);
  dfs2(1, 1);
  cout << ans;
  return 0;
}
/*
xiao yang li zhe me shui a qwq
zen me xie dou neng guo
zi ji zao de dou guo bu liao , ran hou xiao yang li hai guo le
tai ** nan tiao le qwq
*/

前3题写的非常顺利，但是T4是没学过的东西，相当于2h2h没事做qwq

评论

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

正在加载评论...