算法基石：手撕离散化、递归与分治

目录1.离散化例题1火烧赤壁例题2贴海报2.递归初阶例题1汉诺塔问题例题2FBI树3.分治例题1逆序对例题2求第 k 小的数1.离散化当题目中数据范围很大但是数据的总量不是很大并且我们需要用数据的值来映射数组下标时我们就可以用离散化的思想先预先处理一下所有的数据使得每一个数据都映射成一个范围较小的值。比如[9, 99, 999, 9999]离散之后就变成了[1, 2, 3, 4]。这里提供两个离散化模板:模板一//离散化方式一:排序去重二分查找离散化后的值 #includeiostream #includealgorithm using namespace std; const int N1e510; int n; int a[N];//原始数据 int pos;//记录离散化数组中元素的个数 int disc[N];//离散化需要的数组 //二分查找离散化之后的值其实就是排序之后的下标 int find(int x) { int l1,rpos;//注意查找的区间 while(lr) { int mid(lr)1; if(disc[mid]x) rmid; else lmid1; } return l; } int main() { cinn; for(int i1;in;i) { cina[i]; disc[i]a[i]; } sort(disc1,discn1); posunique(disc1,discn1)-disc-1; for(int i1;in;i) { cout离散化之后是: find(a[i])endl; } return 0; }模板二//离散化方式二:排序STL //本质是和方式一一样的只不过借助了STL去重以及查找更方便 #includeiostream #includeunordered_map #includealgorithm using namespace std; const int N1e510; int n; int a[N]; //原始数据 int tmp[N]; //用来排序的数组 int cnt; unordered_mapint,int id; //记录离散化之后的值 int main() { cinn; for(int i1;in;i) { int x;cinx; a[i]x; tmp[i]x; //数据放进离散化数组中 } //离散化:排序放进哈希表中 sort(tmp1,tmp1n); for(int i1;in;i) { if(id.count(tmp[i]))continue; //如果已经存过这个数不做处理 cnt; //这个数映射之后的值 id[tmp[i]]cnt; //放进哈希表中 } //找到离散化之后的值 for(int i1;in;i) { int xa[i]; coutx离散化之后是id[a[i]]endl; } }注意离散化是一种思想模板不需要背根据算法思想就可以实现而且实现离散化的方式也可以在上述模板的基础上修改。离散化在初学的时候比较绕需要注意不把离散前和离散后的数搞混也可以借助画图的方式来分析以免混乱。例题1火烧赤壁题目要求燃烧位置长度之和同时给出了n条起火信息且有[起点, 终点)有一个简单非办法就是创建一个数组根据起火信息来对着火的下标进行标记。但是有重复信息的存在我们标记的这一动作可能会超时同时观察数据范围发现根本无法创建出一个能够容纳所有数的数组。回顾之前的内容我们可以发现差分可以帮助我们快速完成标记这一动作而为了能够创建出不超出范围的数组我们需要使用离散化来达到缩小范围的目的。那么思路就出来了先把数据离散化后进行差分。先用两个数组存储一个区间的两端把数据全都存入一个离散化数组进行离散化差分的时候通过离散前的数组取出离散后的两端进行操作最后还原差分数组根据还原出来的差分数组来计算长度。代码如下#include iostream #include unordered_map #include algorithm using namespace std; const int N 2e4 10; int n; // a存左端点b存右端点 int a[N], b[N]; // 表示离散化数组最后一个元素下标 int pos; // 存两个端点需要双倍空间 int disc[N * 2]; // 差分数组 int f[N * 2]; // 离散前, 离散后 unordered_mapint, int id; int main() { cin n; for(int i 1; i n; i) { // 读入数据 cin a[i] b[i]; // 存入离散化数组 disc[pos] a[i], disc[pos] b[i]; } // 对离散化数组进行排序去重 sort(disc 1, disc 1 pos); pos unique(disc 1, disc 1 pos) - (disc 1); // 用map离散化 for(int i 1; i pos; i) { // 当disc[i]不存在时为插入作用 // 离散前为disc[i]离散后为i id[disc[i]] i; } // 差分 for(int i 1; i n; i) { // 取出左右端点对应的离散后端点 int l id[a[i]], r id[b[i]]; f[l], f[r]--; } // 还原差分 for(int i 1; i pos; i) f[i] f[i - 1]; // 计算结果 int ret 0; for(int i 1; i pos; i) { int j i; // 不为0且不是pos下一个位置的时候 while(f[j] 0 j pos) j; // i 和 j 为离散后的数 // 其恰好为离散数组中离散前元素的下标 ret disc[j] - disc[i]; i j; } cout ret endl; return 0; }例题2贴海报题目要求墙上可见的海报个数依据题意我们可以直接模拟但是区间的长度很大很有可能会超时但是区间个数却很少所以我们依旧离散化处理区间的端点值然后在离散化的基础上进行模拟覆盖。但是我们在离散化区间的时候一定要小心因为我们的离散化操作会把区间缩小从而丢失某些点最终导致结果出现问题。如下例子在离散前墙上可见三张海报但是离散之后墙上只剩下两张海报为了消除这种区间缩小带来的问题我们可以在存入左右端点的时候多存入一个数来扩大区间。又因为最多只有1000张海报在缩小范围之后通过遍历数组的方式在墙数组储存海报信息也不会超时最后只需要遍历墙数组就能知道墙上有多少张海报了。代码如下#include iostream #include algorithm #include unordered_map using namespace std; const int N 1e7 10; int n, m; int a[N], b[N]; unordered_mapint, int id; int pos; int disc[4 * N]; int w[4 * N]; // 墙 // 统计是否被记录过 bool ret[4 * N]; int main() { cin n m; for(int i 1; i m; i) { cin a[i] b[i]; // 在存入离散化数组的时候多加一个数 disc[pos] a[i], disc[pos] a[i] 1; disc[pos] b[i], disc[pos] b[i] 1; } // 排序去重 sort(disc 1, disc 1 pos); pos unique(disc 1, disc 1 pos) - (disc 1); for(int i 1; i pos; i) { id[disc[i]] i; } for(int i 1; i m; i) { // 把r-l范围的元素修改成第i个海报的编号 int l id[a[i]], r id[b[i]]; while(r l) w[l] i; } int sum 0; for(int i 1; i pos; i) { // 墙上没有海报或记录过时跳过 if(!w[i] || ret[w[i]]) continue; sum; ret[w[i]] true; } cout sum endl; return 0; }2.递归初阶递归实际上就是函数自己调用自己。例题1汉诺塔问题这道题给出了三个杆而我们要做的就是经过最少的步骤把从大到小码在a杆的盘子经过c杆最后移到b杆上。先从简单的角度思考问题我们先来看看只有一个盘子的情况一个盘子直接移动就可接下来是两个盘子的情况需要借助c来放1然后2放到b上此时问题就转变为只有一个盘子的情况接下来看看三个盘子的情况。这时候就可以看出很明显的重复了在只有三个盘的时候只要想办法把3挪到了b上那这个问题就会降级为只有两个盘的问题并且当2也放在b上时降级到一个盘的问题最终解决问题其中不同的只有借助哪个杆把盘垒到哪个杆上。所以我们要想方设法把a上的n-1个盘移到c上再把a上的第n个盘移到b上最后把c上的盘移到b上其中有的大量重复过程。对于这种重复的过程的问题就可以通过递归来解决问题递归函数虽然看起来不好写因为涉及到展开的问题。但是在这里我们不考虑展开我们只是相信递归函数有这个能力解决问题那么就能写出递归函数。代码如下#include iostream using namespace std; int n; char a, b, c; // 函数的作用是x上的n个盘子借助y放到z上 void dfs(int n, char x, char y, char z) { // 出口没有盘子的时候结束 if(n 0) return; // 相信递归函数的作用 // 第一步把n-1个x上的盘子借助z放在y dfs(n - 1, x, z, y); // 第二步还剩最后一个盘子在x上接下来输出挪到z上 printf(%c-%d-%c\n, x, n, z); // 第三步把剩下的n-1个y上的盘子借助x放在z上 dfs(n - 1, y, x, z); } int main() { cin n a b c; dfs(n, a, c, b); return 0; }例题2FBI树这道题定义了三种字符串而我们要做的就是不断二分字符串来构建一颗二叉树同时后序遍历这棵树按字符串的种类来打印对应的字符。二叉树的后序就是按照 左子树 右子树 根 的顺序来遍历数组只需要递归就能解决而问题就在于如何来判断字符串类型呢我们可以用前缀和数组来储存字符串中的 0 和 1 这样我们就可以知道任意一段区间内的和是多少如果和为 0 说明为B串如果和等于区间内的元素个数说明为I串否则就为F串。接下来我们需要考虑的就是二分区间求串的类型了当我们采用如下方式计算区间内的串时当二分至只剩下一个元素时无论是 mid (right left) / 2 还是 mid (right left 1) / 2都会有一个区间不存在或者是只剩下一个元素陷入死循环。bfs(left, mid); bfs(mid 1, right);所以我们需要合适的判断来保证函数能够顺利结束一个判断区间合法一个则是阻止死循环。所以我们有如下代码#include iostream using namespace std; const int N 11; int n; // 前缀和数组 int f[1 N]; void bfs(int left, int right) { // 区间不存在的时候结束 if(left right) return; char ch; // 求区间元素之和 int sum f[right] - f[left - 1]; if(sum 0) ch B; else if(sum right - left 1) ch I; else ch F; // 如果right left那么直接输出结束 if(left right) { cout ch; return; } // 二分 int mid (right left) / 2; // 左子树 bfs(left, mid); // 右子树 bfs(mid 1, right); // 根 cout ch; } int main() { cin n; n 1 n; for(int i 1; i n; i) { char ch; cin ch; // 构造前缀和 if(ch 1) f[i] 1; f[i] f[i - 1]; } bfs(1, n); return 0; }3.分治分治就是分而治之就是把一个复杂的问题分成两个或者更多相同或相似的子问题直到最后子问题可以简单的直接求解原问题的解即子问题的解的合并。归并排序就是采用分治的思想实现的。例题1逆序对题目要求指定序列的逆序对数既然要分治我们把一个序列分成左右两个部分分区来求逆序对这样逆序数对 左边序列的逆序对 右边序列的逆序对 右边序列在左边序列产生的逆序对如下例子当我们在算右边的数在前面产生的逆序对时注意到只要左右两边的逆序对已经计算完毕左边和右边的数不管是什么样的排列右边的数的逆序对就是不变的这就是我们可以优化的部分。当数据由无序变为有序时逆序对就会更容易得到。那么在计算最后一部分的逆序对时我们可以将左右部分排升序仍用上面示例的序列认为示例中的序列为一个更长的序列中的某一步分治然后有如下操作但是这么循环肯定会有问题因为在这种条件下的循环为while(cur1 mid || cur2 right)循环结束时必定有一边没有遍历完。现在分类讨论当 cur1 走到mid 1时说明a[cur2]始终是大的那个元素所以cur2及后面的元素的逆序对皆为0当cur2走到right 1时已经没有要求逆序对的元素。所以理论上来说不需要对其进行处理但是我们先把处理放一放先来看看有序序列的得到。这下知道了如何求逆序对那么问题来了如何得到有序序列呢实际上我们在进行上述操作的时候可以发现我们可以利用cur1和cur2和归并排序一样挑出小的那个元素放入一个辅助数组当逆序对找完之时就将辅助数组拷贝回原数组。所以我们引入一个辅助数组当在计算的时候存入元素并且要求两个cur走到结束来保证所有元素存入最后进行拷贝。而这样一个过程实际上是一个重复的过程所以我们可以用递归来实现。但是左右序列的逆序对又怎么求呢实际上根本不用求我们会调用递归函数来求同时我们坚信递归函数可以帮我们得到逆序对即可。有如下代码#include iostream using namespace std; typedef long long LL; const int N 5e5 10; int n; // 原数组 辅助数组 int a[N], t[N]; LL merge(int left, int right) { // 出口不可能区间时返回 if(left right) return 0; LL ret 0; int mid (right left) / 2; // 相信merge会帮你把左右区间的逆序对算出来的 ret merge(left, mid); ret merge(mid 1, right); // 分治 int cur1 left, cur2 mid 1, i left; while(cur1 mid cur2 right) { // 非逆序的情况下拷贝cur1 if(a[cur1] a[cur2]) t[i] a[cur1]; else { ret mid - cur1 1; // 拷贝cur2 t[i] a[cur2]; } } // 处理未循环的情况 while(cur1 mid) t[i] a[cur1]; while(cur2 right) t[i] a[cur2]; // 拷贝回原数组 for(int j left; j i; j) { a[j] t[j]; } return ret; } int main() { cin n; for(int i 1; i n; i) { cin a[i]; } cout merge(1, n) endl; return 0; }例题2求第 k 小的数这道题吗要求第k小的数但是却用第0来表示最小的数所以如果我们储存元素从数组的下标为1的位置开始储存那么我们需要把第k小的数中k使其与用第1来表示的数进行匹配。接下来就是分治我们要按照什么样的规则来划分数组在之前学过的快速排序我们知道如果排升序选中一个key如果在排好的序列中key在第 i 小的位置那么进行一趟快排key就会在第 i 小的位置而key的左边全都是小于key的数右边全是大于k的数。而下一趟则会从key的两边进行刚好分为了三个部分[left, i - 1] [i, i n] [i n 1, right]key可能会有多个。我们可以类似操作来进行快速选择。这下我们就知道如何进行分治了接下来我们来模拟一下过程如果3有多个则[L 1, R - 1] 为 3 的范围。接下来我们不是对左右两个区间进行处理而是判断k会在哪个区间范围内从而选择需要处理的区间如下有一点需要说的是该道题目如果用cin、cout进行输入输出会超时所以这里我们需要用scanf、printf来进行输入输出。下面是代码的实现#include iostream #include ctime using namespace std; const int N 5e6 10; int n, k; int a[N]; // 获得随机key int get_random(int left, int right) { return a[rand() % (right - left 1) left]; } int quick_select(int left, int right) { // 只有一个元素说明就是要找的 if(left right) return a[left]; // 相当于key int p get_random(left, right); int x left - 1, y right 1, i left; while(i y) { if(a[i] p) i; else if(a[i] p) swap(a[x], a[i]); else swap(a[--y], a[i]); } // 划分三个区间 int c1 x, c2 y- 1, c3 right; if(k c1) return quick_select(left, x); else if(k c2) return p; else return quick_select(y, right); } int main() { // 获得随机种子 srand(time(0)); scanf(%d%d, n, k); // 把第0小变为第1小 k; for(int i 1; i n; i) { scanf(%d, a[i]); } printf(%d, quick_select(1, n)); return 0; }