大黄的博客

前言:坚持每天更新博客，今天复习二分查找 概述:二分查找相较于普通的查找的时间复杂度更小，为O（logn）。 二分查找主要针对一段单调的区间，然后将区间分为左右两个部分，通过判断不断缩小范围直到找到答案。 模板其实模板1和模板2本质上是根据代码来区分的，而不是应用场景。如果写完之后发现是l = mid，那么在计算mid时需要加上1，否则如果写完之后发现是r = mid，那么在计算mid时不能加1。 版本一:12345678910int bsearch_1(int l, int r){ while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } return l;} 版本二12345678910int bsearch_2(int l, int r){ while (l < r) { int mid = l + ...

CF1821 A Matching代码实现123456789101112131415161718192021222324252627282930#include<iostream>#include<cstring>#include<vector>#include<algorithm>using namespace std;using LL = long long;int main(){ cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); const int pow10[] = {1, 10, 100, 1000, 10000, 100000}; int T; cin >> T; while(T--){ string s; cin >> s; if (s[0] == '0'){ cout < ...

前言:时隔两天再次写起了博客，最近学习积极性越来越低迷了。 为了我的未来，一定要变得自律起来。废话不多说，今天复习的内容是单调栈 概述:单调栈一般用于解决与下一个更大元素（有关的问题，包括以下几类： 1.寻找每个元素的下一个更大元素。2.寻找每个元素的下一个更大或相等元素。3.寻找每个元素的下一个更小元素或更小或相等元素。在这些问题中，单调栈维护一个单调递增或递减的栈，将元素依次压入栈中。对于每个新元素，我们可以在栈中弹出所有比它小的元素，并将它们的“下一个更大/小元素”设置为当前元素。 实践直接上一道牛客偏难的题目，当初没想到用单调栈解决 题目:最优屏障M国的地势高低不平，现给出一个数组代表此国家某纬度上均匀分布的N座山的海拔高度Hi，已知每座山的山顶上都有一座哨塔，若两个哨兵分别位于第i、j(i<j)座山上，当且仅当两人所在的山比两人之间所有的山都高时，这两个哨兵可以相互监视，M国的防守能力大小为相互监视的哨兵对数。H国早已对M国虎视眈眈，H国的皇帝希望黑魔法师们可以在M国的某两座山之间放置一块巨大的屏障,M国的哨兵不可通过该屏障互相监视。皇帝想让你告诉他最优的屏障放置位置， ...

前言:蓝桥杯前没有学到LCA，最后两题都用到了LCA。 无奈啊，今天补上这个 概述:LCA即在一棵树上，找到两个结点的最近祖先(祖先可能有多个)。 主要有两种算法解决，这里讲解一下倍增dp算法找到LCA。 其基本思想是通过预处理出每个节点距离2^k个祖先的信息，并利用这些信息在查询时快速跳转到两个节点的同一深度，然后再沿着祖先链进行比较，找到它们的LCA。 具体来说，倍增LCA算法分为两个步骤：预处理和查询。预处理阶段需要对整棵树进行遍历，计算出每个节点距离2^k个祖先的距离信息。查询阶段则利用这些信息，在O(logn)的时间内找到两个节点的LCA。 在预处理阶段，我们可以使用动态规划的方式，逐层计算出节点距离2^k个祖先的距离信息。具体来说，设f[i][j]表示节点i距离2^j个祖先的距离，那么有以下递推式： 12f[i][0] = fa[i]f[i][j] = f[f[i][j-1]][j-1] + f[i][j-1] 其中fa[i]表示节点i的父亲节点。可以看出，f[i][j]可以由f[i][j-1]和f[f[i][j-1]][j-1]计算得到。这也就是“倍增”的含义。通过这个递 ...

前言:好久没更新我的博客了，最近变得好懈怠了。我收回之前说的话，蓝桥杯过后有icpc等着我，算法是要继续学的。 学算法感觉成就感挺高的，虽然很难也需要天赋，但是我会继续坚持下去的，加油。 当询问一段区间的和你可能会想到前缀和处理。当修改一段区间的值或只修改数组一个值，你可能会想到差分。 那么问题便来了，我若都要进行，而且操作很多次呢，是不是前缀和的处理以及差分处理会变得十分无助且无用。 所以接下来我们将用一个新的数据结线段树解决这些问题。 概述:线段树是一种基于树形结构实现的数据结构，主要用于高效处理区间查询问题。 具体而言，线段树可以对一个固定大小的数组进行预处理，用于支持多次对其中某个区间的查询和更新操作。线段树的叶子节点对应于数组中的单个元素，而非叶子节点代表了若干个元素的区间。 在处理区间查询问题时，可以通过操作线段树上与查询区间相交的结点，并将这些结点的信息组合起来得到查询结果。在处理区间更新操作时，可以通过操作线段树上与更新区间相交的结点，并将这些结点的信息更新、传递得到更新结果。 因此，线段树主要被用于处理具有区间查询和区间更新操作的数据结构，如动态数组、序列、链表、二维 ...

前言:今天复习这个算法十分犹豫，大家都说spfa算法已死，即在比赛中容易被卡常。 但是大多数情况下用在存在负权边还是可以的，而且还能判断是否存在负权环，只能说该算法的优点远远大于缺点。 所以我是坚决不会用它的 概述:1.spfa在Bellman-Ford算法的基础上，利用队列来进行时间优化的一种可用于解决负边权判断负环的最短路算法。 2.spfa实际上就是先将起始点放入队列中，每次取出一个点，利用这个点将其周围的（与其相连的）点进行优化，如果某点有过松弛，就入队，重复这样的过程直到队列为空。但需要记录进队次数，如果一个点入队次数多于n次，即说明存在负环，则返回负环的结果。 3.判断是否存在负环时，只需要加一个数组time，来表示每个点入队的次数，当大于n时，执行关于负环的操作即可。 4.spfa时间复杂度一般为O(km)，k为一个常数，m为边的个数（当然可以创造出卡spfa的数据使其变为O(nm)），所以没有负权值的情况下优先考虑其他最短路算法。 常见的模板（这里用邻接表） 12345678910111213141516171819202122232425int spfa(){ ...

前言:蓝桥杯的时间快到了，我全心学习算法的日子快到头了，其实学习算法还是挺好玩的。 言归正传，今日浅浅地复习一下拓扑排序，还是挺容易的，只要明白其内涵便可以快速AC。 概述:拓扑排序主要用来解决有向图中的依赖解析问题。 即：对于任何有向图而言，其拓扑排序为其所有节点的一个线性排序(对于同一个有向图而言可能存在多个这样的结点排序)。该排序满足这样的条件——对于图中的任意两个结点u和v，若存在一条有向边从u指向v,则在拓扑排序u一定出现在v的前面。 这里引入一个概念——入度，即该结点被其他结点连接的数量(是从其他结点指向该节点）。 而找到入度为0的点，同时把该点连接的其他结点的边删去，同时连接的结点入度减去1， 再继续找入度点为0的点,重复该循环，直到所有的点都入度为0；注:只有有向非环图才存在拓扑排序 解决拓扑排序问题主要分为两个步骤:1.vector存图(还可以用其他方法存图，例如邻接表，邻接矩阵） 1234void cuntu(int x,int i){ in[x]++;//x的入度数加1 e[i].push_back(x);//x为i的后辈} 2.利用队列bfs ...

前言:前段时间复习了一下DFS，认为BFS不必多用，直到我认识到了BFS才具有最短性。 概述:BFS最让我喜欢的一点是它有固定的模板，也就是套路。先将初始点放进队列中，然后出列遍历每一个点，直到找到最优解，即为最短路。模板如下 1234567891011121314queue<int>q;st[1]=true;q.push(1)//从哪个点出发就先将该点放入队列中while(q.size()){ int t=q.front(); q.pop(); for(int i=h[t];i!=1;i=ne[i]){//bfs这个点的所有路径 int j=e[i]; if(!st[j]){ st[j]=true; q.push(j); } }} 实践和讲解DFS一样都从走迷宫开始 题目:迷宫这里就不继续写题目了，因为之前已经写过了，不了解的可以点击高亮的“迷宫”直接访问 1

前言:在复习hash表的时候遇到了困难，这玩意儿实在是太抽象了。 我感觉这种与数学沾染了的算法与数据结构，都会变得很抽象。 这里讲的是自己手写hash表，而不是stl库中的hash表。 主要是因为有时候引用了stl的undered_map可能会超时，所以下面来模拟一下映射与寻址。 概述:手写hash表有两种方法，这里讲的是开放寻址法。 开放寻址法先定义一个hash数组 1int h[N];//N为数据范围的2倍以上，越大映射得越好。 接下来便是开放寻址 12345678int find(int x){ int t=x(x%M+M)%M;//映射到hash数组上 while(h[t]!=-1&&h[t]!=x){//寻址的过程 if(++t==m) t=0; } return t;} 实践:接下来我们直接上一道蓝桥杯的难题以供大家理解hash表 题目:在一个二维平面上放置着 n个炸雷，第 i个炸雷 (xi,yi,ri)表示在坐标 (xi,yi)处存在一个炸雷，它的爆炸范围 ...