首页 > 代码库 > 【考前复习_各类模板之补充】
【考前复习_各类模板之补充】
额，考前没能把这篇文章发出来，考后发一发。
我已经无法很好的给它们分类了。后面还有一些模板如果没法分类就都放在这里吧。
一、二分答案（贴了另外一个）
while (l<=r) { int mid=(l+r)>>1; if (judge(mid)) l=mid+1; else r=mid-1; } cout<<l;
二、快速幂
int ksm(int x,int y)//x^y{ int t=1,k=y,tmp=x; while (k) { if (k%2) t=t*tmp; k>>=1; tmp=tmp*tmp; } return t;}
三、归并（求逆序对）
void megesort(int l,int r){ if (l==r) return ; int mid=(l+r)>>1; megesort(l,mid); megesort(mid+1,r); int i=l,j=mid+1; int ri[105],id=l; memset(ri,0,sizeof(ri)); while (i<=mid&&j<=r) { if (a[i]<=a[j]){//<= ri[id]=a[i];id++;i++; } else{ ri[id]=a[j];id++;j++; ans+=mid-i+1; } } while (i<=mid) { ri[id]=a[i];id++;i++; } while (j<=r){ ri[id]=a[j];id++;j++; } for (int i=l;i<=r;i++) a[i]=ri[i];}
四、堆（排序，手写priority_queue）
1、加入元素
void pushup(int x)//加入元素x { int now,ne; hep[++siz]=x; now=siz; while (now>1){ ne=now/2; if (hep[now]>=hep[ne]) return ;//小根堆,<=:大根堆 swap(hep[now],hep[ne]); now=ne; }}
2、取出堆顶元素
int pushdown()//取堆顶元素 tmp{ int tmp=hep[1]; hep[1]=hep[siz]; siz--; int now=1,ne; while (now*2<=siz){//把当前位下移到适合位置，然后返回tmp ne=now*2; if (ne<siz&&hep[ne+1]<hep[ne]) ne++;//把左右更小的放在now if (hep[now]<=hep[ne]) return tmp; swap(hep[now],hep[ne]); now=ne; } return tmp;//*** }
五、二分匹配
bool findway(int u){ for (int i=he[u];i;i=ne[i]) if(!check[to[i]]){ check[to[i]]=true; if (match[to[i]]==-1||findway(match[to[i]]))//** { match[to[i]]=u;// return true; } } return false;}int hungary()//KM匈牙利算法{ memset(match,-1,sizeof(match)); for(int i=1;i<=n;i++) { memset(check,0,sizeof(check)); if (findway(i)) ans++; } return ans;}
六、Tarjan（有向图强连通分量）
void tarjan(int u){ dfn[u]=low[u]=++idx; stak[++instak]=u; in[u]=true; for (int i=he[u];i;i=ne[u]) { if (!dfn[to[i]]){ tarjan(to[i]); low[u]=min(low[to[i]],low[u]); } if (in[to[i]]&&dfn[to[i]]<low[u]) low[u]=dfn[to[i]]; } if (dfn[u]==low[u]) { ans++; int j=stak[instak]; while (j!=u) { j=stak[--instak]; in[j]=false; } }}
【考前复习_各类模板之补充】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。