算法基础课(持续更新中)
算法基础课
[toc]
第一章 基础算法(一)
快速排序
1.很久没刷算法题后重新开始刷,发现了容易遗忘的一些点:
(1)const int N=多少是依据题目给出的范围去推断,比如这里快排题要求数组中数字范围是1-100000,那就写成1-100010(多开10防止爆数组),然后再接上对数组的定义int q[N],这样就可以保证开的数组位置是一定管够的。
(2)对于这种功能是处理xxx的函数通常定义为void。
(3)写代码时可以先把int main也就是有关输入、函数调用和输出的部分先写好,再去写具体函数的内容,这样可以减轻处理题目的逻辑容量。
(4)函数定义中参数写 int q[],而在 main 函数调用时只写 q:在 C++ 中,数组名 q 本质上是数组首元素的地址。在函数定义时,int q[] 仅是语法上的声明,表示该参数接收一个数组地址(等价于指针 int *q);而在调用函数时,直接写 q 即可将该地址传入。这种按址传递的方式避免了复制整个数组的巨大开销,并允许函数直接修改原数组的数据。
2.关于quick_sort与分治:
(1)分治通常就是按下面这种形式写:
1 | void function(xxx) |
(2)quick_sort具体处理逻辑部分
1 | int x=q[(l+r)>>1],i=l-1,j=r+1;//定义分界点pivot以及左右指针,-1/+1是因为每一次对i/j循环时都会先++/-- |
3.完整代码
1 |
|
归并排序
1.为什么快排是先处理再递归,而归并是先递归再处理?
归并排序采用的是“后序遍历”思想,必须先通过递归把数组切分到不能再分的单元素状态(此时自然有序),然后在回溯阶段才能将这些有序子序列合并;而快排采用的是“先序遍历”思想,先通过分区逻辑确定一个基准点的位置,再据此划分区间继续向下递归。
2.为什么归并处理边界时必须使用小于等于号?
因为在归并排序的代码逻辑中,mid 和 r 都是闭区间内真实存在的合法下标,如果不加等号,循环就会在处理到最后一个元素之前提前跳出,导致区间边界上的那个数据被遗漏在排序过程之外。如题目要求合并两个只有 1 个元素的区间,左边是 q[0](此时 mid=0),右边是 q[1](此时 r=1)。如果你写 i < mid(即 0 < 0),判断条件立刻失效,循环一次都不会执行,这两个数就永远没法被装进结果数组 tmp 里。
3.完整代码
1 |
|
4.板子
1 | void merge_sort(int q[],int l,int r) |
5.用归并排序求逆序对
(1)为什么用 long long 而不直接用 int
因为在
int 类型约
(2)为什么 res += mid - i + 1
可以理解为merge_sort在执行具体操作之前就已经是一个划分成单个数字组成的有序数列。此时左半区间是有序的,一旦发现
1 |
|
二分
整数二分
1.思路
(1)整体思路就是先考虑数组中位数值q[mid]>k再考虑q[mid]<k的判断,据此不停变换左右边界l/r的取值,最终收束得到k的左右边界取值,输出时均以左边界l为取值;
(2)需要注意的是边界一旦涉及mid-1的操作时取mid=(l+r+1)>>1要有这个+1,不然-1之后mid无法更新就会死循环;此外在跑完k的左边界并输出l后要记得更新l=0,r=n-1这个操作重新计算,不然此时数组边界已经收束就无法再计算k的右边界。
2.题目:789. 数的范围 - AcWing题库
1 |
|
3.板子
1 | bool check(int x) {/* ... */} // 检查x是否满足某种性质 |
浮点数二分
1.思路
先看题目保留n位小数,那么精度就要对应是n+2位小数(比如保留六位小数那么范围就是1e-8);然后取一个必定包含取值范围的左右边界初始值,然后正常取中点计算即可。
1 |
|
3.板子
1 | bool check(double x) {/* ... */} // 检查x是否满足某种性质 |
第一章 基础算法(二)
高精度
高精度加法
本质上是模拟人进行列竖式加法的过程,即
1.思路
(1)先加低位还是高位?
先加低位(个位)。在 main 函数里用 for(int i=a.size()-1;i>=0;i--) 把字符串反向存入了 vector,所以 A[0] 存的是个位,A[1] 存的是十位。
(2)为什么在C.push_back(t%10);用 push_back 而不是 C[i]?
因为 C 刚创建时是空的,根本没有下标 i。 在 C++ 中,vector<int> C; 初始长度为 0。如果写 C[i] = ...,程序会因为访问越界而崩溃。push_back 的作用是“动态扩容”,它会在数组末尾新开辟一个空间并把数放进去。
(3)push_back 和 size() 的适用范围
push_back: 适用于动态序列容器,最常用的是 vector、string 和 deque。
size(): 适用于几乎所有 STL 容器。包括 vector、string、list、map、set 等。
1 |
|
高精度减法
1.思路
(1)输入的处理逻辑整体与高精度加法一致,变化的在于①需要判别A和B谁大②需要处理前导0(把有效数字外高位的没用的0全部扔掉)
(2)对于判别大小的函数cmp而言,首先比较二者位数,位数大者自然大;其次位数相同的情况下,从高位依次比较具体位数的数值,数值大者自然大;最后一样大了就返回一个true;cmp返回比较时就是返回的布尔值(成立为1不成立就是0,转过弯就行)
(3)判定循环是i=A.size()-1;i>=0;i--还是i=o;i<A.size();i++取决于是从高位还是从低位算起;因为读入时采取了i=a.size()-1;i>=0;i--,则此时vector中A[0]代表低位A[n-1]代表高位,因此cmp的比较中还是要从高位算起,因此i=A.size()-1;...
(4)由于cmp已经隐含A>B,因此我们默认A位数更大,外层循环管A.size()而里面再用个B.size()管。
1 |
|
高精度乘法
1.思路
处理逻辑不难,和加减法差不多
1 |
|
高精度除法
1.思路
整体和乘法比较像,但是有三个注意的点:
(1)题目要求输出余数r,因此在写自定义函数的时候一定要记得加引用符&
(2)输出结果对应的是整除,输出余数对应的是取余;由于除法在处理时(也就是div函数内部)和加减乘都不一样,他还是倒序读数,因此最后得reverse把结果再反过来。这么麻烦的目的是使得题目同时高精度加减乘除时都统一;该做的前序0去除也是得有
(3)对于除法,除的交互对象变为b而不是10
1 |
|
前缀和与差分
一维前缀和
1.思路
(1)一维前缀和
s[r]-s[l-1]即可。
(2)需要注意的是对于前缀和与差分,都默认i/j=1;i<=n;i/j++而不是从0开始,原因是数组默认初始时所有值都是零也就是a[0]/a[0][0]=0(以及后面的),而前缀和表达式是从1开始的,(给定a[0]/a[0][0]=0后)则数组也要相应的从1开始(差分则是对前缀和在某一段添加固定值时的效率提升,可以理解为在特定情况下对前缀和的改进,也就是基于前缀和,那么自然是也遵循这个设定)。
2.题目:795. 前缀和 - AcWing题库
1 |
|
二维前缀和
1.思路
做二维题关键就是理清楚数组取值与其相邻两格的取值关系(要在脑子里形成一个网格状的图)。
首先是弄清楚前缀和与具体取值在二维中的表示,就可以在脑中快速形成关系:
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1](多减了一个就补上)+a[i][j](当前取值)

转换为求和之后就可以快速得到特定区间的求和范围及对应求法(如下图所示):(b[][]就是s[][],多在脑中过几遍就会想的更快)

1 |
|
一维差分
1.思路
上文提到,差分的本质就是对前缀和的某种改进(明确一点,差分刻画了前缀和的增长量),因此会有b[i]=a[i]-a[i-1]),希望对原数组中的部分区间加一个固定值c;因此直观地可以把差分理解为把原输出a[i]转换成用b[i]表示并对b[i]进行运算后再转换回a[i]输出;因此转换与输出应当互为相反,因此有转换b[i]=a[i]-a[i-1]; ,输出a[i]=a[i-1]+b[i](二维亦是如此);这个过程中当b[i]加了c,则a[n]=b[1]+…+b[i]+…+b[n]也就都加了c,但我们只希望特定区间(l,r)加c,因此对于r+1外的b数组就要减回c。
2.题目:797. 差分 - AcWing题库
1 |
|
二维差分
1.思路
(1)思路其实就揉合了前面差分的定义
a[i][j]与a[i-1][j-1]的增长量不等于简单的
b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]
(2)总结起来,网格图中前缀和考虑的是(x1,y1)前面的部分,差分考虑的是(x2,y2)后面的部分,这么想就会发现区别了

2.题目:798. 差分矩阵 - AcWing题库
1 |
|
第一章 基础算法(三)
双指针算法
1.思路
使用双指针是降低算法复杂度的一个有效途径,对于原本采用暴力嵌套循环,时间复杂度为
1 | //暴力解法 |
(1)对于最长连续不重复子序列:
数组a表示正常数据内容,s表示a的计数器;s[a[i]]++就是对数值为a[i]的这个数出现次数进行计数;j和i分别代表当前最长连续不重复序列的左边界和右边界,当保证左边界始终不超过右边界且发现某个数值a[i]出现次数大于一次也即s[a[i]]>1时,触发s[a[j]]--:含义是将a[j]的出现次数减一,更直观的解释是把重复的数(中的一个,而对于初始数字也就是s[a[0]]来说就是这个数不可能是左边界了,它就变成0)移出当前最长连续不重复序列的观察窗口,否则就会使得while(j<i&&s[a[i]]>1)重复执行。
(2)对于数组元素的目标和:
①假设输入如下:数组 a = [1, 2, 4, 7] (长度
b = [3, 4, 6, 8] (长度
x = 6
初始状态: i = 0 (指向
j = 3 (指向
| 步骤 | 指针位置 | 当前值 | a[i]+b[j] | 逻辑判断 | 动作 |
| ---- | -------- | -------------- | --------- | -------- | -------------------- |
| 1 | i=0, j=3 | a[0]=1, b[3]=8 | 9 | 9 > 6 | j 左移 (j=3 → 2) |
| 2 | i=0, j=2 | a[0]=1, b[2]=6 | 7 | 7 > 6 | j 左移 (j=2 → 1) |
| 3 | i=0, j=1 | a[0]=1, b[1]=4 | 5 | 5 ≯ 6 | 跳出 while,执行 if |
| 4 | i=0, j=1 | a[0]=1, b[1]=4 | 5 | 5 ≠ 6 | 进入下一轮 for (i=1) |
| 5 | i=1, j=1 | a[1]=2, b[1]=4 | 6 | 6 ≯ 6 | 跳出 while |
| 6 | i=1, j=1 | a[1]=2, b[1]=4 | 6 | 6 = 6 | 匹配成功!输出 1 1 |
②为什么是相向双指针?如何想到?
核心逻辑:单调性(Monotonicity)双指针算法的本质是利用问题的单调性来规避掉不必要的搜索空间。
同向双指针(如滑动窗口): 通常用于处理“连续子数组”问题。当
相向双指针(本题):如果
(3)对于判断子序列:
该算法利用双指针同步扫描,通过不断移动
2.题目
1 |
|
1 |
|
1 |
|
位运算
1.知识点
(1)lowbit(x):提取最低位的 1。lowbit 利用计算机中补码的特性,通过 x & -x 得到
~x + 1(反码加 1),这会导致
(2)x >> n & 1:获取第
x >> n 将目标位移动到最低位(第 0 位),然后与 1(二进制为 ...0001)进行按位与运算,从而屏蔽掉目标位左侧的所有干扰,直接提取出该位的值(结果仅为 0 或 1)。
1 |
|
离散化
1.思路
(1)什么是离散化?为什么要叫这个名字?
原本的坐标轴是“连续”的(或者范围巨大到接近连续),但我们只关心其中散落的、离散的几个点。我们将这些“散落的点”提取出来,压进一个连续的数组里。虽然结果变连续了,但过程是处理离散点,所以叫离散化。
(2)为什么这道题要用离散化?
①空间塞不下: 坐标范围是
int a[2000000000] 的数组,那么电脑内存直接爆掉(需要约 8GB 内存,而题目通常只给 64MB)。
②实际有用点很少: 虽然坐标大,但操作只有
(3)什么是pair?vector<PII>是啥意思?
在 C++ 中,pair 是一个可以把两个不同类型(或相同类型)的值捆绑在一起的结构。
①成员名固定:盒子的第一个格叫 first,第二个格叫 second。
②写法:pair<类型1, 类型2> 变量名;
PII 是别名(typedef pair<int, int> PII;),因为 pair<int, int> 写起来太长;vector<PII> 是由一对对整数组成的动态数组。形象比喻是,int:一个独居的人;PII:一对同居的室友;vector<int>:一排单人间宿舍;vector<PII>:一排双人间宿舍。
(4)处理思路
①记录需求:把所有坐标
②排队领号:把这些坐标从小到大排好,去掉重复的。每个坐标对应的“排队序号”就是它的新名字。
③映射数据:把原本在巨大坐标
a[序号] 里。
④前缀和:在 a 数组上做一遍前缀和。
⑤回答问题:把查询的
2.题目:802. 区间和 - AcWing题库
(1)输入处理:
1 | 3 3 <-- n=3 (加数操作次数), m=3 (询问次数) |
此时代码在做什么:
- 把这 3 对
(x, c)存进vector<PII> add(存加了数的数字的位置,以及加数)。 - 把这 3 对
(l, r)存进vector<PII> query(存要求前缀和的左右边界)。 - 把所有的坐标
1, 3, 7(来自add) 和1, 3, 4, 6, 7, 8(来自query) 全部一股脑塞进alls。
此时
alls的状态:[1, 3, 7, 1, 3, 4, 6, 7, 8]
(2)离散化:
sort(alls.begin(), alls.end()) 和 unique(...)。
①排序:alls 变成 [1, 1, 3, 3, 4, 6, 7, 7, 8]。
②去重:alls 变成 [1, 3, 4, 6, 7, 8](此时该数对应的位置就隐含在数组的位置中,不再是一个pair了)。
③处理 add 里的加数操作:先用find()函数返回r+1也就是前缀和中待加数的位置(前缀和从1开始算),然后把这个数加进去。
(4)算前缀和并返回对应值:
前缀和代码就是s[i]=s[i-1]+a[i],返回求和值(区间值)就是s[r]-s[l-1]
1 |
|
区间合并
1.思路
(1)通过对所有区间按左端点进行升序排列,利用变量维护当前合并区间的边界,遍历时若发现后续区间与当前边界存在交集则更新右边界,若无交集则结算当前区间并重新初始化边界。
(2)在执行 if (r < seg.first) 逻辑块时,为什么必须先 push_back 再更新 l, r?
变量 l 和 r存储的是当前正在处理的合并区间的边界数据,只要存的不是初始的l=r=-2e-9,那么就可以把这个pair压入vector并把边界更新,并等待下一个左右边界判断与当前边界的关系;
①如果不判断l!=-2e9:初始pairl=r=-2e9也会压入数组数据就不对了。
②如果先更新边界并根据这个边界压入vector里:不知道还有没有可以合并的数组。
③不在循环完后手动压入边界至vector:因为一开始先判断的不让初始边界进vector,相当于压入是滞后的,不手动压入一次就会漏掉一个pair。
2.题目:803. 区间合并 - AcWing题库
1 |
|
第二章 数据结构(一)
单链表
1.思路
(1)为什么不用课本上学的结构体来构造链表?
数据结构课本中,链表由节点构成,每个节点保存了值Val和下一个元素的位置*Next这两个信息。节点的表示形式如下:
1 | struct Node{ |
使用这种方法,在创建一个值为 x 新节点的时候使用new:
1 | Node* node = new Node(); |
new的底层涉及内存分配,调用构造函数,指针转换等多种复杂且费时的操作。一秒大概能new 1w次左右。在平时的工程代码中,不会
涉及上万次的new操作,所以这种结构是一种“见代码知意”的好结构(也就是可以用在工程)。
但在算法题场景下,经常碰到操作在10w级别的链表操作;若使用结构体这种操作,则无法在算法规定时间完成任务。因此不能频繁使用
new操作,也即不能使用结构体来实现数组。
(2)详细问题解答:【问题解答用数组模拟单链表】
(3)在 if (!k) head = ne[head]; 中,如何理解 !k 的含义以及这行代码的作用?
! 是逻辑非运算符 (Logical NOT operator)。在逻辑判断中,0固定为False,那么!k就是用来判断是否为0,!0=True <=> k==0,反之为False。因此!核心作用是将操作数的布尔状态“取反”;比如k=5,逻辑上为真,取反就为假,也就是说k!=0前提下!k=False该判断不成立;反之k==0,!k=True。在该题中
2.题目:826. 单链表 - AcWing题库
1 |
|
3.再写一次的错误
(1)ne[idx]=head;head=idx++;写成head=ne[idx]++这就是写反了,应当先更新idx,再更新和蔼的
(2)init();写进了循环里面,这样参数就没办法及时更新
双链表
1.思路
理解这段代码下标逻辑的关键在于两个核心设定:一是 insert(k, x) 的定义是在下标为 k 的节点右侧插入;二是 idx 从 2 开始,导致第
(1)op == "L"(在最左端插入):因为下标 0 是固定的虚拟头节点(左哨兵),根据 insert(k, x) 在 k 右侧插入的定义,直接在 0 后面插入即可成为第一个真实节点。
(2)op == "R"(在最右端插入):因为下标 1 是虚拟尾节点(右哨兵),在最右端插入等价于“在右哨兵左边的那个节点(l[1])的右边插入”。
(3)op == "D"(删除第
idx 从 2 开始分配,第 1 个数下标是 2,第 2 个是 3,推导出第
(4)op == "IL"(在第
l[k+1])的右边插入”。
(5)else (IR)(在第
insert 函数“在给定下标右侧插入”的本意,直接传入第
2.题目:827. 双链表 - AcWing题库
注意:IL、IR是俩字母,所以不能用char要用string
1 |
|
3.再写一次的错误
(1)void init() { r[0]=1; l[1]=0; idx=2; }写成了l[0]=1这样就相当于0左边还有点,这肯定是不对的
(2) l[idx]=l[r[k]]; l[r[k]]=r[idx];,yxc代码中l[idx]=k;写成l[r[k]]也是对的但是自然是k更简洁明了;但是l[r[k]]=r[idx];就不对了,因为idx右边就是r[k]了这样相当于自环了。
(3)忘记了循环输出结果怎么写for(int i=r[0];i!=1;i=r[i])cout<<e[i]<<' ';,注意i!=1中这个1就是init的1,这里的1是虚拟出来的右边界,相当于插入的所有节点都在0,1这俩节点中间。
栈
1.思路
(1)单调栈:题目要找数组里头左边最小的数,首先第一个数进去的时候左边没数,应该输出-1,因此代码结构就是先做逻辑处理再对stk数组进行入栈;然后核心判断逻辑while(top&&stk[top]>=x)top--;tt用于判断stk是否为空,stk[tt]>=x自不必说,随后就一直top--,直到找到第一个在栈中小于x的数;top–只动了栈顶,因此数组是没变化的,但是确实能让指针指向了栈底的数字,所以等价于“出栈”(实际上是没出的),后续就通过stk[++top]=x;直接给使用过的位置替换就行。(注意stk[0]是不存数字的,因为0已经用于判空,因此是++tt)
(2)模拟栈:这个题很简单,就是在单调栈基础上稍微扩展了一下。
(3)表达式求值:该算法基于中缀表达式的算符优先法(Operator-Precedence Parsing),通过维护操作数栈和运算符栈协同实现。在遍历表达式字符串的过程中:若遇到数字,需通过内层循环连续读取字符并转化为十进制整数后压入操作数栈;若遇到左括号,直接压入运算符栈作为局部运算的起始边界;若遇到右括号,则循环调用 eval 函数直至运算符栈顶为左括号,并随后弹出该左括号以完成括号内子表达式的收敛;若遇到普通算术运算符,当运算符栈非空、栈顶不为左括号且栈顶运算符优先级大于或等于当前运算符时,循环调用 eval 执行先行运算以维护运算符的左结合律,随后将当前运算符压入运算符栈;eval 函数的原子操作定义为从操作数栈先后弹出右操作数
解题思路:
①优先级表:用 unordered_map<char, int> 预设好 + - 为 1,* / 为 2。
②eval() 逻辑:
- 从
num弹出 (右操作数)。 - 从
num弹出 (左操作数)。 - 从
op弹出操作符。 - 结果压回
num。
③两个 while 循环:
- 拼数字:
while(isdigit) x = x * 10 + ... - 对左右括号的处理:左括号直接入栈,右括号就运算括号内所有内容,最后把左括号弹出栈。
- 比优先级:
while(op.size() && op.top() != '(' && h[op.top()] >= h[s[i]]) eval();
④后置处理:字符串跑完后,符号栈可能还有剩下的(比如 1+2+3 只处理了第一个 +),所以最后要 while(op.size()) eval();。
2.题目:
1 |
|
1 |
|
1 | //除了常规的两个库,还需要调stack栈,unordered_map无向图(哈希表)和string字符串 |
队列
1.思路
(1)滑动窗口
(1)变量解释(front后面会换成head,这样和tail才配对)
①front 的作用:负责维护滑动窗口边界的有效性。它始终指向当前窗口内最优解(最大值或最小值)的下标;当队头存储的下标超出当前滑动窗口的有效左边界(即 i - k + 1 > q[front])时,通过 front++ 执行队头出队操作,剔除失效的区间元素。
②tail 的作用:负责维护数据结构的单调性。它控制元素的入队与尾部出队;在新元素入队前,通过循环执行 tail-- 弹出队尾所有破坏指定单调性(如非严格递减或非严格递增)的冗余元素,随后通过 q[++tail] = i 将新元素的下标存入队列。
③需要注意的是front说白了是管出不出队,tail是管入不入队,不能简单地认为头一定要大于尾,在这里头反而要小于等于尾,这说明插入的数大于出去的数,队列才是非空的。
(2)核心代码解释
①if(front<=tail&&i-k+1>q[front])front++;:执行队头过期清理。 front <= tail 是边界安全检查,确保队列非空,防止出现空队列越界访问;i - k + 1 > q[front] 用于判定当前队头存储的下标是否已经落后于滑动窗口的有效左边界。若判定为真,说明该最优解已滑出窗口失效,通过 front++ 将其从队头物理逻辑上剔除。
②while(front <= tail && a[i] <= a[q[tail]]) tail--; (以寻找最小值为例):维护队列的单调递增性。 front <= tail 同样保证队列非空;a[i] <= a[q[tail]] 将当前新遍历到的元素与队尾元素进行值比较。若当前元素更小或相等,说明现有的队尾元素在未来绝对不可能成为窗口内的最小值(因为新元素既比它小,存活时间又比它长)。此时触发 tail--,持续将这些丧失竞争力的冗余队尾元素弹出,直至遇到比新元素更小的值或队列被清空。
③ q[++tail] = i;:新元素下标强制入队。 经过上一句的单调性维护(剔除所有劣势元素)后,当前处理的元素下标 i 必须入队。因为它作为当前窗口最新加入的元素,是未来滑动窗口最优解的合法候选者。
④ if(i - k + 1 >= 0) printf("%d ", a[q[front]]);:输出当前窗口的最优解。 i - k + 1 >= 0(即 i >= k - 1)用于拦截未完全成型的窗口,判断当前遍历的进度是否已经容纳了至少 k 个元素。一旦第一个完整的滑动窗口形成,由于单调队列的性质,队头 q[front] 对应的元素 a[q[front]] 绝对是当前窗口的最优解,直接将其取出并打印。
(3)常见问题解答
①a[q[tail]]什么时候只有一个数,什么时候允许有两个数或以上?
当新来的元素比队列中所有的元素都“更优”(例如找最小值时,新来的元素比队列里所有数都小)时,队列会被清空到只剩这一个数。当新来的元素没有破坏单调性,也就是它比队尾元素“更劣”(例如找最小值时,新来的元素比队尾的数更大)时,它无法踢走任何人,只能委屈地排在队尾充当“备胎”。
(4)基于样例手写处理过程

(2)模拟队列
这题关键就在于理清楚头指针与尾指针的数量关系,初始时head=0,tail=-1,tail负责插入数head负责移除树;当没有数时head==tail+1为空;当插入第一个数时tail先加再赋值a[0],此时head==tail非空;再插入第二个数是++tail,此时tail指向1head仍指向0,……,当需要移除数的时候head++,此时虽然数组中仍存着数据(也可以考虑free)但是从指针的角度已经把队头的数扔了。整体操作和模拟栈是很像的,只是从一个指针变成两个。
2.题目:
1 |
|
(2)模拟队列
1 |
|
KMP
1.思路
(1)KMP算法是取三个发明者的首字母得来的名字,算法的目的是在字符串匹配时不用暴力求解(双循环)这种方式而采用部分匹配表的形式避免重复比较。
(2)参考思路解析:字符串匹配的KMP算法 - 阮一峰的网络日志
(3)个人解析:KMP关键就是弄懂如何避免重复比较取而代之地是实现快速从当前失败的匹配串跳到下一个部分成功匹配串的位置,具体来说首先要弄懂待定子串(也就是不确定是不是子串的那个短的字符串,题目里称为模式串 )内部的以某一个pivot(轴)分成两半的串有没有相同部分,然后就是用相同的思路让待定子串在完整字符串(也就是长的字符串)也实现借助相同部分的快速跳跃。
具体来说首先就是弄清楚待定子串里头是否有重复可跳跃位置并用数组ne[]记录。注意处理ne[]时我们已经先让ne[0]=-1因为内部的跳跃不能自己跳转到自己位置,这样无意义,因此设置为-1;故循环时int i=1;i……。然后就是用while反复判断当j没有回到完全无匹配状况,且前后子串确实无法匹配上时就回退代表匹配成功长度的j,i扮演的角色就是不停挪动这个轴,然后看看轴两次能否找到相同部分,找到了匹配长度j++,由此便可记录下子串内部的可跳跃位置,用ne[]存储;
然后再让i~[0,n)因为此时i代表大字符串了,然后j=-1依旧,表示待定子串的重复长度,然后重复待定子串内部的匹配过程即可。因为最后输出的是重复子串的初始位置而非长度,因此用i-j来输出子串位置。
要初始设置的变量是待定子串char p[N](可以记:kmp以p结尾,故待定匹配子串为p),大字符串为char s[N],待定子串内部跳跃位置用ne[N]存储,以及待定子串和大字符串的长度。
(4)疑问:在 KMP 匹配成功一个完整模式串后,执行 j = ne[j] 的核心目的是什么?
核心目的是为了高效处理重叠匹配的情况,利用当前匹配成功的模式串末尾部分(后缀)可能正是下一个潜在匹配开头部分(前缀)的特性,通过
以在 ababa 中搜索 aba 为例,当程序在文本串下标
aba 后,
aba 首尾都是 a 的对称性,让模式串开头的 a 瞬间对齐到文本串刚才匹配成功的那个末尾字符 a(下标 2),使得程序能紧接着从文本串下标
b),从而丝滑地识别出从下标
aba;而如果将
a,进而彻底错过这两个 aba 之间共享的那个字符。
1 |
|
第二章 数据结构(二/三)
三是哈希表+STL常用内容。
Trie树:以树结构存储字符串、数字串等
1.思路
(1)Q:请你说说Trie字典树(前缀树)的思路和代码结构?
A:Trie字典树的思路是利用字符串的公共前缀来节约存储空间,并通过多叉树的层级结构实现高效的字符串插入与查询。在代码构建上首先需要定义全局变量,包括用于模拟多叉树拓扑结构的二维数组(
int son[N][26])存储各个节点的子节点索引,记录以当前节点结尾的字符串数量的数组(int cnt[N]),以及控制节点物理空间动态分配的自增变量(int idx)和接收输入的字符数组(char str[N])。在main函数中循环读取操作指令和目标字符串(scanf("%s%s", op, str)),根据指令类型分别调用插入操作(if(*op == 'I') insert(str))或打印查询结果(else printf("%d\n", query(str)))。在insert函数内部,首先定义游标指针并初始化为根节点0(int p = 0)。随后遍历传入的字符串(for(int i = 0; str[i]; i++)),将每个字符转换为0到25的数字以映射到对应的分支(int u = str[i] - 'a')。如果当前节点对应的该字符分支尚未被创建(if(!son[p][u])),就利用分配器为其分配一个新的非零节点编号(son[p][u] = ++idx),然后让游标指针顺着层级转移到这个子节点(p = son[p][u])。遍历结束后,给游标最终停留的节点打上结束标记并累加字符串个数(cnt[p]++)。在query函数中,同样从根节点开始遍历字符串并进行字符偏移计算。如果在遍历过程中发现某个字符对应的子节点为0(if(!son[p][u])),说明树中并未完整存入过该前缀,直接向外层返回不存在的信号(return 0)。否则继续向下一层状态转移(p = son[p][u]),若游标能顺利遍历完整个字符串,则直接返回最后一个节点上记录的独立字符串数量(return cnt[p])。(2)Q:请你说说Trie树求最大异或对的思路和代码结构?
A:Trie树求最大异或对的思路是将整数转化为二进制串存入字典树,并利用贪心策略从高位到低位优先寻找相反的分支以最大化异或结果。在代码构建上首先需要定义全局变量,包括用于存储原数据的数组(
int a[N]),用于模拟二叉字典树结构的二维数组(int son[M][2]),以及控制节点动态分配的自增变量(int idx)。在main函数中读取数据总量后循环读入每个数字(scanf("%d",&a[i])),并在读取的同时将其二进制形态插入字典树中(insert(a[i]))。随后再次遍历原数组,利用查询函数找出每个数字能构成的最大异或值并更新全局最大结果(res=max(res,query(a[i])))。在insert函数内部,定义游标指针初始化为根节点(int p=0)。通过循环从最高位第30位开始向下处理(for(int i=30;i>=0;i--)),每次通过位运算取出当前位的二进制数值(int u=x>>i&1)。如果对应的分支不存在则分配新节点(if(!son[p][u])son[p][u]=++idx),并让游标进入下一层(p=son[p][u])。在query函数中,同样定义游标和结果变量并从最高位开始遍历查询(for(int i=30;i>=0;i--))。每次取出当前位的数字后(int u=x>>i&1),为了满足贪心要求优先判断树中是否存在与当前位取反的节点分支(if(son[p][!u]))。如果存在相反分支,就让游标向该分支移动(p=son[p][!u]),并通过乘2加1的方式累计当前位异或产生的1(res=res*2+1)。如果不存在相反分支,只能被迫选择相同的分支(p=son[p][u]),此时当前位的异或结果为0,按乘2加0累计进位结果(res=res*2+0)。算法通过这种按位贪心的二叉树路径搜索完成计算,最后函数向外返回单个数字在当前树中所能匹配到的最大异或值(return res)。
2.题目
1 |
|
1 |
|
并查集
1.思路
所谓并查集就是利用树实现对集合的合并与查找(并查集:可以合并可以查找的集合),解题关键在于定义父节点数组p[]并借助find函数沿着p数组最终找到根节点,实现并查。
(1)Q:请你说说并查集维护集合连通性的思路和代码结构?
A:并查集的思路是用树形结构维护元素的连通状态,通过代表元素来实现集合的快速合并与查询。在代码构建上首先需要定义全局变量,也就是用于记录每个节点父节点编号的数组(
int p[N])。在main函数中读取节点总数后,必须对所有节点进行初始化,让每个节点的父节点指向自身(for(int i=0;i<n;i++)p[i]=i),表示初始阶段每个节点各自构成一个独立的集合。接着进入while循环读取具体的操作指令和节点编号(scanf("%s%d%d",op,&a,&b))。如果指令是进行合并操作,就分别查找到两个节点所在树的根节点,并令其中一棵树的根节点作为另一棵树根节点的子节点(if(*op=='M')p[find(a)]=find(b)),以此完成集合的合并。如果指令是查询操作,则直接判断两个节点对应的根节点是否完全相同(if(find(a)==find(b))),并依据真假输出判定结果。这其中的状态流转依赖于独立的查找函数find,当查询某个节点的根节点时,如果发现当前节点还不是树的根节点(if(p[x]!=x)),就会递归调用自身去寻找最终的根节点,并在递归回归的过程中直接把当前节点的父节点更新为最终的根节点(p[x]=find(p[x]))。算法通过这种路径压缩机制有效限制了树的高度,每次查找都能起到优化树结构的作用,最后函数向外层返回求得的根节点编号(return p[x])以供判断或合并使用。(2)Q:请你说说维护集合大小的并查集的思路和代码结构?
A:维护集合大小的并查集的思路是在基础并查集之上增加一个数组专门记录每个根节点所在集合的元素总数。在代码构建上首先需要定义全局变量,除了记录每个节点父节点编号的数组(
int p[N])外,还需要定义记录集合节点数量的数组(int s[N])。在main函数中读取节点总数后,必须对所有节点进行初始化,让每个节点的父节点指向自身(p[i]=i),同时将每个初始独立集合的节点数量设为1(s[i]=1)。接着进入while循环读取具体的操作指令。如果指令是进行合并操作,首先查找两个节点所在的树的根节点,若发现已经处于同一个集合则直接跳过(if(find(a)==find(b))continue;),若不在同一集合,则必须先将要连入的树的根节点记录的数量累加到目标树的根节点数量上(s[find(b)]+=s[find(a)]),然后再执行实际的根节点合并操作(p[find(a)]=find(b)),由于合并后原本根节点的独立性消失,这个先后顺序不能颠倒以免数量统计出错。如果指令是查询两个节点是否连通,则判断它们对应的根节点是否完全相同(if(find(a)==find(b)))。如果指令是查询某个节点所在集合的大小,则通过find函数查找到它的根节点并输出对应数组记录的数量(cout<<s[find(a)]<<endl)。底层依然依赖带有路径压缩功能的查找函数find,在递归寻找最终根节点的过程中直接把沿途节点的父节点更新为最终根节点(p[x]=find(p[x])),以保证树的高度扁平化,最后函数返回求得的根节点编号(return p[x])。
2.题目
1 |
|
1 |
|
堆
1.思路
(1)堆排序
(2)模拟堆
① ph[idx]=cnt; hp[cnt]=idx; h[cnt]=x; 这三个数组分别存储了什么东西?
直观来记
hp[cnt]=idx中数组取值cnt代表该节点在heap中的位置,取值idx代表该节点实际插入位置,因此是hp(heap-pointer);反之ph[idx]=cnt就是已知第idx插入求堆中实际位置cnt;因此在对第k个数操作时才会有k=ph[k]本质上就是得出了k在堆中的实际位置。
答案: 这三个数组构成了双向映射堆的核心,用于在
h[i]:存储堆中下标为
ph[k](Pointer to Heap):存储第
h 中的下标。
hp[i](Heap to Pointer):存储堆下标为
idx)。
举例: 依次执行 I 10 (第1个插入) 和 I 5 (第2个插入)。
插入 10 后:h[1]=10, ph[1]=1, hp[1]=1。
插入 5 后(放入末尾):h[2]=5, ph[2]=2, hp[2]=2。
执行 up(2):由于
h数组:变为h[1]=5, h[2]=10。hp数组:同步交换,变为hp[1]=2, hp[2]=1(说明现在堆顶是第2个插入的)。ph数组:通过hp反向定位并更新,变为ph[2]=1, ph[1]=2(说明第2个插入的数现在在堆顶)。
②为什么 DM 只用了 down,而 D 和 C 操作需要同时使用 down 和 up?
DM 操作:其逻辑是将堆顶(全堆最小值)与堆尾元素交换并删除堆尾。被交换到堆顶的元素原属于底层,其值必然大于等于原堆顶,且通常大于其新的子节点。因此,该节点在逻辑上只能向下移动(down)以重新寻找平衡,不存在向上移动的空间。
D k 或 C k x 操作:其目标是堆中的任意节点。由于第
up;若比子节点大,则需 down。在实际执行中,up 和 down 只会有一个被触发(或都不触发),同时调用两者是为了应对任意位置数值变动的不确定性。
(1)Q:请你说说小根堆建堆及提取最小值的思路和代码结构?
A:小根堆的思路是利用一维数组通过下标的倍数关系模拟完全二叉树,通过向下调整操作维护父节点始终小于等于子节点的性质。在代码构建上首先需要定义全局变量,包括用于存储堆元素的数组(
int h[N])以及记录当前堆内元素数量的变量(int cnt)。在main函数中读取数据时,为了满足左右子节点对应二倍和二倍加一的数学映射关系,数组必须从下标1开始存入数据(for(int i=1;i<=n;i++)scanf("%d",&h[i])),并同步初始化当前堆的总大小(cnt=n)。接着进行整个堆的初始化构建,由于完全二叉树底层的叶子节点天然没有子节点无需向下调整,因此只需从最后一个非叶子节点开始逆序向根节点遍历(for(int i=n/2;i;i--))并逐个调用down函数(down(i))。在down函数内部,首先设定一个临时变量记录当前父节点与两个子节点中最小值的下标(int t=u)。随后分别验证左子节点和右子节点是否在堆的有效范围内,如果节点存在且数值小于当前记录的最小值,就更新这个最小值的下标(if(2*u<=cnt&&h[2*u]<h[t])t=2*u与if(2*u+1<=cnt&&h[2*u+1]<h[t])t=2*u+1)。经过比对后,如果发现最小值不再是原本的父节点自身(if(u!=t)),说明堆的性质被破坏,此时将父节点与最小的那个子节点进行位置交换(swap(h[u],h[t])),并顺着交换后的位置继续递归执行向下调整(down(t))直到完全满足大小关系。完成初步建堆后,main函数在处理提取前m个最小值的需求时,每次直接打印处于堆顶的最小值(printf("%d ",h[1])),随后为了快速删除堆顶,用堆底的最后一个元素将其覆盖并让堆的有效体积减一(h[1]=h[cnt--]),最后从新的堆顶重新执行一次向下调整(down(1))即可恢复堆的结构并等待下一次输出。(2)Q:请你说说带映射的模拟堆的思路和代码结构?
A:模拟堆的思路是在标准小根堆的基础上增加双向映射数组,以支持根据元素的插入顺序对任意位置的元素进行随机修改和删除。在代码构建上首先需要定义全局变量,包括存储堆元素的数组(
int h[N]),记录第k个插入的元素在堆中物理位置的映射数组(int ph[N]),记录堆中物理位置对应第几个插入元素的逆映射数组(int hp[N]),以及堆当前总元素数(int cnt)和插入总次数计数器(int idx)。为了维护映射关系的同步,必须自定义交换函数,在交换两个堆节点时,先交换按物理位置找回插入序号后的指针指向(swap(ph[hp[a]],ph[hp[b]])),再交换物理位置对应的插入序号记录(swap(hp[a],hp[b])),最后交换数值本身(swap(h[a],h[b]))。向下调整函数利用子节点与父节点的比较寻找最小值并向下递归(down(t)),向上调整函数通过判断子节点是否小于父节点不断向上循环交换(while(u/2&&h[u]<h[u/2]))。在main函数中通过循环判定字符串指令,若是插入操作,则同步增加堆体积和插入序号(cnt++,idx++),建立新节点的双向映射(ph[idx]=cnt; hp[cnt]=idx;)并存入数值(h[cnt]=x),最后对其执行向上调整(up(cnt))。若是删除堆顶,则将其与堆末尾元素交换并缩小堆体积(heap_swap(1,cnt--)),随后从堆顶向下调整(down(1))。当需要删除或修改第k个插入的元素时,首先通过映射数组找到该元素当前在堆中的真实物理下标(k=ph[k]),在执行完交换删除(heap_swap(k,cnt--))或直接修改赋值(h[k]=x)后,由于元素变动后可能变大也可能变小,因此必须依次调用向下调整和向上调整(down(k); up(k);),此时算法会自动根据新数值的大小匹配到其中一个正确的方向去执行以恢复堆的单调性。
2.题目
1 |
|
1 |
|
哈希表
1.思路
(1)模拟散列表
散列表的构建有两种方法:拉链法和开放寻址法,为了方便这里就只介绍拉链法(与后续图论相关)。实现的方法与构建单链表类似,最核心就是如何从实际数值映射到哈希表下标来存储:N=100000+3是一个经验值(因为是质数)用于提高哈希表的映射效率。k=(x%N+N)%N本质其实就是k=x%N基于这样的方式去映射到下标,先加再模是对负数的特殊处理,负数的模在C++里还是负数,而数组是从0开始,因此必须得先加再模;后面的操作思想就非常类似于单链表了。
(2)字符串哈希
字符串哈希就是从k进制的角度把字符看成数字,然后用求前缀和的形式去比较哈希值看字符串是否相等。首先需要明确的是相比于前缀和(用右边界前缀和减左边界前缀和)字符串哈希需要给左边界前缀和进位到与右边界前缀和最高位对齐,这样才会得到需要比较的那两位的哈希值。然后注意进位k取得是经验值P=131;随后代码从前往后,先定义ull的哈希数组h[N]和负责管进位数的数组p[N],然后初始化前缀和——即分别设置h[0]=1以及前缀和的初始过程,然后还得初始化进位数组p,然后就是计算前缀和是否相等,由此判断Yes/No。
(1)Q:请你说说拉链法实现哈希表的思路和代码结构?
A:拉链法实现哈希表的思路是通过取模运算将数据映射到固定范围的哈希桶中,并利用单链表解决哈希冲突问题。在代码构建上首先需要定义全局变量,主要是用于模拟多条单链表的数组结构,包括哈希桶头节点数组(
int h[N])、存储具体数值的数组(int e[N])以及存储下一个节点指针的数组(int ne[N])。在main函数中,首先必须初始化所有哈希桶的头节点为-1以表示初始链表均为空(memset(h,-1,sizeof(h))),随后循环读取操作指令和对应的数值(scanf("%s %d",op,&x)),并根据指令调用对应的处理函数(if(*op=='I')insert(x))。在insert函数内部,首先算出数值对应的哈希映射值,为了防止负数取模出现负边界需要加N再取模(int k=(x%N+N)%N)。算出映射位置后,采用头插法将新节点插入到对应的单链表中,先存下节点的值(e[idx]=x),然后让新节点指向当前的头节点(ne[idx]=h[k]),最后更新头节点为新节点的编号并移动全局指针(h[k]=idx++)。在find函数中,同样先计算出目标数值的哈希映射值(int k=(x%N+N)%N),接着遍历该哈希桶对应的单链表(for(int i=h[k];i!=-1;i=ne[i]))。如果在这个链表中找到了与目标相等的值(if(e[i]==x)),说明数据存在并立刻返回成功信号(return true),若整个链表遍历结束仍未触发判断,则说明数据不存在并返回失败信号(return false)。(2)Q:请你说说字符串前缀哈希判断子串相同的思路和代码结构?
A:字符串前缀哈希的思路是将字符串看作P进制数,并利用前缀和思想在常数时间内求出任意子串的哈希值进行比对。在代码构建上首先需要定义全局变量,主要是利用无符号长整型自然溢出等效于取模的特性,定义哈希前缀和数组(
ull h[N])与记录P次方的权重数组(ull p[N]),以及配合前缀和计算从下标1开始存储的字符数组(char str[N])。在main函数中读取字符串后(scanf("%s",str+1)),首先初始化权重数组首位为1(p[0]=1)。随后通过循环遍历整个字符串(for(int i=1;i<=n;i++)),利用递推公式计算各个前缀的哈希值,即将前一个位置的哈希值乘以进制基数并加上当前字符的ASCII码(h[i]=h[i-1]*P+str[i]),同时同步预处理出每一位的权重次方(p[i]=p[i-1]*P)。接着进入求解区间子串哈希值的get函数中,为了截取从l到r的子串哈希值,需要将l前一位的哈希值乘以对应的子串长度权重对齐到r的位置,然后用r位置的整体哈希值减去对齐后的前半部分哈希值(return h[r]-h[l-1]*p[r-l+1])。算法通过这种预处理前缀数组结合区间相减的方式实现了子串的高效降维比对。main函数在处理多组查询时,只需直接判断两段对应区间的get函数返回值是否完全相等(if(get(l1,r1)==get(l2,r2))),并依此输出判定结果即可。
2.题目
1 |
|
1 |
|
STL容器
STL:Standard Template Library标准模板库
vector向量/pair<变量类型1,变量类型2>(存储二元组)
1.vector变长数组,基本思想是倍增:系统为某一程序分配空间时所需时间与空间大小无关,只与申请次数有关;因此申请一次开一个1000大小的空间速度是申请1000次开1个大小空间的1000倍。因此vector开空间采用倍增思想,当个数超过当前大小空间时,就开辟一个当前大小两倍的空间,把当前元素直接复制过去,从而尽可能减少申请次数,允许浪费空间。
2.开vector可以用vector<int> a(10,3),相当于给每变长数组开了10个,每个值为3;也可以用vector<int> a[10],只是开了个vector。
3.vector有的函数是:size()返回元素个数;empty()返回是否为空;clear()清空(大部分容器都没有这个函数);front()/back()返回vector的第一个数/最后一个数;push_back()/pop_back()是把vector的最后一个位置插入数/删除数;begin()/end()分别代表vector的第一个数/最后一个数。
1 | //vector两种迭代方式 |
4.vector还支持比较运算,具体比较方式就是按位字典序,比如下面这个例子a<b是成立的(3<4):
1 | vector<int> a(4,3),b(3,4); |
5.pair二元组前后的变量类型可以任意,比如pair<int,string>;其中pair.first代表第一个元素pair.second代表第二个元素。
6.pair支持比较运算,以first为第一关键字,second为第二关键字(字典序)
1 |
|
7.pair的应用场景:比如说有一个二元组要按照其中一个元素排序,那么就把要排序的元素放在第一关键字,第二关键字的元素就会跟着第一关键字元素一起移动。
8.pair还可以直接用来存储三个属性:pair<int,pair<int,int>>p
string字符串
1.string字符串,substr()返回某个子串,c_str()返回字符数组的头指针。
2.支持的函数:size()/length()返回字符个数/字符串长度;empty()判空;clear()清空字符串。
3.string可以直接用+拼接字符串,比如a+='abc';b+='def'。
4.函数substr(a,b),a是指定起始位置,b是指定长度,这样就可以获取特定子串的内容了:a.substr(1,2)返回的就是从1开始长度为2的字符串子串。如果设定的a,b参数使得字符串子串长度超出字符串本身长度,那么就输出到字符串本身长度为止。如果不提供参数b比如substr(a),那么就返回从a开始的完整子串。
queue队列/priority queue优先队列
1.queue队列,push()从队尾插入,front()返回队头元素,pop()从队头弹出
2.priority queue优先队列(是一个堆),push()插入元素,top()返回堆顶,pop()把堆顶弹出
3.push是向队尾插入元素,front()/back()是返回队头/队尾元素,pop()弹出队头元素, size()/empty()这种常规的当然也有,但是queue是没有clear()的。
stack栈
1.stack是栈,push()是往栈顶添加元素,top()返回栈顶元素,pop()弹出栈顶元素
set,map,multiset,multimap
红黑树就是平衡二叉树的一种;set,map,multiset,multimap基于平衡二叉树(红黑树),动态维护有序序列
1.set(集合): 是一个有序且元素唯一的容器(基于红黑树,插入时自动排序并去重)。
2.multiset(多重集合): 是一个有序但允许元素重复的容器(基于红黑树,插入时自动排序但不断开相同元素)。
set/multiset支持
insert()插入一个数,find()查找一个数,count()返回某一个数的个数,erase(x)输入一个数x删除所有的x,也可以是输入一个迭代器,删除所有迭代器;两个核心操作是lower_bound(x)返回大于等于x的最小的数,upper_bound(x)返回大于x的最小的数
3.map(映射): 是一个存储唯一键值对(key-value)的有序关联容器(基于红黑树,按 key 排序且 key 不可重复)。
4.multimap(多重映射): 是一个存储键值对且允许键重复的有序关联容器(基于红黑树,按 key 排序且允许同一个 key 对应多个 value)。
map就类似于py中的字典,以键值对的形式实现映射
insert()插入的数是一个pair,erase()输入的参数是pair或迭代器,find()查找一个数,最重要的是能像数组一样用,比如:
1 |
|
unordered set,unordered map,unordered multiset,unordered multimap
1.unordered_set: 是一个无序且元素唯一的容器(基于哈希表,插入和查找平均时间复杂度为
2.unordered_multiset: 是一个无序但允许元素重复的容器(基于哈希表,相同哈希值的元素会被放在同一个桶中)。
3.unordered_map: 是一个存储唯一键值对(key-value)的无序关联容器(基于哈希表,按 key 的哈希值存储,key 不可重复)。
4.unordered_multimap: 是一个存储键值对且允许键重复的无序关联容器(基于哈希表,允许同一个 key 映射到多个 value)。
第三章 搜索与图论(一)
DFS
1.思路
(1)排列数字:上数据结构时老师曾提到dfs用栈bfs用队列,bfs确实用队列但dfs通过递归解决。通常解题思路就是先明确终止递归对应的操作(通常对应print一个结果)定义一个存结果的数组和一个状态数组表示是否访问过,如果没访问过即状态数组为false就将其置为true,然后处理相关内容,然后递归调用dfs,然后再将其状态返回false代表往回走。
dfs回溯的时候通常还需要恢复结果数组本身内容,但是这个排列数字刚好自己会覆盖所以就可以省略这一行,但是一般都得对结果数组也有操作
(2)n-皇后:整体处理过程与排列数字一致,主要讲讲状态数组为什么写成col[y]==false&&dg[x-y+n]==false&&udg[x+y]==false:国际象棋皇后可以横走竖走正反对角线走,因为dfs的迭代层u本身表示了行,所以就只定义了列和两个对角线,对于正对角线,其上元素都用x-y表示,但因为其可能为负所以得+n保证为正否则数组下标会溢出;反对角线就用x+y表示,不存在溢出所以直接就写位x+y

2.题目
(1)842. 排列数字 - AcWing题库
1 |
|
1 |
|
BFS
1.思路
(1)Q:请你说说BFS求解二维迷宫最短路的思路和代码结构?
A:BFS求解二维迷宫最短路的思路是利用队列从起点开始向四周逐层扩散,最先到达终点的路径即为最短路径。在代码构建上首先需要定义全局变量,包括用于存储迷宫地图状态的二维数组(
int g[N][N]),记录起点到各个点距离的二维数组(int d[N][N]),以及定义坐标对结构以方便压入队列(typedef pair<int,int> pii)。在main函数中初始化迷宫外围全为墙壁防越界(memset(g,1,sizeof(g)))并循环读取实际的迷宫数据(cin>>g[i][j]),然后调用bfs函数从起点开始搜索。在bfs函数内部,首先建立队列并将起点坐标对压入队列(q.push({a,b}))。进入while循环后,只要队列不为空就取出队头坐标并将其弹出(pii start=q.front(); q.pop();)。随后定义上下左右四个方向的偏移量数组(int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0}),并通过循环遍历这四个方向(for(int i=0;i<4;i++))计算出相邻节点的新坐标(int x=start.first+dx[i],y=start.second+dy[i])。如果发现相邻节点是可以通行的空地(if(g[x][y]==0)),就立刻将其置为1作为障碍物标记以防止重复遍历(g[x][y]=1),并将该相邻节点的距离更新为当前出队节点距离加一(d[x][y]=d[start.first][start.second]+1),最后将新坐标压入队列等待后续扩展(q.push({x,y}))。算法通过这种逐层推进的方式完成地图的探索,最后直接输出目标节点处记录的距离值作为最终结果(cout<<d[n][m])。(2)Q:请你说说BFS求解八数码问题的思路和代码结构?
A:BFS求解八数码问题的思路是将二维网格状态压缩为一维字符串,并通过广度优先搜索寻找到达目标状态的最短交换步数。在代码构建上首先需要定义目标状态字符串(
string end="12345678x"),以及用于记录各个字符串状态距离起点的步数键值对(unordered_map<string,int> d)。在main函数中通过循环读取输入的字符拼接成初始状态字符串(s+=c),然后调用bfs函数求解。在bfs函数内部,首先建立队列(queue<string> q)并将初始字符串压入其中(q.push(s)),同时初始化其处理距离为0(d[s]=0)。进入while循环后,只要队列不为空就取出队头字符串并弹出(string t=q.front(); q.pop();)。随后立刻进行终点判定,如果当前状态等于目标状态则直接返回记录的距离(if(t==end)return distance;)。若未到达目标,则通过内置函数找到字符x在一维字符串中的下标(int k=t.find('x')),并利用除法和取余操作将其转换为二维网格中的逻辑坐标(int x=k/3,y=k%3)。接着遍历上下左右四个方向(for(int i=0;i<4;i++))计算出交换目标的新二维坐标(int a=x+dx[i],b=y+dy[i])。如果新坐标在3乘3的边界范围内(if(a>=0&&a<3&&b>=0&&b<3)),就将字符串中对应位置的字符进行交换以生成新状态(swap(t[k],t[a*3+b]))。此时如果这个新状态在哈希表中未被记录过(if(!d.count(t))),便将其距离更新为当前距离加一(d[t]=distance+1)并压入队列(q.push(t))。完成判断后必须再次进行交换以回溯还原当前出队节点的状态(swap(t[k],t[a*3+b])),从而不影响后续其他方向的探索。算法通过这种状态空间的扩散完成穷举,如果队列排空仍未找到目标状态则返回失败信号(return -1)。
2.题目
1 |
|
1 |
|
树与图的深度优先遍历
1.思路
Q:请你说说DFS求树的重心的思路和代码结构?
A:DFS求树的重心的思路是通过递归遍历计算以每个节点为根的子树大小,并找出删除该节点后剩余各个连通块中节点数的最大值,进而取这些最大值中的最小值来确定重心。在代码构建上首先需要定义全局变量,包括用于存储无向树图的邻接表(
int h[N],e[M],ne[M]),记录节点访问状态的布尔数组(bool state[N]),以及记录遍历过程中最小的最大连通块节点数的变量(int ans=N)。在main函数中初始化邻接表表头(memset(h,-1,sizeof(h)))并循环读取树的边,由于是无向图所以必须连接双向边(add(a,b),add(b,a)),然后从任意节点开始调用dfs函数求解并输出最终结果(cout<<ans<<endl)。在dfs函数内部,首先将当前访问节点标记为已访问(state[u]=true),并初始化两个局部变量,res记录当前节点向下各分支的最大连通块节点数(int res=0),sum记录包含当前节点在内的子树总节点数(int sum=1)。随后遍历与当前节点相连的所有相邻节点(for(int i=h[u];i!=-1;i=ne[i]))。如果发现相邻节点未被访问过(if(!state[j])),就向下递归调用dfs函数计算以该相邻节点为根的子树大小(int size=dfs(j)),将其累加到当前节点的子树总数中(sum+=size),并更新向下分支中的最大连通块节点数(res=max(res,size))。遍历结束后,当前节点上方剩余的整块部分也是一个连通块,其大小为节点总数减去当前子树大小,需要用它再次更新最大连通块的记录(res=max(res,n-sum))。此时res即为以当前节点为假设重心时的最大连通块大小,我们用它来更新全局的最优重心记录(ans=min(ans,res)),最后函数向上一层返回当前子树的总节点数(return sum)以供父节点计算使用。
2.题目:846. 树的重心 - AcWing题库
1 |
|
树与图的广度优先遍历
1.思路
Q:请你说说BFS求无权图最短路的思路和代码结构?
A:BFS求无权图最短路的思路是利用队列进行层序遍历,每次向外扩展一层来保证最先到达目标节点的一定是最短路径。在代码构建上首先需要定义全局变量,包括用于存图的邻接表(
int h[N],e[N],ne[N])以及记录源点到各个节点距离的数组(int d[N])。在main函数中初始化邻接表表头(memset(h,-1,sizeof(h)))并循环读取有向边建图(add(a,b)),然后调用bfs函数求解并输出最终结果。在bfs函数内部,首先将距离数组全部初始化为-1以兼作访问状态标记(memset(d,-1,sizeof(d)))。随后建立队列(queue<int> q),将起点的距离设为0(d[1]=0)并将其压入队列中(q.push(1))。进入while循环后,只要队列不为空就取出队头节点并将其弹出(int t=q.front(); q.pop();)。接着遍历与该出队节点相连的所有相邻节点(for(int i=h[t];i!=-1;i=ne[i]))。如果发现相邻节点的距离仍然为-1,说明该节点尚未被访问过(if(d[j]==-1)),就将其距离更新为当前出队节点的距离加一(d[j]=d[t]+1),并将该相邻节点压入队列以备后续继续扩展(q.push(j))。算法通过这种逐层推进的方式完成整张图的遍历计算,最后函数直接返回目标节点记录的距离值作为结果(return d[n])。
1 |
|
拓扑排序
1.思路
Q:请你说说拓扑排序的思路和代码结构?
A:拓扑排序的思路是基于广度优先搜索不断剥离入度为零的节点来求出有向图的线性依赖序列。在代码构建上首先需要定义全局变量,包括用于存有向图的邻接表(
int h[N],e[N],ne[N]),记录各个节点入度数量的数组(int in[N]),以及用于模拟队列并直接存储最终排序结果的数组(int q[N])。在main函数中初始化邻接表表头(memset(h,-1,sizeof h))并循环读取有向边建图(add(a,b)),同时务必将终点节点的入度加一(in[b]++)。接着调用topsort函数进行求解并根据返回值判断图是否有环。在topsort函数内部,首先初始化模拟队列的头尾指针(int hh=0,tt=-1),并遍历所有节点将初始入度为0的节点压入队列(if(in[i]==0)q[++tt]=i)。进入while循环后,只要队列不为空(while(hh<=tt))就取出队头节点(int t=q[hh++])。随后遍历与该出队节点相连的所有相邻节点(for(int i=h[t];i!=-1;i=ne[i])),将相邻节点的入度减一(in[j]--)以解除依赖关系。如果减一后相邻节点的入度变为0(if(in[j]==0)),说明它的所有前置条件都已满足,便将其压入队列(q[++tt]=j)。算法通过这种不断将前置依赖清零的节点入队的方式完成遍历,最后通过判断入队元素的总数是否等于总节点数来判定图是否为有向无环图(return tt==n-1)。如果判定成功,main函数中直接按序输出模拟队列中的元素即可得到完整的拓扑序列(printf("%d ",q[i]))。
1 |
|
第三章 搜索与图论(二)

Dijkstra(朴素用于稠密图,堆优化用于稀疏图)
Dijkstra不能解决负权边本质是因为Dijkstra基于贪心求最短路径,要求每个点被确定后st[j] = true,dist[j]就是最短距离了,之后就不能再被更新了(一锤子买卖),而如果有负权边的话,那已经确定的点的dist[j]不一定是最短了
1.思路
(1)用邻接矩阵也就是二维矩阵存储图,一维矩阵也就是距离矩阵存储结果,状态矩阵表示点有没有被访问过;每次初始化一个距离最近的点,然后判断:①这个点有没有遍历过②这个点是距离最近的点或者这个点距离比之前的点小,那么就把当前最近点替换为真正的最近点,然后修改状态
(2)
(1)Q:请你说说朴素Dijkstra算法求最短路的思路和代码结构?
A:朴素Dijkstra算法是基于贪心策略每次寻找到源点距离最短且未被访问的节点来逐步更新全局最短路径。在代码构建上首先需要定义全局变量,除了用于存稠密图的邻接矩阵(
int g[N][N])外,还需定义d数组(int d[N])记录源点到各点的最短距离,以及st布尔数组(bool st[N])记录节点是否已经确定了最短路。在main函数中首先必须初始化邻接矩阵的所有边权为正无穷(memset(g,0x3f,sizeof g)),接着读入有向图的边并注意处理重边保留最短边(g[x][y]=min(g[x][y],z)),然后调用Dijkstra函数求解并输出结果。在Dijkstra函数内部,首先初始化所有节点到源点的距离为正无穷(memset(d,0x3f,sizeof d))并将起点距离设为0(d[1]=0)。随后外层循环执行n次以确保为图中的每一个节点确定最短路(for(int i=0;i<n;i++))。在每次循环中,通过内层遍历寻找当前未被确定且距离源点最近的节点t(if(!st[j]&&(t==-1||d[t]>d[j])) t=j;)。找到后将该节点正式标记为已确定最短路(st[t]=true)。随后进行松弛操作,利用刚确定最短路的节点t去尝试更新其他所有节点到源点的距离(d[j]=min(d[j],d[t]+g[t][j]))。算法通过这种贪心更新不断扩展已知最短路的集合,最后函数根据终点的距离是否依然接近正无穷来判定是否可达并返回最终结果(if(d[n]>0x3f3f3f3f/2)return -1; else return d[n];)。(2)Q:请你说说堆优化版Dijkstra算法求最短路的思路和代码结构?
A:堆优化版Dijkstra算法的思路是利用小根堆代替朴素版中的内层循环来高效寻找距离源点最近的未访问节点。在代码构建上首先需要定义全局变量,包括用于存稀疏图的带权邻接表(
int h[N],e[M],ne[M],w[N]),距离数组(int d[N]),以及布尔状态数组(bool st[N])记录节点是否已经出过堆并确定了最短路。在main函数中初始化邻接表表头(memset(h,-1,sizeof h))并循环读入有向边建图(add(x,y,c)),然后调用Dijkstra函数求解并输出最终结果。在Dijkstra函数内部,首先初始化距离数组为正无穷(memset(d,0x3f,sizeof d))并将起点距离设为0(d[1]=0)。随后建立基于pair的小根堆优先队列(priority_queue<pii,vector<pii>,greater<pii>> heap),并将源点的距离和编号以距离排在首位的方式压入堆中(heap.push({0,1}))。进入while循环后,只要堆不为空就不断取出堆顶的最近节点并立刻弹出(pii start=heap.top(); heap.pop();)。此时必须进行冗余过滤,如果该节点之前已经被弹出并确定过最短路径,则直接跳过本轮循环以防止超时(if(st[ver])continue;),否则将其正式标记为已确定(st[ver]=true;)。接着遍历与该出堆节点相连的所有相邻节点(for(int i=h[ver];i!=-1;i=ne[i]))进行松弛判断。如果发现通过当前节点到达相邻节点的距离比原本记录的更短(if(d[j]>distance+w[i])),就更新距离数值(d[j]=distance+w[i]),并将更新后的距离和对应的相邻节点重新压入堆中等待后续扩展(heap.push({d[j],j}))。算法通过这种优先队列调度的贪心策略完成已知最短路集合的扩展,最后函数根据终点的距离是否依然接近正无穷来判定是否可达并返回最终结果(if(d[n]>0x3f3f3f3f/2)return -1; else return d[n];)。
2.题目
(1)849. Dijkstra求最短路 I - AcWing题库
1 |
|
(2)850. Dijkstra求最短路 II - AcWing题库
1 |
|
bellman-ford算法
通常情况下spfa全方位碾轧贝尔曼福德算法,只有当限制边的数量的时候spfa会超时被卡。
1.思路
Q:请你说说Bellman-Ford算法求有边数限制的最短路的思路和代码结构?
A:Bellman-Ford算法的思路是通过对所有边进行多次独立松弛操作来求出最短路径,特别适用于解决带有最多经过k条边限制的最短路问题。在代码构建上首先需要定义全局变量,关键是定义结构体数组(
struct edge e[M])存储每条边的起点、终点及权重,以及d数组(int d[N])记录源点到各点的距离和back数组(int back[N])用于保存上一轮的距离状态。在main函数中循环读取所有边并直接存入结构体(e[i]={x,y,w}),然后调用bellman_ford函数求解,并根据目标节点的距离是否依然接近正无穷来判定终点是否不可达(if(d[n]>0x3f3f3f3f/2))。在bellman_ford函数内部,首先初始化距离数组为正无穷(memset(d,0x3f,sizeof d))并将起点距离设为0(d[1]=0)。随后进入外层循环,循环次数直接对应限制的最多经过边数k(for(int i=0;i<k;i++))。在每次外层循环开始时,必须将当前的d数组状态备份到back数组中(memcpy(back,d,sizeof d)),这是为了防止在本轮后续的松弛中发生串联更新,从而保证每次外层循环严格只向外扩展一条有效边。接着进入内层循环遍历图中的所有m条边(for(int j=0;j<m;j++)),严格利用back数组中保存的上一轮状态对当前边进行松弛判断并更新距离(d[e[j].y]=min(d[e[j].y],back[e[j].x]+e[j].w))。算法通过这种限制迭代次数并依赖备份数组更新的机制完成计算,最后在main函数中输出到达目标节点的最短距离(cout<<d[n]<<endl)。
2.题目:853. 有边数限制的最短路 - AcWing题库
1 |
|
spfa算法
1.思路
(1)Q:请你说说spfa算法求最短路的思路和代码结构?
A:spfa算法是基于Bellman-Ford算法的队列优化,通过仅将被更新过距离的节点放入队列来避免无效的松弛操作。在代码构建上首先需要定义全局变量,除了用于存图的带权邻接表(
int h[N],e[M],ne[M],w[N])外,还需定义d数组(int d[N])记录源点到各点的最短距离,以及st布尔数组(bool st[N])记录节点当前是否处于队列之中。在main函数中初始化邻接表表头(memset(h,-1,sizeof h))并循环读取所有有向边建图(add(x,y,c)),然后调用spfa函数求解并根据返回值判定终点是否不可达(if(spfa()>0x3f3f3f3f/2))。在spfa函数内部,首先初始化所有点到源点的距离为正无穷(memset(d,0x3f,sizeof d))并将起点距离设为0(d[1]=0)。随后建立队列并将源点入队,同时标记其已在队列中(q.push(1); st[1]=true;)。进入while循环后,只要队列不为空就不断取出队头节点(int start=q.front(); q.pop();),并立刻取消其在队列中的状态标记(st[start]=false),允许该节点在未来被找到更短路径时再次入队。随后遍历与该出队节点相连的所有相邻节点(for(int i=h[start];i!=-1;i=ne[i]))进行松弛判断。如果发现通过当前节点到达相邻节点的距离比原本记录的更短(if(d[j]>d[start]+w[i])),就更新短距离(d[j]=d[start]+w[i]),此时如果该相邻节点不在队列中(if(!st[j])),便将其压入队列并更新在队状态(q.push(j); st[j]=true;)。算法通过这种队列驱动的松弛操作完成计算,最后函数返回到达目标节点的最短距离(return d[n])。(2)Q:请你说说SPFA算法判定负环的思路和代码结构?
A:spfa判定负环的思路是利用松弛操作并记录最短路径包含的边数,根据抽屉原理判断图内是否存在环。在代码构建上首先需要定义全局变量,除了用于存图的带权邻接表(
int h[N],e[M],w[M],ne[M])外,还需定义d数组(int d[N])记录相对距离,cnt数组(int cnt[N])记录从虚拟起点到达该节点的最短路径所包含的边数,以及st布尔数组(bool st[N])记录节点当前是否处于队列之中。在main函数中初始化邻接表表头(memset(h,-1,sizeof h))并循环读取边建图(add(a,b,c)),然后调用spfa函数并根据其布尔返回值输出判定结果(if(spfa())cout<<"Yes";)。在spfa函数内部,由于判定负环只关心距离是否能无休止地减少而不关心绝对距离,因此无需将d数组初始化为正无穷。考虑到图可能不连通导致负环无法从单一节点出发到达,首先需将所有的节点统统压入队列并标记在队状态(for(int i=1;i<=n;i++){q.push(i); st[i]=true;})。进入while循环后,不断取出队头节点(int start=q.front(); q.pop();)并立刻取消其在队列中的标记(st[start]=false)。随后遍历与该节点相连的所有相邻节点(for(int i=h[start];i!=-1;i=ne[i]))进行松弛判断。如果发现到达相邻节点的距离能够变得更短(if(d[j]>d[start]+w[i])),就更新距离数值(d[j]=d[start]+w[i]),并令相邻节点的边数等于当前出队节点的边数加一(cnt[j]=cnt[start]+1)。此时立刻进行防死循环判定,如果该路径上的边数已经大于等于图的总节点数(if(cnt[j]>=n)),说明路径中必然包含了重复节点且构成负权环,直接向上层返回存在负环的信号(return true)。此时如果该相邻节点不在队列中(if(!st[j])),便将其压入队列继续参与后续的松弛(q.push(j); st[j]=true;)。如果队列正常排空且未触发边界条件,说明全图不存在负环,函数返回不存在的结果(return false)。
2.题目
1 |
|
1 |
|
Floyd算法
1.思路
Q:请你说说Floyd算法求多源汇最短路的核心思路和代码结构?
A:Floyd算法的核心思想是基于动态规划利用中间节点不断松弛任意两点之间的最短距离。在代码构建上首先需要定义核心变量,关键是定义二维数组(
int d[N][N])作为邻接矩阵来存储图中两点间的当前最短距离。在main函数中首先对邻接矩阵进行初始化,遍历所有节点的编号(for(int i=1;i<=n;i++)与for(int j=1;j<=n;j++)),将自身到自身的距离设为0(if(i==j)d[i][j]=0)而其余节点间设为正无穷(else d[i][j]=inf)。接着读入图的有向边,注意处理可能存在的重边并保留最短的一条(d[a][b]=min(d[a][b],c))。然后调用核心函数floyd进行求解,三层循环必须按顺序,最外层循环必须是遍历充当中间跳板的节点编号k(for(int k=1;k<=n;k++)),随后内部两层循环分别遍历起点i和终点j。接着进行核心的状态转移判断,评估通过中间点k是否能使起点i到终点j的距离变得更短,如果可以就更新这个最优距离(d[i][j]=min(d[i][j],d[i][k]+d[k][j]))。算法通过这种不断引入新节点作为中转站的方式完成所有节点对的最短路径计算。main函数最后在处理查询时,由于图中可能存在负权边导致原有的正无穷被轻微减小,因此根据最短距离是否仍然大于正无穷的一半来判定两点之间是否绝对不可达(if(d[x][y]>inf/2))并输出对应的结果。
2.题目:854. Floyd求最短路 - AcWing题库
1 |
|
第三章 搜索与图论(三)
Prim算法
1.思路
(1)朴素prim:将距离数组初始化为正无穷0x3f,然后按照点的数量从0~n进行遍历:令t为到集合外距离最近的点,用t更新其他点到当前已经在连通块的点的集合的距离,更新进来的点其状态置为true
Q:请你说说Prim算法求最小生成树的核心思路和代码结构?
A:Prim算法的核心思想是从一个起始点开始逐步将距离当前生成树集合最近的未访问节点纳入树中。在代码构建上首先需要定义核心变量,除了用于存稠密图的邻接矩阵(
int g[N][N])外,关键是定义d数组(int d[N])记录节点到当前生成树集合的最短距离以及st数组(int st[N])记录节点是否已经加入生成树。在main函数中首先必须初始化邻接矩阵的所有边权为正无穷(
memset(g,0x3f,sizeof g)),接着读入无向图的边并注意处理重边保留最短边(g[a][b]=g[b][a]=min(g[a][b],c)),然后调用核心函数进行求解并根据返回的最小总权重判断图是否连通(if(t>0x3f3f3f3f/2))。进入核心的prim函数中,首先初始化所有节点到集合的距离为正无穷(
memset(d,0x3f,sizeof d))并默认将第一个节点作为起点(d[1]=0)。随后外层循环执行n次以确保囊括所有节点(for(int i=0;i<n;i++)),在每次循环中通过内层遍历寻找当前未加入生成树且距离树集合最近的节点t(if(!st[j]&&(t==-1||d[t]>d[j])))。找到后如果发现该最近节点的距离依旧为正无穷则说明图不完全连通直接提前返回异常值(if(d[t]>0x3f3f3f3f/2)return 0x3f3f3f3f)。否则我们将这条最短边权累加进总结果(res+=d[t])并将该节点正式标记为加入生成树(st[t]=true)。随后进行最重要的状态更新,利用刚加入集合的新节点t去更新其他所有未加入节点到整个生成树集合的最小距离(d[j]=min(d[j],g[t][j])),这里本质上距离是相较于集合来说的,这与Dijkstra相较于当前源点来说的距离更新有着核心区别。算法通过这种贪心策略不断扩充集合,最后函数返回累加的最小生成树总权重(return res)。
2.题目:858. Prim算法求最小生成树 - AcWing题库
1 |
|
Kruskal算法
1.思路
①将所有边按权重从小到大排序,可以采用快排/c++库的sort(时间复杂度O(mlogm))
②枚举每条边a、b,权重是c,如果a和b尚不连通,那么将这条边加入到集合里
Q:请你说说Kruskal算法求最小生成树的核心思路和代码结构?
A:Kruskal算法的核心思路是基于贪心策略结合并查集按边权从小到大构建生成树。在代码构建上首先需要定义核心变量,关键是定义结构体数组(
struct edge e[M])存储边的端点及权重并重载小于号以支持按边权排序(return w<W.w),以及用于维护连通性的并查集父节点数组(int p[N])。在main函数中读取所有边存入结构体(e[i]={a,b,w})后调用核心函数进行求解,并根据返回值判断图是否连通(if(t>0x3f3f3f3f/2))。接着进入核心函数kruskal中,首先对全局所有边进行升序排序(sort(e,e+m))并初始化并查集(for(int i=1;i<=n;i++)p[i]=i)。随后遍历排序后的每一条边(for(int i=0;i<m;i++)),进行核心的判环与状态判断。如果当前边的两个端点在并查集中不属于同一个集合(if(find(a)!=find(b))),我们就执行并查集的合并操作(p[find(a)]=find(b)),并累加这条边的权重(res+=w)同时有效边数加一(cnt++)。算法通过这种方式不断挑出最短且不构成环的边加入集合。函数最后判断加入树中的边数是否达到收敛条件(if(cnt<n-1))来确定图是否完全连通,并返回最小总权重(return res)。
2.题目:859. Kruskal算法求最小生成树 - AcWing题库
1 |
|
染色法判定二分图
1.思路
Q:请你说说染色法判定二分图的核心思路和代码结构?
A:染色法判定二分图的核心是通过深度优先搜索dfs尝试为图的节点交替着色。除了用于存双向图的邻接表外,关键是定义color数组(
int color[N])记录每个节点的颜色状态,在main函数中外层循环遍历每一个节点以应对非连通图的情况(for(int i=1;i<=n;i++)),如果当前节点未被染色(if(!color[i]))则以它为起点染第一种颜色并进行深搜,若深搜发现冲突则标记失败并提前退出(if(!dfs(i,1)){flag=false; break;}),接着进入核心的递归函数dfs中,首先为当前节点赋上指定的颜色(color[u]=c),然后遍历与当前节点相连的所有相邻节点(for(int i=h[u];i!=-1;i=ne[i])),如果相邻节点未被着色(if(!color[j]))则将其颜色反转为另一种后继续递归深搜,若深搜失败直接向上层传递失败信号(if(!dfs(j,3-c))return false),随后进行核心的冲突判断,如果相邻节点已经被着色且颜色与当前节点完全相同(else if(color[j]==c)),则说明构不成二分图直接返回失败信号(return false),算法通过这种深度优先的交替着色不断检测边连接的合法性,最终遍历完毕且无冲突即代表着色成功(return true),main函数中最后根据状态变量输出判定结果(if(flag)cout<<"Yes"<<endl;)。
1 |
|
匈牙利算法
1.思路
Q:请你说说匈牙利算法求二分图最大匹配的核心思路和代码结构?
A:匈牙利算法的核心是寻找增广路,在代码构建上首先需要定义核心变量,除了用于存图的邻接表外,关键是定义match数组(
int match[N])记录右侧节点的匹配对象以及st布尔数组(bool st[N])记录当前轮次右侧节点的访问状态,在main函数中外层循环遍历左侧的每一个节点(for(int i=1;i<=n1;i++)),并且每次调用查找函数前必须清空st数组的访问状态(memset(st,false,sizeof st)),接着进入核心的递归函数find中遍历与当前左侧点相连的所有右侧点(for(int i=h[x];i!=-1;i=ne[i])),如果该右侧点在当前轮次未被访问(if(!st[j]))则将其置为已访问状态(st[j]=true),随后进行核心判断,如果该右侧点尚未被匹配或者它绑定的左侧点能通过递归找到其他空闲点(if(match[j]==0||find(match[j]))),我们就将该右侧点与当前左侧点绑定(match[j]=x)并返回成功信号(return true),算法通过这种递归回溯不断尝试为已匹配的节点腾出新位置,main函数中每次find成功总匹配数即加一(if(find(i))res++)。
1 |
|
第四章 数学知识:数论之质数、约数、欧拉函数、容斥定理
质数
- 质数:在所有大于1的整数中,如果只包含1和本身两个约数(因数),那么这个数就被称为质数,或者素数。(相当于因数(约数)包含了质数,质数是因数里的特殊部分)
(1)质数的判定
①试除法(暴力解法):直接循环遍历从2~n-1中还有没有别的数可以被整除,有的话说明不知1和本身,就不是质数;否则就是质数——时间复杂度
。 ②试除法(改进解法):其改进思路是约数通常都是成对出现,比如12/3=4,3和4都是约数,那么枚举的时候只需要枚举小的约数即可,数学定义上是
成立,那么 也成立,那么只需要枚举d即可,上界是 ,范围是 ,写成循环就是 for(int i=2;i<=n/i;i++)——时间复杂度,一定是刚好 (2)分解质因数
质因数:既是给定正整数的因数(能将其整除),本身又是质数(大于1且只能被1和自身整除)的数。比如数字12,它的因数有1、2、3、4、6、12,在这些因数当中,只有2和3是质数,所以12的质因数就是2和3。
分解质因数就是把一个给定的数字拆解成几个质数相乘的形式(在数学上通常表示为
)。比如输入了 6:6 可以拆成 2 × 3,写成指数形式就是。所以它的质因数(底数)是 2 和 3,出现的次数(指数)都是 1。因此输出就是先打印 2 1,再打印3 1。也是试除法:时间复杂度最好
最坏 ,比质数判定强
1.思路
(1)
Q:请你说说试除法判定质数的思路和代码结构?
A:试除法判定质数的思路是利用约数成对出现的性质,只需枚举较小的那部分约数即可判断目标数是否存在除1和自身外的其他约数。在代码构建上首先需要定义全局变量,包括用于记录需要判断的正整数数量的变量(
int n)。在main函数中,首先读入测试数据的数量(cin>>n),随后进入遍历循环(for(int i=0;i<n;i++)),在循环内部定义局部变量并读入当前需要判定的数值(int x; cin>>x),接着调用判定函数判断该数是否为质数,如果返回真则输出Yes(if(is_prime(x))cout<<"Yes"<<endl;),否则输出No(else cout<<"No"<<endl;)。进入is_prime判定函数,首先处理边界情况,如果传入的数值小于2,依据质数定义直接返回假(if(x<2)return false;)。接着进入尝试除法的循环,为了防止乘法溢出并减少运算量,循环条件限定为枚举变量i小于等于目标数x除以i的商(for(int i=2;i<=x/i;i++))。在循环内部判定x能否被当前的i整除,如果成立说明x存在除1和自身外的其他约数,直接返回假(if(x%i==0)return false;)。当循环正常结束且未触发返回假的分支时,说明该数满足质数条件,最终返回真(return true;)。
(2)
Q:请你说说分解质因数的思路和代码结构?
A:分解质因数的思路是利用算术基本定理和试除法策略,从小到大枚举可能的因子,将目标数不断除以该因子以求得每个质因数的底数和指数,同时利用数学性质将枚举上限压缩至当前剩余数值的平方根以降低时间复杂度。在代码构建上首先需要定义全局变量,包括用于记录测试数据数量的整型变量(
int n)。在main函数中,首先读入测试数据的数量(cin>>n),随后进入遍历循环(for(int i=0;i<n;i++)),在循环内部定义局部变量并读入当前需要分解的正整数(int x; cin>>x),接着直接调用分解函数对该数进行处理(divide(x);)。进入divide分解函数,由于从较小数开始遍历能够保证每次能够整除目标数的因子必定是质数,因此构建试除循环,循环自2开始,条件限定为枚举变量i小于等于当前x除以i的商(for(int i=2;i<=x/i;i++))。在循环内部,首先判断当前的x能否被i整除(if(x%i==0)),如果成立则说明i是x的一个质因数,随即定义局部变量用于记录该质因数出现的次数即指数(int s=0;)。接着通过内层循环将该质因数从x中彻底除尽,只要能够整除就更新x的值并递增指数计数(while(x%i==0) x/=i,s++;),随后输出当前质因数的底数和指数(cout<<i<<' '<<s<<endl;)。当外层试除循环结束后,进行最后的边界判定,如果除尽所有较小质因数后剩余的数值大于1(if(x>1)),说明此时剩下的x是原数中唯一大于其初始平方根的质因数,直接将其作为底数并连同指数1一起输出(cout<<x<<' '<<1<<endl;)。在函数末尾输出一个空行(cout<<endl;),用于分隔各个测试用例的输出结果。
(3)也可以参考动画中国大学生计算机设计大赛《素数筛选—欧拉线性筛选法详解》
Q:请你说说给定这段质数判定代码的思路和代码结构?
A:给定代码实际采用的是试除法判定单个数是否为质数的思路,利用约数成对出现的性质,只需枚举较小的那部分约数即可判断目标数是否存在除1和自身外的其他约数。在代码构建上首先需要定义全局变量,包括用于记录需要判断的正整数数量的变量(
int n)。在main函数中,首先读入测试数据的数量(cin>>n),随后进入遍历循环(for(int i=0;i<n;i++)),在循环内部定义局部变量并读入当前需要判定的数值(int x; cin>>x),接着调用判定函数判断该数是否为质数,如果返回真则输出Yes(if(is_prime(x))cout<<"Yes"<<endl;),否则输出No(else cout<<"No"<<endl;)。进入is_prime判定函数,首先处理边界情况,如果传入的数值小于2,依据质数定义直接返回假(if(x<2)return false;)。接着进入尝试除法的循环,循环条件限定为枚举变量i小于等于目标数x除以i的商(for(int i=2;i<=x/i;i++)),借此防止乘法溢出并减少运算量。在循环内部判定x能否被当前的i整除,如果成立说明x存在除1和自身外的其他约数,直接返回假(if(x%i==0)return false;)。当循环正常结束且未触发返回假的分支时,说明该数满足质数条件,最终返回真(return true;)。
2.题目
1 |
|
1 |
|
1 |
|
约数
- 约数(即因数):如果一个数除以另一个数的余数为0,即a%b == 0, 则b是a的约数
(1)如何求一个数x的所有约数:用 x 除以 1 到 x 的所有数,如果余数是0,则把除数加到答案中。为了提升效率,也是x只管
范围的数,然后如果 就再加 的数进去 (2)求约数(因数)个数:一个数的约数是由这个数的几个质因子相乘得到的,例如12 的质因子有2、3,12的约数有:1、2、3、4、6、12。12 可以分解为:
。所以2可以取0 ~ 2个,3种取法。3可以取 0~1个,2种取法。12的约数一共: 个。也就是可以把一个数 写成: ,其中 为质数。则N的约数个数为:
1.思路
(1)试除法求约数
Q:请你说说试除法求约数的思路和代码结构?
A:试除法求约数的思路是利用约数成对出现的规律,通过遍历较小的一半约数即可推导出另一半较大的约数,进而获取目标数的所有约数。在代码构建上首先需要定义全局变量,包括用于记录需要处理的数据组数的整型变量(
int n;)。在main函数中,首先读入测试数据的总组数(cin>>n;),随后利用while循环处理每一组数据(while(n--)),在循环内部定义局部变量并读入当前需要求约数的正整数(int x; cin>>x;),接着直接调用求解函数对该数值进行处理(get_divisors(x);)。进入get_divisors求解函数,由于事先无法确定目标数的约数个数,首先定义一个整型动态数组用于存储找到的约数(vector<int> res;)。接着进入寻找约数的循环,从1开始遍历,为减少计算量,循环条件限定为枚举变量i小于等于目标数x除以i的商(for(int i=1;i<=x/i;i++))。在循环内部判断目标数能否被当前的i整除(if(x%i==0)),如果能整除说明i是一个约数,将其存入动态数组中(res.push_back(i);),同时为了避免在目标数是完全平方数时重复添加同一个约数,需要判断当前约数与对应的另一半约数是否相等,若不相等则将另一半约数也加入数组(if(i!=x/i)res.push_back(x/i);)。由于成对添加导致数组内的约数并不是完全有序的,在循环结束后调用标准库函数对结果数组进行升序排序(sort(res.begin(),res.end());)。最后通过范围for循环依次输出数组中的每个约数(for(auto x:res)cout<<x<<' ';),并在当前组数据输出完毕后换行(cout<<endl;)。
(2)约数个数
Q:请你说说约数个数的思路和代码结构?
A:约数个数的思路是利用算术基本定理,将多个数的乘积转化为各个数分别进行质因数分解,统一统计所有质因数的总指数,最后根据约数个数定理将各质因数指数加一后连乘求得总约数个数。在代码构建上首先需要定义全局变量,包括题目要求的取模常数(
const int mod=1e9+7;),为防止连乘溢出而定义的类型别名(typedef long long ll;),以及记录输入正整数数量的整型变量(int n;)。在main函数中,首先读入测试数据的数量(cin>>n;),随后定义一个无序映射表用于记录和累加所有数值分解出的质因数及其对应的指数(unordered_map<int,int> primes;)。接着通过while循环依次处理每一个输入的数字(while(n--)),在循环内部读入当前正整数(int x; cin>>x;),并直接对其进行试除法分解质因数。分解循环自2开始枚举可能的质因数,为降低时间复杂度,循环条件限定为枚举变量i小于等于当前x除以i的商(for(int i=2;i<=x/i;i++))。在循环内部,只要当前的x能被i整除,就进入内层循环不断将i从x中除尽,同时在映射表中累加该质因数出现的次数即指数(while(x%i==0)x/=i,primes[i]++;)。当该数的试除循环结束后,进行边界判定,如果除尽所有较小质因数后剩余的x仍大于1(if(x>1)primes[x]++;),说明剩下的数值是该数中唯一大于其初始平方根的质因数,将其在映射表中的指数累加一次。当所有输入的数均分解并统计完毕后,定义长整型变量用于记录最终的约数个数并初始化为乘法单位元1(ll res=1;)。最后通过范围for循环遍历映射表中的每一个键值对(for(auto p:primes)),依据约数个数定理将当前质因数的指数加一后乘到结果变量上,并每次计算后对给定常数取模(res=res*(p.second+1)%mod;),加一是因为该质因数的选取次数包含了从0次到最高次的情况。循环结束后输出最终计算的模后结果(cout<<res<<endl;),程序结束运行。
(3)约数之和
Q:请你说说约数之和的思路和代码结构?
A:约数之和的思路是利用算术基本定理,将多个数的乘积转化为对各个数分别进行质因数分解以统一统计所有质因数及其总指数,最后依据约数之和定理计算每个质因数各次幂的等比数列求和并连乘得出最终结果。在代码构建上首先需要定义全局变量,包括题目要求的取模常数(
const int mod=1e9+7;),为防止连乘溢出而定义的类型别名(typedef long long ll;),以及记录输入正整数数量的整型变量(int n;)。在main函数中,首先读入测试数据的数量(cin>>n;),随后定义一个无序映射表用于记录和累加所有数值分解出的质因数及其对应的总指数(unordered_map<int,int> primes;)。接着通过while循环依次处理每一个输入的数字(while(n--)),在循环内部读入当前正整数(int x; cin>>x;),并对其进行试除法分解质因数。分解循环自2开始枚举可能的质因数,循环条件限定为枚举变量i小于等于当前x除以i的商(for(int i=2;i<=x/i;i++))以降低时间复杂度。在循环内部,只要当前的x能被i整除,就进入内层循环不断将i从x中除尽,同时在映射表中累加该质因数出现的次数即指数(while(x%i==0)x/=i,primes[i]++;)。当该数的试除循环结束后进行边界判定,如果除尽所有较小质因数后剩余的x仍大于1(if(x>1)primes[x]++;),说明剩下的数值是该数中唯一大于其初始平方根的质因数,将其在映射表中的指数累加一次。当所有输入的数均分解并统计完毕后,定义长整型变量用于记录最终的约数之和并初始化为乘法单位元1(ll res=1;)。最后通过范围for循环遍历映射表中的每一个键值对(for(auto p:primes)),分别提取当前的质因数底数和指数(ll a=p.first,b=p.second;),并定义局部变量用于记录单个底数对应项的求和结果并初始化为1(ll t=1;)。接着利用while循环按照指数递减的次数执行迭代计算(while(b--)),每次将当前求和变量乘以底数后加一并取模(t=(t*a+1)%mod;),以此递推得出该质因数从零次幂到最高次幂相加的总和。在该质因数的计算循环结束后,将单项的求和结果乘到总结果变量上并再次取模(res=res*t%mod;)以防止溢出。遍历映射表的循环结束后输出最终计算的取模结果(cout<<res<<endl;),程序结束运行。
(4)最大公约数
Q:请你说说最大公约数的思路和代码结构?
A:最大公约数的思路是利用欧几里得算法(辗转相除法),通过不断将除数与余数作为新的操作数进行递归求解,直到余数为零时即可确定最大公约数。在代码构建上,主流程直接在main函数中展开,首先定义局部变量用于记录需要处理的数据对数(
int n;)并读入该数值(cin>>n;)。随后利用while循环依次处理每一对输入数据(while(n--)),在循环内部定义局部变量并读入当前需要求最大公约数的两个正整数(int a,b; cin>>a>>b;),接着调用自定义的gcd函数对这两个数进行计算,将返回值输出并换行(cout<<gcd(a,b)<<endl;)。进入gcd求解函数,函数接收两个整型参数,内部逻辑严格依据辗转相除法执行。首先进行递归终止条件的判定,即判断第一个数能否被第二个数整除,如果取模结果为零(if(a%b==0)),说明当前的第二个数即为所求的最大公约数,直接将其返回(return b;)。如果取模结果不为零,则将第二个数和两数取模的余数作为新的参数,递归调用函数自身继续向下求解(else return gcd(b,a%b);)。此外,代码中还展示了另一种解法结构,即如果不手写递归逻辑,可以直接调用C++标准模板库中内置的相关函数(__gcd(a,b))来进行计算,该函数同样能够输出最大公约数结果,在实际编写时可根据需求选择使用。
2.题目
1 |
|
这题关键就是记住
res=1,res=(res*p.second+1)%mod,其中p.second是指数(分解出来的质因数的次数)
1 |
|
这题关键就是记住
res=1,res=(res*p.first+1)%mod,其中p是底数(分解出来的质因数)
1 |
|
1 | //解法1;直接调stl的__gcd(a,b)函数,注意是两个下划线 |
欧拉函数
欧拉函数作用是求一个数n和1~n中与之互斥的数并返回个数,比如对于6,那么1~6中与之互斥的数有1和5,那么欧拉函数
。 。比如:x=10,其互质数为1,3,7,9共4个;euler的做法是循环遍历找互质数,先找到的第一个质因数2,此时res=10/2*(2-1)=5,x=10/2=5,此时i=3,3<=5/3不成立因此就到判断x>1成立,把5也弄进来,res=5/5*(5-1)=4,就算出了个数。 ps:先除再乘是因为先乘很有可能会溢出但是先除肯定不会,比较安全
这题关键就是记住
res=res/i*(i-1)
1.思路
(1)欧拉函数
Q:请你说说欧拉函数的思路和代码结构?
A:欧拉函数的思路是利用算术基本定理中的欧拉函数乘积公式,结合试除法分解质因数的过程,依次求出目标数的各个质因子,并在遍历过程中直接累乘计算求出与目标数互质的数的个数。在代码构建上首先需要定义全局变量,包括用于记录需要处理的数据个数的整型变量(
int n;)。在main函数中,首先读入测试数据的总数量(cin>>n;),随后利用while循环依次处理每一个正整数(while(n--)),在循环内部定义局部变量并读入当前的数值(int x; cin>>x;),接着直接调用自定义的求解函数进行计算,并将返回的欧拉函数值输出换行(cout<<euler(x)<<endl;)。进入euler求解函数,首先定义局部变量用于记录最终结果,依据公式将初始值设为传入的数值本身(int res=x;)。接着进入寻找质因数的作用域(代码逻辑上依托类似于for(int i=2;i<=x/i;i++)的枚举遍历),判断当前的x能否被枚举变量i整除(if(x%i==0)),如果能整除说明i是x的一个质因数,此时依据欧拉函数乘积公式,通过先除后乘的方式更新结果变量以防止运算过程中发生数据溢出(res=res/i*(i-1);),随后利用内层循环将该质因数从x中彻底除尽(while(x%i==0)x/=i;)。当分解过程结束后进行最后的边界判定,如果除尽所有较小质因数后剩余的x仍大于1(if(x>1)),说明剩下的数值是该数中唯一大于其初始平方根的质因数,利用相同的乘积公式将其代入结果变量进行最后一轮更新(res=res/x*(x-1);)。最后将计算完毕的结果变量返回给主调函数(return res;)。
(2)筛法求欧拉函数
Q:请你说说筛法求欧拉函数的思路和代码结构?
A:筛法求欧拉函数的思路是利用线性筛机制在筛选合数的同时,利用欧拉函数的积性性质推导出每个数的欧拉函数值,最终累加得出指定范围内所有数对应的欧拉函数之和。在代码构建上首先需要定义全局变量,包括用于防止累加溢出的长整型别名(
typedef long long ll;),定义数组容量上限的常量(const int N=1000010;),存储每个数对应欧拉函数值的数组(int euler[N];),存储依次找出的质数的数组(int primes[N];),记录各个数字是否已经被筛去的布尔状态数组(bool st[N];),以及记录输入边界和当前已存储质数数量的整型变量(int n,cnt;)。在main函数中,首先读入求和的区间上限边界值(cin>>n;),随后直接调用求解函数并传入该值进行处理(get_eulers(n);),结束程序。进入get_eulers求解函数,首先初始化数字1的欧拉函数值为1(euler[1]=1;)。接着开启从2遍历至n的线性筛外层循环(for(int i=2;i<=n;i++)),在循环内部,若当前数字对应的状态数组值为假(if(!st[i])),说明该数字未被筛去即为质数,将其记录进质数数组中(primes[cnt++]=i;),并根据质数的定义直接赋予其欧拉函数值为自身数值减一(euler[i]=i-1;)。随后进入遍历已知质数空间的内层循环,为防止越界,循环终止条件限定为当前的质数与变量i的乘积不超过给定的上限n(for(int j=0;primes[j]<=n/i;j++))。在内层循环中,首先将当前质数与i的乘积所对应的数字在状态数组中标为合数(st[primes[j]*i]=true;)。接着进行递推分支判定,如果i能被当前枚举的质数整除(if(i%primes[j]==0)),说明该质数此前已经是i的质因子,质因数种类并未增加,直接依据公式将其值乘以该质数完成递推(euler[primes[j]*i]=primes[j]*euler[i];),并立刻中断内层循环(break;)以确保后续合数仅被其最小质因子筛去。如果不能整除(else),说明当前枚举的质数是新出现的质因子,两者互质,依据欧拉函数积性性质完成状态递推计算(euler[primes[j]*i]=(primes[j]-1)*euler[i];)。当整个双层筛选循环执行完毕后,定义长整型变量用于记录总和并初始化为0(ll res=0;),通过单层循环遍历累加1至n的所有欧拉函数值(for(int i=1;i<=n;i++)res+=euler[i];),最终将计算获得的总和输出并换行(cout<<res<<endl;)。
2.题目
1 |
|
参考题解:筛法求欧拉函数
筛法是一种基于“合数必然包含素因子”这一算术基本定理的素数生成算法;它的核心操作是从最小的素数开始,按递增顺序严格遍历自然数序列(2~n所有数都得过一遍,也就是线性筛),一旦确认当前数字未被标记(即为素数),便将其特定倍数作为合数进行标记并剔除,最终序列中所有未被标记的数字即为给定范围内的全部素数。
1 |
|
容斥原理
1.思路

以题目样例为例:
1 |
|
第五章 动态规划(一):背包问题
背包问题理论上都可以压缩为1维,但需要区分下面的概念
1.i、j、k的可能含义:如果遍历中只有i和j,那么i通常代表遍历轮次,j代表背包容量。因此i如果要用就必须要是1~n因为i受i-1轮的影响;j就可以从0~m因为容量可以是0;如果还有k就通常代表背包装的物品的个数,那么k*v[i]<=j,代表装下k个大小为v的i物品要小于背包j的当前容量
2.j的倒序与顺序遍历:如果希望状态压缩其且装下的物品是有限个(01背包、多重背包),那么j就得倒序开始防止重复使用某个物品;如果希望状态压缩但是装下物品可以是无限个(完全背包),那么j就可以正序遍历。只需要记住正序遍历会存在一个物品重复使用的问题,因此有限个物品的时候就倒序遍历
3.为什么01背包可以直接把j>=v[i]放到循环里分组背包却不行:因为分组还得在组间和组内遍历,而不像01背包只有一个组直接内部遍历就可以
01背包问题
1.思路
【题目描述】 有
件物品和一个容量是 的背包。每件物品只能使用一次。第 件物品的体积是 ,价值是 。求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出最大价值。 【题目分析】 本题是动态规划中背包模型的理论基础。题目限定每种物品仅有一件,即面对每件物品仅存在“放入”或“不放入”两种决策状态。算法需要记录在不同可用容量下的最大价值,其状态转移逻辑在于比对不放入当前物品时的既有价值,以及放入当前物品后剩余容量能构成的最大价值加上当前物品价值,取两者中的较大值。在利用一维滚动数组进行空间压缩时,必须采用逆序遍历容量,以确保上一层状态不被当前层提前覆盖,从而严格满足每个物品只被使用一次的约束条件。
Q:请你说说01背包问题的思路和代码结构?
A:01背包问题旨在解决给定数量有限的物品和一个固定容量的背包,每件物品仅用一次且具备特定体积和价值,要求在不超过背包容量的前提下使得装入物品的总价值最大这一需求,其代码求解思路是利用动态规划结合滚动数组的空间压缩策略,通过逐个判断物品的取舍来推导并记录特定容量下的最大总价值。在代码构建上首先需要定义全局变量,包括限制数组大小的常量(
const int N=1010;),分别用于记录每件物品体积和价值的数组(int v[N],w[N];),用于记录不同背包占用容量下对应最大价值的状态数组(int f[N];),以及记录物品总数和背包最大容量的整型变量(int n,m;)。在main函数中,首先读入物品总数量与背包最大容量(cin>>n>>m;)。随后进入外层循环依次处理每一件物品的取舍状态(for(int i=1;i<=n;i++)),在循环内部读入当前第i件物品的体积和价值(cin>>v[i]>>w[i];)。接着开启遍历背包占用容量的内层循环,为了保证当前物品只被放入一次,避免前序容量在这一轮更新数据后被后续容量复用计算,内层循环必须按照容量从大到小的倒序方向进行,并限定终止条件为当前背包容量大于等于该件物品的体积(for(int j=m;j>=v[i];j--))。在内层循环中直接执行状态转移操作,对比不放入该物品时当前容量的既有价值,以及放入该物品后剩余容量能达到的最大价值加上当前物品自身价值,将两者中的较大值覆盖更新至当前容量的状态数值中(f[j]=max(f[j],f[j-v[i]]+w[i]);)。当所有的物品遍历和状态更新彻底结束后,对应最大背包容量的状态数组元素即为全量计算后的最大价值,将其输出并换行(cout<<f[m]<<endl;),程序结束运行。
2.题目:2. 01背包问题 - AcWing题库
1 | [//]: # (打卡模板,上面预览按钮可以展示预览效果 ^^) |
完全背包问题
1.思路
【题目描述】 有
种物品和一个容量是 的背包,每种物品都有无限件可用。第 种物品的体积是 ,价值是 。求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出最大价值。 【题目分析】 本题是动态规划中完全背包模型的理论基础。与01背包问题的区别在于,每种物品的数量无限,即决策状态从“选或不选”扩展为“选0件、1件、2件……”。在利用一维滚动数组进行空间压缩优化时,状态转移方程要求当前容量的状态需要基于同层(即已经考虑过放入当前物品)的较小容量状态进行推导。因此,内层关于背包容量的循环必须采用正序遍历,使得物品可以被重复选取,以此满足每种物品无限件可用的条件。
Q:请你说说完全背包问题的思路和代码结构?
A:完全背包问题的思路是利用动态规划策略,通过逐个推导容量状态来记录最大价值,并在状态转移时通过改变容量的遍历方向来满足单种物品允许被无限次放入的条件。在代码构建上首先需要定义全局变量,包括限制数组大小的常量(
const int N=1010;),用于记录各物品体积和价值的数组(int v[N],w[N];),用于记录不同背包占用容量下最大总价值的状态数组(int f[N];),以及记录物品种数和背包总容量的整型变量(int n,m;)。在main函数中,首先读入物品总种数与背包最大容量(cin>>n>>m;)。随后进入外层循环依次处理每一种物品(for(int i=1;i<=n;i++)),在循环内部读入当前第i种物品的体积和价值(cin>>v[i]>>w[i];)。接着开启遍历背包占用容量的内层循环,为了实现同一种物品能够被重复装入,内层循环必须按照容量从小到大的正序方向进行,从当前物品的体积开始遍历至背包的最大容量(for(int j=v[i];j<=m;j++))。在正序遍历的机制下,当前容量状态更新时可以复用本轮内已经计算过放入当前物品的较小容量状态,以此达到重复选取的目的。在内层循环中执行状态转移操作,对比不放入当前物品时该容量的既有价值,以及放入当前物品后剩余容量对应的最大价值加上当前物品自身价值,将两者中的较大值覆盖更新至当前容量的状态数值中(f[j]=max(f[j],f[j-v[i]]+w[i]);)。当所有的物品遍历和状态更新结束后,对应最大背包容量的状态数组元素即为所求的最大价值,将其输出并换行(cout<<f[m]<<endl;),程序结束运行。
2.题目:3. 完全背包问题 - AcWing题库
1 |
|
多重背包问题 I
1.思路
【题目描述】
有
种物品和一个容量是 的背包。第 种物品最多有 件,每件体积是 ,价值是 。求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。输出最大价值。 【题目分析】
本题是动态规划中多重背包模型的基础版本。由于数据范围较小,可以直接基于01背包问题的状态转移方程进行扩展。题目限定每种物品有固定的数量上限,因此决策状态变为了“选0件、选1件……选
件”。算法在01背包的基础上增加了一层循环来枚举选择的件数。在利用一维数组进行空间压缩时,外层背包容量的遍历仍需严格遵循倒序遍历的原则,以确保每种物品在更新当前阶段状态时,使用的都是上一阶段未受当前物品影响的干净状态,从而严格满足物品数量上限的约束条件。 Q:请你说说多重背包问题 I的思路和代码结构?
A:多重背包问题I的思路是将问题转化为01背包问题的扩展,利用动态规划策略,通过增加一层循环来暴力枚举每种物品的具体选取数量,从而在满足背包容量和单种物品数量限制的前提下求得总体最大价值。在代码构建上首先需要定义全局变量,包括限制数组大小的常量(
const int N=110;),用于记录不同背包占用容量下最大总价值的状态数组(int f[N];),分别用于记录每种物品体积、价值和数量限制的数组(int v[N],w[N],s[N];),以及记录物品种数和背包总容量的整型变量(int n,m;)。在main函数中,首先读入物品总种数与背包最大容量(cin>>n>>m;)。随后进入外层循环依次处理每一种物品(for(int i=1;i<=n;i++)),在循环内部读入当前第种物品的体积、价值和限制数量( cin>>v[i]>>w[i]>>s[i];)。接着开启遍历背包占用容量的第二层循环,为了保证当前种类物品的选取数量严格受限于该轮计算,避免同层较小容量更新后的状态被后续较大容量错误复用,该循环必须按照容量从大到小的倒序方向进行,从最大容量遍历至0(for(int j=m;j>=0;j--))。在容量循环内部,开启第三层循环用于枚举当前物品可能选取的个数,枚举继续执行的条件是选取数量不能超过该物品的给定数量上限,并且这 个物品的总占用体积不能超过当前的背包容量( for(int k=0;k<=s[i]&&k*v[i]<=j;k++))。在最内层循环中执行状态转移计算,比对不改变当前容量已有价值的状态,以及选入个当前物品后剩余容量对应的最大价值加上这 个物品的总价值,将两者中的较大值覆盖更新至当前容量的状态数值中( f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);)。当所有物品、容量与个数枚举的遍历更新彻底结束后,对应最大背包容量的状态数组元素即为全量计算后的最大总价值,将其输出并换行(cout<<f[m]<<endl;),程序结束运行。
1 |
|
多重背包问题 II
1.思路
【题目描述】
有
种物品和一个容量是 的背包。第 种物品最多有 件,每件体积是 ,价值是 。求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。输出最大价值。 【题目分析】
本题是多重背包问题的进阶版本。由于数据范围增大,若继续采用基础版本中暴力枚举选取数量的方法,会导致三重循环从而引发超时(TLE)。因此需要采用二进制拆分优化策略,将每种数量为
的物品,按照二进制数的幂次(1, 2, 4, 8...)拆分成多个独立的物品,最后的剩余数量单独作为一个物品。这样可以将原问题转化为一个纯粹的01背包问题,通过对拆分后的新物品集合进行倒序容量遍历求解,将时间复杂度从 降至 。 Q:请你说说多重背包问题 II的思路和代码结构?
A:多重背包问题 II的思路是利用二进制拆分策略,将给定数量的同种物品依据二进制幂次进行打包拆分,从而将多重背包问题转化为规模显著缩小后的01背包问题,以此降低时间复杂度。在代码构建上首先需要定义全局变量,考虑到二进制拆分后物品总数会从1000增加至约1000乘以
,设定拆分后物品数组容量及背包容量常量( const int N=12010,M=2010;),分别用于记录拆分后每件新物品体积和价值的数组(int v[N],w[N];),用于记录不同背包占用容量下最大总价值的状态数组(int f[M];),以及记录输入物品种数和背包总容量的整型变量(int n,m;)。在main函数中,首先读入物品初始种数与背包最大容量(cin>>n>>m;)。接着定义局部变量用于记录拆分后生成的全新物品总数(int cnt=0;)。随后进入外层循环处理输入的每一种物品(for(int i=1;i<=n;i++)),在循环内部读取当前物品的单一重量、价值和数量限制(int a,b,s; cin>>a>>b>>s;),并定义二进制打包的初始基准量为1(int k=1;)。接着开启while循环进行拆分,只要当前基准量不超过该物品剩余总数(while(k<=s)),就生成一件新的打包物品,新物品总数累加(cnt++;),该打包物品的体积和价值分别为单件参数乘以当前基准量(v[cnt]=a*k; w[cnt]=b*k;),随后将物品剩余总数减去当前基准量(s-=k;),并将基准量按二进制递增规律乘以2(k*=2;)。当while循环结束后,若原物品数量仍有剩余(if(s>0)),则将剩余部分单独打包成最后一件新物品并记录参数(cnt++; v[cnt]=a*s; w[cnt]=b*s;)。完成所有物品的输入与拆分后,将控制01背包遍历的物品总数替换为拆分后的新包总数(n=cnt;)。随后直接套用01背包算法逻辑,开启外层循环依次处理拆分后的每一件新物品(for(int i=1;i<=n;i++)),并开启倒序遍历背包容量的内层循环,从最大容量遍历至当前新物品的体积(for(int j=m;j>=v[i];j--))。在内层循环中执行状态转移,对比不放入该打包物品时的既有价值与放入该打包物品后的总价值,取较大值覆盖更新至当前容量的状态数值中(f[j]=max(f[j],f[j-v[i]]+w[i]);)。在01背包遍历过程彻底结束后,对应最大背包容量的状态数组元素即为所求的最大总价值,将其输出并换行(cout<<f[m]<<endl;),程序结束运行。
1 |
|
分组背包问题
1.思路
【题目描述】
有
组物品和一个容量是 的背包。每组物品有若干个,同一组内的物品最多只能选一个。每件物品的体积是 ,价值是 ,其中 是组号, 是组内编号。求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。输出最大价值。 【题目分析】
本题是动态规划中分组背包模型的基础版本。题目限制每组物品中最多只能选择一件,因此决策状态变为了针对每一组物品,选择“不选”、“选第1件”、“选第2件”……“选第k件”。在利用一维数组进行空间压缩优化时,外层循环遍历物品组,中层循环倒序遍历背包容量,内层循环遍历组内各个物品。中层循环必须严格倒序,以确保当前容量的状态更新是基于上一组的干净状态,从而保证每组至多只有一个物品被选中。此外,因为同组内的物品体积大小不一定单调递增,中层容量循环应直接遍历至0,在最内层遍历具体物品时再进行容量容纳判定。
Q:请你说说分组背包问题的思路和代码结构?
A:分组背包问题的思路是利用动态规划策略,将决策维度设定为物品组,针对每一组枚举选择不装或装入其中某一件物品,从而在满足容量限制及每组最多选一件的约束下推导出总体的最大价值。在代码构建上首先需要定义全局变量,包括限制数组大小的常量(
const int N=110;),用于记录不同背包占用容量下最大总价值的状态数组(int f[N];),分别利用二维数组记录第i组第j个物品体积和价值的数组(int v[N][N],w[N][N];),记录每组物品数量的一维数组(int s[N];),以及记录物品组数和背包总容量的整型变量(int n,m;)。在main函数中,首先读入物品组数与背包最大容量(cin>>n>>m;)。随后进入第一个外层循环读取数据(for(int i=1;i<=n;i++)),先读入当前第i组的物品数量(cin>>s[i];),接着开启内层循环依次读入该组内每一个物品的具体体积和价值(for(int j=1;j<=s[i];j++){cin>>v[i][j]>>w[i][j];})。数据读取完毕后,开启状态转移求解的三重循环。最外层循环依次处理每一组物品(for(int i=1;i<=n;i++))。中层循环遍历背包占用容量,为了确保每一组内部至多只有一个物品被选中,避免同层状态更新复用本组其他物品刚更新过的状态,该循环必须按照容量从大到小的倒序方向进行,且由于组内各物品的体积大小不可预知,容量需一直倒序遍历至0(for(int j=m;j>=0;j--))。在容量循环内部开启最内层循环,遍历当前组内的所有可选物品编号(for(int k=1;k<=s[i];k++))。在最内层循环中,先判定当前的背包剩余容量是否大于等于该物品的体积(if(v[i][k]<=j)),如果满足条件,则对比当前容量在不选该物品时的已有价值,以及装入该物品后剩余容量所对应的最大价值加上该物品自身价值,将两者中的较大值更新至当前容量的状态数值中(f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);)。当所有物品组、容量空间及组内物品均遍历并更新完毕后,对应最大背包容量的状态数组元素即为计算出的最大总价值,将其输出并换行(cout<<f[m]<<endl;),程序结束运行。
2.题目:9. 分组背包问题 - AcWing题库
1 |
|
第五章 动态规划(二):线性DP与区间DP
线性DP1:数字三角形
1.思路
Q:请你说说数字三角形的思路和代码结构?
A:数字三角形的思路是利用动态规划策略,自顶向下递推计算到达每一个节点的最大路径和,通过比对来自左上方和正上方的路径累加值来选取较大者,进而求得从顶部到底层的最大路径数字和。在代码构建上首先需要定义全局变量,包括限制二维数组大小的常量(
const int N=510;),用于记录到达各个节点最大路径和的状态数组以及存储原始三角形数值的数组(int f[N][N],a[N][N];),以及记录三角形层数的整型变量(int n;)。在main函数中,首先读入三角形的总层数(cin>>n;)。接着使用内置函数将状态数组的内存空间统一初始化为极小值负无穷(memset(f,-0x3f,sizeof f);),目的是防止在状态转移时由于越界访问(例如列下标为0)而引入默认的0值,从而干扰可能存在负数数据的路径和计算。随后利用双层循环依次读取三角形每一层的具体数值存入原始数组(cin>>a[i][j];)。数据读取完毕后,直接给动态规划的起点状态赋值,即第一层第一个节点的最大路径和等于其自身数值(f[1][1]=a[1][1];)。随后开启状态转移的双层循环,因为第一层已赋值,外层循环直接从第二层开始遍历至底层(for(int i=2;i<=n;i++)),内层循环遍历每一列(for(int j=1;j<=n;j++))。在内层循环中执行状态转移计算,当前节点的状态等于其左上方节点状态与正上方节点状态两者中的较大值加上当前节点自身的原始数值(f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];)。当整个三角形的状态推导结束后,定义局部变量用于记录最终答案,并同样初始化为负无穷以应对最终结果仍可能为负数的情况(int ans=-0x3f3f3f3f;)。最后通过单层循环遍历底层的每一个状态节点(for(int i=1;i<=n;i++)),通过不断比对更新找出最后一行中的最大值(ans=max(ans,f[n][i]);),将其作为整条路径的最大和输出并换行(cout<<ans<<endl;),程序结束运行。
1 |
|
线性DP2:最长上升子序列I(无需优化)
1.思路
Q:请你说说最长上升子序列I的思路和代码结构?
A:最长上升子序列的思路是利用动态规划策略,通过记录以每个元素为结尾的递增子序列的最大长度,逐个比对当前元素与之前元素的大小关系来推导状态,进而求得整个序列中的最大严格递增长度。在代码构建上首先需要定义全局变量,包括限制数组大小的常量(
const int N=1010;),用于记录以各位置为结尾的最长上升子序列长度的状态数组以及存储原始输入数列的数组(int f[N],a[N];),还有记录数列总长度的整型变量(int n;)。在main函数中,首先读入数列的总长度(cin>>n;),随后利用单层循环依次读取数列中的每一个数字并存入原数组中(for(int i=1;i<=n;i++)cin>>a[i];)。数据读取完毕后开启状态转移的双层循环,外层循环依次计算以每一个位置为结尾的状态(for(int i=1;i<=n;i++))。在处理当前位置时,考虑到每个数字本身至少可以构成一个长度为1的子序列,因此首先将当前位置的状态初始值设为1(f[i]=1;)。接着开启内层循环,遍历排在当前数字前面的所有元素(for(int j=1;j<i;j++)),判断前面的数字是否严格小于当前数字(if(a[j]<a[i]))。如果满足条件,说明当前数字可以拼接在前面该数字所在的递增子序列之后,此时比对不拼接的既有长度与拼接后的新长度,将两者中的较大值覆盖更新至当前位置的状态数值中(f[i]=max(f[i],f[j]+1);)。当整个状态转移双层循环彻底结束后,定义一个局部变量用于记录最终的最大长度并初始化为0(int ans=0;),随后利用单层循环遍历整个状态数组,通过不断比对找出所有计算结果中的最大值(for(int i=1;i<=n;i++)ans=max(ans,f[i]);),最后将其作为整个数列的最长上升子序列长度输出并换行(cout<<ans<<endl;),程序结束运行。
1 |
|
线性DP3:最长上升子序列Ⅱ(需用贪心+二分优化)
1.思路
Q:请你说说最长上升子序列 II的思路和代码结构?
A:最长上升子序列 II的思路是利用贪心策略结合二分查找,通过维护一个记录各长度递增子序列末尾最小值的数组,不断将原序列中的元素替换到该数组中合适的位置以降低末尾数值,从而在降低时间复杂度的同时求得最长递增子序列的长度。在代码构建上首先需要定义全局变量,包括限制数组大小的常量(
const int N=100010;),用于记录各长度递增子序列末尾最小值的状态数组以及存储原始输入数列的数组(int q[N],a[N];),还有记录数列总长度的整型变量(int n;)。在main函数中,首先读入数列的总长度(cin>>n;),随后利用单层循环依次读取数列中的每一个数字并存入原数组中(for(int i=1;i<=n;i++)cin>>a[i];)。数据读取完毕后,定义一个整型变量用于记录当前最长上升子序列的长度并初始化为0(int len=0;)。接着开启遍历原数组的单层循环(for(int i=1;i<=n;i++)),在循环内部针对当前数字执行二分查找以寻找其能接在哪个长度的子序列之后,定义查找区间的左右端点,左端点初始为0,右端点初始为当前的最大长度(int l=0,r=len;)。进入二分查找的while循环,条件为左端点小于右端点(while(l<r)),在循环内部计算中间索引,为了防止当左右端点相差1时由于整数除法向下取整造成的死循环,需要在相加时额外加1(int mid=(l+r+1)>>1;)。随后判断状态数组中该中间索引对应的数值是否严格小于当前遍历到的原数组数字(if(q[mid]<a[i])),如果满足则说明当前数字可以接在长度为mid的子序列后面,便将左端点更新为该中间索引(l=mid;),否则说明当前数字无法接在后面,将右端点缩小至中间索引减一(else r=mid-1;)。二分查找结束后,右端点r即为当前数字能够接上的最长子序列的长度,随后将其更新或追加到状态数组中对应长度加一的位置上(q[r+1]=a[i];),这一步通过替换较大的末尾数值使该长度的子序列末尾元素变得更小,进而让后续数字更容易接上。最后判断如果当前计算出的新长度大于已记录的最大长度变量,则将最大长度递增(if(r+1>len)len++;)。当整个原数组遍历处理彻底结束后,直接输出最终记录的最大长度变量并换行(cout<<len<<endl;),程序结束运行。
2.题目:896. 最长上升子序列 II - AcWing题库
1 |
|
线性DP4:最长公共子序列
1.思路

Q:请你说说最长公共子序列的思路和代码结构?
A:最长公共子序列的思路是利用动态规划策略,通过比对两个字符串在不同长度前缀下的匹配情况,利用二维状态转移方程记录并递推两者的最长公共部分长度,从而求得完整字符串的最长公共子序列总长度。在代码构建上首先需要定义全局变量,包括限制二维数组大小的常量(
const int N=1010;),用于记录两个字符串分别匹配到不同位置时对应公共子序列长度的状态数组(int f[N][N];),用于存储待匹配字符序列的字符数组(char a[N],b[N];),以及记录两个待匹配字符串总长度的整型变量(int n,m;)。在main函数中,首先读入两个字符串的长度边界值(cin>>n>>m;),接着利用格式化输入将两个字符串读入字符数组,为了使后续状态转移过程中的物理下标与逻辑长度保持一致并避免越界,数据统一从数组索引为1的位置开始读入存储(scanf("%s%s",a+1,b+1);)。数据读取完毕后直接开启状态转移的双层循环,外层循环依次遍历第一个字符串的每一个有效字符位置(for(int i=1;i<=n;i++)),内层循环依次遍历第二个字符串的每一个有效字符位置(for(int j=1;j<=m;j++))。在内层循环中执行具体的状态转移推导,首先处理不匹配的常规转移路径,即当前状态直接继承第一个字符串短一个字符或者第二个字符串短一个字符时的最大匹配长度,将两者比对后的较大值赋予当前状态节点(f[i][j]=max(f[i-1][j],f[i][j-1]);)。随后进行字符相等判定分支,如果第一个字符串的当前字符与第二个字符串的当前字符恰好相同(if(a[i]==b[j])),说明该字符可以被纳入公共子序列,此时比对当前刚刚继承的既有状态数值,以及两个字符串均短一个字符时的状态数值加上当前匹配成功的长度1,将两者中的较大值覆盖更新至当前状态节点中(f[i][j]=max(f[i][j],f[i-1][j-1]+1);)。当全量字符的双层遍历更新彻底结束后,二维状态数组在右下角对应两个字符串完整长度索引位置上的数值即为所求的最长公共子序列最大长度,将其输出并换行(cout<<f[n][m]<<endl;),程序结束运行。
1 |
|
线性DP5:最短编辑距离
1.思路
Q:请你说说最短编辑距离的思路和代码结构?
A:最短编辑距离的思路是利用动态规划策略,通过记录两个字符串在不同长度前缀下的最小操作次数,依次推导插入、删除和替换操作对应的状态变化,进而求得将源字符串转换为目标字符串所需的最少操作次数。在代码构建上首先需要定义全局变量,包括限制二维数组大小的常量(
const int N=1010;),用于记录两个字符串分别匹配到不同前缀长度时对应最小操作次数的状态数组(int f[N][N];),用于存储源字符串和目标字符串的字符数组(char a[N],b[N];),以及记录两个字符串各自总长度的整型变量(int n,m;)。在main函数中,首先利用流输入依次读入源字符串的长度、源字符串自身、目标字符串的长度以及目标字符串,为了使状态转移过程中的物理下标与逻辑长度保持一致,字符串数据均统一从数组索引为1的位置开始读入(cin>>n>>a+1>>m>>b+1;)。接着进行动态规划边界状态的初始化,开启单层循环将状态数组第一列的所有元素赋予对应的行索引号(for(int i=1;i<=n;i++)f[i][0]=i;),代表源字符串变为长度为0的空串需要执行连续的删除操作;同理开启循环将状态数组第一行的所有元素赋予对应的列索引号(for(int j=1;j<=m;j++)f[0][j]=j;),代表空串变为目标字符串需要执行连续的插入操作。初始化完成后开启状态转移的双层循环,外层循环依次遍历源字符串的每一个有效字符位置(for(int i=1;i<=n;i++)),内层循环依次遍历目标字符串的每一个有效字符位置(for(int j=1;j<=m;j++))。在内层循环中执行具体的状态转移推导,首先考虑对源字符串进行删除或插入操作的情况,计算源字符串短一个字符时的已知操作次数加一,与目标字符串短一个字符时的已知操作次数加一,将两者比对后的较小值赋予当前状态节点(f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);)。随后依据当前位置的字符是否相同进行判定分支,如果源字符串的当前字符与目标字符串的当前字符恰好相同(if(a[i]==b[j])),说明该位置直接匹配成功无需额外编辑操作,此时比对当前刚刚记录的操作次数与两个字符串均短一个字符时的操作次数,取两者中的较小值覆盖更新当前状态(f[i][j]=min(f[i][j],f[i-1][j-1]););如果两个字符不相等(else),说明该位置需要执行一次字符替换操作才能匹配,则比对当前已记录的操作次数与两个字符串均短一个字符时的操作次数加上这1次替换操作,取较小值覆盖更新当前状态(f[i][j]=min(f[i][j],f[i-1][j-1]+1);)。当全量字符的双层遍历更新彻底结束后,二维状态数组在右下角对应两个字符串完整长度索引位置上的数值即为所求的最短编辑距离,将其输出并换行(cout<<f[n][m]<<endl;),程序结束运行。
1 |
|
线性DP6:编辑距离
1.思路
Q:请你说说编辑距离的思路和代码结构?
A:编辑距离的思路是利用动态规划策略计算两个字符串之间的最短编辑距离,并在此基础上嵌套循环处理多组字符串匹配查询,从而统计出满足编辑操作次数上限要求的字符串数量。在代码构建上首先需要定义全局变量,包括限制数组大小的常量(
const int N=1010;),用于记录两个字符串分别匹配到不同前缀长度时对应最小操作次数的状态数组(int f[N][N];),用于存储初始给定多个字符串的二维字符数组(char str[N][15];),以及记录给定字符串数量和查询次数的整型变量(int n,m;)。在main函数中,首先读入字符串数量与查询次数(cin>>n>>m;)。随后进入单层循环依次读取每一个给定的字符串,为了使动态规划状态转移过程中的物理下标与逻辑长度保持一致以处理边界情况,读入操作统一从每行字符数组索引为1的位置开始存储(cin>>str[i]+1;)。字符串读取完毕后,通过while循环依次处理每一次查询(while(m--))。在查询循环内部,定义局部字符数组存储查询字符串,并定义整型变量存储操作次数上限,同样从索引1开始读入查询字符串及其对应上限(cin>>s+1>>limit;)。接着定义计数变量并初始化为0(int res=0;),利用单层循环遍历之前存储的所有给定字符串(for(int i=1;i<=n;i++)),逐一调用封装好的编辑距离求解函数,判断当前字符串转换到查询字符串的距离是否小于等于上限,如果满足则计数增加(if(edit_distance(str[i],s)<=limit)res++;),当该轮查询的所有匹配对比结束后,将最终统计的符合条件的数量输出并换行(cout<<res<<endl;)。进入edit_distance求解函数,函数接收两个待比较的字符数组作为参数,首先通过标准库函数配合加1的地址偏移量求得两个字符串的实际逻辑长度(int la=strlen(a+1),lb=strlen(b+1);)。接着进行动态规划边界状态的初始化,开启循环将状态数组第一列的元素赋予对应的行索引号(for(int i=1;i<=la;i++)f[i][0]=i;),代表变为长度为0的空串需执行的连续删除操作次数;同理将状态数组第一行的元素赋予对应的列索引号(for(int j=1;j<=lb;j++)f[0][j]=j;),代表空串变为目标字符串需执行的连续插入操作次数。初始化完成后开启状态转移的双层循环,外层循环遍历第一个字符串的字符位置(for(int i=1;i<=la;i++)),内层循环遍历第二个字符串的字符位置(for(int j=1;j<=lb;j++))。在内层循环中执行状态转移,首先计算删除或插入操作的情况,取两者短一个字符时的操作次数加一进行比对,将较小值赋予当前状态节点(f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);)。随后依据当前位置的字符是否相同进行分支判定,如果两字符恰好相同(if(a[i]==b[j])),说明该位置无需额外编辑操作,比对当前记录操作次数与两字符串均短一个字符时的操作次数,取较小值覆盖更新(f[i][j]=min(f[i][j],f[i-1][j-1]););如果不相等(else),则比对当前记录操作次数与两字符串均短一个字符时的操作次数加上一次替换操作的数值,取较小值覆盖更新(f[i][j]=min(f[i][j],f[i-1][j-1]+1);)。双层遍历彻底结束后,返回二维状态数组在对应两字符串完整长度索引位置上的数值即为最短编辑距离(return f[la][lb];)。
2.题目:899. 编辑距离 - AcWing题库
1 |
|
区间DP:石子合并
1.思路
Q:请你说说石子合并的思路和代码结构?
A:石子合并的思路是利用区间动态规划策略,结合前缀和数组快速计算连续区间的总质量,通过依次枚举区间长度、起始位置以及切分点,从小到大推导局部子区间的最小合并代价,最终求得整体的最小合并代价。在代码构建上首先需要定义全局变量,包括限制数组大小的常量(
const int N=310;),用于记录不同区间最小合并代价的二维状态数组(int f[N][N];),用于记录区间前缀和及每堆石子原始质量的数组(int s[N],a[N];),以及记录石子总堆数的整型变量(int n;)。在main函数中,首先读入石子的总堆数(cin>>n;)。随后利用单层循环依次读取每堆石子的质量存入原数组(cin>>a[i];),并同步累加计算前缀和以便在后续状态转移时以常数时间获取任意连续区间的单次合并代价(s[i]=s[i-1]+a[i];)。数据读取与准备完毕后,进入状态转移的三重嵌套循环。由于长度为1的单堆石子本身无需合并,其代价自然为0,因此最外层用于枚举区间长度的循环直接从2开始遍历至最大总堆数(for(int len=2;len<=n;len++))。中层循环用于遍历该长度下的区间起点位置,为防止数组越界,循环终点限定为起终点跨度不超过总堆数(for(int i=1;i+len-1<=n;i++)),并在循环内部计算定义当前区间的左右端点下标(int l=i,r=i+len-1;),同时必须将当前区间范围的状态数值初始化为极大值以保证后续求最小值的比较逻辑能够正常运行(f[l][r]=0x3f3f3f3f;)。接着开启最内层循环遍历当前区间内的所有合法切分点位置(for(int k=l;k<r;k++))。在最内层循环中执行具体的状态转移推导,对比当前记录的该区间既有最小代价,以及在当前切分点处将其拆分为左右两部分后两部分各自的已有合并代价之和加上合并这两个整体所需的当前大区间总石子质量,取两者中的较小值覆盖更新至当前区间的状态数值中(f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);)。当三重循环将所有区间跨度和切分位置的情况全部遍历更新完毕后,二维状态数组在起点为1、终点为n对应索引位置上的数值即为全局所有石子合并的最小总代价,将其输出并换行(cout<<f[1][n]<<endl;),程序结束运行。
2.题目:282. 石子合并 - AcWing题库
1 |
|
第五章 动态规划(三):计数类DP、数位统计DP、状态压缩DP、树形DP、记忆化搜索
计数类DP
1.思路
2.题目:900. 整数划分 - AcWing题库
1 |
|
数位统计DP
1.思路
略
2.题目:338. 计数问题 - AcWing题库
略
状态压缩DP
状态压缩就是用一个整数(通常是它的二进制形式)来表示一个集合或者一种复杂的排列状态。
比如:在传统的DP中,如果我们要记录一排格子的占用情况(比如 5 个格子,有空和占用两种情况),我们可能需要开一个五维数组
f[2][2][2][2][2]。 而在状压 DP 中,我们把这 5 个格子的状态当成一个二进制数,比如10101(十进制的 21),那么我们只需要一维数组f[21]就可以存下这个状态了。这极大地“压缩”了状态的存储空间。
1.思路
(1)蒙德里安的梦想
Q:请你说说蒙德里安的梦想的思路和代码结构?
A:蒙德里安的梦想的思路是利用状态压缩动态规划策略,通过只考虑横向放置的长方形,将其对下一列的占用状态转化为二进制数,并预先筛选出能让剩余连续空位为偶数以合法放置竖向长方形的单列状态及列间转移关系,进而逐列递推计算出完全分割给定棋盘的方案总数。在代码构建上首先需要定义全局变量,包括用于防止方案数相加溢出的长整型别名(
typedef long long ll;),限定行数与二进制状态空间上限的常量(const int N=12,M=1<<N;),用于记录递推至第i列且伸出状态为j的方案总数的二维状态数组(ll f[N][M];),存储单列二进制状态是否合法的布尔数组(bool st[M];),记录每种状态可合法转移的上一列状态集合的二维动态数组(vector<int> state[M];),以及记录当前棋盘行数和列数的整型变量(int n,m;)。在main函数中,通过while循环持续读入行数和列数,并利用逻辑或判断确保当两者不全为零时才继续执行处理逻辑(while(cin>>n>>m,n||m))。进入循环内部,首先通过单层循环预处理单列的所有可能二进制状态是否合法(for(int i=0;i<1<<n;i++)),在循环内定义记录连续0个数的变量和合法性标志(int cnt=0; bool is_valid=true;),接着逐位检查当前二进制串(for(int j=0;j<n;j++)),如果当前位是1(if(i>>j&1)),则判断此前累计的连续0个数是否为奇数(if(cnt&1)),若是说明无法填满竖向方块,将标志置为假并跳出循环(is_valid=false; break;),否则将连续0计数器清零(cnt=0;);如果当前位是0则计数器递增(else cnt++;)。内层循环结束后再次检查末尾剩余的连续0是否为奇数并处理(if(cnt&1)is_valid=false;),将判定结果存入布尔数组(st[i]=is_valid;)。随后预处理合法的状态转移集合,再次遍历当前列的所有状态(for(int i=0;i<1<<n;i++)),先清空当前状态对应的动态数组(state[i].clear();),然后遍历前一列的所有状态(for(int j=0;j<1<<n;j++)),判断两列是否无横向重叠冲突且合并后的空位能合法放置竖向方块(if((i&j)==0&&st[i|j])),若满足则将该状态加入当前列的转移集合中(state[i].push_back(j);)。接着初始化状态数组全为0(memset(f,0,sizeof f);),并设定第0列不伸出任何方块的初始状态方案数为1(f[0][0]=1;)。最后开启按列递推的双层循环,外层遍历列数(for(int i=1;i<=m;i++)),内层遍历当前列所有状态(for(int j=0;j<1<<n;j++)),并遍历当前状态允许转移的所有前一列状态(for(auto k:state[j])),执行状态转移计算进行方案数累加(f[i][j]+=f[i-1][k];)。当全部递推完毕后,输出到达第m列且不向越界列伸出方块的合理方案总数结果(cout<<f[m][0]<<endl;)。
(2)最短Hamilton路径
Q:请你说说最短Hamilton路径的思路和代码结构?
A:最短Hamilton路径的思路是利用状态压缩动态规划策略,通过二进制数串表示图中各节点的访问状态,记录在特定访问状态下且以特定节点为终点时的路径权重总和,并依据前驱节点的合法状态逐步推导得出覆盖所有节点的最短路径长度。在代码构建上首先需要定义全局变量,包括限制节点数与二进制状态空间上限的常量(
const int N=20,M=1<<N;),用于记录不同访问状态及终点节点下对应最小路径权重的二维状态数组以及存储图中各点之间距离的权重矩阵(int f[M][N],w[N][N];),还有记录图中节点总数的整型变量(int n;)。在main函数中,首先读入节点总数(cin>>n;)。随后利用双层循环依次读取图中所有点到点的距离并存入权重矩阵(cin>>w[i][j];)。数据读取完毕后,使用内置函数将状态数组的内存空间统一初始化为正无穷(memset(f,0x3f,sizeof f);),以确保后续求最小值的状态转移逻辑正常生效。接着设定动态规划的初始起点状态,即仅访问过第0个节点且当前正处于该节点的路径长度为0(f[1][0]=0;),其中1对应的二进制表示恰好代表第0位已被访问。随后开启状态转移的三重嵌套循环,最外层循环遍历所有可能的二进制访问状态(for(int i=0;i<1<<n;i++)),中层循环遍历当前所在的终点节点编号(for(int j=0;j<n;j++))。在中层循环内部,首先通过位运算判定当前状态是否包含对节点j的访问(if(i>>j&1)),如果包含,则开启最内层循环遍历所有可能的前驱节点k(for(int k=0;k<n;k++))。在最内层循环中,再次通过位运算判定当前状态是否也包含了对节点k的访问(if(i>>k&1)),如果满足,则执行具体的状态转移推导,对比当前已记录的该状态下到达j的最小路径长度,以及将状态中除去节点j的访问记录后到达前驱节点k的最小路径长度加上从k到j的距离,取两者中的较小值覆盖更新至当前状态数值中(f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]);)。当全量状态及节点的三重遍历彻底结束后,二维状态数组中对应所有节点均被访问且终点为最后一个节点索引位置上的数值即为所求的最短路径长度,将其输出并换行(cout<<f[(1<<n)-1][n-1]<<endl;),程序结束运行。
2.题目:
1 |
|
(2)91. 最短Hamilton路径(旅行商问题TSP) - AcWing题库
1 |
|
树形DP
1.思路
Q:请你说说没有上司的舞会的思路和代码结构?
A:没有上司的舞会的思路是利用树形动态规划结合深度优先搜索,通过自底向上的回溯过程,在保证相邻节点(即直接上下级关系)不被同时选中的约束条件下,分别推导各个节点被选中与不被选中时的最大快乐指数总和。在代码构建上首先需要定义全局变量,包括限制数组大小的常量(
const int N=6010,M=6010;),用于记录对应节点在不选与选中状态下最大快乐指数的二维状态数组(int f[N][2];),用于构建树形结构邻接表的头节点数组、边数组、后继数组及索引指针(int h[N],e[M],ne[M],idx;),记录每个职员快乐指数的数组(int happy[N];),用于判定节点是否存在父节点以寻找树根的布尔数组(bool has_father[N];),以及记录总人数的整型变量(int n;)。在main函数中,首先读入职员总数(cin>>n;),并利用内置函数将邻接表头节点数组初始化为-1(memset(h,-1,sizeof h);)。随后通过单层循环读取每个职员的快乐指数并存入对应数组(for(int i=1;i<=n;i++)cin>>happy[i];)。接着利用循环读取职员间的上下级关系(for(int i=1;i<n;i++)),在循环内部读入下属和上司编号(cin>>a>>b;),标记下属存在父节点(has_father[a]=true;),并调用建边函数由上司向下属建立单向边(add(b,a);)。数据读取与建图完成后,定义根节点变量从1开始寻找(int root=1;),通过while循环遍历直到找到不存在父节点的根节点(while(has_father[root])root++;)。接着直接调用深搜函数对根节点进行处理(dfs(root);)。最后对比根节点被选中与不被选中两种状态下的数值,输出两者中的较大值并换行(cout<<max(f[root][0],f[root][1])<<endl;),程序结束运行。进入dfs深度优先搜索函数,该函数接收当前节点编号作为参数(void dfs(int u)),首先将当前节点被选中状态的初始值设定为其自身的快乐指数(f[u][1]=happy[u];)。随后通过for循环依邻接表遍历当前节点的所有直接下属分支(for(int i=h[u];i!=-1;i=ne[i])),提取下属节点编号(int j=e[i];)并对其递归调用深搜函数(dfs(j);)。该递归机制使得程序持续向下探索至无下属的叶子节点,并在无路可走时解除挂起状态逐层回溯合并结果。在回溯阶段的状态累加操作中,如果当前节点不被选中,则其下属处于可选或不选均可的合法状态,将其下属两种状态中的较大值累加到当前节点不选的状态数值上(f[u][0]+=max(f[j][0],f[j][1]););如果当前节点被选中,则受约束条件限制其下属必须不被选中,直接将下属不选的状态数值累加到当前节点选中的状态数值上(f[u][1]+=f[j][0];),以此逻辑自底向上推导直至整棵树的状态合并完毕。
1 |
|
记忆化搜索
1.思路
Q:请你说说滑雪的思路和代码结构?
A:滑雪的思路是利用记忆化搜索(即动态规划结合深度优先搜索)策略,通过探索从网格中每一个点出发向四个方向所能滑行的最长轨迹,并在搜索过程中利用状态数组保存已计算过的节点结果,从而避免指数级的重复递归遍历,高效求得全局的最长滑行距离。在代码构建上首先需要定义全局变量,包括限制矩阵大小的常量(
const int N=310;),用于记录从各个坐标点出发的最长滑雪区域数的记忆化状态数组以及存储滑雪场各区域高度的矩阵数组(int f[N][N],g[N][N];),记录矩阵行数和列数的整型变量(int n,m;),以及用于控制上下左右四个滑动方向的坐标偏移量数组(int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};)。进入具体的递归求解函数
dp,该函数接收当前所在位置的坐标作为参数(int dp(int x,int y)),内部首先利用引用变量直接绑定当前坐标的状态数组元素,以简化后续的读写更新操作(int &v=f[x][y];)。接着判断该位置是否已经被计算过,如果状态值不为初始标记-1则直接返回该已有结果,以免除重复递归(if(v!=-1)return v;)。若未被计算过,则将当前状态的初始值设为1,代表滑行轨迹至少包含自身这1个区域(v=1;)。随后开启单层循环遍历四个移动方向(for(int i=0;i<4;i++)),计算出相邻区域的新坐标(int xx=x+dx[i],yy=y+dy[i];)。接着判断新坐标是否未越出矩阵边界,并且新区域的高度严格小于当前区域的高度(if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&g[xx][yy]<g[x][y])),若满足向下滑动的条件,则对新坐标发起递归调用,比对当前记录的轨迹长度与向该方向滑动后的递归返回长度加一,取两者中的较大值覆盖更新当前状态数值(v=max(v,dp(xx,yy)+1);)。当所有可能方向均探索完毕后,返回推导出的最大状态值(return v;)。在main函数中,首先读入滑雪场矩阵的行列数(
cin>>n>>m;),随后利用双层循环依次读取每一个区域的高度数据并存入矩阵数组(cin>>g[i][j];)。数据读取完毕后,使用内置函数将记忆化状态数组的内存空间统一初始化为-1,以标记所有点初始均为未访问状态(memset(f,-1,sizeof f);)。接着定义局部变量用于记录全局的最长滑行长度并初始化为0(int res=0;),最后开启双层循环遍历矩阵中的每一个坐标点(for(int i=1;i<=n;i++)),将每个点依次作为起点调用递归函数求解最长滑行长度,并通过不断比对找出所有尝试中的最大值更新至全局变量中(res=max(res,dp(i,j));),将其作为整个滑雪场可完成的最长滑雪区域数输出并换行(cout<<res<<endl;),程序结束运行。
2.题目:901. 滑雪 - AcWing题库
1 |
|
第六讲 贪心
区间问题
1.思路
(1)区间选点
Q:请你说说区间选点的思路和代码结构?
A:区间选点的思路是利用贪心策略,通过将所有区间按照右端点从小到大进行排序,优先选择每个区间的右端点作为覆盖点,以求尽可能多地覆盖后续的区间,从而在遍历全部区间后得出所需的最少点数。在代码构建上首先需要定义全局变量,包括限制数组大小的常量(
const int N=100010;),用于存储区间左右端点的结构体(struct range)并在其中重载小于号运算符以便后续按右端点升序排序(bool operator< (const range &w)const {return r<w.r;}),利用该结构体声明的数组(range[N];),以及记录区间总数的整型变量(int n;)。在main函数中,首先读入区间总数(cin>>n;)。随后利用单层循环依次读取每一个区间的左右端点并存入结构体数组中(cin>>range[i].l>>range[i].r;)。数据读取完毕后,直接调用标准库排序函数对整个结构体数组进行排序(sort(range,range+n);)。接着定义局部变量,其中res用于记录所需的最小点数并初始化为0,end用于记录当前选定点的坐标,并初始化为一个极小值(如-2e9)以保证第一个区间一定能触发新选点操作(int res=0,end=-2e9;)。随后开启单层循环依次遍历排序后的每一个区间(for(int i=0;i<n;i++)),在循环内部进行贪心判断,如果当前记录的选点坐标严格小于该区间的左端点(if(end<range[i].l)),说明该区间尚未被前面的选点覆盖,必须新增一个点,此时将点数计数器加一(res++;),并将当前选点坐标贪心地更新为该区间的右端点(end=range[i].r;)。当所有区间均被遍历判断完毕后,输出最终累加所得的最少点数记录变量并换行(cout<<res<<endl;),程序结束运行。
(2)最大不相交区间数量
Q:请你说说最大不相交区间数量的思路和代码结构?
A:最大不相交区间数量的思路是利用贪心策略,其核心算法与“区间选点”问题完全等价。因为如果集合中存在
个完全不相交的区间,覆盖它们至少需要 个独立的点;而贪心算法证明只要将这 个点分别放置在这 个区间的右端点上,就足以覆盖所有的区间。因此,所需的最少点数就恰好等于最大不相交区间的数量。通过将所有区间按照右端点从小到大进行排序,我们每次贪心地选择结束时间最早的区间(即右端点最小),以便为后续区间留出最大的空间,遇到重叠的区间则直接跳过,从而选出尽可能多的互不相交的区间。在代码构建上首先需要定义全局变量,包括限制数组大小的常量( const int N=100010;),用于存储区间左右端点的结构体(struct range)并在其中重载小于号运算符以便后续按右端点升序排序(bool operator< (const range &w)const {return r<w.r;}),利用该结构体声明的数组(range[N];),以及记录区间总数的整型变量(int n;)。在main函数中,首先读入区间总数(cin>>n;)。随后利用单层循环依次读取每一个区间的左右端点并存入结构体数组中(cin>>range[i].l>>range[i].r;)。数据读取完毕后,直接调用标准库排序函数对整个结构体数组进行排序(sort(range,range+n);)。接着定义局部变量,其中res用于记录选出的最大不相交区间数量(即点数)并初始化为0,end用于记录当前已选中区间的右端点边界,并初始化为一个极小值(如-2e9)以保证第一个区间一定能被选中(int res=0,end=-2e9;)。随后开启单层循环依次遍历排序后的每一个区间(for(int i=0;i<n;i++)),在循环内部进行贪心判断,如果当前记录的边界坐标严格小于该区间的左端点(if(end<range[i].l)),说明该区间与之前选中的区间均不相交,此时将区间计数器加一(res++;),并将当前边界坐标贪心地更新为该区间的右端点(end=range[i].r;)。当所有区间均被遍历判断完毕后,输出最终累加所得的最大不相交区间数量并换行(cout<<res<<endl;),程序结束运行。
(3)区间分组
Q:请你说说区间分组的思路和代码结构?
A:区间分组的思路是利用贪心策略结合优先队列(小根堆)来解决。由于该算法目标是在数轴上进行连续的状态划分与分组,必须按照区间的左端点从小到大进行升序排序,以确保在处理当前区间时,左侧的所有覆盖状态和冲突关系均已确定。遍历区间时,我们只需关注当前所有已分配的分组中结束时间最早的那一个。如果当前区间的左端点小于或等于最早的分组结束时间(题意说明包括端点也算相交),说明它与现有的所有组都存在重叠,只能为其单独开辟一个新组;如果大于最早的结束时间,说明可以将当前区间接在该组后面,并更新该组的最晚结束时间。使用小根堆可以完美满足这一“动态获取最小值”的需求,最终堆内的元素个数即为所求的最小分组组数。
在代码构建上首先需要定义全局变量,包括限制数组大小的常量(
const int N=100010;),用于存储区间左右端点的结构体(struct range)并在其中重载小于号运算符以便后续按左端点升序排序(bool operator< (const range &w)const {return l<w.l;}),利用该结构体声明的数组(range[N];),以及记录区间总数的整型变量(int n;)。在main函数中,首先读入区间总数(cin>>n;)。随后利用单层循环依次读取每一个区间的左右端点并存入结构体数组中(cin>>range[i].l>>range[i].r;)。数据读取完毕后,调用标准库函数对整个结构体数组进行排序(sort(range,range+n);)。接着定义一个小根堆(优先队列)用于动态维护和获取各分组的右端点数值(priority_queue<int,vector<int>,greater<int> > heap;)。随后开启单层循环依次遍历排序后的每一个区间(for(int i=0;i<n;i++)),将当前区间赋值给局部变量(auto x=range[i];)。在循环内部进行贪心判断,如果当前堆为空,或者堆顶记录的最早结束时间大于等于当前区间的左端点(if(heap.empty()||heap.top()>=x.l)),说明产生冲突,必须新开一个分组,直接将当前区间的右端点压入堆中(heap.push(x.r););否则,说明不产生冲突,当前区间可以复用最早结束的那个分组,先将旧的堆顶弹出(heap.pop();),然后再将当前区间的右端点压入堆中以更新该分组的新结束时间(heap.push(x.r);)。当所有区间均被遍历判断完毕后,代表总分组数量的堆大小即为最终答案,将其输出并换行(cout<<heap.size()<<endl;),程序结束运行。
(4)区间覆盖
Q:请你说说区间覆盖的思路和代码结构?
A:区间覆盖的思路是利用贪心策略结合双指针算法。作为典型的线性扫描问题,为了在数轴上自左向右进行连续覆盖,首先需要将所有区间按照左端点从小到大进行排序。随后设定待覆盖的目标起始点,每次在所有左端点能够覆盖当前目标起始点的区间中,贪心地挑选出一个右端点最大的区间,以此确保单次选择能够向右延伸得尽可能远。选定后,将目标起始点更新为该最大右端点,并继续寻找下一个最优区间,直到目标终点被完全覆盖;若中途发现能够延伸的最大右端点仍够不到当前目标起始点,则说明出现断层,无法完成覆盖。
在代码构建上首先需要定义全局变量,包括限制数组大小的常量(
const int N=100010;),用于存储区间左右端点的结构体(struct range)并在其中重载小于号运算符以便后续按左端点升序排序(bool operator< (const range &w)const {return l<w.l;}),利用该结构体声明的数组(range[N];),以及记录提供区间总数的整型变量(int n;)。在main函数中,首先读入待覆盖指定区间的左右端点(cin>>st>>ed;),接着读入给定区间的总数(cin>>n;)。随后利用单层循环依次读取每一个给定区间的左右端点并存入结构体数组中(cin>>range[i].l>>range[i].r;)。数据读取完毕后,调用标准库函数对整个结构体数组按左端点进行排序(sort(range,range+n);)。接着定义局部变量,其中
res用于记录所使用的最少区间数量并初始化为0,success作为布尔型标志位记录是否成功完全覆盖,初始化为false。随后开启外层单层循环依次遍历排序后的每一个区间(for(int i=0;i<n;i++))。在循环内部应用双指针思想,定义内层指针j初始等于当前外层指针i,并定义变量r记录当前能找到的最大右端点,初始化为一个极小值(int j=i,r=-2e9;)。接着开启内层while循环,条件为指针未越界且当前区间左端点小于等于待覆盖起点(while(j<n&&range[j].l<=st)),在循环内不断比对并提取能覆盖起点的区间中最大的右端点,同时指针j右移(r=max(r,range[j].r); j++;)。内层循环结束后,进行三种情况的判断:第一,如果找到的最大右端点仍小于当前待覆盖起点(
if(r<st)),说明区间中间有断层,直接将结果置为-1并跳出外层循环(res=-1; break;);第二,如果正常衔接,则区间使用数量加一(res++;),紧接着判断该最大右端点是否已经大于等于总目标终点(if(r>=ed)),若满足则说明覆盖完成,将成功标志置为真并跳出循环(success=true; break;);第三,若尚未覆盖到终点,则将新的待覆盖起点更新为刚找到的最大右端点(st=r;),同时由于内层指针j已经遍历过了这些区间,为了避免外层循环重复遍历,将外层指针直接快进更新至j-1的位置(i=j-1;)。当循环结束或被打破后,最后判断如果未成功覆盖全过程(if(!success)),则将结果强制置为-1(res=-1;)。最后输出结果记录变量并换行(cout<<res<<endl;),程序结束运行。
2.题目
1 |
|
1 |
|
1 |
|
1 |
|
Huffman树
1.思路
Q:请你说说合并果子的思路和代码结构?
A:合并果子的思路是利用贪心策略,其核心模型就是经典的哈夫曼树(Huffman Tree)。为了使总耗费的体力最小,我们应该始终优先合并当前重量最小的两堆果子,这样可以保证较小的重量被重复累加的次数最多,较大的重量被累加的次数最少。由于在合并过程中会不断产生新的果子堆,我们需要一个能够动态维护最小值的数据结构,因此优先队列(小根堆)是解决此问题的完美选择。
在代码构建上首先需要定义全局变量,即记录果子种类数(堆数)的整型变量(
int n;)。在main函数中,首先读入果子的总堆数(cin>>n;)。接着利用C++标准模板库定义一个小根堆(优先队列),用于自动对插入的数据进行升序维护(priority_queue<int,vector<int>,greater<int> > heap;)。随后利用while循环依次读取每堆果子的初始重量,并将其全部压入小根堆中(while(n--){int x; cin>>x; heap.push(x);})。数据全部读入并自动构建好小根堆后,定义一个局部变量用于累加每次合并所耗费的体力总和,并初始化为0(int res=0;)。接下来开启核心的合并循环,循环的条件是堆内的元素个数严格大于1(
while(heap.size()>1)),因为当只剩下最后1堆时说明所有合并操作已经完成。在循环内部,连续两次调用top()函数获取当前堆顶的最小元素和次小元素,并分别用变量a和b记录,每次获取后都要调用pop()函数将其从堆中弹出(int a=heap.top();heap.pop(); int b=heap.top();heap.pop();)。然后将这两堆果子的重量之和累加到体力耗费总和变量中(res+=a+b;),最后再将合并后的新果子堆重量重新压入小根堆中参与后续的排序与合并(heap.push(a+b);)。当循环彻底结束时,最终累加所得的体力耗费总和变量即为最小体力耗费值,将其输出并换行(cout<<res<<endl;),程序结束运行。
2.题目:148. 合并果子 - AcWing题库
1 |
|
排序不等式
1.思路
Q:请你说说排队打水的思路和代码结构?
A:排队打水的思路是利用贪心策略,其核心思想类似于操作系统中的最短任务优先调度算法。为了使所有人的总等待时间最小,应该让打水时间短的人排在前面。这是因为排在第
个位置(下标从0开始)的人在打水时,排在他后面的 个人都需要原地等待他耗费的时间。因此,只需将所有人的打水时间从小到大进行升序排序,就能确保让最多的人等待最短的时间,从而使全局的等待时间总和达到最小。在代码构建上首先需要定义全局变量,包括限制数组大小的常量( const int N=100010;),用于存储每个人装满水桶所需时间的整型数组(int t[N];),以及记录排队总人数的整型变量(int n;)。在main函数中,首先读入排队的总人数(cin>>n;)。随后利用单层循环依次读取每个人的打水时间并存入数组中(cin>>t[i];)。数据读取完毕后,直接调用标准库排序函数对整个时间数组进行升序排序(sort(t,t+n);)。接着定义一个长整型局部变量用于累加总的等待时间,并初始化为0(long long res=0;),此处必须使用long long类型是因为当最大为 时,总等待时间累加可能会达到 级别,从而导致标准整型 int溢出。随后开启单层循环依次遍历排序后的数组(for(int i=0;i<n;i++)),在循环内部计算当前这名打水者对其后排队者的延误时间,将其自身的打水时间乘以需要等待他的剩余人数(即n-1-i)并累加到结果变量中(res+=t[i]*(n-1-i);)。当所有打水者的延误时间遍历累加完毕后,输出最终的总等待时间并换行(cout<<res<<endl;),程序结束运行。
2.题目:913. 排队打水 - AcWing题库
1 |
|
绝对值不等式
1.思路
Q:请你说说货仓选址的思路和代码结构?
A:货仓选址的思路是利用绝对值不等式(中位数定理)结合贪心策略。问题要求在数轴上找一个点,使其到所有给定商店的绝对距离之和最小。我们可以将商店按照坐标首尾两两配对:最左和最右一组、次左和次右一组以此类推。对于任意一对商店,根据绝对值不等式,当且仅当货仓建在它们两者的坐标闭区间内部时,到这两个商店的距离之和最小(恒等于这两家商店之间的距离)。为了让所有首尾配对的区间都能同时满足该最小化条件,货仓的最优选址必须处于所有这些区间的交集之中,而这个交集恰好就是整组坐标序列的中位数点。因此,只需将坐标排序,选定中位数点后累加所有点到它的距离即可。
在代码构建上首先需要定义全局变量,包括限制数组大小的常量(
const int N=100010;),用于存储各商店坐标的整型数组(int d[N];),以及记录商店总数的整型变量(int n;)。在main函数中,首先读入商店总数(cin>>n;)。随后利用单层循环依次读取每一个商店的坐标并存入数组中(cin>>d[i];)。数据读取完毕后,直接调用标准库排序函数对坐标数组进行升序排序(sort(d,d+n);),以此确立商店在数轴上的绝对顺序以寻找中位数。接着定义一个整型局部变量用于累加最小距离总和,并初始化为0(int res=0;)。随后开启单层循环依次遍历排序后的所有坐标(for(int i=0;i<n;i++)),在循环内部,通过n/2获取排序后数组的中位数值d[n/2]作为最优货仓坐标(对于奇数个数恰好是正中间的数,偶数个数则是中间偏右的数,均满足题意),计算当前商店坐标与该中位数坐标的差值,并利用标准库绝对值函数求出正向距离后累加到结果变量中(res+=abs(d[i]-d[n/2]);)。当所有商店的距离遍历累加完毕后,输出最终的总距离之和并换行(cout<<res<<endl;),程序结束运行。
2.题目:104. 货仓选址 - AcWing题库
1 |
|
推公式
1.思路
Q:请你说说耍杂技的牛的思路和代码结构?
A:耍杂技的牛的思路是利用贪心策略解决最大值最小化问题。为了使所有奶牛的风险值(即头顶上方所有牛的总重量减去自身强壮程度)中的最大值尽可能小,我们应该将重量和强壮程度之和(
)较小的奶牛放在上面,较大的放在底部。通过数学推导(微扰法)可以证明,当存在相邻的两头牛时,按照 升序排列能严格保证这两头牛中的最大风险值变得更小,进而推导出全局最优解。 在代码构建上首先需要定义全局变量,包括限制数组大小的常量(
const int N=50010;),用于存储每头奶牛重量与强壮程度的结构体(struct cow),并在其中重载小于号运算符以便后续按重量与强壮程度之和进行升序排序(bool operator< (const cow &c)const {return w+s<c.w+c.s;}),利用该结构体声明的数组(cow[N];),以及记录奶牛总数的整型变量(int n;)。在main函数中,首先读入奶牛的总数(cin>>n;)。随后利用单层循环依次读取每头奶牛的重量和强壮程度并存入结构体数组中(cin>>cow[i].w>>cow[i].s;)。数据读取完毕后,直接调用标准库排序函数对整个结构体数组完成排序(sort(cow,cow+n);)。接着定义两个局部变量,其中
sum用于累加当前奶牛头顶上所有奶牛的总重量并初始化为0;res用于记录所有奶牛风险值中的最大值,由于奶牛的强壮程度可能远大于其头顶的总重量从而导致风险值为负,因此必须将其初始化为一个极小的负数(如-2e9)以保证正常进行最大值比对(int sum=0,res=-2e9;)。随后开启单层循环自顶向下依次遍历排序后的每一头奶牛(for(int i=0;i<n;i++)),在循环内部,首先计算当前奶牛的风险值(即头顶累加重量减去自身强壮程度),并与已记录的最大风险值进行比对,取较大者覆盖更新(res=max(res,sum-cow[i].s););完成当前奶牛风险值的评估后,再将其自身的重量累加到sum变量中供下一头奶牛使用,这一先后顺序完美契合了“奶牛无需承受自身重量”的物理逻辑(sum+=cow[i].w;)。当所有奶牛均被遍历并计算完毕后,输出最终记录的风险值最大值(此时即为最优排序下的最小可能值)并换行(cout<<res<<endl;),程序结束运行。
1 |
|
完结撒花~
