思路 问题可以转化为 求每个区间(区间长度大于1的区间)的最大值 与 最小值，最大值之和 减去 最小值之和 就是答案 注：下面所提区间，默认 区间长度大于 1 如何求 最大值之和 与 最小值之和 1：枚举每个区间，时间复杂度 O(n^2) ==> 超时 2：枚举每个值，假设该值为区间最大值 此时 num_1 * maxm_1 + num_2 * maxm_2 + ... + num_n * maxm_n = 最大值之和 num_i 表示 maxm_i 这个值 可以在 num_i 个区间里作为最大值 求最小值之和 同理求 num_i ： 不妨令 a[i] 为最大值，我们求出 a[i...

看了大佬题解，学到了 Code #include <bits/stdc++.h> using namespace std; int m,k,x; char s[10]; struct cmp{ bool operator () (const int & x,const int & y) const { if(abs(x-y)<=k) return false; return x < y; } }; set<int,cmp> se; int main(){ scanf(&quot...

每次合并最轻的两堆 Code #include <bits/stdc++.h> using namespace std; const int N = 10010; typedef long long ll; priority_queue<int,vector<int>,greater<int> >q; int a[N]; int n; int main(){ cin>>n; for(int i=1;i<=n;i++){ int x; cin>>x; ...

转化为：括号匹配 Code #include <bits/stdc++.h> using namespace std; const int N = 100; char s[N]; int main(){ cin>>s+1; int d=0; bool op=false; for(int i=1;s[i];i++){ if(s[i]=='a') d++; else { if(d<=0) op=true; d--; } } ...

思路 优先队列 Code #include <bits/stdc++.h> using namespace std; const int N = 100010; priority_queue<int,vector<int>,greater<int> >q; bool st[N]; int n,x; string s; int main(){ cin>>n; for(int i=1;i<=N;i++) q.push(i); while(n--){ cin>>s; ...

思路 下一次出现最晚的 被 弹出队列 ==> 最佳页面置换算法 （OPT）而不是 剩余出现次数最少的 被 弹出队列 Code #include <bits/stdc++.h> using namespace std; const int N = 50010; struct node{ int id; int nex; bool operator < (const node &x) const { return nex < x.nex ;} }; bool st[N]; int pos[N],Nex[N]; int a[N];...

思路 递归 Code #include <bits/stdc++.h> using namespace std; const int N = 20; bool st[N]; void dfs(int u,string s){ if(u==8) { for(int i=0;i<8;i++) cout<<s[i]<<" \n"[i==7]; } if(u>=8) return; for(int i=1;i<=8;i++){ if(!st[i]){ ...

思路 法1：手写栈 Code #include <bits/stdc++.h> using namespace std; const int N = 110; char stk[N]; string s; int hh; bool check(int h,int i){ if(stk[i]=='o'&&stk[h]=='o') return true; if(stk[i]=='O'&&stk[h]=='O') return true; return false; } int main(){ while(ci...

思路 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...