思路 M 对互相仇恨的罪犯，我们按仇恨值从大到小排序，对于每一对互相仇恨的罪犯，我们要设法将他们分配在不同的监狱里，反正不能在同一监狱里 如果不可避免的在同一监狱了 也就是与我们的策略发生冲突了，那么此时的仇恨值就是答案 如果到最后都不曾发生冲突，那么答案是 0，因为此时：任意一对会冲突的罪犯 都不会位于同一个监狱(二分图) 不管是 从大到小排序 还是 分配在不同的监狱里，这一切都是为了保证：矛盾的最大值最小(题意要求) 法1：种类并查集：开二倍空间 令 x 表示 x 自身，x + n 表示 x 的敌人 Code #include <bits/stdc++.h> using nam...

Code  #include <bits/stdc++.h> using namespace std; const int N = 1e6+10; string stk[N]; int hh; int main(){ int q; while(cin>>q){ hh=0; for(int i=1;i<=q;i++){ int op; cin>>op; if(op==1){ string s; cin>>s; stk[hh+1]=stk[hh]+s; hh++; } else if(op==2){ int k; cin>>k; s...

并查集 + map Code #include <bits/stdc++.h> using namespace std; const int N = 20010; unordered_map<string,string>fa; int n,m; string find(string x){ if(x==fa[x]) return x; return fa[x]=find(fa[x]); } int main(){ cin>>n>>m; for(int i=1;i<=n;i++) { string s; cin>> s; fa[s...

思路 枚举每个矩形，求出该矩形向左右两侧延伸能得到的最大矩形面积：res_i答案就是 max(res_1,res_2,...,res_n) 代码中一些变量的解释：l[i]：矩形 i 的左边界：从 i 向左延伸，第一个比其高度小的矩形位置r[i]：同理 Code #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e6+10; int l[N],r[N]; int a[N],h[N]; int stk[N]; int hh,n; int main(){ cin>&g...

思路 问题可以转化为 求每个区间(区间长度大于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("%d %d",&m,&k); whi...

每次合并最轻的两堆 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; q.push(x); } ll res=0; while(q.siz...

转化为：括号匹配 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--; } } if(op||d) puts("Bad"); else puts("Good"); return 0; }

思路 优先队列 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; if(s[0]=='D'){ cin>>x;...

思路 下一次出现最晚的 被 弹出队列 ==> 最佳页面置换算法 （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]; int n,m,q; int ...

思路 递归 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]){ st[i]=true; string ss=s; ss+=i+'0'; dfs...

思路  法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(cin>> s){ hh=0; f...

思路  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++){ stk[++hh]=a[i]; while(hh...

思路 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>>n>>m>>c; for(int i=...