大黄的博客

前言：昨天不小心玩嗨了，不想更新，坚持了快两个星期的好习惯就这样没了，我对自己真的好失望啊。 言归正传，今日复习了KMP算法，一种解决主串的模式定位问题，比如解决一个主串中是否有另外一个副串。 概述:kmp算法主要分为两个部分:1.预处理next数组，2.匹配主子串 预处理next数组kmp与暴力最大的不同在于kmp会根据之前匹配的数据进行处理，以便后面的匹配。 kmp预处理next数组原理上是记录相同的前后缀，并用next数组记录前缀（遍历的时候指针是在后缀） 而自己跟自己匹配就是找相同前后缀 123456789for(int i=2,j=0;i<=lb;i++){ while(j&&b[i]!=b[j+1]){ j=ne[j]; } if(b[i]==b[j+1]){ j++; } ne[i]=j;} 匹配主子串让主子串进行匹配，如果主串某一位置不匹配子串某一位置，子串从后缀跳到前缀（因为不匹配的前面所以的部分子串与主串相同） 如果子串走到了子 ...

前言：今日刷题发现蓝桥杯好多dp问题。 刚好刷到了一道01背包问题，简单地AC后，将全部的背包问题复习了一下 接下来让我浅浅地分享一下背包问题家族 概述：背包问题一共有三大类:01背包、完全背包、多重背包。 01背包：01背包问题是比较简单的，简单来说就是每种物品只能选一次，在有限的体积下选取价值最大的。之所以称之为01背包问题，是因为在只有二进制的计算机中0常常表示否，也就是拒绝，1恰巧相反。01背包常见的模板如下 1234for(int i=1;i<=n;i++){ for(int j=m;j>=v[i];j--){ dp[j]=max(dp[j],dp[j-v[i]]+w[i]); } 完全背包:完全背包与01背包的不同在于完全背包的每种物品有无数件，只要空间足够可以无限取。完全背包常见的模板如下 12345for(int i=1;i<=n;i++){ for(int j=v[i];j<=v;j++){ dp[j]=max(dp[j],dp[j-v[i]]+w[ ...

前言:这段时间刚复习完dfs，然后在洛谷上用模板暴力解决了一道N皇后问题。 而当我想继续将N皇后问题一网打尽时，有一道N皇后问题直接让我TLE，让我这个蒟蒻不能AC这道题目。 而这道题恰好克制了朴素的dfs，也就是需要优化dfs。本蒟蒻花了好长时间看了代码终于弄懂了，也就是运用位运算优化了dfs 接下来让我来分享一下位运算这个常用的小算法。 概述：下面介绍两个常用的位运算的函数（其实也不能称之为函数），都是针对为了表示二进制的数 求n的第k为数字：1n>>k&1; 返回n的第一位1二进制数:123int lowbit(x){ return x&-x;} OK简单地介绍了一下位运算，接下来用实战来领悟得更透彻一些 实战题目：还是N皇后正如题目所说，这题是著名的N皇后问题。第一行有一个N。接下来有N行N列描述一个棋盘，“*”表示可放“.”表示不可放。输出方案数 位运算代码实现：1234567891011121314151617181920212223242526272829303132333435#include<bits/std ...

前言:今日浅浅地玩了一下刺客信条奥赛德，总结还不错。不闹了，让我来介绍一下今天的主角并查集 $ 概述:并查集还是很神奇的，常常地用在处理两个集合问题，例如两集合的关系。 并查集有三大核心步骤–初始化、寻找根部、合并，可以当成解题模板使用 初始化即先将每一个元素的祖宗设为自己。 12for(int i;i<=n;i++)f[i]=i; 寻找根部，找到该元素的祖宗。 123int find(int x)if(f[x]==x)return x ;return f[x]=find(f[x]);//这一步为路径压缩，使得每一个元素都指向该集合的祖宗。 合并就是将两个元素或者两个集合进行合并，将一方的根节点连接到另一方的根节点，进行认祖归宗。 1f[find(a)]=find(b); 简单地介绍了一下并查集，现在我们开始实战环节。 实战题目：并查集如题，现在有一个并查集，你需要完成合并和查询操作。 第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。 接下来 M 行，每行包含三个整数 Z_i,X_i,Y_i 。 当 Z_i=1 时，将 X_i 与 Y_i 所在的集合合并。 ...

前言:今日打只狼打得吐血了，直接把它给卸载了，然后狠狠地复习了一下深度优先的算法、 so现在让我来分享一下深度优先搜索也就是dfs 概述:深度优先搜索可以理解为一个栈，一直遍历一条路径，直至终点才将这个栈释放，再用栈存储其他路径。 同时该算法和bfs（广度优先搜索）一样只能用于权重一样的题目中，而出现只有大小不一的正权边优先使用Dijksra，含有负权边使用bell ford。 当dfs到达一条终点后它便会回溯，找其他的路径，不断地比较，找到最优解。但值得注意的是深度优先搜素不具有最短性 只有广度优先搜索才具有最短性（即访问最近的点才能具有最短性）。现在让我用例题了解一下深度优先搜索的搜索方式以及回溯过程 #实践: 题目：迷宫给定一个 N×M 方格的迷宫，迷宫里有 T 处障碍，障碍处不可通过。 在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。 给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。 代码实现:123456789101112131415161718192021222324252627282930313233343 ...

前言:今日温习了前段时间学习的Dijkstra算法我在复习这个算法的时候，常常因为没有初始化或者条件判断而错误。 现在让我来浅谈一下我对该算法的理解 概述：该算法常常应用在处理单源最短路问题，具体的数学证明以及原理可以查百度。 大致是通过不断迭代找到当前最短路径，再通过该最短路径往后延伸，找到到终点的最短路径。 常见的Dijkstra算法分为朴素版以及堆优化版，前者的时间复杂度为O(N*N),后者的时间复杂度为O(MlogN)，其中N为点的个数，M为边的个数 朴素版用来处理稠密图，稠密图用邻接矩阵存储图，堆优化版用来处理稀疏图，稀疏图用邻接表存储图。 实践题目:租用游艇长江游艇俱乐部在长江上设置了 n 个游艇出租站 1,2,……,n。游客可在这些游艇出租站租用游艇，并 在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为 r(i,j)（1<=i<=j）。 试设计一个算法，计算出从游艇出租站1到游艇出租站n所需的最少租金。 解法一：朴素版Dijkstra123456789101112131415161718192021222324252627282930 ...

前言：昨日学习状态压缩dp学的我快疯掉了，第一次接触状压dp雀氏第一时间很难接受。 so写一篇博客加以总结 概述：状态压缩不同于线性dp区间dp等，经常用二进制数表示某一种状态。 下面就让两道题带你了解状压dp的魅力。 实践:题目一：蒙德里安的梦想求把 NM的棋盘分割成若干12的长方形，有多少种方案 代码实现：1234567891011121314151617181920212223242526272829303132333435363738#include<bits/stdc++.h>using namespace std;const int N=12,M=1<<N;long long dp[N][M];//建立动态规划数组bool st[M];int main(){ int n,m; while(cin>>n>>m,n|m){//读入数据 for(int i=0;i<1<<n;i++){ st[i]=true;//先初始化该二进制是否合法， ...

前言：好几个星期前学的，逐渐淡忘了，今日再次遇见，专门写一篇博客介绍很好用的一个算法–差分 概述:差分算法适用于区间加减一个数，是前缀和的逆运算，二者经常出现在同一题目。 同时差分和前缀和一样分为一维差分与二维差分，下面将用题目带大家了解差分 实践:一维差分一维差分核心公式 12a[l]+=w;//注意是对差分数组进行操作a[r+1]-=w; 题目:小明的彩灯小明拥有N个彩灯，第i个彩灯的初始亮度为ai。 小明将进行Q次操作，每次操作可选择一段区间，并使区间内彩灯的亮度+x（x可能为负数）。 求Q次操作后每一个彩灯的亮度（若彩灯亮度为负数则输出为0） 代码实现: 差分+前缀和123456789101112131415161718192021222324252627282930#include<bits/stdc++.h>using namespace std;const int N=1e5;int s[N],a[N];void insert(int l,int r,int w)//进行差分，使得区间加减w{ a[l]+=w; a[r+1]-=w;&# ...

前言：今日之所学区间dp，归一总结 概述：所谓区间dp，指在一段区间上进行动态规划，一般做法是由长度较小的区间往长度较大的区间进行递推，最终得到整个区间的答案，而边界就是长度为1以及2的区间。区间dp常见的转移方程如下： 1dp(i,j) = min{dp(i,k-1) + dp(k,j)} + w(i,j) (i < k <= j) 实践题目：石子合并 在一个操场摆放 N堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 2 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。试设计出一个算法,计算出将 N堆石子合并成 1堆的最小得分 解法：12345678910111213141516171819202122#include<bits/stdc++.h>using namespace std;const int N=105;int dp[N][N],s[N];int main(){ int n; cin>>n; for(int i=1;i<=n;i++){cin& ...

前言：今日所学知识点–线性dp在此进行归纳和总结，以及分享题解 概述：线性动态规划，是较常见的一类动态规划问题，其是在线性结构上进行状态转移，这类问题不像背包问题、区间DP等有固定的模板。 线性动态规划的目标函数为特定变量的线性函数，约束是这些变量的线性不等式或等式，目的是求目标函数的最大值或最小值。 因此，除了少量问题有固定的模板外，大部分都要根据实际问题来推导得出答案。 实践题目一：数学三角形给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。 解法：自顶向下dp123456789101112131415161718#include<bits/stdc++.h>using namespace std;const int N=1e3+10;int dp[N][N],w[N][N];int main(){ int n; ...