二分图：图中有两个点集，集合内的点互不连边，两个集合的点互相连边 二分图最大匹配：在二分图找到最多的匹配数 匈牙利算法： 时间复杂度： 邻接矩阵:O(n^3) 邻接表:O(n*m) int e[N][N]; //邻接矩阵 //可以用邻接表稍微优化一下 int vis[N],link[N]; //link[i]表示编号为i的人的对象是谁(编号为i的女生喜欢的男生是谁) //vis[i]表示i是否在增广路上出现过 int dfs(int x){ //男生x for(int i=1;i<=n;++i){ //女生i if(!e[i][x]||vis[i]) continue; //!e[i][...

题目：最长对称子串 #include<bits/stdc++.h> using namespace std; int ans; string str; int main(){ getline(cin,str); int len=str.size(); for(int i=0;i<len;++i){ int l=0; while(i-l>=0&&i+l<=len-1&&str[i-l]==str[i+l]) l++; ans=max(ans,2*l-1); } for(int i=0;i<len;++i){ int l=0; w...

#include<bits/stdc++.h> using namespace std; int const INF=0x3f3f3f3f; int const N=1e4+7; int n,cnt; int f[N],num[N],h[N],sr[N]; set<int>s; struct L{ int p,num; double h,s; }w[N]; int find(int x){ return f[x]==x?x:f[x]=find(f[x]); } void merge(int a,int b){ int fx=find(a),fy=find(b); if(...

狄尔沃斯定理的划分数和序列长度：不升（下降）————上升不降（上升）————下降 #include<bits/stdc++.h> using namespace std; int const N=1e5+7; int n,a[N]; vector<int>v; int main(){ cin >> n; for(int i=1;i<=n;++i) cin >> a[i]; for(int i=1;i<=n;++i){ int z=lower_bound(v.begin(),v.end(),a[i])-v.begin(); if(z==...

此题咋一看是拆查集，但拆查集反过来是并查集（即反向操作）反向操作需要延迟操作 #include<bits/stdc++.h> using namespace std; int const N=5e2+7; int n,m,k,cnt; vector<int>v[N]; int vis[N],op[N],f[N],num[N]; int find(int x){ return f[x]==x?x:f[x]=find(f[x]); //以后RE的时候，检查一下递归 } void merge(int x,int y){ f[find(x)]=find(y); } int ma...

#include<bits/stdc++.h> using namespace std; int const N=30+7; int n; int z[N],q[N]; struct node{ int w; node *l,*r; }; node* dfs(int l1,int r1,int l2,int r2){ if(l1>r1||l2>r2) return NULL; node* rt=new node; //注意 rt->w =q[l2]; int i=l1; for(i=l1;i<=r1;++i){ if(z[i]==q[l2]) break; ...

二叉搜索树的中序遍历一定是一个递增序列 #include<bits/stdc++.h> using namespace std; int const N=1e3+7; int n; int a[N]; struct node{ int w; node *l,*r; }; node* dfs(int l,int r,int f){ if(l>r) return NULL; int i=0; node *rt=new node; rt->w =a[l]; if(f==0){ for(i=l+1;i<=r;++i){ if(a[i]>=a[l]) break; }...

堆的三个函数 用法详解 题目  小根堆：根小于儿子，左右儿子间并无大小关系要求，不要和搜索树搞混了 堆类似优先队列（就是优先队列），所以默认大者优先，重载小于号时，像优先队列一样考虑即可堆是完全二叉树，插入元素时，先插入树的右下方，再进行上浮（移到合适的位置）make_heap(), pop_heap(), push_heap() //创建，弹出，插入堆一般和vector一起用此题要询问节点间的关系，所以没用优先队列 ~为取反操作，计算机内部的取反（全部取反）（^1是个位数取反）-1在计算机内部是以补码的形式存在，它取反为0，其余数取反均不为0str.find("abc")...

#include<bits/stdc++.h> using namespace std; int const N=1e2+7; int const M=25e4+7; int n,m,t; int e[N][N],f[N]; int find(int x){ return f[x]==x?x:f[x]=find(f[x]); } void merge(int x,int y){ f[find(x)]=find(y); } int main(){ cin >> n >> m >> t; for(int i=1;i<=n;++i) f[i]=i...

先序和后序可以确定根再利用根在中序中确定左右子树 #include<bits/stdc++.h> using namespace std; int const N=37; int const M=25e4+7; int n; int h[N],z[N]; vector<int>v; void dfs(int l1,int r1,int l2,int r2){ if(l1>r1||l2>r2) return ; for(int i=l1;i<=r1;++i){ if(z[i]==h[r2]){ v.push_back(h[r2]); dfs(l1,i-1...

dijstra的松弛操作的条件一般不变当==也要进行操作时，else if即可（具体见代码） 一般操作是在松弛内进行的 #include<bits/stdc++.h> using namespace std; int const N=5e2+7; int const M=25e4+7; struct node{ int a,next,len; }e[M<<1]; int cnt,head[N]; void add(int x,int y,int len){ e[++cnt].a =y; e[cnt].len =len; e[cnt].next =head[x]; hea...

1、 明码  #include<bits/stdc++.h> using namespace std; int const N=1e4+7; void pan(int x,int t){ if(t==7){ if(x<0) cout << "*"; else cout << " "; if(x&1) cout << "*"; else cout << " "; return ; } pan(x>>1,t+1); if(x&1) cout << "*"; else cout <<...

网络分析 参考博客 带权并查集详解 带权并查集（核心）： 1、路压要维护权值（考虑怎么维护） 2、合并时也要维护权值（考虑怎么维护） 3、并查集一般对根节点进行操作 dis与差分： 1、差分是当前元素与前一个元素的差值 ，dis是当前节点与父节点的差值 2、差分做前缀和为原数组 ，dis对祖先做前缀和为原权值 f[x]表示当前x的父亲（未更新） #include<bits/stdc++.h> using namespace std; int const N=1e4+7; int n,m; int f[N],w[N],dis[N]; //w表示集合根节点的权值 //dis[i]表示i...

蓝桥要多枚举几种情况1、双指针不要越界 完全二叉树的权值  #include<bits/stdc++.h> using namespace std; #define ll long long #define INF 0x7fffffff int const N=1e5+7; ll n,m,cnt,ans,p; ll a[N]; int main(){ cin >> n; ans=-INF; for(int i=1;i<=n;++i){ cin >> a[i]; } int depth=log(n)/log(2)+1; int j=1; for(int ...