noip 模板库
NOIP相关资料下载
读入优化
char ch;
void read(int &n)
{
n=0;
ch=G();
while((ch<‘0’ || ch>‘9’) && ch!=’-’)ch=G();
ll w=1;
if(ch==’-’)w=-1,ch=G();
while(‘0’<=ch && ch<=‘9’)n=(n<<3)+(n<<1)+ch-‘0’,ch=G();
n*=w;
}
输出优化
void write(int x)
{if(x>9) write(x/10);P(x%10+'0');
}
最短路（spfa）
memset(dis,127,sizeof(dis));
memset(bz,1,sizeof(bz));
bz[n]=dis[n]=0;
d[1]=n;
int head=0,tail=1;while(headdis[x]+v[i] || (dis[a[i]]==dis[x]+v[i] && b[f[a[i]]]>b[x])){dis[a[i]]=dis[x]+v[i];f[a[i]]=x;if(bz[a[i]]){bz[a[i]]=0;d[++tail]=a[i];}}bz[x]=1;
}
高精度
void add(arr a,arr b)
{memset(t,0,sizeof(t));int m=max(a[0],b[0]);for(int i=1;i<=m;i++){t[i]+=a[i]+b[i];t[i+1]+=t[i]/mo;t[i]=t[i]%mo;}if(t[m+1]>0)t[0]=m+1;else t[0]=m;
}void dd(arr a,arr b)
{memset(tt,0,sizeof(tt));for(int i=1;i<=a[0];i++){tt[i]+=a[i]-b[i];while(tt[i]<0){tt[i]+=mo;tt[i+1]--;}}tt[0]=a[0];while(!tt[tt[0]])tt[0]--;
}
线段树
void work(int x)
{if(t[x].l>=opl && t[x].r<=opr){if(opx==1)t[x].x=min(t[x].x,ops);if(opx==2)ops=min(ops,t[x].x);return;}if(t[x].l==t[x].r)return;int m=(t[x].l+t[x].r)/2;if(opl<=m)work(x+x);if(m并查集
int get(int x){return x==f[x]?x:f[x]=get(f[x]);}
1
哈希
inline void ins()
{int x=y%mo;while(f[x]!=0 && f[x]!=y)x=(x+1)%mo;f[x]=y;g[x]++;
}inline int find()
{int x=y%mo;while(f[x]!=0 && f[x]!=y)x=(x+1)%mo;return g[x];
}
tarjan
void tarjan(int x)
{ti++;dfn[x]=low[x]=ti;bz[x]=0;ta++;z[ta]=x;for(int i=lst[x];i;i=nxt[i]){if(dfn[to[i]]==0){tarjan(to[i]);low[x]=min(low[x],low[to[i]]);}else if(!bz[to[i]])low[x]=min(low[x],dfn[to[i]]);}if(low[x]==dfn[x]){for(cnt++;z[ta]!=x && ta;ta--)F[g[z[ta]]=cnt]+=V[z[ta]],bz[z[ta]]=1;F[g[z[ta]]=cnt]+=V[z[ta]],bz[z[ta]]=1;ta--;}
}
tarjan（人工栈）
void tarjan(int x){d[r=1]=x;while(r){x=d[r];if(dfn[x]==0){z[++top]=x;bz[x]=w[x]=0;dfn[x]=low[x]=++now;}if(b[x]){int i=b[x];if(p[i]==0){low[x]=min(low[x],low[to[i]]);} elseif(bz[to[i]]){if(p[i]){d[++r]=to[i];p[i]=0;continue;}}else if(!w[to[i]])low[x]=min(low[x],dfn[to[i]]);b[x]=nxt[i];}else{ if(low[x]==dfn[x]){cnt++;z[top+1]=-1;while(z[top+1]!=x){f[z[top]]=cnt;v[cnt]++;w[z[top]]=1;top--;}ans=max(ans,v[cnt]);}r--;}}}
倍增LCA
int lca(int x,int y)
{if(deep[x]>deep[y])swap(x,y);for(int j=19;j>=0;j--)if(deep[x]<=deep[f[y][j]])y=f[y][j];if(x==y)return x;for(int j=19;j>=0;j--)if(f[x][j]!=f[y][j])x=f[x][j],y=f[y][j];return f[x][0];
}
树状数组
int low(int x)
{return x & (-x);
}int find(int x,int y)
{int s=0;for(int i=x;i;i=i-low(i))s+=z[y][i];return s;
}void change(int x,int y,int s)
{for(int i=x;i<=n;i=i+low(i))z[y][i]+=s;
}
优先队列（堆）
#include
#include
#include
#include
using namespace std;struct node{int x;
};priority_queue q;
//定义一个类型为node的优先队列（使用堆的队列） bool operator <(node a,node b){return a.x>b.x;
}
//因为优先队列默认为从大到小（ 用"<"比较），我们若要从小到大，就要重新定义"<"为相反操作
int main(){int n;cin>>n;if (q.empty()) cout<<"The heap is empty!"<>t.x;q.push(t);//将t加入队列 }for (int i=1;i<=n;++i){node t;t=q.top();//取出队首 q.pop();//将队首弹出 cout< trie
int ins(char* s,int len)
{int x=1;for(int p=1;p<=len;p++){if(tr[x].son[s[p]-'a']==0){deep[++tot]=deep[x]+1;tr[x].son[s[p]-'a']=tot;f[tot][0]=x;for(int j=1;j<20;j++)f[tot][j]=f[f[tot][j-1]][j-1];}x=tr[x].son[s[p]-'a'];}return x;
}
kmp
void make(int* t,int len)
{memset(nxt,0,sizeof(nxt));int j=0;for(int i=2;i<=len;i++){while(j>0 && t[j+1]!=t[i])j=nxt[j];if(t[i]==t[j+1])j++;nxt[i]=j;}
}int kmp(int l)
{int j=0,sum=0;for(int i=1;i0 && a[i]!=b[j+1])j=nxt[j];if(a[i]==b[j+1])j++;if(j==l){sum++;j=nxt[l];}}return sum;
}
最小生成树（克鲁斯卡尔）
for(int i=1;t二分图匹配（匈牙利算法）
bool find(int x)
{for(int i=b[x];i;i=next[i]){if(bz[t[i]])continue;bz[t[i]]=1;if(g[t[i]]==0 || find(g[t[i]])){g[t[i]]=x;return 1;}}return 0;
}
最长回文串
void manacher(char s[], int length, int rad[]) {for (int i=1,j=0,k; i < length; i+=k) {while (s[i-j-1] == s[i+j+1]) ++j;rad[i] = j;for (k = 1; k <= rad[i] && rad[i-k] != rad[i]-k; ++k) { rad[i+k] = min(rad[i-k], rad[i]-k);}j = max(j-k, 0);}
}
网络流
int nxt[N*2],to[N*2],v[N*2],last[N],cur[N],tot;
int q[N],h[N],S,T,ans;
int a[M][M],n,m,t;bool bfs()
{int head=0,tail=1;for(int i=0;i<=T;i++)h[i]=-1;q[0]=S;h[S]=0;while(head!=tail){int now=q[head];head++;for(int i=last[now];i;i=nxt[i])if(v[i] && h[to[i]]==-1){h[to[i]]=h[now]+1;q[tail++]=to[i];}}return h[T]!=-1;
}int dfs(int x,int f)
{if(x==T)return f;int w,used=0;for(int i=cur[x];i;i=nxt[i])if(h[to[i]]==h[x]+1){w=f-used;w=dfs(to[i],min(w,v[i]));v[i]-=w;v[i^1]+=w;if(v[i])cur[x]=i;used+=w;if(used==f)return f;}if(!used)h[x]=-1;return used;
}void dinic()
{while(bfs()){for(int i=0;i<=T;i++)cur[i]=last[i];ans+=dfs(S,inf);}
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！