要怎么办呢牛
要怎么办呢牛
全部文章
分类
题解(23)
归档
标签
去牛客网
登录
/
注册
要怎么办呢牛的博客
记录日常、思考、算法
全部文章
(共7篇)
序列重排
语法收获:vector可以用于二元组、三元组和多元组的大小比较,支持字典序,类似于pair 思路 思路1 正解证明 这是一道构造+思维题目,题目本身具有很强的性质,如果能够找到这个性质,就能够很轻松的求解,但是如果没想到,就只能暴搜了。通过证明,我们可以发现符合必要条件的的序列是唯一的,所以我们的...
DFS
思维题
构造
2022-01-16
0
539
马蹄铁
思路 因为这道题目的数据范围很小,可以直接使用DFS搜索所有的情况。 我们先来分析一下合法括号字符串的特点: 左半部分全是左括号,右半部分全是右括号 左右括号数量相等 再看一下左右括号状态的转移: 如果当前字符串最右边是左括号,那么它可以接收左括号或者右括号 如果当前字符串最右边是右括号,那么...
DFS
括号序列
2022-01-15
0
1110
城堡问题
思路 这道题目乍一看感觉挺复杂的,其实它的本质还是一个Flood Fill算法,代码还是那些,大概只有一行不一样。 首先来看这个模型,一个房间其实就是一个连通块,题目让求所有的连通块的数量还有最大的面积,那无非就是使用BFS 或者DFS遍历一遍图。问题的关键在于这个输入好复杂啊,有点不明所以,但是经...
DFS
BFS
Flood Fill
二进制
2022-01-13
0
372
奶牛选美
思路 首先,发现题目的数据范围是1≤N,M≤50,很小,502=250050^2=2500502=2500,是三次方级别,如果把两个断点都枚举一遍,大概是10610^6106级别,不会超时。 把题目意思抽象出来大致意思是: 给定两个顶点集合,在两个集合中各找一个点,求两个点之间的最短距离(这里的路...
DFS
BFS
Flood Fill
曼哈顿距离
枚举
2022-01-13
0
402
树的重心
本题的本质是树的dfs, 每次dfs可以确定以u为重心的最大连通块的节点数,并且更新一下ans。 也就是说,dfs并不直接返回答案,而是在每次更新中迭代一次答案。 树的dfs框架 //数组建立的邻接表 int h[N], e[N * 2], ne[N * 2], idx; void add(int...
DFS
树
2022-01-12
0
453
n-皇后问题
框架 void dfs(开始位置 u) { if(以后搜索完) { 输出结果; return; } //枚举在这个位置可能转移到的所有状态 for(所有可能转移到的状态) { 转移到新状态; ...
DFS
2022-01-12
0
318
排列数字[全排列]
把搜索的过程想象成一棵树,一共有n个位置需要填写,我们的顺序是从第一个位置开始向后填写,在过程中需要注意记录哪些数字还没有填写,还有,记得恢复状态 //枚举第u个位置 void dfs(int u) { if(已经遍历完) { 输出结果; return; ...
DFS
2022-01-12
0
434