听课部分：(0:30-3:30)

一、递归

定义：一个函数在执行时再次调用函数“本身”（逻辑相同，但使用了不同的空间去执行）

例1：NC15173 The Biggest Water Problem

给你一个数，让他进行巴啦啦能量，沙鲁沙鲁，小魔仙大变身，如果进行变身的数不满足条件的话，就继续让他变身。。。直到满足条件为止。

 

巴啦啦能量，沙鲁沙鲁，小魔仙大变身：对于一个数，把他所有位上的数字进行加和，得到新的数。

 

如果这个数字是个位数的话，那么他就满足条件。 思路：无 例2：NC15979 小q的数列
小q最近迷上了各种好玩的数列，这天，他发现了一个有趣的数列，其递推公式如下：
f[0]=0 f[1]=1;
f[i]=f[i/2]+f[i%2];(i>=2)
现在，他想考考你，问：给你一个n，代表数列的第n项，你能不能马上说出f[n]的值是多少，以及f[n]所代表的值第一次出现在数列的哪一项中？（这里的意思是：可以发现这个数列里某几项的值是可能相等的，则存在这样一个关系f[n'] = f[n] = f[x/2]+f[x%2] = f[x]...（n'<n<x） 他们的值都相等，这里需要你输出最小的那个n'的值)(n<10^18) 思路：无 例3：辗转相除法求最大公约数 辗转相除法又叫欧几里得算法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a%b) 证明该式成立 证：设d是a，b的最大公约数，a=k1d，b=k2d（k1，k2均为整数） a-b=k1d-k2d=(k1-k2)d，d是a-b的因数 所以d是b和a-b的因数 又设b和a-b存在比d大的公因数为t b=k3t，a-b=k4t 则 a=(k3+k4)t t也是a的因子，也就是说出现了比d大的ab的公因子，与假设矛盾 故d就是b和a-b的最大公约数 代码： int gcd(int a,int b) { 　　if(b==0) return a;
　　return gcd(b,a%b);
} 例4：归并排序&快速排序 三种O(n^2)的排序：冒泡、选择、插入 三种不基于比较的排序：桶、基数（按位排序的桶）、计数（有前缀和的桶） 归并排序：每次把待排序区间一分为二，将两个子区间排序，然后将两个已经排好序的序列合并 复杂度：O(nlogn)

 1 void mymerge(int l, int mid, int r)
 2 {
 3     int p = l, q = mid + 1;
 4     for (int i = l; i <= r; ++i)
 5     {
 6         if ((q > r) || (p < mid && arr[p] <= arr[q]))
 7             b[i] = arr[p++];
 8         else
 9             b[i] = arr[q++];
10     }
11     for (int i = l; i <= r; ++i)
12         arr[i] = b[i];
13 }
14 void merge_sort(int l, int r)
15 {
16     if (l == r)
17         return;
18     int mid = (l + r) / 2;
19     merge_sort(l, mid);
20     merge_sort(mid + 1, r);
21     mymerge(l, mid, r);
22 }

 

变形1：求逆序对的个数

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

逆序对：对于一个包含N个非负整数的数组A[1..n]，如果有i < j，且

A[i] > A[j]，则称(A[i],A[j])为数组A中的一个逆序对

思路1：暴力双循环（n^2）

思路2：记录冒泡排序的交换次数（n^2）

思路3：记录相对顺序调整时，会产生多少逆序对（nlogn）（使用下标进行计算）

将cnt+=min-p+1的计算加入上面代码的else中即可。

本题揭示了要会手写排序而不能只会sort的意义

快速排序：选择一个基准，将小于基准的放在基准左边，大于基准的放在基准右边，然后对基准左右都继续执行如上操作直到全部有序。 快排的最坏情况会退化到冒泡的复杂度

 1 void quick_sort(int l, int r)
 2 {
 3     int i = l, j = r;
 4     int mid = (l + r) / 2;
 5     int x = arr[mid];
 6     while (i <= j)
 7     {
 8         while (arr[i] < x)
 9             ++i;
10         while (arr[j] > x)
11             --j;
12         if (i <= j)
13         {
14             swap(arr[i], arr[j]);
15             ++i;
16             --j;
17         }
18     }
19     if (l < j)
20         quick_sort(l, j);
21     if (i < r)
22         quick_sort(i, r);
23 }

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

思路：每次分配完成时，都丢掉一半的序列

例5：汉诺塔问题 前n-1个 A--B 第n个 A--C 前n-1个 B--C 思路：无