要怎么办呢牛
要怎么办呢牛
全部文章
题解
归档
标签
去牛客网
登录
/
注册
要怎么办呢牛的博客
记录日常、思考、算法
全部文章
/ 题解
(共23篇)
序列重排
语法收获:vector可以用于二元组、三元组和多元组的大小比较,支持字典序,类似于pair 思路 思路1 正解证明 这是一道构造+思维题目,题目本身具有很强的性质,如果能够找到这个性质,就能够很轻松的求解,但是如果没想到,就只能暴搜了。通过证明,我们可以发现符合必要条件的的序列是唯一的,所以我们的...
DFS
思维题
构造
2022-01-16
0
546
马蹄铁
思路 因为这道题目的数据范围很小,可以直接使用DFS搜索所有的情况。 我们先来分析一下合法括号字符串的特点: 左半部分全是左括号,右半部分全是右括号 左右括号数量相等 再看一下左右括号状态的转移: 如果当前字符串最右边是左括号,那么它可以接收左括号或者右括号 如果当前字符串最右边是右括号,那么...
DFS
括号序列
2022-01-15
0
1114
拖拉机
思路 首先,读题把原问题抽象为模型(矩阵),然后思考如何转化为具体的算法,可以发现,这个问题可以转化为最短路模型, 点是所有的格子,边是上下左右四个方向。有障碍物时,点权为1,空地点权则为0。移除干草捆的最小数量就是起点到 原点(0,0)的最短距离。 经过上述分析,我们就把原题转化为了最短路模型...
双端队列BFS
最短路
图论
Dijkstra
2022-01-14
0
344
岛
思路 首先,阅读题目,抽象出来问题的模型。这里有个十分重要的点,想通之后就会变得简单些 问题中说水位是连续上升的,但是仔细一想,只有水位达到某个山的高度时,题目的状态才会发生变化,当水位在其他位置时无论怎么变化对题目状态是没有丝毫影响的。所以,我们只需要考虑题目中所有出现过的高度就行了 然后,考...
枚举
排序
2022-01-13
0
324
城堡问题
思路 这道题目乍一看感觉挺复杂的,其实它的本质还是一个Flood Fill算法,代码还是那些,大概只有一行不一样。 首先来看这个模型,一个房间其实就是一个连通块,题目让求所有的连通块的数量还有最大的面积,那无非就是使用BFS 或者DFS遍历一遍图。问题的关键在于这个输入好复杂啊,有点不明所以,但是经...
DFS
BFS
Flood Fill
二进制
2022-01-13
0
375
奶牛选美
思路 首先,发现题目的数据范围是1≤N,M≤50,很小,502=250050^2=2500502=2500,是三次方级别,如果把两个断点都枚举一遍,大概是10610^6106级别,不会超时。 把题目意思抽象出来大致意思是: 给定两个顶点集合,在两个集合中各找一个点,求两个点之间的最短距离(这里的路...
DFS
BFS
Flood Fill
曼哈顿距离
枚举
2022-01-13
0
405
有向图的拓扑序列
思路 拓扑排序其实就是一个BFS的搜索过程,注意如何使用队列来维护的,另外,还要注意一下图的存储方式 const int N = 1e5 + 10;//数据范围,一般边数组要比点数组多开一倍空间 int n, m;//点数和边数 int h[N], e[N], ne[N], idx = 0; vo...
拓扑排序
图论
BFS
2022-01-12
0
592
图中点的层次
典型的bfs最短路搜索 框架 void bfs() { q.push(起点); while(队列不空) { auto t = 队首元素; for(所有相邻节点) { 如果可以扩展,就扩展,入队;...
BFS
2022-01-12
0
318
树的重心
本题的本质是树的dfs, 每次dfs可以确定以u为重心的最大连通块的节点数,并且更新一下ans。 也就是说,dfs并不直接返回答案,而是在每次更新中迭代一次答案。 树的dfs框架 //数组建立的邻接表 int h[N], e[N * 2], ne[N * 2], idx; void add(int...
DFS
树
2022-01-12
0
465
八数码
重点在于如何表示状态和如何进行状态转移 框架 void bfs() { q.push(起点); while(队列不空) { auto t = 队首元素; for(所有相邻节点) { 如果可以扩展...
BFS
2022-01-12
0
483
首页
上一页
1
2
3
下一页
末页