🙄

语法收获：vector可以用于二元组、三元组和多元组的大小比较，支持字典序，类似于pair 思路 思路1 正解证明 这是一道构造+思维题目，题目本身具有很强的性质，如果能够找到这个性质，就能够很轻松的求解，但是如果没想到，就只能暴搜了。通过证明，我们可以发现符合必要条件的的序列是唯一的，所以我们的必要条件就变成了充要条件，我们就可以利用这个条件轻松求解。 思路2 DFS枚举所有情况 在周赛的时候，我是直接想的DFS，害，刚学DFS没多久，这是第一个自己做出来的DFS😂😂，但是它的正解竟然还不是DFS！ 大致思路就是枚举每一位，如果前一个位置的数字确定了，后一位只有两种情况，这样不断地去...

思路 因为这道题目的数据范围很小，可以直接使用DFS搜索所有的情况。 我们先来分析一下合法括号字符串的特点： 左半部分全是左括号，右半部分全是右括号 左右括号数量相等 再看一下左右括号状态的转移： 如果当前字符串最右边是左括号，那么它可以接收左括号或者右括号 如果当前字符串最右边是右括号，那么它只能接收右括号 关于实现，可以在dfs函数上加几个参数，代表已经存在的l和r的数量，另外dfs函数开始的地方要标记一下，在dfs函数结束前面要恢复状态。 代码 //普通DFS #include<bits/stdc++.h> using namespace std; cons...

思路 首先，读题把原问题抽象为模型（矩阵），然后思考如何转化为具体的算法，可以发现，这个问题可以转化为最短路模型， 点是所有的格子，边是上下左右四个方向。有障碍物时，点权为1，空地点权则为0。移除干草捆的最小数量就是起点到 原点（0，0）的最短距离。 经过上述分析，我们就把原题转化为了最短路模型，我们可以使用Dijkstra算法求解，但是注意到一个性质： 在这个图中，点权只能取1或者0 具有这种性质的最短路可以使用双端队列BFS求解，能够在线性时间内完成求解。 因为只存在0和1， 我们可以把Dijkstra算法中的堆简化成双端队列，从而省去了O(logn)O(logn)O(logn)...

思路 首先，阅读题目，抽象出来问题的模型。这里有个十分重要的点，想通之后就会变得简单些 问题中说水位是连续上升的，但是仔细一想，只有水位达到某个山的高度时，题目的状态才会发生变化，当水位在其他位置时无论怎么变化对题目状态是没有丝毫影响的。所以，我们只需要考虑题目中所有出现过的高度就行了 然后，考虑问题的规模时1<=N<=1051<=N<=10^51<=N<=105，大致上可以使用O(n)O(n)O(n)或者O(nlogn)O(nlogn)O(nlogn)的算法求解。我们可以考虑枚举一下所有高度。于是，对每一个高度，我们要考虑所有发生变化的山。如何做？我们...

思路 这道题目乍一看感觉挺复杂的，其实它的本质还是一个Flood Fill算法，代码还是那些，大概只有一行不一样。 首先来看这个模型，一个房间其实就是一个连通块，题目让求所有的连通块的数量还有最大的面积，那无非就是使用BFS 或者DFS遍历一遍图。问题的关键在于这个输入好复杂啊，有点不明所以，但是经过仔细分析，就可以发现这是一个二进制形式的表示方法，对于某个方向，只需要看特定的第几位是零还是1就行了。 为了方便，这里顶的的方向向量与之前的不太一致，主要是为了使得方向i和二进制第i位对应。然后判断从当前块能不能走到相邻的块只需要一句话就可以了。十分巧妙 if(g[a][b] >> i...

思路 首先，发现题目的数据范围是1≤N,M≤50，很小，502=250050^2=2500502=2500,是三次方级别，如果把两个断点都枚举一遍，大概是10610^6106级别，不会超时。 把题目意思抽象出来大致意思是： 给定两个顶点集合，在两个集合中各找一个点，求两个点之间的最短距离（这里的路线是只能横着走或者竖着走） 接下来给出一个性质 假设距离最短的路线的两个端点分别是(x1,y1)(x_1,y_1)(x1​,y1​)和(x2,y2)(x_2,y_2)(x2​,y2​)，那么最短距离就等于∣x1−y1∣+∣x2−y2∣|x_1-y_1| + |x_2-y_2|∣x1​−y1​∣+...

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

典型的bfs最短路搜索 框架 void bfs() { q.push(起点); while(队列不空) { auto t = 队首元素; for(所有相邻节点) { 如果可以扩展，就扩展，入队; } } } 代码 //bfs #include<bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int n, m; int h[N], e[N], ne[N], idx = 0; ...

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

重点在于如何表示状态和如何进行状态转移 框架 void bfs() { q.push(起点); while(队列不空) { auto t = 队首元素; for(所有相邻节点) { 如果可以扩展，就扩展，入队; } } } #include<bits/stdc++.h> using namespace std; int bfs(string start) { string end = "12345678x"; queue<...

框架 void bfs() { q.push(起点); while(队列不空) { auto t = 队首元素; for(所有相邻节点) { 如果可以扩展，就扩展，入队; } } } 代码 #include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII;//存储点对 const int N = 110; int n, m; int g[N][N]; int ...

框架 void dfs(开始位置 u) { if(以后搜索完) { 输出结果; return; } //枚举在这个位置可能转移到的所有状态 for(所有可能转移到的状态) { 转移到新状态; dfs(新的开始位置); 恢复状态; } } 思路1 比较原始的方法，枚举每一个位置放不放皇后，时间复杂度为O(2n)O(2^n)O(2n) #include<iostream> using namespace std; const int N = 20...

把搜索的过程想象成一棵树，一共有n个位置需要填写，我们的顺序是从第一个位置开始向后填写，在过程中需要注意记录哪些数字还没有填写，还有，记得恢复状态 //枚举第u个位置 void dfs(int u) { if(已经遍历完) { 输出结果; return; } for() { 遍历每个可能转移到的状态; 做出改变； dfs(下一层); 恢复状态; } } //全排列问题 #include<iostream> using namespace std; co...