专栏文章

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

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

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minkq6po
此快照首次捕获于
2025/12/02 04:00
3 个月前
此快照最后确认于
2025/12/02 04:00
3 个月前
查看原文
呜呜呜set常数怎么那么大，2×1052 \times 10^5 的 O(qlog⁡n)\mathcal{O(q \log n)} 给我卡没了啊啊啊。
今天还捆绑呜呜呜，大挂分。
预期：100 + 100 + 0 + 40
实际：40 + 100 + 0 + 40

T1

原题
今天有点弱智，前30min都没想到T1。
可以发现每次修改只影响一列一行，所以我们用set记下每一行和每一列，这样就可以查最大值，还能修改。再看看这一行和这一列中的最大值是否合法，计算答案。
直接开始写，写到一半又想拉屎，拉完回来45min了，写完刚好50min。
CPP
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 2e5 + 5;

int n, m, q, ans;
vector<int> a[kMaxN];
set<int> r[kMaxN], c[kMaxN], s;
unordered_map<int, pair<int, int>> mp;

bool check(int x) {
  return (*r[mp[x].first].rbegin()) == (*c[mp[x].second].rbegin());
}

int main() {
  cin >> n >> m >> q;
  for (int i = 1; i <= n; i++) {
    a[i].push_back(0);
    for (int j = 1, x; j <= m; j++) {
      cin >> x;
      mp[x] = {i, j};
      r[i].insert(x);
      c[j].insert(x);
      a[i].push_back(x);
    }
  }
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      ans += ((*r[i].rbegin()) == (*c[j].rbegin()));
  for (int z, y, t; q; q--) {
    cin >> z >> y >> t;
    ans -= check((*r[z].rbegin())) + check((*c[y].rbegin())) - ((*r[z].rbegin()) == (*c[y].rbegin()));
    r[z].erase(a[z][y]);
    c[y].erase(a[z][y]);
    a[z][y] = t;
    mp[t] = {z, y};
    r[z].insert(t);
    c[y].insert(t);
    ans += check((*r[z].rbegin())) + check((*c[y].rbegin())) - ((*r[z].rbegin()) == (*c[y].rbegin()));
    cout << ans << '\n';
  }
  return 0;
}
这里就可以引出我的挂分的根本原因了。注意题目中写到只会修改为更大的值，所以只需要记录一个最大值，修改就直接与修改后的值取最大值。
赛后补题：
CPP
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 2e5 + 5;

int n, m, q, ans, r[kMaxN], c[kMaxN];
vector<int> a[kMaxN];
unordered_map<int, pair<int, int>> mp;

bool check(int x) {
  return r[mp[x].first] == c[mp[x].second];
}

int main() {
  cin >> n >> m >> q;
  for (int i = 1; i <= n; i++) {
    a[i].push_back(0);
    for (int j = 1, x; j <= m; j++) {
      cin >> x;
      mp[x] = {i, j};
      r[i] = max(r[i], x);
      c[j] = max(c[j], x);
      a[i].push_back(x);
    }
  }
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      ans += (r[i] == c[j]);
  for (int z, y, t; q; q--) {
    cin >> z >> y >> t;
    ans -= check(r[z]) + check(c[y]) - (r[z] == c[y]);
    r[z] = max(r[z], t);
    c[y] = max(c[y], t);
    a[z][y] = t;
    mp[t] = {z, y};
    ans += check(r[z]) + check(c[y]) - (r[z] == c[y]);
    cout << ans << '\n';
  }
  return 0;
}
捆绑测试我爱你，set我爱你，DFbd我爱你。

T2

T2和T3混着看的，然后就很爆炸，想了很久很久，直到2h40min时才会T2呜呜呜。
T2 T3
显然，只有细胞 ii 的易感染度最高的病毒编号是 ii，病毒 ii 才是稳定的。
接下来我们需要判断病毒是否可行。
只要有一个细胞可以使该病毒寄生并不会被消灭，该病毒就可行。
所以我们只需要枚举细胞，再枚举病毒寄生于该细胞是否可行。
而可行的条件即为，所有该细胞中易感染度高于该病毒的易感染度的病毒存活在初始细胞中，可以被易感染度低于该病毒的病毒直接消灭。
所以，我们将可以直接消灭存活于细胞 ii 的病毒 ii 的所有病毒向 ii 连边，然后枚举细胞和病毒。
枚举病毒时，按照易感染度从低往高枚举，先判断是否可行，再将该点和与该点直接相邻的点打上标记，并统计标记个数。
若标记个数减去当前病毒的标记 ≥n−1\ge n - 1，该病毒可行。
CPP
#include <bits/stdc++.h>

using namespace std;

int n, a[505][505], p, cnt, f[505];
vector<int> ans, e[505];

void fill(int x) {
  f[x] = 1;
  cnt++;
  for (int i : e[x])
    if (!f[i]) {
      f[i] = 1;
      cnt++;
    }
}

int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    int flag = 0;
    for (int j = 1; j <= n; j++) {
      cin >> a[i][j];
      if (a[i][j] == i)
        flag = 1;
      if (!flag)
        e[a[i][j]].push_back(i);
    }
    if (a[i][1] == i) {
      cnt++;
      ans.push_back(i);
    }
  }
  cin >> p;
  if (p == 1) {
    cout << cnt << '\n';
    for (int i : ans) 
      cout << i << ' ';
  } else {
    set<int> s;
    for (int i = 1; i <= n; i++) {
      cnt = 0;
      memset(f, 0, sizeof(f));
      for (int j = n; j; j--) {
        if (cnt - f[a[i][j]] >= n - 1)
          s.insert(a[i][j]);
        if (!f[a[i][j]]) 
          fill(a[i][j]);
      }
    }
    cout << s.size() << '\n';
    for (int i : s)
      cout << i << ' ';
  }
  return 0;
}

T3

别看了，没时间写了呜呜呜。

T4

原题
O(n4)\mathcal{O(n^4)} 很简单，枚举四个端点即可。
那 O(n3)\mathcal{O(n^3)} 也就不难了，先枚举一段，第二段用双指针即可。
40pts：
CPP
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int kMaxN = 5e5 + 5;

int n, m, a[kMaxN], x[kMaxN], b[kMaxN], y[kMaxN], f[kMaxN << 1];

signed main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
    cin >> a[i];
  for (int i = 1; i <= n; i++)
    cin >> x[i];
  for (int i = 1; i <= m; i++)
    cin >> b[i];
  for (int i = 1; i <= m; i++)
    cin >> y[i];
  int ans = 0, ansl1 = 0, ansr1 = 0, ansl2 = 0, ansr2 = 0;
  int now = 0, mx = 0, mxl = 0, mxr = 0, l = 1, r = 1;
  for (; r <= m; r++) {
    now += y[r];
    f[b[r]]++;
    while (f[b[r]] > 1 && l <= r) {
      f[b[l]]--;
      now -= y[l];
      l++;
    }
    if (now > mx) {
      mxl = l;
      mxr = r;
      mx = now;
    }
  }
  for (int k = l; k <= r; k++)
    f[b[k]]--;
  if (mxl > mxr)
    mxl = mxr = 0;
  if (mx > ans) {
    ans = mx;
    ansl1 = 0, ansr1 = 0, ansl2 = mxl, ansr2 = mxr;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n + m; j++)
      f[j] = 0;
    int sum = 0;
    for (int j = i; j <= n; j++) {
      sum += x[j];
      f[a[j]]++;
      int now = 0, mx = 0, mxl = 0, mxr = 0, l = 1, r = 1;
      for (; r <= m; r++) {
        now += y[r];
        f[b[r]]++;
        while (f[b[r]] > 1 && l <= r) {
          f[b[l]]--;
          now -= y[l];
          l++;
        }
        if (now > mx) {
          mxl = l;
          mxr = r;
          mx = now;
        }
      }
      for (int k = l; k <= r; k++)
        f[b[k]]--;
      if (mxl > mxr)
        mxl = mxr = 0;
      if (mx + sum > ans) {
        ans = mx + sum;
        ansl1 = i, ansr1 = j, ansl2 = mxl, ansr2 = mxr;
      }
    }
  }
  cout << ans << '\n' << ansl1 << ' ' << ansr1 << '\n' << ansl2 << ' ' << ansr2;
  return 0;
}

总结

T1里更大的数在我们的ptf里甚至加粗了，我还没看到呜呜呜。
稀有读题错误，呜呜我错了。
还有set常数怎么那么大，慎用。

评论

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

正在加载评论...