OI-板子汇总
乱序，想到什么可以补充。
Tarjan 求强连通分量
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
stack<int> s;
vector<int> g[N];
vector<int> g_2[N];
//cscc代表强连通分量的数量，scc代表每个点所属的强连通分量的编号，ins代表是否在栈中
int dfsn[N],low[N],ins[N],scc[N],deep,cscc,n;
void tarjan(int p)
{
low[p]=dfsn[p]=++deep;
ins[p]=1;
s.push(p);
for(auto &q:g[p])//遍历出边
{
if(!dfsn[q])//未访问
{
tarjan(q);
low[p]=min(low[p],low[q]);
}//访问过且q可达p，因为栈中元素强连通
else if(ins[q]) low[p]=min(low[p],dfsn[q]);//注意这里为什么是dfsn[q]而不是low[q]
}
if(low[p]==dfsn[p])
{
int top=0;
cscc++;
do
{
top=s.top();
s.pop();
ins[top]=0;
scc[top]=cscc;
}while(top!=p);
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)//原图不一定是强连通图，因此每个节点都要看一遍
if(!dfsn[i])//未访问过
tarjan(i);
for(int i=1;i<=n;i++)
for(auto j:g[i])//以i为起点的出边
if(scc[i]!=scc[j])//如果不是一个强连通分量，那就可以把两个强连通分量当作两个点连接起来
g_2[scc[i]].push_back(scc[j]);//j是i的出边，即j的强连通分量是i的强连通分量的出边
return 0;
}缩点
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
const int M=1e5+10;
int a[N];
int n,m,sum,ans=-1;
bool vis[N];
vector<int> e[N];
vector<int> mp[N];
stack<int> s;
bool ins[N];
int low[N],dfsn[N],cnt,cscc,scc[N],val[N],rd[N],dist[N];
void tarjan(int p)
{
low[p]=dfsn[p]=++cnt;
ins[p]=true;
s.push(p);
for(auto &q:e[p])
{
if(!dfsn[q])
{
tarjan(q);
low[p]=min(low[p],low[q]);
}
else if(ins[q]) low[p]=min(low[p],dfsn[q]);//在栈里说明可达
}
if(low[p]==dfsn[p])
{
int top=0;
cscc++;
do
{
top=s.top();
s.pop();
ins[top]=0;
scc[top]=cscc;
val[cscc]+=a[top];
} while (top!=p);
}
}
void topsort()
{
queue<int> q;
for(int i=1;i<=cscc;i++)
if(!rd[i])
{
q.push(i);
dist[i]=val[i];
}
while(!q.empty())
{
int u=q.front();
q.pop();
for(auto &v:mp[u])
{
dist[v]=max(dist[v],dist[u]+val[v]);
rd[v]--;
if(!rd[v]) q.push(v);
}
}
for(int i=1;i<=cscc;i++)
ans=max(ans,dist[i]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
e[u].push_back(v);
}
for(int i=1;i<=n;i++)
if(!dfsn[i]) tarjan(i);
for(int i=1;i<=n;i++)
for(auto &j:e[i])//j是i的出边的终点
if(scc[i]!=scc[j])
mp[scc[i]].push_back(scc[j]),rd[scc[j]]++;
topsort();
printf("%d",ans);
return 0;
}Tarjan 求割点/割边
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
vector<int> e[N];
int dfsn[N],low[N],fa[N];
int cnt;
vector<int> point;
/*割点*/
void tarjan(int p,bool root=true)
{
int tot=0;
low[p]=dfsn[p]=++cnt;
for(auto &q:e[p])//枚举p的出边
{
if(!dfsn[q])//这个点没访问过
{
tarjan(q,false);//递归，并且这个点不是根
low[p]=min(low[p],low[q]);//更新父节点的low值
tot+=(low[q]>=dfsn[p]);//子节点的low值比父节点的dfs序还要大，那就把需要p的子树个数加一
//需要p的子树是指删去p后子树无法与外界联系
}
else//访问过，那就对low值取min
{
low[p]=min(low[p],dfsn[q]);
}
}
if(tot>root)//是根那就要大于1，否则就要大于0
point.push_back(p);
}
vector<pair<int,int> > bridges;
/*割边*/
void tarjan_0(int p)
{
low[p]=dfsn[p]=++cnt;
for(auto &q:e[p])
{
if(!dfsn[q])
{
fa[q]=p;
tarjan_0(q);
low[p]=min(low[p],low[q]);
if(low[q]>dfsn[p]) bridges.emplace_back(p,q);
}
else if(fa[p]!=q) low[p]=min(low[p],dfsn[q]);
}
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
}Tarjan 求点双连通分量
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+100;
const int M=2e6+100;
int n,m,edcnt,cnt,cdcc;
int fir[N],low[N],dfsn[N];
vector<int> dcc[N];
stack<int> s;
vector<int> point;
struct edge
{
int to,nxt;
}e[M<<1];
void add(int u,int v)
{
e[++edcnt].to=v;
e[edcnt].nxt=fir[u];
fir[u]=edcnt;
}
void tarjan(int p,bool root=true)
{
int tot=0;
dfsn[p]=low[p]=++cnt;
s.push(p);
if(root&&fir[p]==0)
{
dcc[++cdcc].push_back(p);//孤立点
return;
}
for(int i=fir[p];i;i=e[i].nxt)
{
int v=e[i].to;
if(!dfsn[v])
{
tarjan(v,false);
low[p]=min(low[v],low[p]);
if(low[v]>=dfsn[p])
{
tot++;
if(tot>root) point.push_back(p);
cdcc++;
int top;
do
{
top=s.top();
s.pop();
dcc[cdcc].push_back(top);
} while (top!=v);
dcc[cdcc].push_back(p);
}
}
else low[p]=min(low[p],dfsn[v]);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
if(u==v) continue;
add(u,v);
add(v,u);
}
for(int i=1;i<=n;i++)
if(!dfsn[i]) tarjan(i);
printf("%d\n",cdcc);
for(int i=1;i<=cdcc;i++)
{
printf("%d",(int)dcc[i].size());
for(auto &j:dcc[i])
printf(" %d",j);
puts("");
}
return 0;
}Tarjan 求边双连通分量
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
const int M=2e6+10;
int fir[N],low[N],dfsn[N];
int n,m,edcnt=1,cnt,cdcc;
bool bridge[M<<1];
vector<int> dcc[N];
stack<int> s;
struct edge
{
int to,nxt;
}e[M<<1];
void add(int u,int v)
{
e[++edcnt].to=v;
e[edcnt].nxt=fir[u];
fir[u]=edcnt;
}
void tarjan(int p,int f)
{
low[p]=dfsn[p]=++cnt;
s.push(p);
for(int i=fir[p];i;i=e[i].nxt)
{
int q=e[i].to;
if(!dfsn[q])
{
tarjan(q,i);
low[p]=min(low[p],low[q]);
if(dfsn[p]<low[q]) bridge[i]=bridge[i^1]=true;
}
else if(i!=(f^1)) low[p]=min(low[p],dfsn[q]);//不是反向边
}
if(dfsn[p]==low[p])
{
cdcc++;
int top;
do
{
top=s.top();
s.pop();
dcc[cdcc].push_back(top);
} while (top!=p);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
if(u==v) continue;
add(u,v);
add(v,u);
}
for(int i=1;i<=n;i++)
{
if(!dfsn[i]) tarjan(i,0);
}
printf("%d\n",cdcc);
for(int i=1;i<=cdcc;i++)
{
printf("%d",(int)dcc[i].size());
for(auto &j:dcc[i])
printf(" %d",j);
puts("");
}
return 0;
}其中利用了异或的性质，偶数加一奇数减一，令初始cnt为1使得边的编号从2开始，这样就可以通过异或1轻松知道反向边的编号了。
最短路
Bellman-Ford
#include<bits/stdc++.h>
using namespace std;
#define maxn 10000007
int n,dist[maxn],m,first[maxn];
int s[maxn],e[maxn],d[maxn];
int main()
{
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&s[i],&e[i],&d[i]);//起点，终点，长度
}
memset(dist,0x3f,sizeof(dist));
dist[1]=0;//起点距离
for(int i=1;i<n;i++)//最多n-1条边,最多松弛n-1次，因为如果倒着来的话，所有点的dist都未知，每次只能更新一个点（一点点往后推），因此每轮会至少松弛一个点
for(int j=1;j<=m;j++)//枚举边
{
dist[e[j]]=min(dist[e[j]],dist[s[j]]+d[j]);
}
return 0;
}SPFA
Bellman-Ford的队列优化
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000007
int first[maxn],dist[maxn];
bool inque[maxn];
struct edge
{
int e,next;
int d;//长度
}ed[maxn];
int cnt;
void add_edge(int u,int v,int w)
{
cnt++;
ed[cnt].next=first[u];
ed[cnt].e=v;
ed[cnt].d=w;
first[u]=cnt;
}
void spfa(int s)
{
memset(dist,0x3f,sizeof(dist));
dist[s]=0;
inque[s]=true;//这里不写也可以，因为第一次取出的一定是首点
queue<int> q;
q.push(s);//一开始只知道s的最短路
while(q.size())
{
int now=q.front();
q.pop();
inque[now]=false;//记录当前点在不在队列里
for(int i=first[now];i;i=ed[i].next)
{
int e=ed[i].e;
int d=dist[now]+ed[i].d;
if(d<dist[e])
{
dist[e]=d;//如果e变短了，那么也可以用它去更新其他点的最短路
if(!inque[e])
{
inque[e]=true;
q.push(e);
}
}
}
}
}
int main()
{
return 0;
}判断负环
可以记录每个点到起点经过的边数，边数不超过n-1；也可以记录每个点的入队次数，这个次数不能超过n-1。
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000007
int first[maxn],dist[maxn],times[maxn];
bool inque[maxn];
struct edge
{
int e,next;
int d;//长度
}ed[maxn];
int cnt;
int T,n,m;
void add_edge(int u,int v,int w)
{
cnt++;
ed[cnt].next=first[u];
ed[cnt].e=v;
ed[cnt].d=w;
first[u]=cnt;
}
bool spfa(int s)
{
memset(times,0,sizeof(times));
memset(inque,0,sizeof(inque));
memset(dist,0x3f,sizeof(dist));
times[s]=1;
dist[s]=0;
queue<int> q;
q.push(s);//一开始只知道s的最短路
while(q.size())
{
int now=q.front();
q.pop();
inque[now]=false;//记录当前点在不在队列里
for(int i=first[now];i;i=ed[i].next)
{
int e=ed[i].e;
int d=dist[now]+ed[i].d;
if(d<dist[e])
{
dist[e]=d;//如果e变短了，那么也可以用它去更新其他点的最短路
if(!inque[e])
{
inque[e]=true;
q.push(e);
times[e]++;//记录入队次数
if(times[e]>n)//因为有0号点
return true;//存在负环
}
}
}
}
return false;
}
int main()
{
scanf("%d",&T);
for(int i=1;i<=T;i++)
{
scanf("%d%d",&n,&m);
for(int j=1;j<=m;j++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(c>=0)
{
add_edge(a,b,c);
add_edge(b,a,c);
}
else add_edge(a,b,c);
}
if(spfa(1))
cout<<"YES"<<endl;
else cout<<"NO"<<endl;
memset(first,0,sizeof(first));
}
return 0;
}Dijkstra
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000007
int dist[maxn],first[maxn];
int n,m,s;
bool righ[maxn];//这个点有没有放到右边去
struct point{
int p,d;//原点到p的最短距离为d
point(){}
point(int a,int b){p=a;d=b;}
};
bool operator<(const point &a,const point &b)//STL默认大根堆，上面是大的
{
return a.d>b.d;//小根堆
}
priority_queue<point> heap;
//松弛操作
struct edge
{
int e,next;
int d;//长度
}ed[maxn];
int cnt;
void add_edge(int u,int v,int w)
{
cnt++;
ed[cnt].next=first[u];
ed[cnt].e=v;
ed[cnt].d=w;
first[u]=cnt;
}
void dijkstra(int s)
{
memset(dist,0x3f,sizeof(dist));//全部都赋值为最大值
dist[s]=0;//s到s
heap.push(point(s,0));
//可以无变量名
while(!heap.empty())
{
point now=heap.top();
heap.pop();
if(righ[now.p]) continue;//判断要写在这里，不能直接判断堆顶，因为可能pop之后堆就空了导致RE
int p=now.p;
// int d=now.d;//未加堆优化版，找到目前dist最小的点
// int p=-1;//代表还没选任何点
// for(int j=1;j<=n;j++)//循环后就找到了在左边最短路最小的点
// {
// if(!righ[j]&&(p==-1||dist[p]>dist[j]))//righ[]代表有没有放到右边去
// p=j;
righ[p]=1;//放到右边，枚举出边
for(int j=first[p];j; j=ed[j].next)//ed[j].e即为p的下一个点
{
int e=ed[j].e;
int d=dist[p]+ed[j].d;
if(dist[e]>d)
{
dist[e]=d;
if(!righ[e]) heap.push(point(e,d));//没访问过并且松弛过的点
}
}
}
}
signed main()
{
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add_edge(u,v,w);
}
dijkstra(s);
for(int i=1;i<=n;i++)
{
if(dist[i]==1061109567)
{
cout<<2147483647<<" ";
continue;
}
printf("%d ",dist[i]);
}
return 0;
}Floyed
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dist[i][j]=max(dist[i][j],dist[i][k]+dist[k][j]);Johnson
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4 + 10;
const int M = 6e3 + 10;
int n, m, edcnt;
int h[N];
int s[N],t[N],d[N];
int fir[N];
int dist[N];
bool vis[N];
struct edge
{
int to, val, nxt;
}e[(M << 1) + N];
struct point
{
int id,len;
point(){}
point(int a,int b):id(a),len(b){}
bool operator < (const point &x)const
{
return len > x.len;
}
};
void Add(int u, int v, int w)
{
e[++edcnt].nxt = fir[u];
e[edcnt].to = v;
e[edcnt].val = w;
fir[u] = edcnt;
}
void Dijkstra(int s)
{
memset(dist, 0x3f, sizeof(dist));
memset(vis, 0, sizeof(vis));
dist[s] = 0;
priority_queue<point> q;
while(!q.empty()) q.pop();
q.push(point(s,0));
while(!q.empty())
{
point now = q.top();
q.pop();
if(vis[now.id]) continue;
vis[now.id] = true;
for(int i = fir[now.id]; i; i = e[i].nxt)
{
int v = e[i].to;
int d = dist[now.id] + e[i].val;
if(d < dist[v])
{
dist[v] = d;
if(!vis[v]) q.push(point(v,dist[v]));
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1; i <= m; ++i)
scanf("%d%d%d",&s[i],&t[i],&d[i]);
int tot = m;
for(int i = 1; i <= n; ++i)
{
s[++tot] = 0;
t[tot] = i;
d[tot] = 0;
}
for(int i = 1; i <= n; ++i) // 多加了一个源点，所以最多松弛 n 次
for(int j = 1; j <= n + m; ++j) // n+m条边
h[t[j]] = min(h[t[j]], h[s[j]] + d[j]);
for(int j = 1; j <= n + m; ++j)
if(h[t[j]] > h[s[j]] + d[j])
{
printf("-1");
return 0;
}
for(int i = 1; i <= m; ++i)
Add(s[i], t[i], d[i] + h[s[i]] - h[t[i]]);
for(int i = 1; i <= n; ++i)
{
Dijkstra(i);
ll ans = 0;
for(int j = 1; j <= n; ++j)
ans += j * (dist[j] == 0x3f3f3f3f ? 1e9 : dist[j] - h[i] + h[j]);
printf("%lld\n", ans);
}
return 0;
}倍增求 LCA
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000007
int dist[maxn],first[maxn],f[maxn][20],depth[maxn],g[maxn][20];
int n,m,s;
struct edge
{
int e,next;
int d;//长度
}ed[maxn];
int cnt;
void add_edge(int u,int v,int w)
{
cnt++;
ed[cnt].next=first[u];
ed[cnt].e=v;
ed[cnt].d=w;
first[u]=cnt;
}
void dfs(int now)//从根节点开始dfs//预处理
{
for(int i=first[now];i;i=ed[i].next)
if(ed[i].e!=f[now][0])
{
int p=ed[i].e;
depth[p]=depth[now]+1;
f[p][0]=now;
g[p][0]=ed[i].d;//代表从p向上走……步（这里指一步）所经过的最短距离为这条边的边权
for(int x=1;x<=18;x++)
{
f[p][x]=f[f[p][x-1]][x-1];
g[p][x]=min(g[p][x-1],g[f[p][x-1]][x-1]);
}
dfs(p);
}
}
//1.调整深度2.一起跳
int get_lca(int p1,int p2)//魔改后是求边权最小值
{
depth[0] = -1; // 防止跳到零号点
if(depth[p1]<depth[p2]) swap(p1,p2);//保证p1较深
for(int x=18;x>=0;x--)
{
int p=f[p1][x];
if(depth[p]>=depth[p2])
{
p1=p;//完成后p1p2深度就一致了
}
}
if(p1==p2) return p1;//防止p1，p2在同一点上
for(int x=18;x>=0;x--)
{
if(f[p1][x]!=f[p2][x])
{
p1=f[p1][x],p2=f[p2][x];
}
}
return f[p1][0];
}离散化
#include<bits/stdc++.h>
using namespace std;
const int N=500;
struct dat{
int val,id;
}olda[N];
int newa[N];
bool cmp(dat x,dat y)
{
return x.val<y.val;
}
int n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&olda[i].val);
olda[i].id=i;
}
sort(olda+1,olda+1+n,cmp);
for(int i=1;i<=n;i++)
{
newa[olda[i].id]=i;
if(olda[i].val==olda[i-1].val)
newa[olda[i].id]=newa[olda[i-1].id];
}
for(int i=1;i<=n;i++)
{
printf("%d ",newa[i]);
}
return 0;
}高精度
加法
#include<bits/stdc++.h>
using namespace std;
int a[520],b[520],c[520];
int main()
{
string A,B;
cin>>A>>B;
int len=max(A.length(),B.length());
for(int i=A.length()-1,j=1;i>=0;i--,j++)
a[j]=A[i]-'0';
for(int i=B.length()-1,j=1;i>=0;i--,j++)
b[j]=B[i]-'0';
for(int i=1;i<=len;i++)
{
c[i]+=a[i]+b[i];
c[i+1]=c[i]/10;
c[i]%=10;
}
if(c[len+1])
len++;
for(int i=len;i>=1;i--)
printf("%d",c[i]);
}乘法
#include<bits/stdc++.h>
using namespace std;
int a[10200],b[10200],c[10200];
int main()
{
string A,B;
cin>>A>>B;
int lena=A.length(),lenb=B.length();
for(int i=lena-1;i>=0;i--)
a[lena-i]=A[i]-'0';
for(int i=lenb-1;i>=0;i--)
b[lenb-i]=B[i]-'0';
for(int i=1;i<=lena;i++)
{
for(int j=1;j<=lenb;j++)
{
c[i+j-1]+=a[i]*b[j];
}
}
int len=lena+lenb;
for(int i=1;i<=len;i++)
{
c[i+1]+=c[i]/10;
c[i]%=10;
}
while(!c[len])
len--;
for(int i=max(1,len);i>=1;i--)
printf("%d",c[i]);
}排序
快速排序
#include<bits/stdc++.h>
using namespace std;
int s[200005];
void qsort(int a[],int l,int r)
{
int i=l,j=r,flag=a[(l+r)/2],tmp;
do{
while(a[i]<flag) i++;
while(a[j]>flag) j--;
if(i<=j)
{
swap(a[i],a[j]);
// tmp=a[i];
// a[i]=a[j];
// a[j]=tmp;
i++,j--;
}
}while(i<=j);
if(l<j)
qsort(a,l,j);
if(i<r)
qsort(a,i,r);
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
scanf("%d",&s[i]);
qsort(s,1,n);
for(int i=1;i<=n;i++)
{
printf("%d ",s[i]);
}
}拓扑排序
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m;
int h[N],e[N],nex[N],cnt;
int que[N],d[N];
void add(int a,int b)//他是从0~m-1
{
e[++cnt]=b;//end
nex[cnt]=h[a];
h[a]=cnt;
}
bool topsort()
{
int hh=1,tt=0;
for(int l=1;l<=n;l++)
if(!d[l])
que[++tt]=l;
while(hh<=tt)
{
int t=que[hh++];//取出队首
for(int i=h[t];i!=-1;i=nex[i])
{
int j=e[i];
d[j]--;
if(d[j]==0)
que[++tt]=j;
}
}
return tt==n;
}
int main()
{
scanf("%d%d",&n,&m);
memset(h,-1,sizeof(h));
for(int i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
d[b]++;
}
if(topsort())
{
for(int i=1;i<=n;i++)
printf("%d ",que[i]);
puts("");
}
else
cout<<-1<<endl;
return 0;
}最小生成树
Kruscal
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+7;
int n,m;
int fa[N];
struct edge{
int u,v,w;//u-----w------>v
}eg[1000005];
bool cmp(edge a,edge b)
{
return a.w<b.w;
}
int cnt,ans,tot;
void add(int u,int v,int w)
{
eg[++cnt].u=u;
eg[cnt].v=v;
eg[cnt].w=w;
}
int find(int x)
{
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void Kruscal()
{
sort(eg+1,eg+m+1,cmp);
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++)
{
int rootu=find(eg[i].u);
int rootv=find(eg[i].v);
if(rootu!=rootv)
{
ans+=eg[i].w;
tot++;
fa[rootu]=rootv;
}
}
return;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&eg[i].u,&eg[i].v,&eg[i].w);
return 0;
}Prim
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000007
int dist[maxn],first[maxn];
int n,m,s;
bool righ[maxn];//这个点有没有放到右边去
struct point{
int p,d;//原点到p的最短距离为d
point(){}
point(int a,int b){p=a;d=b;}
};
bool operator<(const point &a,const point &b)//STL默认大根堆，上面是大的
{
return a.d>b.d;
}
priority_queue<point> heap;
//松弛操作
struct edge
{
int e,next;
int d;//长度
}ed[maxn];
int cnt;
void add_edge(int u,int v,int w)
{
cnt++;
ed[cnt].next=first[u];
ed[cnt].e=v;
ed[cnt].d=w;
first[u]=cnt;
}
void prim(int s)
{
memset(dist,0x3f,sizeof(dist));//全部都赋值为最大值
dist[s]=0;//s到s
heap.push(point(s,0));
while(!heap.empty())
{
point now=heap.top();
heap.pop();
int p=now.p;
if(righ[p]) continue;
righ[p]=1;//放到右边
for(int j=first[p];j;j=ed[j].next)//ed[j].e即为p的下一个点
{
int e=ed[j].e;
int d=ed[j].d;
if(dist[e]>d)
{
dist[e]=d;
if(!righ[e]) heap.push(point(e,d));
}
}
}
}
signed main()
{
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add_edge(u,v,w);
}
return 0;
}莫队
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+8;
int q,a[N],cnt[N],l=1,r=0,now=0,belong[N];
struct query
{
int l,r;
}e[N];
int cmp(query a, query b)
{
return (belong[a.l]^belong[b.l])?belong[a.l]<belong[b.l]:((belong[a.l]&1)?a.r<b.r:a.r>b.r);
}
void add(int pos)
{
if(!cnt[a[pos]]) ++now;
++cnt[a[pos]];
}
void del(int pos)
{
--cnt[a[pos]];
if(!cnt[a[pos]]) --now;
}
void work()
{
for(int i=1;i<=q;i++)
{
int ql,qr;
scanf("%d%d",&qr,&ql);
while(l<ql) del(l++);
while(l>ql) add(--l);
while(r<qr) add(++r);
while(r>qr) del(r--);
printf("%d",now);
}
}
int main()
{
return 0;
}快读
int
inline int read()
{
int x=0,y=1;
char c=getchar();
while(c>'9'||c<'0')
{
if(c=='-') y=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
return x*y;
}double
inline double read()
{
double x=0,y=1,w=1;
char c=getchar();
while(c>'9'||c<'0')
{
if(c=='-') y=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
if(c=='.')
{
c=getchar()
while(c>='0'&&c<='9')
{
w=w/10.0;
x+=(c-'0')*w;
c=getchar();
}
}
return x*y;
}线段树
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
typedef long long ll;
int a[N];
struct node
{
int l,r;
ll add,sum;
}tr[N<<2];
void pushup(int u)//上传
{
tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void pushdown(int u)//下放
{
node &root=tr[u],&left=tr[u<<1],&righ=tr[u<<1|1];
if(root.add)
{
left.add+=root.add;
left.sum+=1ll*(left.r-left.l+1)*root.add;
righ.add+=root.add;
righ.sum+=1ll*(righ.r-righ.l+1)*root.add;
root.add=0;
}
}
void build(int u,int l,int r)//从u开始递归，建l~r的树，一般为build(1,1,n)
{
tr[u].l=l,tr[u].r=r;
if(l==r)
{
tr[u].sum=a[r];
tr[u].add=0;
return;
}
int mid=(l+r)>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
void modify(int u,int l,int r,int d)//从u开始递归，查询区间，加上d
{
if(tr[u].l>=l&&tr[u].r<=r)
{
tr[u].sum+=1ll*(tr[u].r-tr[u].l+1)*d;
tr[u].add+=d;
return;
}
pushdown(u);
int mid=(tr[u].l+tr[u].r)>>1;
if(l<=mid) modify(u<<1,l,r,d);
if(r>mid) modify(u<<1|1,l,r,d);
pushup(u);
}
ll query(int u,int l,int r)//从u开始递归，查询l，r之间的区间和
{
if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;
pushdown(u);
int mid=(tr[u].l+tr[u].r)>>1;
ll sum=0;
if(l<=mid) sum+=query(u<<1,l,r);
if(r>mid) sum+=query(u<<1|1,l,r);
return sum;
}
int main()
{
return 0;
}#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
int n, m, q;
int a[N];
struct Node
{
int l, r;
LL sum, add, mul;
}tr[N << 2];
void pushup(int u)
{
tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % q;
}
void eval(Node &t, LL add, LL mul)
{
t.sum = (t.sum * mul % q + (t.r - t.l + 1) * add % q);
t.add = (t.add * mul % q + add) % q;
t.mul = t.mul * mul % q;
}
void pushdown(int u)
{
eval(tr[u << 1], tr[u].add, tr[u].mul);
eval(tr[u << 1 | 1], tr[u].add, tr[u].mul);
tr[u].add = 0;
tr[u].mul = 1;
}
void build(int u, int l, int r)
{
tr[u].l = l, tr[u].r = r, tr[u].add = 0, tr[u].mul = 1;
if(l == r)
{
tr[u].sum = a[r];
return;
}
int mid = (l + r) >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void modify(int u, int l, int r, int add, int mul)
{
if(tr[u].l >= l && tr[u].r <= r)
{
eval(tr[u], add, mul);
return;
}
pushdown(u);
int mid = (tr[u].l + tr[u].r) >> 1;
if(l <= mid) modify(u << 1, l, r, add, mul);
if(r > mid) modify(u << 1 | 1, l, r, add, mul);
pushup(u);
}
LL query(int u, int l, int r)
{
if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
pushdown(u);
int mid = (tr[u].l + tr[u].r) >> 1;
LL sum = 0;
if(l <= mid) sum = (sum + query(u << 1, l, r)) % q;
if(r > mid) sum = (sum + query(u << 1 | 1, l, r)) % q;
return sum;
}
int main()
{
scanf("%d%d%d", &n, &m, &q);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
build(1, 1, n);
while(m--)
{
int op, l, r, k;
scanf("%d%d%d", &op, &l, &r);
if(op == 1)
{
scanf("%d", &k);
modify(1, l, r, 0, k);
}
else if(op == 2)
{
scanf("%d", &k);
modify(1, l, r, k, 1);
}
else printf("%lld\n", query(1, l, r));
}
return 0;
}可持久化
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
int n, m, cnt;
int idx;
int a[N];
int root[N];
struct Node
{
int l, r;
int key;
}tr[23 * N];
void build(int &u, int l, int r)
{
u = ++idx;
if(l == r)
{
tr[u].key = a[r];
return;
}
int mid = (l + r) >> 1;
build(tr[u].l, l, mid);
build(tr[u].r, mid + 1, r);
}
void modify(int &u, int p, int l, int r, int x, int v)
{
u = ++idx;
tr[u] = tr[p];
if(l == r)
{
tr[u].key = v;
return;
}
int mid = (l + r) >> 1;
if(x <= mid) modify(tr[u].l, tr[p].l, l, mid, x, v);
else modify(tr[u].r, tr[p].r, mid + 1, r, x, v);
}
int query(int u, int l, int r, int x)
{
if(!u) return 0;
if(l == r) return tr[u].key;
int mid = (l + r) >> 1;
if(x <= mid) return query(tr[u].l, l, mid, x);
if(x > mid) return query(tr[u].r, mid + 1, r, x);
return 0;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
build(root[0], 1, n);
while(m--)
{
int op, last, loc, val;
scanf("%d%d", &last, &op);
if(op == 1)
{
scanf("%d%d", &loc, &val);
modify(root[++cnt], root[last], 1, n, loc, val);
}
else if(op == 2)
{
scanf("%d", &val);
printf("%d\n", query(root[last], 1, n, val));
root[++cnt] = root[last];
}
}
return 0;
}平衡树
Treap
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
const int INF = 1e8;
int n, root, idx;
struct Node
{
int l, r, key, val;
int cnt, siz;
}tr[N];
int get_node(int key)
{
tr[++idx].key = key;
tr[idx].val = rand();
tr[idx].cnt = tr[idx].siz = 1;
return idx;
}
void pushup(int p)
{
tr[p].siz = tr[tr[p].l].siz + tr[tr[p].r].siz + tr[p].cnt;
}
void build()
{
root = get_node(-INF);
tr[root].r = get_node(INF);
pushup(root);
}
void zig(int &p)
{
int q = tr[p].l;
tr[p].l = tr[q].r;
tr[q].r = p;
p = q;
pushup(tr[p].r);
pushup(p);
}
void zag(int &p)
{
int q = tr[p].r;
tr[p].r = tr[q].l;
tr[q].l = p;
p = q;
pushup(tr[p].l);
pushup(p);
}
void insert(int &p, int key)
{
if(!p) p = get_node(key);
else if(tr[p].key == key) tr[p].cnt++;
else if(tr[p].key > key)
{
insert(tr[p].l, key);
if(tr[tr[p].l].val > tr[p].val) zig(p);
}
else
{
insert(tr[p].r, key);
if(tr[tr[p].r].val > tr[p].val) zag(p);
}
pushup(p);
}
void remove(int &p, int key)
{
if(!p) return;
if(tr[p].key == key)
{
if(tr[p].cnt > 1) tr[p].cnt--;
else if(tr[p].l || tr[p].r)
{
if(!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val)
{
zig(p);
remove(tr[p].r, key);
}
else
{
zag(p);
remove(tr[p].l, key);
}
}
else p = 0;
}
else if(tr[p].key > key) remove(tr[p].l, key);
else remove(tr[p].r, key);
pushup(p);
}
int get_rank(int p, int key)
{
if(!p) return 1;
if(tr[p].key == key) return tr[tr[p].l].siz + 1;
if(tr[p].key > key) return get_rank(tr[p].l, key);
return tr[tr[p].l].siz + tr[p].cnt + get_rank(tr[p].r, key);
}
int get_key(int p, int rank)
{
if(!p) return INF;
if(tr[tr[p].l].siz >= rank) return get_key(tr[p].l, rank);
if(tr[tr[p].l].siz + tr[p].cnt >= rank) return tr[p].key;
return get_key(tr[p].r, rank - tr[tr[p].l].siz - tr[p].cnt);
}
int get_prev(int p, int key)
{
if(!p) return -INF;
if(tr[p].key >= key) return get_prev(tr[p].l, key);
return max(tr[p].key, get_prev(tr[p].r, key));
}
int get_next(int p, int key)
{
if(!p) return INF;
if(tr[p].key <= key) return get_next(tr[p].r, key);
return min(tr[p].key, get_next(tr[p].l, key));
}
int main()
{
build();
scanf("%d", &n);
while(n--)
{
int op, x;
scanf("%d%d", &op, &x);
switch(op)
{
case 1:
insert(root, x);
break;
case 2:
remove(root, x);
break;
case 3:
printf("%d\n", get_rank(root, x) - 1);
break;
case 4:
printf("%d\n", get_key(root, x + 1));
break;
case 5:
printf("%d\n", get_prev(root, x));
break;
case 6:
printf("%d\n", get_next(root, x));
break;
}
}
return 0;
}字符串
KMP
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
char a[N],b[N];
int nxt[N];
int la,lb;
void calc()
{
for(int i=1,j=0;i<lb;i++)
{
while(j&&b[i]!=b[j]) j=nxt[j-1];
if(b[i]==b[j]) j++;
nxt[i]=j;
}
}
void kmp()
{
for(int i=0,j=0;i<la;i++)
{
while(j&&a[i]!=b[j]) j=nxt[j-1];
if(a[i]==b[j]) j++;
if(j==lb)
{
printf("%d\n",i-j+2);
j=nxt[j-1];
}
}
}
int main()
{
scanf("%s%s",a,b);
la=strlen(a);
lb=strlen(b);
calc();
kmp();
for(int i=0;i<lb;i++)
printf("%d ",nxt[i]);
return 0;
}Z
#include<bits/stdc++.h>
using namespace std;
char s[1000005];
int n;
int z[100005];
int main()
{
n=strlen(s);
z[0]=n;
for(int i=1,l=0,r=0;i<n;i++)
{
if(z[i-l]<r-i+1)//当前已经相同的部分比已知lcp要大
z[i]=z[i-l];
else
{
z[i]=max(r-i+1,0);
while(i+z[i]<n&&s[z[i]]==s[i+z[i]]) z[i]++;
l=i,r=i+z[i]-1;
}
}
return 0;
}Manacher
#include<bits/stdc++.h>
using namespace std;
int n;
int d[1000005];
char s[1000005];
int main()
{
for(int i=0,l=0,r=-1;i<n;i++)
{
int j=l+r-i;//对称点
int dj=j>=0?d[j]:0;//不能越界
d[i]=max(min(dj,r-i+1),0);
if(j-dj<l)//j-dj+1<=l
{
while(i-d[i]>=0&&i+d[i]<n&&s[i-d[i]]==s[i+d[i]]) d[i]++;
l=i-d[i]+1,r=i+d[i]-1;
}
}
return 0;
}Trie
数学
快速幂
非递归：
int ksm(int x, int y)
{
int res = 1;
while(y > 0)
{
if(y & 1) res = res * x;
x = x * x;
y >>= 1;
}
return res;
}递归：
int ksm(int x, int y)
{
if(y == 1) return x;
int z = ksm(x, (y >> 1));
z = z * z;
if(y & 1) z = z * x;
return z;
}素性测试
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int prime[] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
int n;
ll Ksm(int x, int y, int p)
{
ll res = 1;
while(y > 0)
{
if(y & 1) res = res * x % p;
x = x * x % p;
y >>= 1;
}
return res;
}
bool Miller_Rubbin(int n, int a)
{
int d = n - 1, r = 0;
while(!(d & 1))
{
d >>= 1;
r++;
}
int x = Ksm(a, d, n);
if(x == 1) return true;
for(int i = 1; i <= r; ++i)
{
if(x == n - 1) return true;
x = 1ll * x * x % n;
}
return false;
}
bool Check(int x)
{
if(n < 2) return false;
for(int i = 1; i <= 12; ++i)
{
if(!Miller_Rubbin(x, prime[i])) return false;
}
return true;
}
int main()
{
int t;
scanf("%d", &t);
cout << Check(t) << endl;
return 0;
}