OI常用模板
Nemlit
2018-11-08 19:26:57
```
void Prim()
{
memset(dis,127,sizeof(dis));
for(int i=head[1];i;i=e[i].next) dis[e[i].v]=min(dis[e[i].v],e[i].w);
for(int i=1;i<n;++i)
{
int minn=inf,now=0;
for(int j=2;j<=n;++j)
if(dis[j]<minn&&!vis[j]) minn=dis[j],now=j;
ans+=dis[now];
vis[now]=1;
for(re int j=head[now];j;j=e[j].next)
dis[e[j].v]=min(dis[e[j].v],e[j].w);
}
}
void eulershai()
{
for(int i=2;i<=n;i++)
{
if(!f[i]) p[++cnt]=i;
for(int j=1;j<=cnt;j++)
{
if(i*p[j]>n) break;
f[i*p[j]]=1;
if(!(i%p[j])) break;
}
}
}
void spfa(int s)
{
memset(vis,0,sizeof(vis));
memset(dis,127,sizeof(dis));
int l=1,r=0;
q[++r]=s,dis[s]=0;
while(l<=r)
{
int u=q[l++];
vis[u]=0;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v,w=e[i].w;
if(dis[v]>dis[u]+w)
{
if(++col[v]>n) return 0;//负环
dis[v]=dis[u]+w,ans[v]=ans[u];//最短路记数
if(!vis[v]) q[++r]=v,vis[v]=1;
}
else if(dis[v]==dis[u]+1) ans[v]+=ans[u]//最短路记数
}
}
}
il void add(int x,int v)
{
while(x<=n) a[x]+=v,x+=lb(x);
}
int query(int x)
{
re int ans=0;
while(x) ans+=a[x],x-=lb(x);
return ans;
}
//单点加+区间查：
//add(x,v);
//printf("%d\n",query(y)-query(x-1));
//区间加+单点查：
//add(x,z),add(y+1,-z);
//printf("%d\n",query(x));
void threecut()
{
while(r-l>eps)
{
re D mid=(r-l)/3;
f(l+mid)>f(r-mid)?r-=mid:l+=mid;
}
}
void ST()
{
log[0]=-1;
for(re int i=1;i<=n;++i)
{
st[0][i]=a[i];
log[i]=log[i>>1]+1;
}
for(re int j=1;j<20;++j)
for(re int i=1;i+(1<<j)-1<=n;++i)
st[j][i]=max(st[j-1][i],st[j-1][i+(1<<j-1)]);
l=read(),r=read();
re int t=log[r-l+1];
cout<<max(st[t][l],st[t][r-(1<<t)+1]);
}
void aca()
{
memset(c,0,sizeof(c));
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
for(int k=1;k<=n;++k) c[i][j]+=a[i][k]*a[k][j];
memcpy(a,c,sizeof(c));
}
void acb()
{
memset(c,0,sizeof(c));
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
for(int k=1;k<=n;++k) c[i][j]+=a[i][k]*b[k][j];
memcpy(b,c,sizeof(c));
}
void ksm()
{
memcpy(b,a,sizeof(a));
while(k)
{
if(k&1ll) acb();
k>>=1,aca();
}
}
void sort(int l,int r)
{
if(l==r) return;
int mid=(l+r)>>1;
sort(l,mid),sort(mid+1,r);
int x=l,y=mid+1,p=l;
while(x<=mid&&y<=r)
{
if(a[x]>=a[y])
{
b[p++]=a[y++];
ans+=mid-x+1;
}
else b[p++]=a[x++];
}
while(x<=mid) b[p++]=a[x++];
while(y<=r) b[p++]=a[y++];
for(int i=l;i<=r;i++) a[i]=b[i];
}
void KMP()
{
n=strlen(a+1),m=strlen(b+1);
for(re int i=2,j=0;i<=m;++i)
{
while(j&&b[i]!=b[j+1]) j=p[j];
if(b[i]==b[j+1]) ++j;
p[i]=j;
}
for(re int i=1,j=0;i<=n;++i)
{
while(j&&b[j+1]!=a[i]) j=p[j];
if(a[i]==b[j+1]) ++j;
if(m==j) printf("%d\n",i-m+1),j=p[j];
}
}
il void exgcd(int a,int b,int&x,int&y)
{
if(!b)
{
x=1,y=0;
return;
}
exgcd(b,a%b,y,x);
y-=x*(a/b);
}
void getinv()
{
inv[1]=1;
for(re int i=2;i<=n;++i) inv[i]=(inv[p%i]*(p-p/i))%p;
}
void TarjanLCA()
{
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(v==father[u]) continue;
father[v]=u;
Tarjan(v);
hb(v,u),vis[v]=1;
}
for(int i=head1[u];i;i=q[i].next)
if(vis[q[i].v])
ans[i]=find(q[i].v);
}
int outLCA()
{
for(int i=1;i<=m;i++)
printf("%d\n",max(ans[i<<1],ans[(i<<1)-1]));
}
ll C(int n,int m)
{
if(m>n) return 0;
return ((fac[n]*inv(m))%p*inv(n-m))%p;
}
inline ll lucas(int n,int m)
{
if(m==0) return 1;
return (lucas(n/p,m/p)*C(n%p,m%p))%p;
}
struct node
{
int now,w;
il bool operator<(const node&x) const{return w>x.w;}
};
il void Dij()
{
memset(dis,127,sizeof(dis));
dis[s]=0;
q.push((node){s,0});
while(!q.empty())
{
re node t=q.top(); q.pop();
if(!vis[t.now])
{
vis[t.now]=1;
for(re int i=head[t.now];i;i=e[i].next)
{
if(!vis[e[i].v])
{
dis[e[i].v]=min(dis[e[i].v],dis[t.now]+e[i].w);
q.push((node){e[i].v,dis[e[i].v]});
}
}
}
}
}
void LCS()
{
for(re int i=1;i<=n;++i) a[read()]=i;//最长公共子序列
for(re int i=1;i<=n;++i)
{
re int x=a[read()];
if(x>dp[len]) dp[++len]=x;
else
{
re int l=1,r=len;
while(l<=r)
{
re int mid=(l+r)/2;
if(dp[mid]<x) l=mid+1;
else r=mid-1;
}
dp[l]=x;
}
}
printf("%d",len);
}
void manacher()
{
s[0]='!',s[1]='#';
char c=get_char();
while(c!=EOF)
{
s[len++]=c,s[len++]='#';
c=getchar();
}
for(int i=1;i<len;i++)
{
if(i<mx) p[i]=min(p[2*mid-i],mx-i);
else p[i]=1;
while(s[i-p[i]]==s[i+p[i]]) p[i]++;
if(mx<i+p[i])
{
mid=i;
mx=i+p[mid];
}
maxlen=max(maxlen,p[i]);
}
printf("%d",maxlen-1);
}
il void tarjancut(int u,int fr)
{
dfn[u]=low[u]=++tim;
st[++top]=u;
col=0;
for(ri int i=head[u];i;i=e[i].nxt)
{
ri int v=e[i].v;
if(!dfn[v])
{
col++;
tarjan(v,u);
low[u]=min(low[u],low[v]);
if((u!=root&&dfn[u]<=low[v])||(u==root&&col>1)) ans[u]=1;
}
else low[u]=min(low[u],dfn[v]);
}
}
void tarjansuo()
{
dfn[u]=low[u]=++tim;
st[++top]=u;
for(re int i=head[u];i;i=e[i].next)
{
re int v=e[i].v;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!suo[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
++co;
while(st[top+1]!=u)
{
suo[st[top]]=co;
sum[co]+=a[st[top--]];
}
}
}
void Gauss()
{
for(re int i=1;i<=n;++i)
{
re int max=i;
for(re int j=i+1;j<=n;++j)
if(fabs(a[j][i])>fabs(a[max][i])) max=j;
for(re int j=1;j<=n+1;++j)
swap(a[i][j],a[max][j]);
if(!a[i][i]) return puts("No Solution"),0;
for(re int j=1;j<=n;++j)
{
if(j!=i)
{
re D temp=a[j][i]/a[i][i];
for(re int k=i+1;k<=n+1;++k) a[j][k]-=a[i][k]*temp;
}
}
}
for(re int i=1;i<=n;++i) printf("%.2lf\n",a[i][n+1]/a[i][i]);
}
il void SA()
{
re D xx=xans,yy=yans,t=T;
while(t>EPS)
{
re D xt=xx+(rand()*2-RAND_MAX)*t;
re D yt=yy+(rand()*2-RAND_MAX)*t;
re D now=getans(xt,yt);
re D deta=now-ans;
if(deta<0)
{
xx=xans=xt,yy=yans=yt;
ans=now;
}
else if(RAND_MAX*exp(-deta/t)>rand()) xx=xt,yy=yt;
t*=delta;
}
}
void Binary()
{
for(re int i=1;i<=n;++i)
{
re int W=read(),V=read(),num=read();
for(re int j=1;j<=num;j<<=1)
{
w[++cnt]=j*W,v[cnt]=j*V;
num-=j;
}
if(num) w[++cnt]=num*W,v[cnt]=num*V;
}
for(re int i=1;i<=cnt;++i)
for(re int j=m;j>=v[i];--j)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
int getp(int x)
{
int ans=x;
for(int i=2;i*i<=x;++i)
{
if(x%i==0)
{
ans-=ans/i;
while(x%i==0) x/=i;
}
}
return x>1?ans-ans/x:ans;
}
void Euler()
{
for(re int i=1;i<=n;++i) p[i]=i;
for(re int i=2;i<=n;++i)
if(p[i]==i)
for(re int j=i;j<=n;j+=i) p[j]=p[j]*(i-1)/i;
}
int fx[4]={1,0,0,-1},fy[4]={0,-1,1,0};
il void dfs(int x,int y,int sum,int last)
{
re int tl=gu();
if(ans==sum)
{
if(tl==0) b=1;
return;
}
if(b||sum+tl-1>ans) return;
++sum;
for(re int i=0;i<4;++i)
{
re int vx=x+fx[i],vy=y+fy[i];
if(vx>2||vx<0||vy>2||vy<0||i+last==3) continue;
swap(a[vx][vy],a[x][y]),dfs(vx,vy,sum,i),swap(a[vx][vy],a[x][y]);
}
}
void Astar()
{
while(1)
{
dfs(sx,sy,0,-1);
if(b) return printf("%d",ans),0;
++ans;
}
}
void treeDP()
{
sort(e+1,e+n+1,cmp);//右端点排序
memset(f,127,sizeof(f));
f[L]=0;
build(1,L,R);
for(re int i=1;i<=n;++i)
{
f[e[i].v]=min(f[e[i].v],query(1,L,R,e[i].u-1,e[i].v)+e[i].w);
change(1,L,R,e[i].v,f[e[i].v]);
if(e[i].v>=R)
{
if(f[e[i].v]<1234567890) printf("%d",f[e[i].v]);
else puts("-1");
return;
}
}
}
int mathDP(int now,int last,int lend,int higher)
{
if(!now) return 1;
if(dp[now][last][higher][lend]!=-1) return dp[now][last][higher][lend];
int temp=0,n=(lend?a[now]:9);
for(register int i=0;i<=n;++i)
if(abs(i-last)>=2)
temp+=mathDP(now-1,(((!i)&&higher)?-10:i),(lend&&(i==n)),((!i)&&higher));
return dp[now][last][higher][lend]=temp;
}
int work(int x)
{
cnt=0;
while(x) a[++cnt]=x%10,x/=10;
memset(dp,-1,sizeof(dp));
return dfs(cnt,-10,1,1);
}
namespace Dinic
{
bool bfs()
{
memset(deep,0,sizeof(deep));
q.push(s);
deep[s]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(!deep[v]&&e[i].w>0)
{
deep[v]=deep[u]+1;
q.push(v);
}
}
}
return deep[t];
}
int dfs(int u,int minn)
{
if(u==t) return minn;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(e[i].w&&deep[v]==deep[u]+1)
{
int l=dfs(v,min(minn,e[i].w));
if(l>0)
{
e[i].w-=l,e[i+1].w+=l;
return l;
}
}
}
return 0;
}
int dinic()
{
int low,ans=0;
while(bfs()) while(low=dfs(s,INF)) ans+=low;
return ans;
}
}
struct Heap
{
int now;
D gu,w;
il bool operator<(Heap x) const{return gu>x.gu;}
}u;
priority_queue<Heap> h;
il void KAstar()
{
h.push((Heap){1,dis[1],0});
while(!h.empty())
{
u=h.top();
h.pop();
if(E<u.w) return;
if(n==u.now)
{
++ans,E-=u.w;
continue;
}
for(re int i=head[u.now];i;i=e[i].next)
{
h.push((Heap){e[i].v,v.w+dis[e[i].v],u.w+e[i].w});
}
}
}
```