CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
归并排序求逆序对
1
2
3
4
5
6
7
8
9
10
ll merge_sort(ll *b, ll *e) //int存答案会爆
{
if (e - b < 2)
return 0;
ll *m = b + (e - b) / 2, ans = merge_sort(b, m) + merge_sort(m, e);
for (ll *i = b, *j = m; i < m && j < e; ++i)
for (; j < e && *j < *i; ++j)
ans += m - i;
return inplace_merge(b, m, e), ans;
}
约瑟夫问题
1
2
3
4
5
6
7
8
9
ll josephus(ll n, ll k) //编号0~n-1，每k个出列，时间复杂度O(min(n,k))
{
if (n < 3)
return k % n;
if (n < k)
return (Josephus(n - 1, k) + k) % n;
ll ret = Josephus(n - n / k, k) - n % k;
return ret < 0 ? ret + n : ret + ret / (k - 1);
}
堆的操作
和 STL 的函数push_heap、pop_heap用法完全相同，实现的是大根堆。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ll pushHeap(ll *b, ll *e)
{
ll tmp = *--e;
for (int i = e - b, p;; b[i] = b[p], i = p)
if (i <= 0 || b[p = (i - 1) / 2] >= tmp)
return b[i] = tmp;
}
ll popHeap(ll *b, ll *e)
{
ll tmp = b[0];
for (int i = 0, siz = --e - b, ch;; b[i] = b[ch], i = ch)
{
if (ch = i * 2 + 1, ch + 1 < siz && b[ch] < b[ch + 1])
++ch;
if (i >= siz / 2 || b[siz] >= b[ch])
return b[i] = b[siz], b[siz] = tmp;
}
}
蔡勒公式
$w=(\lfloor\frac{c}{4}\rfloor-2c+y+\lfloor\frac{y}{4}\rfloor+\lfloor\frac{13(m+1)}{5}\rfloor+d-1)\mod7$
w：$0,1,\dots,6$对应周日，周一，$\dots$，周六
c：世纪减 1（即年份前两位数）。
y：年份后两位数。
m：月（$3\leq m\leq14$，即在蔡勒公式中，1、2 月要看作上一年的 13、14 月来计算）。
d：日。
曼哈顿距离的变换
$\mid x_1−x_2\mid +\mid y_1−y_2\mid=\max (\mid (x_1 + y_1)−(x_2 + y_2)\mid ,\mid (x_1 −y_1)−(x_2 −y_2)\mid )$
皮克定理
顶点坐标均是整点（或说正方形格点）的简单多边形中，面积 S 和内部格点数目 n、边上格点数目 m 的满足关系$S=n+\frac{m}{2}-1$。
矩形面积并、矩形面积交、矩形周长并（线段树、扫描线总结）
详见这篇博文。