离散数学 wu-kan

归并排序求逆序对

使用示例

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;
}

约瑟夫问题

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_heappop_heap用法完全相同,实现的是大根堆。

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$。

矩形面积并、矩形面积交、矩形周长并(线段树、扫描线总结)

详见这篇博文