要怎么办呢牛

题解

/ 注册

全部文章 / 题解（共23篇）

序列重排

语法收获：vector可以用于二元组、三元组和多元组的大小比较，支持字典序，类似于pair 思路思路1 正解证明这是一道构造+思维题目，题目本身具有很强的性质，如果能够找到这个性质，就能够很轻松的求解，但是如果没想到，就只能暴搜了。通过证明，我们可以发现符合必要条件的的序列是唯一的，所以我们的...

DFS 思维题构造

2022-01-16

0 545

马蹄铁

思路因为这道题目的数据范围很小，可以直接使用DFS搜索所有的情况。我们先来分析一下合法括号字符串的特点：左半部分全是左括号，右半部分全是右括号左右括号数量相等再看一下左右括号状态的转移：如果当前字符串最右边是左括号，那么它可以接收左括号或者右括号如果当前字符串最右边是右括号，那么...

DFS 括号序列

2022-01-15

0 1117

拖拉机

思路首先，读题把原问题抽象为模型（矩阵），然后思考如何转化为具体的算法，可以发现，这个问题可以转化为最短路模型，点是所有的格子，边是上下左右四个方向。有障碍物时，点权为1，空地点权则为0。移除干草捆的最小数量就是起点到原点（0，0）的最短距离。经过上述分析，我们就把原题转化为了最短路模型...

双端队列BFS 最短路图论 Dijkstra

2022-01-14

0 350

岛

思路首先，阅读题目，抽象出来问题的模型。这里有个十分重要的点，想通之后就会变得简单些问题中说水位是连续上升的，但是仔细一想，只有水位达到某个山的高度时，题目的状态才会发生变化，当水位在其他位置时无论怎么变化对题目状态是没有丝毫影响的。所以，我们只需要考虑题目中所有出现过的高度就行了然后，考...

枚举排序

2022-01-13

0 336

城堡问题

思路这道题目乍一看感觉挺复杂的，其实它的本质还是一个Flood Fill算法，代码还是那些，大概只有一行不一样。首先来看这个模型，一个房间其实就是一个连通块，题目让求所有的连通块的数量还有最大的面积，那无非就是使用BFS 或者DFS遍历一遍图。问题的关键在于这个输入好复杂啊，有点不明所以，但是经...

DFS BFS Flood Fill 二进制

2022-01-13

0 379

奶牛选美

思路首先，发现题目的数据范围是1≤N,M≤50，很小，502=250050^2=2500502=2500,是三次方级别，如果把两个断点都枚举一遍，大概是10610^6106级别，不会超时。把题目意思抽象出来大致意思是：给定两个顶点集合，在两个集合中各找一个点，求两个点之间的最短距离（这里的路...

DFS BFS Flood Fill 曼哈顿距离枚举

2022-01-13

0 407

有向图的拓扑序列

思路拓扑排序其实就是一个BFS的搜索过程，注意如何使用队列来维护的，另外，还要注意一下图的存储方式 const int N = 1e5 + 10;//数据范围，一般边数组要比点数组多开一倍空间 int n, m;//点数和边数 int h[N], e[N], ne[N], idx = 0; vo...

拓扑排序图论 BFS

2022-01-12

0 591

图中点的层次

典型的bfs最短路搜索框架 void bfs() { q.push(起点); while(队列不空) { auto t = 队首元素; for(所有相邻节点) { 如果可以扩展，就扩展，入队;...

BFS

2022-01-12

0 315

树的重心

本题的本质是树的dfs，每次dfs可以确定以u为重心的最大连通块的节点数，并且更新一下ans。也就是说，dfs并不直接返回答案，而是在每次更新中迭代一次答案。树的dfs框架 //数组建立的邻接表 int h[N], e[N * 2], ne[N * 2], idx; void add(int...

DFS 树

2022-01-12

0 456

八数码

重点在于如何表示状态和如何进行状态转移框架 void bfs() { q.push(起点); while(队列不空) { auto t = 队首元素; for(所有相邻节点) { 如果可以扩展...

BFS

2022-01-12

0 481