码蹄杯 2026 提高组初赛第2场记录

2026-04-262026-04-29

Info

距离结束还有9分钟，但是已经写不出来了，做了5道，罚时3次，比上次进步了一题，封榜前是696名，总人数5697人，看能不能水到个奖吧

最后排名是823/5000+(不知道一道都没做出来的算不算)，希望给个银吧

1 签到

维护最大和最小的x和y的值，计算框出的面积

void solve() {
  int n;
  cin >> n;
  i64 x2 = 0, y2 = 0, x1 = INT_MAX, y1 = INT_MAX;
  while (n --) {
    i64 x, y;
    cin >> x >> y;
    x1 = min(x1, x);
    y1 = min(y1, y);
    x2 = max(x2, x);
    y2 = max(y2, y);
  }
  cout << (x2 - x1) * (y2 - y1) << endl;
}

3 枚举

算出两两之间的距离，找到每列的最大值的最小值

void solve() {
  int n;
  cin >> n;
  auto loc = vector(n, vector(2, 0));
  for (int i = 0; i < n; i ++) cin >> loc[i][0] >> loc[i][1];

  auto time = vector(n, vector(n, 0));

  auto calc = [&](int u, int v) {
    return abs(loc[u][0] - loc[v][0]) + abs(loc[u][1] - loc[v][1]);
  };
  for (int u = 0; u < n; u ++) {
    for (int v = u + 1; v < n; v ++) {
      time[u][v] = calc(u, v);
      time[v][u] = time[u][v];
    }
  }
  int ans = INT_MAX;
  for (int v = 0; v < n; v ++) {
    int cnt = 0;
    for (int u = 0; u < n; u ++) {
      cnt = max(cnt, time[u][v]);
    }
    ans = min(ans, cnt);
  }
  cout << ans << endl;
}

7 贡献法？

最多交换的次数是\(\frac{n(n - 1)m}{2}\)，去除掉不用交换的

吃了3发罚时因为i64 ans = n * (n - 1) / 2 * m不能写成i64 ans = n * (n - 1) * m / 2，太狗了

void solve() {
  i64 n, m;
  cin >> n >> m;
  vector<string> maze(n);
  for (int i = 0; i < n; i ++) cin >> maze[i];
  i64 ans = n * (n - 1) / 2 * m;
  for (int c = 0; c < m; c ++) {
    vector<i64> cnt(30);
    for (int r = 0; r < n; r ++) {
      cnt[maze[r][c] - 'a'] ++;
    }
    for (int i = 0; i < 30; i ++) {
      if (cnt[i]) ans -= (cnt[i] * (cnt[i] - 1) / 2);
    }
  }
  cout << ans << endl;
}

8 位运算

void solve() {
  int n;
  cin >> n;
  i64 ans = 0;
  while (n --) {
    int x;
    cin >> x;
    int high = x >> 4;
    int low = (x & 15) << 4;
    ans += high;
    ans += low;
  }
  cout << ans << endl;
}

10 签到

void solve() {
  string s;
  cin >> s;
  int a, b;
  int n = s.size();
  cin >> a>> b;
  for (int i = a; i <= n - 1 - b; i ++) cout << s[i];
  cout << endl;
}

没开出来的

9

贪心 + 01背包 ST表优先队列，都思考过，但还是没思考出来

玛德，是multiset + upper_bound，完全忘记STL里可以用二分了

set, multiset, map, multimap(这是啥没见过), vector, deque都能用upper_bound

4

树 + 回溯

感觉还要加上组合数学...回溯也要魔改，最后还是没想出来

玛德是树形dp，高攀了高攀了

码蹄杯 2026 提高组 初赛 第2场 记录