愚蠢错误集合

离谱的错误集合，希望不要重蹈覆辙。

最近更新：2022-03-04

语法

对 C++ 语法特性不了解所致的错误。

自定义 hash 的格式

class custom_hash {
 public:
  std::size_t operator()(const type& x) const { // 注意没有 static，且返回值为 std::size_t
    // do something...
  }
};

2022-03-04: 因为这个 CE 了半小时。

代码编写错误

在伪代码不会出现而在真实代码会出现的错误。

`std::size_t` 的倒序枚举

1
2
3

for (std::size_t i = vec.size() - 1; i >= 0; --i) {
  // do something...
}

这段代码当 vec.size() == 0 时会出问题，因为 std::size_t 是无符号整型。

2022-03-18: 因为这个调了 15 分钟。

`std::multiset::erase` 传入值的行为

std::multiset<int> mset;
mset.insert(4);
mset.insert(4);
mset.erase(4); // 这一行实际上会清除所有值为 4 的元素

当传入值后，std::multiset::erase 会将所有值为 val 的都删去，时间复杂度为 $O(\log |S|+cnt)$，其中 $cnt$ 为删除的数的个数。

平衡树的旋转操作

void func() {
	// ...
  tree[u].fa = x;
  tree[x].son[k] = u; // 注意父子双方都需要被更新
  // ...
 	tree[u].fa = tree[v].fa;
  if (tree[tree[v].fa]) { tree[tree[v].fa].son[k] = u; } // 注意不要修改 tree[0]
  // ...
  tree[root] = 0; // 注意需要保证 tree[root] = 0
  return;
}

2022-05-06: WA 了 45 分钟。

不符直觉错误

与预期表现不符的错误。

动态开点的 size 顺序

int build(int l, int r) {
  if (l == r) { /* do something...*/ }
  int mid = (l + r) / 2;
  tree[sze] = {build(l, mid), build(mid + 1, r), 0};
  return sze++;
}

注意上面的赋值语句实际上将值赋给了左儿子（因为递归的时候 sze 并没有改变）。

一个解决方案是开一个临时变量存储。

2022-04-22: 卡了一小会。

`std::lower_bound` 传入 non-LegacyRandomAccessIterator 的复杂度

1 2	std::set<int> set; std::lower_bound(set.begin(), set.end(), val)

std::set<>::iterator 是 LegacyForwardIterator，但是不是 LegacyRandomAccessIterator。非常遗憾，std::lower_bound 仍然能 work，但是它是用遍历的方法——

The number of comparisons performed is logarithmic in the distance between first and last (At most $\log_2(\mathrm{last} - \mathrm{first}) + O(1)$ comparisons). However, for non-LegacyRandomAccessIterators, the number of iterator increments is linear. Notably, std::set and std::multiset iterators are not random access, and so their member functions std::set::lower_bound (resp. std::multiset::lower_bound) should be preferred.

— from CppReference

2022-05-16: TLE 了好久。

强制在线下的评测结果

如果题目强制在线而在某一次询问中程序 WA，那么可能会导致下一次输入解密后内容变动，可能导致 RE/TLE/MLE 等错误。

2022-05-20: RE 但是一直找不到 RE 的地方……

Eratosthenes 筛法的变种

void sieve(int n) {
  std::memset(ispr, 0x01, sizeof(ispr));
  ispr[1] = 0;
  for (int i = 2; i * i <= n; ++i) { // here
    if (ispr[i]) {
      primes.push_back(i);
      for (int j = i * i; j <= n; j += i) {
        ispr[j] = 0;
      }
    }
  }
  return;
}

通常我们在传入 $n$ 后枚举 $i$ 仅需要到 $\lfloor\sqrt n\rfloor$，但是如果需要记录一个 prime 数组的话就不是这样。

2022-05-30: 卡了一中午不知道错在哪里。

语法