ZZZYM

分类

知识整理(2) 题解(19)

/ 注册

全部文章（共21篇）

题解 | #[NOIP2002]字串变换#

字串变换参考题解思路由于字符串变换的状态很多，空间复杂度和时间复杂度过大，所以采用双向广搜代码 #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, i...

广度优先搜索

2022-02-21

0 482

题解 | #迷宫#

迷宫类似的一道题的题解参考博客思路思路与上面那道类似的题目基本一致，唯一需要注意的是：对当前出队结点ttt，如果ttt的四个方向上有传送门，不仅要把ttt的四个方向中合法方向加入队列，还需要把所有传送门所在的点加入队列，而不是等到出队的点是传送门时再将所有传送门加入队列。具体地，可以参考...

广度优先搜索

2022-02-21

0 429

题解 | #maze#

maze 思路将每个点上的入口到对应出口也看成一条路径, 只不过从这条路径走距离一次+3 然后就是普通的bfs，注意队列要使用优先队列, 因为此时的队列不再具备步数的单调性，需要人为保证步数单调性。优先队列元素定义如下，注意优先队列的重载，可以参考《算法笔记》P223 struct Node ...

广度优先搜索

2022-02-20

0 386

题解 | #送外卖#

送外卖思路(反向建图+bfs) 注意本题所求的是最小字典序的字符串，而不是最小长度的字符串，所以需要反向建图，求出state[i]=truestate[i]=truestate[i]=true表示点iii可以到达点nnn(反向建图的bfs1函数中结点编号1-n，求最小字典序的bfs函数中结点编号...

广度优先搜索

2022-02-20

8 524

题解 | #寻找道路#

寻找道路思路建两个图, 一个图是原图，一个图是将原图的边全部反向后的图，在反向图中以终点ed为起点进行bfs遍历，标记所有遍历到的点state[i]=true 在原图上进行bfsbfsbfs遍历，在原本bfs将点加入队列的条件的基础上，增加一个条件：如果一个点jjj的所有邻接点的statest...

广度优先搜索

2022-02-20

0 484

题解 | #模拟战役#

模拟战役思路 Flood Fill 代码 #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, int> PII; typedef pair<doub...

广度优先搜索

2022-02-20

0 376

题解 | #智乃买瓜(another version)#

智乃买瓜(another version) 思路 iii从1到m枚举dp数组, 如果dp[1]>0dp[1]>0dp[1]>0, 说明有dp[1]dp[1]dp[1]个重量为2的瓜, 因为重量和为1的方案只能由1个重量为2的瓜买一半得到。对dp数组中的每一项, 消除重量为2的瓜...

动态规划

2022-02-20

0 357

题解 | #I 智乃的密码#

2022牛客寒假算法基础集训营3——I 智乃的密码原题链接思路(双指针) iii: 枚举密码的左边界 j−1j-1j−1: 表示第一个满足条件3(包含至少三种字符)的右边界对每个i,j,合法左边界l=max(j−1,i+L−1),合法右边界r=min(n−1,i+R−1)对每个i,j, 合法...

双指针

2022-02-20

0 310

题解 | #小沙的魔法#

B 小沙的魔法原题链接思路首先，将问题转化为：将高度为hih_ihi的城市降为0 如果不进行合并操作，需要进行ans=∑i=1nhians=\sum _{i=1} ^ {n}h_ians=∑i=1nhi次操作2 对每条边a−b(a和b为城市编号)a-b(a和b为城市编号)a−b(a和b...

贪心并查集

2022-02-13

2 406

题解 | #满意的集合#

牛客小白月赛43_E题满意的集合题目链接题解链接思路十进制数字各位之和%3=0\%3=0%3=0, 则是一种可行的方案 dp[i][j]dp[i][j]dp[i][j]: 表示从1-i数字中选，十进制数字各位之和%3=j\%3=j%3=j的方案个数，则dp数组第二维只要开3即可。最后答...

动态规划

2022-01-14

3 377