2025-10-18模拟赛总结

· · 生活·游记

前言

是捆绑😯 我们没救了😨

A

签到题😙。

考试时一直过不了大样例😡，调了一个多小时🥵，后来发现是贡献算错了😭。

我们发现所有数互不相同，且每次修改只会增大😄。考虑记录下每一行的最大值及其位置，修改时直接更新然后算贡献即可。

其实还有一种更简单的做法🤔，直接 \mathcal{O}(q \min\{n, m\}) 暴力修改🙂，最坏时间复杂度 \mathcal{O}(q \sqrt{nm})，甚是巧妙👍👍👍

展示一下我的考场代码😁：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, q, x[N][2], y[N][2], s, c[N][2];
bool C(int i, int j) {
  return x[i][1] == j && y[j][1] == i;
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m >> q;
  for (int i = 1; i <= n; i++)
    for (int j = 1, w; j <= m; j++) {
      cin >> w;
      w > x[i][0] && (x[i][0] = w, x[i][1] = j);
      w > y[j][0] && (y[j][0] = w, y[j][1] = i);
    }
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) s += C(i, j);
  for (int i, j, w; q; q--) {
    cin >> i >> j >> w;
    bool f = !C(i, j);
    w > x[i][0] && (x[i][1] != j && (s -= C(i, x[i][1])), x[i][0] = w, x[i][1] = j);
    w > y[j][0] && (y[j][1] != i && (s -= C(y[j][1], j)), y[j][0] = w, y[j][1] = i);
    cout << (s += f && C(i, j)) << "\n";
  }
  return 0;
}

T2

我是祝睿融😍！这么祝睿融的题都没想出来😭😭😭

只写出了 p = 1 的情况😪，拼尽全力无法战胜 p = 2 的情况了😣

最后就只拿到了 p = 1 的 40 分😫

😒😒😒😒😒😒😒😒😒

T3

最开始写了个假贪心，结果发现又看错题了😂样例都没过去。后来发现并没有那么简单，根本不会做🙁感觉是个什么神秘树形 DP，但是不会做。

这道还是原题，他们基本上都做过😢听说是他们老师讲过了。神秘树形背包+上下界优化，根本写不出😥

T4

可恶捆绑！我的暴力居然都挂了一半的分😐依旧不知道为什么WA了

一点也不好玩😶

后记

👌👌👌