Atcoder ABC 470 A~C 题解

August 8, 2026Atcoder ABC1min read...

C题做的不太顺，后面的题就不做了😴

void solve() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i ++) {
    if (i % 3 == 0) cout << "Fizz\n";
    else cout << i << endl;
  }
}

void solve() {
  int n;
  cin >> n;
  vector<int> cnt(n + 1);
  for (int i = 0;i < n; i ++) {
    int c;
    cin >> c;
    cnt[c] ++;
  }
  int mx = *max_element(cnt.begin(), cnt.end());
  cout << n - mx << endl;
}

最开始想复杂了的一道题，想要通过统计某些量来实现每次query都是O(1)，真是傻逼了

实际就使用set维护好op == 2时要减的坐标就行了

正确性证明

每遍历一个正数位置，它的值就会减少 1。而所有元素增加的总次数最多等于 1 操作的数量，即不超过 Q。由于元素值不会变为负数，所有减少的总次数也不超过所有增加的总次数，因此总遍历次数为

然而在使用set的时候又踩坑了，在使用auto遍历set时，如果对set进行erase，会导致迭代器失效，产生未定义行为。

一定要在遍历的时候进行erase的话，要么使用multiset，要么在遍历的时候直接使用迭代器遍历。

void solve() {
  int n, q;
  cin >> n >> q;
  vector<int> a(n + 2);
  unordered_set<int> st;
  int ans = 0;

  for (int i = 1; i <= q; i ++) {
    int op, x;
    cin >> op;
    if (op == 1) {
      cin >> x;
      a[x] ++;
      if (a[x] == 1) {
        st.insert(x);
      }
      ans = ans ^ a[x] ^ (a[x] - 1);
    } else {
      for (auto x : st) {
        if (a[x] == 1) st.erase(x);
        a[x] --;
        ans = ans ^ a[x] ^ (a[x] + 1);
      }
    }
    cout << ans << endl;
  }
}

A

B

C

Comments