递归笔记

例1：NC15173 The Biggest Water Problem

例2：NC15979 小q的数列

例3：辗转相除法求最大公约数

证明：

设gcd(a,b) = gcd(b,a-b) = d

(设d是a,b的最大公约数）

a = k1 * d

b = k2 * d

且k1,k2均为整数

a - b = k1 * d - k2 * d = (k1 - k2) * d

d是a-b的因数

d是b和a-b的因数

上述证明d是公因数，下述证明最大

反证：设b和a-b有一个比d大的公因数为e

b = k3 * e

a-b = k4 * e

相加得：a = (k3 + k4)*e

e也是a的因子，也是a,b公因子

此时e才是最大公因子

假设不成立，得证

int gcd(a, b)
{
  if (b ==0) return a;
  return gcd(b, a % b);
}

例4：归并排序&快速排序

三种O(n ^ 2)的排序：冒泡、选择、插入

三种不基于比较的排序：桶、基数、计数

桶：统计每个数字出现次数

计数：在桶的基础上做前缀和——可以知道这个数排第几位

基数：数据范围太大，桶不好开

先按个位排，再按十位排

归并排序：每次把待排序列区间一分为二，将两个子区间排序，然后将两个已经排好序的序列合并（双指针）

模板：

#include<bits/stdc++.h>
using namespace std;
int a[1000], n;
int b[1000];

void hebin(int l, int mid, int r)
{
	int p = 1, q = mid + 1;
	for (int i = 1; i <= r; i++)
	{
		if ((q > r) || (p <= mid && a[p] <= a[q]))
		{
			b[i] = a[p++];
		}
		else b[i] = a[q++];
	}
	for (int i = 1; i <= r; i++)
		a[i] = b[i];
}

void merge_sort(int l, int r)
{
	if (l == r) return;
	int mid = (l + r) / 2;
	merge_sort(l, mid);
	merge_sort(mid + 1, r);
	hebin(l, mid, r);
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
	}
	merge_sort(1, n);
	for (int i = 1; i <= n; i++)
	{
		printf("%d ", a[i]);
	}

变形1：求逆序对个数

给你一个序列，求出这个序列的逆序对个数

逆序对：对于一个包含N个非负整数的数组A[1...n]，如果有i < j, 且A[i] > A[j] ，则称(A[i],A[j])为数组A中的一个逆序对。

注意到：逆序对个数等于冒泡排序的交换次数

排序本质是消灭逆序对的过程

else
{
  b[i] = a[q++]
  cnt += mid - p + 1;
 }

快速排序：选择一个基准，将小于基准的放在基准左边，大于基准的放在基准右边，然后对基准左右都继续执行如上操作直到全部有序。

void quick_sort(int l, int r)
{
	int i = l, j = r;
	int mid = (l + r) / 2;
	int x = a[mid];
	while (i <= j)
	{
		while (a[i] < x) i++;
		while (a[j] > x) j--;
		if (i <= j)
		{
			swap(a[i], a[j]);
			i++; j--;
		}
	}
	if (l < j) quick_sort(l, j);
	if (i < r) quick_sort(i, r);
}

变形2：NC 207028 求一个序列的第k小数

利用快排的思路

int finding(int l, int r, int k)
{
	if (l == r) return a[l];
	int i = l, j = r;
	int mid = (l + r) / 2;
	int x = a[mid];
	while (i <= j)
	{
		while (a[i] < x) i++;
		while (a[j] > x) j--;
		if (i <= j)
		{
			swap(a[i], a[j]);
			i++; j--;
		}
	}
	if (k <= j) return finding(l, j, k);
	else if (i <= k) return finding(i, r, k);
	else return a[k];
}

例5：汉诺塔问题