OI Tricks

记录一些见到的感觉很有用的 tricks。

• 平均值

对于和的平均值（形式化地，\(\bar a = \dfrac{\sum_{i = 1} ^ n a_i}{n}\)），可以转化成 \(a_i - \bar a\) 然后和 \(0\) 乱搞。

• 异或哈希
  就是 xor hash，可以在 CF 上找到详细教程：Link。

  主要用于只关心元素集而不关心顺序的时候。（可能吧？毕竟理解还不是很深。）

  推荐生成随机数的写法：

  unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
  mt19937 myrand(seed);
  uniform_int_distribution<long long> dist(0, LONG_LONG_MAX);
  

  • solution

• 中位数

  二分中位数 \(mid\)，然后把 \(\geq mid\) 的与 \(< mid\) 的重新赋值，再做操作。

• 回退背包