听课部分:(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 思路:无