模板整理(2022.10)
1.线性筛素数
bool is_prime[100000005];//是否为素数
int prime[100005],cnt;//素数数组,cnt:素数个数
void get_prime(int maxn){
memset(is_prime,1,sizeof(is_prime));
is_prime[1]=0;
for(int i=2;i<=maxn;i++){
if(is_prime[i])prime[++cnt]=i;//是素数
for(int j=1;j<=cnt&&i*prime[j]<=maxn;j++){//筛
is_prime[i*prime[j]]=0;
if(i%prime[j]==0)break;//背板
}
}
}
2.并查集
int fa[MAXN];
void init(int maxn){for(int i=1;i<=maxn;i++)fa[i]=i;}//初始化
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}//找祖先(顺藤摸瓜,带路径压缩)
void link(int x,int y){//连接两个点
int fx=find(x),fy=find(y);
if(fx!=fy)fa[fx]=fy;//防止环
}
bool ask(int x,int y){return find(x)==find(y);}//判断两个点是否是同一个祖先
3.快速幂
int Pow(int n,int k,int m){//求n^k(mod m)
int ans=1;
while(k){
if(k&1)ans=(ans*n)%m;
n=(n*n)%m;
k>>=1;
}
return ans;
}
4.最小生成树
1.Kruskal
struct edge{int u,v,w;};
vector<edge> v;
bool cmp(edge a,edge b){return a.w<b.w;}
//并查集模板
//input...
init(n);
sort(v.begin(),v.end(),cmp);//排序
int cnt=0,ans=0;
for(int i=0;i<m;i++){
if(cnt==n-1)break;//选好了
int fx=find(v[i].u),fy=find(v[i].v);
if(fx!=fy)fa[fx]=fy,ans+=v[i].w,cnt++;//选
}
//output...
2.Prim
int prim(){
memset(dis,0x3f,sizeof(dis));
q.push(node{1,0});
int cnt=0,ans=0;
while(cnt<n&&!q.empty()){
node now=q.top();q.pop();
if(vis[now.x])continue;
vis[now.x]=true;
ans+=now.dis,cnt++;
for(int i=head[now.x];i;i=nxt[i]){
if(dis[ver[i]]>edge[i]){
dis[ver[i]]=edge[i];
q.push(node{ver[i],dis[ver[i]]});
}
}
}
return ans;
}
//main()
//input...
//ans=prim();
//output...
5.字典树
class Trie{
private:
int t[3000011][70];
int cnt[3000011];
int tot;
int char_int(char x){//可根据实际情况更改
if(x>='A'&&x<='Z')return x-'A';
if(x>='a'&&x<='z')return x-'a'+26;
if(x>='0'&&x<='9')return x-'0'+52;
}
public:
void clear(){//清空
for(int i=0;i<=tot+2;i++){
for(int j=0;j<=70;j++){
t[i][j]=0;
}
}
for(int i=0;i<=tot+2;i++)cnt[i]=0;
tot=0;
}
void Insert(string s){//插入
int len=s.size(),now=0;
for(int i=0;i<len;i++){
int c=char_int(s[i]);
if(!t[now][c])t[now][c]=++tot;
now=t[now][c];
cnt[now]++;
}
}
int Ask(string s){//询问(前缀)
int len=s.size(),now=0;
for(int i=0;i<len;i++){
int c=char_int(s[i]);
if(!t[now][c])return 0;
now=t[now][c];
}
return cnt[now];
}
};
6.求逆元
1.线性求逆元
int ni[3000001];
void get_ni(int n,int p){//求1~n所有数在(mod p)意义下的逆元
ni[1]=1;
for(int i=2;i<=n;i++)
ni[i]=p-(p/i)*ni[p%i]%p;//不理解,背板即可
}
2.费马小定理(模数p为质数时)
\[a^{-1} \equiv a^{p-2}\pmod p \]用快速幂即可。
3.Exgcd
还不会，普及组应该不会考，之后再来补充
7. LCA
//dfs ... (get de[x] and fa[x])
int getlca(int x,int y){
if(de[x]<de[y])swap(x,y);
for(int i=19;i>=0;i--){
if(de[fa[x][i]]>=de[y])
x=fa[x][i];
if(x==y)
return x;
}
for(int i=19;i>=0;i--)
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
8.KMP
nxt[1]=0;//背板即可
for(int i=2,j=0;i<=lenb;i++){
while(j&&strb[j+1]!=strb[i])j=nxt[j];//求出最长公共前后缀
if(strb[j+1]==strb[i])j++;
nxt[i]=j;
}
for(int i=1,j=0;i<=lena;i++){
while(j&&strb[j+1]!=stra[i])j=nxt[j];
if(strb[j+1]==stra[i])j++;
if(j==lenb){
printf("%d\n",i-lenb+1);//匹配的位置
j=nxt[j];
}
}
9.manacher
while(scanf("%c",&c)!=EOF){//背板,考的可能性不大吧
if(c=='\n')break;
s[len++]='#';
s[len++]=c;
}
s[len++]='#';
int l=0,r=-1,ans=0;
for(int i=0;i<len;i++){
if(i<=r)p[i]=min(p[l+r-i],r-i+1);
while(i+p[i]<len&&i-p[i]>=0&&s[i+p[i]]==s[i-p[i]])p[i]++;
if(i+p[i]-1>r){
r=i+p[i]-1;
l=i-p[i]+1;
}
ans=max(ans,p[i]);
}
10.最短路
1.Floyd
Time:\(O(n^3)\)
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
2.SPFA
他死了
3.Dijkstra
Time:\(O(mlogm)\)
memset(dis,0x7f,sizeof(dis));
q.push(pir(0,s));
dis[s]=0;
while(!q.empty()){
int x=q.top().id;
q.pop();
if(vis[x])continue;
vis[x]=1;
for(int i=head[x];i;i=nxt[i]){
int y=ver[i],z=edge[i];
if(dis[y]>dis[x]+z){
dis[y]=dis[x]+z;
q.push(pir(dis[y],y));
}
}
}
11.Tarjan
1.强连通分量
void tarjan(int x){
low[x]=dfn[x]=++cnt;
stk.push(x);
instack[x]=1;
for(int i=head[x];i;i=nxt[i]){
int v=ver[i];
if(!dfn[v]){
tarjan(v);
low[x]=min(low[x],low[v]);
}else if(instack[v])
low[x]=min(low[x],dfn[v]);
}
if(dfn[x]==low[x]){
sc++;
while(stk.top()!=x){
scc[stk.top()]=sc;
sccs[sc]++;
instack[stk.top()]=0;
stk.pop();
}
scc[x]=sc;
instack[x]=0;
sccs[sc]++;
stk.pop();
}
}
2.割点
void tarjan(int x,bool root){//x:当前节点,root:是不是根
cnt++;
dfn[x]=cnt;//当前dfn
low[x]=dfn[x];//low的初始值等于dfn
int num=0;//字数个数,用于统计特殊情况
for(int i=head[x];i;i=nxt[i]){
int v=ver[i];
if(!dfn[v]){//没被访问过,树边
fa[v]=x;//统计父节点
tarjan(v,false);//dfs
low[x]=min(low[x],low[v]);//统计low值
if(!root&&low[v]>=dfn[x])//不是根且满足条件
isg[x]=true;//时割点
if(root)//是根
num++;//统计子树
}else if(v!=fa[x])//不是父节点,被访问过,虚边
low[x]=min(low[x],dfn[v]);//统计low值
}
if(root&&num>1)//是根且满足条件
isg[x]=true;//是割点
}
3.桥
void tarjan(int x){
cnt++;
dfn[x]=cnt;//dfn
low[x]=dfn[x];//low
for(int i=head[x];i;i=nxt[i]){
int v=ver[i];
if(!dfn[v]){//树边
fa[v]=x;//统计父节点
tarjan(v);
low[x]=min(low[x],low[v]);//low
if(low[v]>dfn[x])//条件
ans.push_back(make_pair(x,v));//统计答案
}else if(v!=fa[x])//不是父节点,被访问过,虚边
low[x]=min(low[x],dfn[v]);//low
}
}
4.点双连通分量
void tarjan(int x,int fa){
dfn[x]=low[x]=++cnt;
stk[++top]=x;
int son=0;
for(int i=head[x];i;i=nxt[i]){
int v=ver[i];
if(!dfn[v]){
tarjan(v,x);
son++;
low[x]=min(low[x],low[v]);
if(low[v]>=dfn[x]){
bcc++;
while(stk[top]!=v&&top!=0)ans[bcc].push_back(stk[top--]);//弹出不是v的
ans[bcc].push_back(stk[top--]);//弹出v
ans[bcc].push_back(x);
}
}else if(v!=fa) low[x]=min(low[x],dfn[v]);
}
if(fa==0&&son==0)ans[++bcc].push_back(x);
}
5.边双连通分量
void tarjan(int x,int fa){
low[x]=dfn[x]=++cnt;
for(int i=head[x];i;i=nxt[i]){
int v=ver[i];
if(!dfn[v]){
tarjan(v,x);
low[x]=min(low[x],low[v]);
if(low[v]>dfn[x])is_bridge[i]=1,is_bridge[i^1]=1;
}else if(v!=fa) low[x]=min(low[x],dfn[v]);
}
}
void dfs(int x){
if(vis[x])return;
vis[x]=1;
ans[dcc].push_back(x);
for(int i=head[x];i;i=nxt[i]){
if(is_bridge[i])continue;
dfs(ver[i]);
}
}
12. 欧拉路径
void dfs(int x){
for(int i=nex[x];i<g[x].size();i=nex[x]){
nex[x]=i+1;
dfs(g[x][i]);
}
stk.push(x);
}
int main(){
//input...
for(int i=1,x,y;/*....*/;i++){
//input...
g[x].push_back(y);
in[y]++,out[x]++;
}
int flag=1,cnt1=0,cnt2=0,st=1;
for(int i=1;i<=n;i++){
if(in[i]!=out[i])flag=0;
if(in[i]==out[i]+1)cnt1++;
if(in[i]==out[i]-1)cnt2++,st=i;
}
if(!flag&&!(cnt1==1&&cnt2==1))return puts("No"),0;
dfs(st);
while(!stk.empty()){
/*output:stk.top()*/
stk.pop();
}
return 0;
}
/*
欧拉路径判定(是否存在):
有向图欧拉路径:
图中恰好存在1个点出度比入度多1,这个点即为起点.1个点入度比出度多1,这个点即为终点.其余节点出度=入度.
有向图欧拉回路:所有点的入度=出度(起点和终点可以为任意点).
无向图欧拉路径:
图中恰好存在2个点的度数是奇数,其余节点的度数为偶数,这两个度数为奇数的点即为欧拉路径的起点和终点.
无向图欧拉回路:所有点的度数都是偶数(起点和终点可以为任意点).
注:存在欧拉回路(即满足存在欧拉回路的条件),也一定存在欧拉路径.
*/
13.中国剩余定理
㵘㵘㵘，还是个暴力
int now=a[1],ans=b[1];
for(int i=2;i<=n;i++){
while(ans%a[i]!=b[i])ans+=now;
now=lcm(now,a[i]);
}
14.树状数组
int lowbit(int x){return x&(-x); }
void add(int x,int i){
for(int j=i;j<=n;j+=lowbit(j))
t[j]+=x;
}
int count(int o){
int x=o,ans=0;
while(x!=0){
ans+=t[x];
x-=lowbit(x);
}
return ans;
}
int count(int x,int y){return count(y)-count(x-1);}