思路 Code #include <bits/stdc++.h> using namespace std; const int N = 1e7+10; int a[N],f[N]; int stk[N]; int hh; int n; int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=n;i>=1;i--) f[i]=max(f[i+1],a[i]); int t=0; for(int i=1;i<=n;i++){...

思路 01 背包 + 并查集 Code #include <bits/stdc++.h> using namespace std; const int N = 10010; int p[N]; int fa[N]; int f[N],v[N],w[N]; int n,m,c; int find(int x){ if(x==fa[x]) return x; return fa[x]=find(fa[x]); } int main(){ int T; cin>>T; while(T--){ cin>&...

C 题题解 思路：构造 参考：https://blog.nowcoder.net/n/9efb42ac11a64a5ebcf0d604115df70d Code #include <bits/stdc++.h> using namespace std; string s1,s2,s3; int a,b,c,n; int main(){ cin>>a>>b>>c>>n; int minm=min(min(a,b),c); for(int i=1;i<=minm;i++) s1+='a'; s3...

I 题题解 思路 题意:通过对 a 中若干个元素 加1(每个元素只能加1次)，使得逆序对的数目变少，问逆序对数目 最少可变为几因为 a 是 1 到 n 的全排列，即 [1,n] 中每个元素均出现且只出现一次所以 我们每次 加1操作 最多消掉一个逆序对 ，该逆序对 满足 i < j && ai > aj && ai = aj+1我们把这样的逆序对 称为 "目标逆序对”所以，我们只需要统计有多少个 目标逆序对就行，刚开始时的逆序对数目 减去 目标逆序对的数目 就是答案 ps: 需注意一种特殊情况:假设存在 逆序对 : i < j &amp...

J 题题解 浮点二分 ＋ 前缀和 思路 结论：对序列 a 求得最大的 平均值 res_a，再对序列 b 求得最大的 平均值 res_b，res_a + res_b 就是答案res_a 的解释 及 求法 解释： 对于 序列 a 中 所有满足区间长度 大于或者等于 x 的 的区间 每个满足条件的区间 都有1个平均值 res_i (区间元素和 / 区间长度) res_a = max(res_1,res_2,...,res_n) 求法： 第一想法：穷举每个满足条件的区间，更新最大平均值，但因为区间长度是至少为x ，而不是刚好为x 所以穷举的时间复杂度 是O(n^2)，显然会 T 第二想法：穷举每个...

B题题解 队友别骂了，别骂了，我不该以为这题是最短路 思路 为了实现最少花费，需满足：在我们涂完若干个点后，其他的点对总花费不再有贡献（涂黑这些点时不花钱了）我们会发现 ：最少，我们需要涂黑 n + m - 1 个点，且涂完这些点后 所有的行 和所有的列 会都在一个联通块里面 举例 如下：不妨令 n = 2，m = 2，此时我们最少需要涂 3个点令 g[1][1] = g[1][2] = g[2][1] = 1，g[2][2] = 3为了最少花费，我们要涂的三个点显然是：(1,1)，(1,2)，(2,1)涂完(1,1)后，我们把 行1 和 列1 放到一个联通块里面涂完(1,2)后，我们把 行1...

I 题题解 思路 广搜 Code #include <bits/stdc++.h> using namespace std; const int N = 50; struct node{ int x1,y1; int x2,y2; int cnt; char c; }p[N][N][N][N]; char A[N][N],B[N][N]; char C[4]={'D','L','R','U'}; int rou1[4][2]={1,0,0,-1,0,1,-1,0}; int rou2[4][2]={1,0,0,1,0,-1,-1,0}; b...

K题题解 法1： 构造拓扑关系 思路：先假设 我们要求的序列 a 为: 1、2、3、...... 、n然后对序列 a 进行题目描述中的单调栈操作， 构造出满足 所给b[i] 的拓扑关系拓扑关系：在这里 指位置间的拓扑关系 ，比如 pos1 指向 pos2 , 代表 a[pos1] 需大于 a[pos2] Code 如下 #include <bits/stdc++.h> using namespace std; typedef pair<int,int> PII; const int N = 1e6+10; PII p[N]; int a[N],b[N]; ...

有边数限制的最短路 —— bellman_ford 模板题 时间复杂度 O（nm） #include <bits/stdc++.h> using namespace std; const int N = 1010, M = 20010; struct node{ int a,b,w; }p[M]; int a[N]; int sum[N]; int dist[N]; int backup[N]; int n,m,k; int t; int bellman_ford(){ memset(dist,0x3f,sizeof dist); dist[1]=0...

思路 枚举中转点，当中转点为 i 时对应得到：res_i = f[i][0] + f[i][1]那么最终的答案 res = max(-1，res_1，res_2，res_3，...... ，res_n)f[i][0]：点 i 可到达的最远点(记其为x) 与点 i 之间的 距离f[i][1]：点 i 可到达的次最远点(除 x 外，距离 i 最远的点，记其为 y) 与点 i之间 的距离注：f[i][0] 与 f[i][1] 可能相等，但 x、y、i 三个点不能重复若 i 找不到 对应的两个点 x、y , 则令 f[i][0] = f[i][1] =-1，以便不影响最终的结果 所以我们的思路是这样的...

思路 题意：求 让蜥蜴没办法达到终点所必须花费的最小总代价我们通过 把特殊的走道转化为墙壁（ 转换代价为g[i][j] ），来使蜥蜴最终无法到达终点 g[i][j]取不同值的意义：-1代表墙壁，0代表走道，而1到10^9之间的正整数代表特殊的走道。因为 g[i][j] = -1 代表已经是墙壁，故转换代价为 0，因此我们让 g[i][j] = -1的，g[i][j] = 0而g[i][j] = 0 的 代表无法转换为墙壁，故代价是无穷大，因此我们让 g[i][j] = 0的，g[i][j] = 1e18 因为 蜥蜴在左上角，终点在右下角，要使得蜥蜴无法到达终点 就必须 有 ''一道墙'' 把蜥...

思路 求从 1 到 n 的最短路，需注意的是 图上所有边的边权会实时改变如何改变：每次走过一条边之后，所有的 x 都会 执行一次操作：x = 1/(1-x)，x 是 边权，所有的 x 指所有边即 边权会随着走过的边的数目的改变而改变 所以该题 不再仅仅是最短路问题，而是变成了 最短路 + dp 问题 不妨令 dist[i][j]：表示 从 1 到 i 经过了 j 条边的最短路所以 我们最终只需求 min（ dist[n][0]，dist[n][1]，dist[n][2]，...... ，dist[n][M] ） M 代表最多走过的边的数目 但是 因为边是双向边，所以理论上来讲 我们可走过无穷条...

思路 求能从 1 号点到达 n 号点 并且 满足相关条件的最短路条件：穿过的被***城镇 不能超过 K 个 解法：最短路 ＋ dp dist[i][j]：从起点开始 穿过了j个被***的城市 到达i点的 最短距离ps：dist 最后一定是最短距离，但中间过程的值不一定是，因为后续可能被再次更新 所以我们只需要求 min( dist[n][0] , dist[n][1] , dist[n][2] , ...... , dist[n][k] ) 至于 dist ，我们在 dijkstra 中求得为了求得 dist 我们需额外 将 当前穿过被***城市的数量 加入到队列中去，这点与 以往的 dij...

根本不需要分层图，其实是dijkstra模板题 思路 让我们求从 s 到 t 的最短路关键点在于建边 有手就行 很简单一题，不废话了，代码如下 Code #include <bits/stdc++.h> using namespace std; const int N = 1e3+10; bool st[N]; int a[N]; int dist[N]; int g[N][N]; int n,m,s,t; int dijkstra(){ memset(dist,0x3f,sizeof dist); dist[s]=0; for(int i=0...