板子备忘

以前用过的算法模板。

线性筛素数

给定一个范围N，你需要处理M个某数字是否为质数的询问（每个数字均在范围1-N内）

在没有读入优化的情况下，这份代码提交到洛谷上速度尚可。

#include<cstdio>
using namespace std;

const int MAXN = 10000100;
bool composite[MAXN];
int prime[MAXN],tail;

void get_prime(int n)
{
    composite[0]=true;
    composite[1]=true;
    for(int i=2;i<=n;i++)
    {
        if(!composite[i])prime[tail++]=i;
        for(int j=0;j<tail&&i*prime[j]<=n;j++)
        {
            composite[i*prime[j]]=true;
            if(!(i%prime[j]))break;
        }
    }
}

int main()
{
    int n,t,temp;
    scanf("%d%d",&n,&t);
    get_prime(n);
    
    for(int i=1;i<=t;i++){
        scanf("%d",&temp);
        if(composite[temp])puts("No");
        else puts("Yes");
    }
    
    return 0;
}

KMP字符串匹配

KMP：一个人能走的多远不在于他在顺境时能走的多快，而在于他在逆境时多久能找到曾经的自己。

对着ryf的博客思路自己写的代码实现，直观但是效率低（会超时）：

#include <iostream>
#include <string>
#include <vector>

int tsize, ssize;
std::vector<int> mynext;

void getNext(std::string &t){
    mynext.resize(tsize);
    mynext[0]=0;
    for(int i=1; i<tsize; i++){
        int k=mynext[i-1];
        while((t[i] != t[k]) && (k!=0))k=mynext[k-1];
        if(t[i] == t[k])mynext[i]=k+1;
        else mynext[i]=0;
    }
}

inline void output(int i){
    std::cout<<i+1<<"\n";
}

void kmp(std::string &s, std::string &t, int startpos){
    int i = startpos, j = 0;
    ssize = s.size(), tsize = t.size();
    getNext(t);
    while(s[i]!=t[0]){i++;}
    int icopy = i;

    while(i+tsize<=ssize){
        while(s[i]!=t[0] && i+tsize<ssize){i++; icopy=i;}
        if(s[icopy]==t[j]){
            icopy++, j++;
            if(j==tsize){
                output(i);
                i += j-mynext[j-1];
                icopy = i; j = 0;
            }
        }
        else{
            if(i+tsize>=ssize)return;
            i += j-mynext[j-1];
            icopy = i; j = 0;
        }
    }
}

int main(){
    std::string s, t;
    std::cin>>s>>t;
    kmp(s, t, 0);

    for(auto i = mynext.begin(); i != mynext.end(); i++){
        std::cout<<*i<<" ";
    }
    return 0;
}

提交入口： https://www.luogu.com.cn/problem/P3375

根据教学视频改进的可用版本：

#include <cstdio>
#include <cstring>

const int MAXL = 1e6+10;
char s[MAXL], t[MAXL];
int mynext[MAXL], ssize, tsize;

inline void output(int i){
    printf("%d\n",i+1);
    //题目要求下标从1开始
    //仅在输出时作相应处理
}
/*   需要其他形式的KMP可以由以下代码改：
class Solution {
public:
    void getNext(int* next, const string& s) {
        int j = 0;
        next[0] = 0;
        for(int i = 1; i < s.size(); i++) {
            while (j > 0 && s[i] != s[j]) {
                j = next[j - 1];
            }
            if (s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }
    }
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;
        }
        int next[needle.size()];
        getNext(next, needle);
        int j = 0;
        for (int i = 0; i < haystack.size(); i++) {
            while(j > 0 && haystack[i] != needle[j]) {
                j = next[j - 1];
            }
            if (haystack[i] == needle[j]) {
                j++;
            }
            if (j == needle.size() ) {
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};
*/
void getNext(){
    int j = 0;
    mynext[0] = 0;
    for(int i=1; i<tsize; i++){
        while(j>0 && t[i]!=t[j]) j=mynext[j-1];
        if(t[i]==t[j]) j++;
        mynext[i] = j;
    }
}
    
void kmpfind(){
    if(!tsize){printf("寻找内容为空串！\n"); return;}
    getNext();
    int j = 0;
    for (int i = 0; i < ssize; i++) {
        while(j > 0 && s[i] != t[j]) {
            j = mynext[j-1];
        }
        if(s[i]==t[j]) j++;
        if (j==tsize) {
            output(i-tsize+1);
            j = mynext[j-1];
        }
    }
}

int main(){
    scanf("%s%s",s,t);
    ssize=strlen(s); tsize=strlen(t);
    //本程序下标都是从0开始
    kmpfind();

    for(int i = 0; i<tsize; i++){
        printf("%d ",mynext[i]);
    }
    return 0;
}

并查集

#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=10010;
int uset[MAXN];

void makeset(int size){
    for(int i=0;i<size;i++)uset[i]=i;
}

int find(int x){
    if(x!=uset[x])uset[x]=find(uset[x]);
    return uset[x];
}

void unionset(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)return;
    uset[x]=y;
}


int main()
{
    int n,m; cin>>n>>m;
    makeset(n+1);
    
    int z,x,y;
    while(m--)
    {
        scanf("%d%d%d",&z,&x,&y);
        if(z==1)unionset(x,y);
        else if(z==2){
            if(find(x)==find(y))
            printf("Y\n");
            else printf("N\n");
        }
    }
    
    return 0;
}

自适应辛普森

题面：https://www.luogu.com.cn/problem/P4525

#include <cstdio>
#include <cmath>

double a,b,c,d,L,R;
inline double f(double x){
    return (c*x+d)/(a*x+b);
}

inline double simpson(double l, double r){
    double mid = l+(r-l)/2;
    return (f(l)+4*f(mid)+f(r))/6.0*(r-l);
}

double asr(double l, double r, double eps, double S, int cnt){
    double mid = l+(r-l)/2;
    double s1 = simpson(l, mid), s2 = simpson(mid, r);
    if(fabs(s1+s2-S)<=15*eps && cnt<=0)
        return s1+s2+(s1+s2-S)/15.0;
    return asr(l, mid, eps/2, s1, cnt-1) + asr(mid, r, eps/2, s2, cnt-1);
}

double calc(double l, double r, double eps){
    return asr(l, r, eps, simpson(l,r), 12);
}

int main(){
    scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&L,&R);
    printf("%.6lf",calc(L,R,1e-6));
    return 0;
}

Huffman树

参考：https://blog.csdn.net/weixin_43191865/article/details/97974221

一些概念：

• 结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。
• 树的带权路径长度为树中所有叶子结点的带权路径长度之和，通常记作WPL。例如下图所示的这颗树的带权路径长度为：WPL=7*1+5*2+2*3+4*3

当用n个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”。在构建哈弗曼树时，只需要遵循一个原则：权重越大的结点离树根越近。

例如：3 4 5 8 ，设最后答案为ans

首先我们选3 4，合并节点，新点权值为7，并加入原序列，ans+=(3+4)

然后新序列中合并5和7，新点权值为12，ans+=(5+7)

最后合并12和8，新节点为20，跳出循环，ans+=(12+8)

最后的哈夫曼树就是右边黑色的那棵树，答案就是ans。

对于某一个节点，因为其被合并之后的值给了新的节点，而新的节点合并的时候又会加上这个值，实际上是不断为答案作贡献的。

k叉哈夫曼树： 为保证其根节点可以选到k个子树，假设节点个数为n，需要满足(n-1)mod(k-1)==0的条件，若不满足，为原序列补0。

例题：NOI2015荷马史诗

参考代码：

#include <cstdio>
#include <queue>
#define MAX(a,b) ((a)>(b)?(a):(b))

typedef long long LL;
struct node{
    LL w,depth;
    bool operator<(const node& v)const{
        if(w!=v.w) return w>v.w;
        else return depth>v.depth;
    }
};
std::priority_queue<node> qwq;
LL n,k,ans;

int main(){
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++){
        LL tempw;
        scanf("%lld",&tempw);
        qwq.push((node){tempw,1});
    }

    LL qwqsize = qwq.size();
    while((qwqsize-1)%(k-1)){
        qwq.push((node){0,1});
        qwqsize++;
    }

    while(qwqsize>=k){
        LL tw = 0,tdep = -1;
        for(int i=1; i<=k; i++){
            node tq = qwq.top();
            qwq.pop(); qwqsize--;
            tdep = MAX(tdep,tq.depth);
            tw += tq.w;
        }
        ans += tw;
        qwq.push((node){tw,tdep+1});
        qwqsize++;
    }

    printf("%lld\n%lld",ans,qwq.top().depth-1);
    return 0;       
}

拓扑排序

例题：https://www.luogu.com.cn/problem/P1983

参考代码：

#include <cstdio>
#include <queue>
#include <cstring>

const int MAXN = 1e3+10;
const int MAXM = 5e7+10; //算出来的空间花费远比这个多，windows会阻止运行，算错了？
int tot,head[MAXN],n,m,spot[MAXN],in[MAXN],ans;
struct Edge{int v,next;}edge[MAXM];
bool isspot[MAXN],has[MAXN][MAXN];

inline void addedge(int x,int y){
    edge[++tot].v=y;
    edge[tot].next=head[x];
    head[x]=tot;
} //本题不应当采用这种存图方式，但我直接用has数组避免重构了

std::queue<int> qwq;
void toposort(){    //这里的toposort为适应题目做了改造
    int cnt1 = 0, cnt2 = 0;
    for(int i=1;i<=n;i++){
        if(!in[i]){ 
            qwq.push(i);
            cnt1++;
        }
    }

    while(!qwq.empty()){
        int x = qwq.front();
        qwq.pop(); cnt1--;
        for(int i=head[x];i;i=edge[i].next){
            int y=edge[i].v; in[y]--;
            if(!in[y]){
                qwq.push(y);
                cnt2++;
            }
        }
        if(!cnt1){ans++; cnt1=cnt2; cnt2=0;}  //神之一手（雾）
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int s; scanf("%d",&s);
        memset(isspot,false,sizeof(isspot));
        for(int j=1;j<=s;j++){
            scanf("%d",&spot[j]);
            isspot[spot[j]]=true;
        }
        for(int j=spot[1];j<=spot[s];j++){ //连续站点枚举
            if(!isspot[j]){
                for(int k=1;k<=s;k++){
                    if(has[spot[k]][j])continue;
                    has[spot[k]][j] = true;
                    addedge(spot[k],j);
                    in[j]++;
                }
            }
        }
    }

    toposort();
    printf("%d",ans);
    return 0;
}

最小生成树

给出一个无向图，求出最小生成树，如果该图不连通，则输出orz

输入格式：

第一行包含两个整数N、M，表示该图共有N个结点和M条无向边。（N<=5000，M<=200000）

接下来M行每行包含三个整数Xi、Yi、Zi，表示有一条长度为Zi的无向边连接结点Xi、Yi

输出格式：

输出包含一个数，即最小生成树的各边的长度之和；如果该图不连通则输出orz

//kruscal
#include<cstdio>
#include<algorithm>
using namespace std;

const int MAXN = 5000+10;
const int MAXM = 200000+10;
struct Edge{int u,v,w;}edge[MAXM];
int uset[MAXN],n,m,ans;

int find(int x){
    if(uset[x]!=x)uset[x]=find(uset[x]);
    return uset[x];
}

void unionset(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)return;
    uset[x]=y;
}

bool cmp(Edge x,Edge y){return x.w<y.w;}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        edge[i].u=x;
        edge[i].v=y;
        edge[i].w=z;
    }
    
    sort(edge+1,edge+1+m,cmp);
    for(int i=0;i<=n;i++)uset[i]=i;
    
    int cnt=0;
    for(int i=1;i<=m;i++)
    {
        int x=find(edge[i].u);
        int y=find(edge[i].v);
        if(x==y)continue;
        ans+=edge[i].w;
        unionset(x,y);
        if(++cnt==n-1)break;
    }
    
    if(cnt<n-1)printf("orz");
    else printf("%d",ans);
    return 0;
}

单源最短路径

给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入格式：

第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。

接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。

输出格式：

一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则最短路径长度为2147483647）

$SPFA$

#include<bits/stdc++.h>
#define MAXM 500010
#define MAXN 10010
#define INF 2147483647
using namespace std;

int n,m,s,dis[MAXN];
bool inq[MAXN];
struct Edge{int v,w,next;}edge[MAXM];
int tot,head[MAXN];

inline void addedge(int x,int y,int z){
    edge[++tot].v=y;
    edge[tot].w=z;
    edge[tot].next=head[x];
    head[x]=tot;
}

void spfa()
{
    queue<int> qwq;
    for(int i=1;i<=n;i++)dis[i]=INF;
    
    qwq.push(s);
    dis[s]=0;inq[s]=true;
    
    while(!qwq.empty())
    {
        int x=qwq.front();
        qwq.pop(); inq[x]=false;
        
        for(int i=head[x];i;i=edge[i].next){
            int y=edge[i].v;
            if(dis[y]>dis[x]+edge[i].w){
                dis[y]=dis[x]+edge[i].w;
                if(!inq[y]){qwq.push(y);inq[y]=true;}
            }
        }
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        addedge(x,y,z);
    }
    
    spfa();
    
    for(int i=1;i<=n;i++)
     if(s==i)printf("0 ");
     else printf("%d ",dis[i]);
    
    return 0;
}

$Dijkstra$

#include<cstdio>
#include<queue>
#define MAXM 200010
#define MAXN 100010
using namespace std;

const int INF =2147483647;
int n,m,s,dis[MAXN];
bool done[MAXN];
int tot,head[MAXN];
struct Edge{int v,w,next;}edge[MAXM];

inline void addedge(int x,int y,int z)
{
    edge[++tot].v=y;
    edge[tot].w=z;
    edge[tot].next=head[x];
    head[x]=tot;
}

struct node{
    int u,dist;
    bool operator<(const node& v)const{
        return dist>v.dist;
    }
};

priority_queue<node> qwq;
inline void dijkstra()
{
    for(int i=1;i<=n;i++)dis[i]=INF;
    dis[s]=0;
    qwq.push((node){s,0});
    
    while(!qwq.empty())
    {
        node front=qwq.top(); qwq.pop();
        int u=front.u,dist=front.dist;
        if(done[u])continue;
        done[u]=true;
        for(int i=head[u];i;i=edge[i].next)
        {
            int y=edge[i].v,z=edge[i].w;
            if(dis[u]+z<dis[y])
            {
                dis[y]=dis[u]+z;
                qwq.push((node){y,dis[y]});
            }
        }
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&s);
    int x,y,z;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        addedge(x,y,z);
    }
    
    dijkstra();
    
    for(int i=1;i<=n;i++)printf("%d ",dis[i]);
    return 0;
}

树状数组

已知一个数列，你需要进行下面两种操作：

1.将某一个数加上x

2.求出某区间每一个数的和

#include<cstdio>
#define lowbit(x) (x&(-x))
using namespace std;

const int MAXN = 500010;
int c[MAXN],n,m;

inline int sum(int i)
{
    int s=0;
    while(i>0){
        s+=c[i];
        i-=lowbit(i);
    }
    return s;
}

inline void update(int i,int value)
{
    while(i<=n){
        c[i]+=value;
        i+=lowbit(i);
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int temp;scanf("%d",&temp);
        update(i,temp);
    }
    
    for(int i=1;i<=m;i++)
    {
        int flag,x,y;
        scanf("%d%d%d",&flag,&x,&y);
        if(flag==1) update(x,y);
        else printf("%d\n",sum(y)-sum(x-1));
    }
    
    return 0;
}

已知一个数列，你需要进行下面两种操作：

1.将某区间每一个数数加上x

2.求出某一个数的值

#include<cstdio>
#define lowbit(x) (x&(-x))
using namespace std;

const int MAXN = 500010;
int c[MAXN],n,m,pre,now;

inline int sum(int i)
{
    int s=0;
    while(i>0){
        s+=c[i];
        i-=lowbit(i);
    }
    return s;
}

inline void update(int i,int value)
{
    while(i<=n){
        c[i]+=value;
        i+=lowbit(i);
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&now);
        update(i,now-pre);
        pre=now;
    }
    
    for(int i=1;i<=m;i++)
    {
        int flag,x;
        scanf("%d%d",&flag,&x);
        if(flag==1)
        {
            int y,k;scanf("%d%d",&y,&k);
            update(x,k);update(y+1,-k);
        }
        else printf("%d\n",sum(x));
    }
    
    return 0;
}

最近公共祖先

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;

const int MAXN = 500010;
const int MAXM = MAXN-1;
int max0,n,m,tot,head[MAXN];
int fa[MAXN][25],dep[MAXN],s;
struct Edge{int v,next;}edge[MAXM<<1];

inline void addedge(int x,int y)
{
    edge[++tot].v=y;
    edge[tot].next=head[x];
    head[x]=tot;
}

void lcainit(int x)
{
    for(int i=1;i<=max0;i++)
    if(fa[x][i-1])fa[x][i]=fa[fa[x][i-1]][i-1];
    else break;
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].v;
        if(y!=fa[x][0]){
            fa[y][0]=x;
            dep[y]=dep[x]+1;
            lcainit(y);
        }
    }
}

inline int lca(int u,int v)
{
    if(dep[u]<dep[v])swap(u,v);
    int delta=dep[u]-dep[v];
    for(int x=0;x<=max0;x++)
    if((1<<x)&delta)u=fa[u][x];
    if(u==v)return u;
    for(int x=max0;x>=0;x--)
    if(fa[u][x]!=fa[v][x]){
        u=fa[u][x];
        v=fa[v][x];
    }
    return fa[u][0];
}

int main()
{
    scanf("%d%d%d",&n,&m,&s);
    max0=(int)(log(n)/log(2))+3;
    
    for(int i=1;i<n;i++){
        int x,y;scanf("%d%d",&x,&y);
        addedge(x,y);addedge(y,x);
    }
    
    lcainit(s);
    
    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d\n",lca(a,b));
    }
    
    return 0;
}

割边

提交入口：https://www.luogu.com.cn/problem/T103481

#include <cstdio>
#define MIN(a,b) ((a)<(b)?(a):(b))

const int MAXN = 5e4+10;
const int MAXM = 3e5+10;
int head[MAXN],tot,n,m,num,dfn[MAXN],low[MAXN],ans;
struct Edge{int v,next;}edge[MAXM<<1];

inline void addedge(int x,int y){
    edge[++tot].v=y;
    edge[tot].next=head[x];
    head[x]=tot;
}

void tarjan(int x, int in_edge){
    dfn[x]=low[x]=++num;
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].v;
        if(!dfn[y]){
            tarjan(y,i); //把事情当作已经完成是理解递归的关键
            low[x]=MIN(low[x], low[y]);
            if(dfn[x]<low[y]) ans++; //割边判定
        }
        else if(i!=(in_edge^1))
            low[x]=MIN(low[x], dfn[y]);
        //不能通过来时的对应边访问父亲，但可以通过其他重边访问父亲
    }
}

int main(){
    scanf("%d%d",&n,&m);
    tot = 1;
    for(int i=1; i<=m; i++){
        int x,y; scanf("%d%d",&x,&y);
        addedge(x,y); addedge(y,x);
    }

    for(int i=1; i<=n; i++)
        if(!dfn[i]) tarjan(i,0);
    
    printf("%d",ans);
    return 0;
}

若需要输出割边：

#include <cstdio>
#define MIN(a,b) ((a)<(b)?(a):(b))

const int MAXN = 5e4+10;
const int MAXM = 3e5+10;
int head[MAXN],tot,n,m,num,dfn[MAXN],low[MAXN];
struct Edge{int v,next;}edge[MAXM<<1];
bool isbridge[MAXM<<1];

inline void addedge(int x,int y){
    edge[++tot].v=y;
    edge[tot].next=head[x];
    head[x]=tot;
}

void tarjan(int x, int in_edge){
    dfn[x]=low[x]=++num;
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].v;
        if(!dfn[y]){
            tarjan(y,i); //把事情当作已经完成是理解递归的关键
            low[x]=MIN(low[x], low[y]);
            if(dfn[x]<low[y]){
                isbridge[i]=isbridge[i^1]=true;
            }
        }
        else if(i!=(in_edge^1))
            low[x]=MIN(low[x], dfn[y]);
        //不能通过来时的对应边访问父亲，但可以通过其他重边访问父亲
    }
}

int main(){
    scanf("%d%d",&n,&m);
    tot = 1;
    for(int i=1; i<=m; i++){
        int x,y; scanf("%d%d",&x,&y);
        addedge(x,y); addedge(y,x);
    }

    for(int i=1; i<=n; i++)
        if(!dfn[i]) tarjan(i,0);
    
    for(int i=2; i<tot; i+=2) //无向图
        if(isbridge[i]) //i^1在前是因为edge[].v是到达的点
            printf("%d %d\n",edge[i^1].v,edge[i].v);
    
    return 0;
}

割点

提交入口： https://www.luogu.com.cn/problem/P3388

#include <cstdio>
#define MIN(a,b) ((a)<(b)?(a):(b))
using namespace std;

const int MAXN = 2e4+3;
const int MAXM = 1e5+3;
int n,m,head[MAXN],tot,ans;
int num,dfn[MAXN],low[MAXN],sroot;
struct Edge{int v,next;}edge[MAXM<<1];
bool iscut[MAXN];

inline void addedge(int x, int y){
    edge[++tot].v=y;
    edge[tot].next=head[x];
    head[x]=tot;
}

void tarjan(int x){
    dfn[x]=low[x]=++num;
    int mflag = 0;
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].v;
        if(!dfn[y]){
            tarjan(y);
            low[x]=MIN(low[x],low[y]);
            if(low[y]>=dfn[x]){
                mflag++; 
                if(x!=sroot || mflag>1)iscut[x]=true;
            }
        }
        else low[x]=MIN(low[x],dfn[y]);
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y; scanf("%d%d",&x,&y);
        if(x==y)continue;
        addedge(x,y); addedge(y,x);
    }

    for(int i=1;i<=n;i++)
        if(!dfn[i])sroot=i,tarjan(i);

    for(int i=1;i<=n;i++)
        if(iscut[i])ans++;
    printf("%d\n",ans);
    for(int i=1;i<=n;i++)
        if(iscut[i])printf("%d ",i);
    
    return 0;
}

强连通分量缩点

题目描述：https://www.luogu.org/problemnew/show/P3387

#include<cstdio>
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
using namespace std;

const int maxn=1e4+3;
const int maxm=1e5+3;
struct Edge{int v,next;};
Edge edge[maxm],edge2[maxm];
int head[maxn],w[maxn],dfn[maxn],low[maxn],stac[maxn],color[maxn];
int n,m,tot,num,top,cnt,ans;
int head2[maxn],W[maxn],tot2,sum[maxn];
bool ins[maxn];

inline void addedge(int x,int y){
    edge[++tot].v=y;
    edge[tot].next=head[x];
    head[x]=tot;
}

inline void addedge2(int x,int y){
    edge2[++tot2].v=y;
    edge2[tot2].next=head2[x];
    head2[x]=tot2;
}

inline void input(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        addedge(x,y);
    }
}

int dfs(int x){
    if(sum[x])return sum[x];
    int temp=0;
    for(int i=head2[x];i;i=edge2[i].next){
        temp=MAX(temp,dfs(edge2[i].v));
    }
    sum[x]=W[x]+temp;
    return sum[x];
}

void tarjan(int x){
    low[x]=dfn[x]=++num;
    stac[++top]=x; ins[x]=true;
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].v;
        if(!dfn[y]){
            tarjan(y);
            low[x]=MIN(low[x],low[y]);
        }
        else if(ins[y]){
            low[x]=MIN(low[x],dfn[y]);
        }
    }
    if(dfn[x]==low[x]){
        ++cnt; int y;
        do{
            y=stac[top--]; ins[y]=false;
            color[y]=cnt;
            W[cnt]+=w[y];
        }while(x!=y);
    }
}

int main(){
    input();
    for(int i=1;i<=n;i++){
        if(!dfn[i])tarjan(i);
    }

    for(int x=1;x<=n;x++){
        for(int i=head[x];i;i=edge[i].next){
            int y=edge[i].v;
            if(color[x]!=color[y]){
                addedge2(color[x],color[y]);
            }
        }
    }
    for(int i=1;i<=cnt;i++){
        if(!sum[i]){
            ans=MAX(ans,dfs(i));
        }
    }

    printf("%d",ans);
    return 0;
}

非压位高精

虽然重载的运算符两边数据类型都是Bigint，但因为自动强制转换，所以用[Bigint] * [int]也不会错。

在大数除int、大数对int取余时，效率不及专门功能的函数

参考：CSDN用户 代号4101

#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#define MAX(a,b) ((a)>(b)?(a):(b))
using namespace std;

const int MAXLEN = 1000;  //最长的数字长度

struct Bigint{
    int d[MAXLEN],len;
    void clean(){while(len>1&&!d[len-1])len--;} //去前导0

    Bigint(){memset(d,0,sizeof(d));len=1;}
    Bigint(int num){*this=num;}
    Bigint(char* num){*this=num;}

    Bigint operator = (const char* num){
        len=strlen(num);
        for(int i=0;i<len;i++)d[i]=num[len-1-i]-'0';
        clean();
        return *this;
    }

    Bigint operator = (int num){
        char s[MAXLEN];
        sprintf(s,"%d",num);
        *this=s;
        return *this;
    }

    Bigint operator + (const Bigint& b){ //只能大数加小数
        Bigint c=*this; int i;
        for(i=0;i<b.len;i++){
            c.d[i]+=b.d[i];
            if(c.d[i]>9)c.d[i]%=10,c.d[i+1]++;
        }
        while(c.d[i]>9)c.d[i++]%=10,c.d[i]++;
        c.len=MAX(len,b.len);
        if(c.d[i]&&c.len<=i)c.len=i+1;
        return c;
    }

    Bigint operator - (const Bigint& b){ //不能用小数减大数
        Bigint c=*this; int i;
        for(i=0;i<b.len;i++){
            c.d[i]-=b.d[i];
            if(c.d[i]<0)c.d[i]+=10,c.d[i+1]--;
        }
        while(c.d[i]<0)c.d[i++]+=10,c.d[i]--;
        c.clean();
        return c;
    }
    
    Bigint operator * (const Bigint& b)const{
        int i,j; Bigint c;
        c.len=len+b.len;
        for(j=0;j<b.len;j++)
            for(i=0;i<len;i++)
                c.d[i+j]+=d[i]*b.d[j];
        for(i=0;i<c.len-1;i++)
            c.d[i+1]+=c.d[i]/10,c.d[i]%=10;
        c.clean();
        return c;
    }

    Bigint operator / (const Bigint& b){
        int i,j;
        Bigint c=*this,a=0;
        for(i=len-1;i>=0;i--){
            a=a*10+d[i];
            for(j=0;j<10;j++)if(a<b*(j+1))break;
            c.d[i]=j;
            a=a-b*j;
        }
        c.clean();
        return c;
    }

    Bigint operator % (const Bigint& b){
        int i,j; Bigint a=0;
        for(i=len-1;i>=0;i--){
            a=a*10+d[i];
            for(j=0;j<10;j++)if(a<b*(j+1))break;
            a=a-b*j;
        }
        return a;
    }

    Bigint operator += (const Bigint& b){
        *this=*this+b;
        return *this;
    }

    bool operator < (const Bigint& b)const{
        if(len!=b.len)return len<b.len;
        for(int i=len-1;i>=0;i--)
            if(d[i]!=b.d[i])return d[i]<b.d[i];
        return false;
    }

    bool operator > (const Bigint& b)const{return b<*this;}
    bool operator <= (const Bigint& b)const{return !(b<*this);}
    bool operator >= (const Bigint& b)const{return !(*this<b);}
    bool operator != (const Bigint& b)const{return b<*this||*this<b;}
    bool operator == (const Bigint& b)const{return !(b<*this)&&!(b>*this);}

    string str()const{
        char s[MAXLEN]={};
        for(int i=0;i<len;i++)s[len-1-i]=d[i]+'0';
        return s;
    }
};

istream& operator >> (istream& in,Bigint& x){
    string s; in>>s;
    x=s.c_str();
    return in;
}

ostream& operator << (ostream& out,const Bigint& x){
    out<<x.str();
    return out;
}

int main(){     //just an example...
    Bigint s=0,t;
    while(cin>>t){
        if(t.len==1&&!t.d[0])break;
        s=s+t;
    }
    cout<<s<<endl;
    return 0;
}

压位高精

题面：https://www.luogu.com.cn/problem/P2152

自己缝的稍慢版本：

#include <cstdio>
#include <ctype.h>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef unsigned int uint;
#define rint register int
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))

inline int rd() {
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
    return x*f;
}

const int N=10010;
const int base=10000;
const int limit=4;
int power_10[]={1,10,100,1000,1000,10000};

struct Bigint {
    int a[N],len;
    Bigint(){memset(a,0,sizeof(a)),len=0;}
    void clean(){while(len>1&&!a[len-1])len--;} //去前导0
    void init(LL x) {
        while(x)a[len++]=x%base,x/=base;
    }
    void read() {
        char s[N];
        scanf("%s",s);
        len=1;
        int n=strlen(s),t=0;
        for(rint i=n-1;~i;--i,++t) {
            a[len-1]+=(s[i]-'0')*power_10[t];
            if(t+1==limit)t=-1,++len;
        }
        if(!t)--len;
    }
    void print(char c=-1) {
        printf("%lld",a[len-1]);
        for(rint i=len-2;i>=0;--i)printf("%0*lld",limit,a[i]);
        if(~c)putchar(c);
    }

    Bigint(int num){*this=num;}
    Bigint(char* num){*this=num;}
    Bigint operator = (const char* num){
        len=strlen(num);
        for(int i=0;i<len;i++)a[i]=num[len-1-i]-'0';
        clean();
        return *this;
    }
    Bigint operator = (int num){
        char s[N];
        sprintf(s,"%d",num);
        *this=s;
        return *this;
    }

    bool operator < (const Bigint& b)const{
        if(len!=b.len)return len<b.len;
        for(rint i=len-1;~i;i--)
            if(a[i]!=b.a[i])return a[i]<b.a[i];
        return false;
    }
    bool operator > (const Bigint& b)const{return b<*this;}
    bool operator <= (const Bigint& b)const{return !(b<*this);}
    bool operator >= (const Bigint& b)const{return !(*this<b);}
    bool operator != (const Bigint& b)const{return b<*this||*this<b;}
    bool operator == (const Bigint& b)const{return !(b<*this)&&!(b>*this);}
};
Bigint operator + (const Bigint &a,const Bigint &b) {
    Bigint c;int mx=MAX(a.len,b.len);c.len=mx;
    for(rint i=0;i<mx;++i)c.a[i]=a.a[i]+b.a[i];
    for(rint i=0;i<mx;++i)if(c.a[i]>=base)++c.a[i+1],c.a[i]-=base;
    if(c.a[c.len])++c.len;
    return c;
}
Bigint operator - (const Bigint &a,const Bigint &b) {
    Bigint c;int mx=a.len;c.len=mx;
    for(rint i=0;i<mx;++i)c.a[i]=a.a[i]-b.a[i];
    for(rint i=0;i<mx;++i)if(c.a[i]<0)--c.a[i+1],c.a[i]+=base;
    while(c.len&&!c.a[c.len-1])--c.len;
    return c;
}
Bigint operator * (const Bigint &a,const Bigint &b) {
    Bigint c;int mx=a.len+b.len-1;c.len=mx;
    for(rint i=0,mxa=a.len;i<mxa;++i)
        for(rint j=0,mxb=b.len;j<mxb;++j) {
            c.a[i+j]+=a.a[i]*b.a[j];
            if(c.a[i+j]>=base)c.a[i+j+1]+=c.a[i+j]/base,c.a[i+j]%=base;
        }
    if(c.a[c.len])++c.len;
    return c; 
}
Bigint operator / (const Bigint &a,const int &b) {
    Bigint c;int mx=a.len;
    LL now=0;
    for(rint i=mx-1,s=0;~i;--i) {
        now=now*base+a.a[i];
        if(now/b)s=1;
        if(!s)continue;
        c.a[c.len++]=now/b;
        now%=b;
    }
    reverse(c.a,c.a+c.len);
    return c;
}

Bigint biggcd(Bigint x,Bigint y){
    int xcnt2=0, ycnt2=0;
    while(!(x.a[0]&1)){xcnt2++; x=x/2;}
    while(!(y.a[0]&1)){ycnt2++; y=y/2;}
    int z=MIN(xcnt2,ycnt2);
    while(x!=y){
        if(x<y){swap(x,y);}
        x=x-y;
        while(!(x.a[0]&1)){x=x/2;}
    }
    Bigint temp = 2;
    while(z--){x=x*temp;}
    return x;
}

int main(){
    Bigint a,b;
    a.read(); b.read();
    biggcd(a,b).print();
    return 0;
}

下面给出更好的版本，注意与原代码有改动：

• 增加了biggcd
• 在 class 中图省事将所有权限改成了 public ，这并不推荐

//来源: https://paste.ubuntu.com/p/7VKYzpC7dn/
//作者：小黑AWM+MashPlant
//注：可以直接把BigInt和一样用cin cout都行，就是高精乘为了速度才用了FFT降低了精度，有需要可以自行更改。
#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
using namespace std;
const double PI = acos(-1.0);
struct Complex{
    double x,y;
    Complex(double _x = 0.0,double _y = 0.0){
        x = _x;
        y = _y;
    }
    Complex operator-(const Complex &b)const{
        return Complex(x - b.x,y - b.y);
    }
    Complex operator+(const Complex &b)const{
        return Complex(x + b.x,y + b.y);
    }
    Complex operator*(const Complex &b)const{
        return Complex(x*b.x - y*b.y,x*b.y + y*b.x);
    }
};
void change(Complex y[],int len){
    int i,j,k;
    for(int i = 1,j = len/2;i<len-1;i++){
        if(i < j)    swap(y[i],y[j]);
        k = len/2;
        while(j >= k){
            j = j - k;
            k = k/2;
        }
        if(j < k)    j+=k;
    }
}
void fft(Complex y[],int len,int on){
    change(y,len);
    for(int h = 2;h <= len;h<<=1){
        Complex wn(cos(on*2*PI/h),sin(on*2*PI/h));
        for(int j = 0;j < len;j += h){
            Complex w(1,0);
            for(int k = j;k < j + h/2;k++){
                Complex u = y[k];
                Complex t = w*y[k + h/2];
                y[k] = u + t;
                y[k + h/2] = u - t;
                w = w*wn;
            }
        }
    }
    if(on == -1){
        for(int i = 0;i < len;i++){
            y[i].x /= len;
        }
    }
}
class BigInt
{
public:
#define Value(x, nega) ((nega) ? -(x) : (x))
#define At(vec, index) ((index) < vec.size() ? vec[(index)] : 0)
    static int absComp(const BigInt &lhs, const BigInt &rhs)
    {
        if (lhs.size() != rhs.size())
            return lhs.size() < rhs.size() ? -1 : 1;
        for (int i = lhs.size() - 1; i >= 0; --i)
            if (lhs[i] != rhs[i])
                return lhs[i] < rhs[i] ? -1 : 1;
        return 0;
    }
    using Long = long long;
    const static int Exp = 9;
    const static Long Mod = 1000000000;
    mutable std::vector<Long> val;
    mutable bool nega = false;
    void trim() const
    {
        while (val.size() && val.back() == 0)
            val.pop_back();
        if (val.empty())
            nega = false;
    }
    int size() const { return val.size(); }
    Long &operator[](int index) const { return val[index]; }
    Long &back() const { return val.back(); }
    BigInt(int size, bool nega) : val(size), nega(nega) {}
    BigInt(const std::vector<Long> &val, bool nega) : val(val), nega(nega) {}

    friend std::ostream &operator<<(std::ostream &os, const BigInt &n)
    {
        if (n.size())
        {
            if (n.nega)
                putchar('-');
            for (int i = n.size() - 1; i >= 0; --i)
            {
                if (i == n.size() - 1)
                    printf("%lld", n[i]);
                else
                    printf("%0*lld", n.Exp, n[i]);
            }
        }
        else
            putchar('0');
        return os;
    }
    friend BigInt operator+(const BigInt &lhs, const BigInt &rhs)
    {
        BigInt ret(lhs);
        return ret += rhs;
    }
    friend BigInt operator-(const BigInt &lhs, const BigInt &rhs)
    {
        BigInt ret(lhs);
        return ret -= rhs;
    }
    BigInt(Long x = 0)
    {
        if (x < 0)
            x = -x, nega = true;
        while (x >= Mod)
            val.push_back(x % Mod), x /= Mod;
        if (x)
            val.push_back(x);
    }
    BigInt(const char *s)
    {
        int bound = 0, pos;
        if (s[0] == '-')
            nega = true, bound = 1;
        Long cur = 0, pow = 1;
        for (pos = strlen(s) - 1; pos >= Exp + bound - 1; pos -= Exp, val.push_back(cur), cur = 0, pow = 1)
            for (int i = pos; i > pos - Exp; --i)
                cur += (s[i] - '0') * pow, pow *= 10;
        for (cur = 0, pow = 1; pos >= bound; --pos)
            cur += (s[pos] - '0') * pow, pow *= 10;
        if (cur)
            val.push_back(cur);
    }
    BigInt &operator=(const char *s){
        BigInt n(s);
        *this = n;
        return n;
    }
    BigInt &operator=(const Long x){
        BigInt n(x);
        *this = n;
        return n;
    }
    friend std::istream &operator>>(std::istream &is, BigInt &n){
        string s;
        is >> s;
        n=(char*)s.data();
        return is;
    }
    BigInt &operator+=(const BigInt &rhs)
    {
        const int cap = std::max(size(), rhs.size()) + 1;
        val.resize(cap);
        int carry = 0;
        for (int i = 0; i < cap - 1; ++i)
        {
            val[i] = Value(val[i], nega) + Value(At(rhs, i), rhs.nega) + carry, carry = 0;
            if (val[i] >= Mod)
                val[i] -= Mod, carry = 1;
            else if (val[i] < 0)
                val[i] += Mod, carry = -1;
        }
        if ((val.back() = carry) == -1) //assert(val.back() == 1 or 0 or -1)
        {
            nega = true, val.pop_back();
            bool tailZero = true;
            for (int i = 0; i < cap - 1; ++i)
            {
                if (tailZero && val[i])
                    val[i] = Mod - val[i], tailZero = false;
                else
                    val[i] = Mod - 1 - val[i];
            }
        }
        trim();
        return *this;
    }
    friend BigInt operator-(const BigInt &rhs)
    {
        BigInt ret(rhs);
        ret.nega ^= 1;
        return ret;
    }
    BigInt &operator-=(const BigInt &rhs)
    {
        rhs.nega ^= 1;
        *this += rhs;
        rhs.nega ^= 1;
        return *this;
    }
    friend BigInt operator*(const BigInt &lhs, const BigInt &rhs)
    {
        int len=1;
        BigInt ll=lhs,rr=rhs;
        ll.nega = lhs.nega ^ rhs.nega;
        while(len<2*lhs.size()||len<2*rhs.size())len<<=1;
        ll.val.resize(len),rr.val.resize(len);
        Complex x1[len],x2[len];
        for(int i=0;i<len;i++){
            Complex nx(ll[i],0.0),ny(rr[i],0.0);
            x1[i]=nx;
            x2[i]=ny;
        }
        fft(x1,len,1);
        fft(x2,len,1);
        for(int i = 0 ; i < len; i++)
            x1[i] = x1[i] * x2[i];
        fft( x1 , len , -1 );
        for(int i = 0 ; i < len; i++)
            ll[i] = int( x1[i].x + 0.5 );
        for(int i = 0 ; i < len; i++){
            ll[i+1]+=ll[i]/Mod;
            ll[i]%=Mod;
        }
        ll.trim();
        return ll;
    }
    friend BigInt operator*(const BigInt &lhs, const Long &x){
        BigInt ret=lhs;
        bool negat = ( x < 0 );
        Long xx = (negat) ? -x : x;
        ret.nega ^= negat;
        ret.val.push_back(0);
        ret.val.push_back(0);
        for(int i = 0; i < ret.size(); i++)
            ret[i]*=xx;
        for(int i = 0; i < ret.size(); i++){
            ret[i+1]+=ret[i]/Mod;
            ret[i] %= Mod;
        }
        ret.trim();
        return ret;
    }
    BigInt &operator*=(const BigInt &rhs) { return *this = *this * rhs; }
    BigInt &operator*=(const Long &x) { return *this = *this * x; }
    friend BigInt operator/(const BigInt &lhs, const BigInt &rhs)
    {
        static std::vector<BigInt> powTwo{BigInt(1)};
        static std::vector<BigInt> estimate;
        estimate.clear();
        if (absComp(lhs, rhs) < 0)
            return BigInt();
        BigInt cur = rhs;
        int cmp;
        while ((cmp = absComp(cur, lhs)) <= 0)
        {
            estimate.push_back(cur), cur += cur;
            if (estimate.size() >= powTwo.size())
                powTwo.push_back(powTwo.back() + powTwo.back());
        }
        if (cmp == 0)
            return BigInt(powTwo.back().val, lhs.nega ^ rhs.nega);
        BigInt ret = powTwo[estimate.size() - 1];
        cur = estimate[estimate.size() - 1];
        for (int i = estimate.size() - 1; i >= 0 && cmp != 0; --i)
            if ((cmp = absComp(cur + estimate[i], lhs)) <= 0)
                cur += estimate[i], ret += powTwo[i];
        ret.nega = lhs.nega ^ rhs.nega;
        return ret;
    }
    friend BigInt operator/(const BigInt &num,const Long &x){
        bool negat = ( x < 0 );
        Long xx = (negat) ? -x : x;
        BigInt ret;
        Long k = 0;
        ret.val.resize( num.size() );
        ret.nega = (num.nega ^ negat);
        for(int i = num.size() - 1 ;i >= 0; i--){
            ret[i] = ( k * Mod + num[i]) / xx;
            k = ( k * Mod + num[i]) % xx;
        }
        ret.trim();
        return ret;
    }
    bool operator==(const BigInt &rhs) const
    {
        return nega == rhs.nega && val == rhs.val;
    }
    bool operator!=(const BigInt &rhs) const { return nega != rhs.nega || val != rhs.val; }
    bool operator>=(const BigInt &rhs) const { return !(*this < rhs); }
    bool operator>(const BigInt &rhs) const { return !(*this <= rhs); }
    bool operator<=(const BigInt &rhs) const
    {
        if (nega && !rhs.nega)
            return true;
        if (!nega && rhs.nega)
            return false;
        int cmp = absComp(*this, rhs);
        return nega ? cmp >= 0 : cmp <= 0;
    }
    bool operator<(const BigInt &rhs) const
    {
        if (nega && !rhs.nega)
            return true;
        if (!nega && rhs.nega)
            return false;
        return (absComp(*this, rhs) < 0) ^ nega;
    }
    void swap(const BigInt &rhs) const
    {
        std::swap(val, rhs.val);
        std::swap(nega, rhs.nega);
    }
};

BigInt biggcd(BigInt x,BigInt y){
    int xcnt2=0, ycnt2=0;
    while(!(x.val[0]&1)){xcnt2++; x=x/2;}
    while(!(y.val[0]&1)){ycnt2++; y=y/2;}
    int z=MIN(xcnt2,ycnt2);
    while(x!=y){
        if(x<y){swap(x,y);}
        x=x-y;
        while(!(x.val[0]&1)){x=x/2;}
    }
    BigInt temp = 2;
    while(z--){x=x*temp;}
    return x;
}
/*
BigInt ba,bb;
int main(){
    cin>>ba>>bb;
    cout << ba + bb << '\n';//和
    cout << ba - bb << '\n';//差
    cout << ba * bb << '\n';//积
    BigInt d;
    cout << (d = ba / bb) << '\n';//商
    cout << ba - d * bb << '\n';//余
    return 0;
}*/

BigInt a,b;
int main(){
    cin>>a>>b;
    cout<<biggcd(a,b);
    return 0;
}

作为对比，给出原作者的代码：

//作者：小黑AWM+MashPlant
//注：可以直接把BigInt和一样用cin cout都行，就是高精乘为了速度才用了FFT降低了精度，有需要可以自行更改。
#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const double PI = acos(-1.0);
struct Complex{
    double x,y;
    Complex(double _x = 0.0,double _y = 0.0){
        x = _x;
        y = _y;
    }
    Complex operator-(const Complex &b)const{
        return Complex(x - b.x,y - b.y);
    }
    Complex operator+(const Complex &b)const{
        return Complex(x + b.x,y + b.y);
    }
    Complex operator*(const Complex &b)const{
        return Complex(x*b.x - y*b.y,x*b.y + y*b.x);
    }
};
void change(Complex y[],int len){
    int i,j,k;
    for(int i = 1,j = len/2;i<len-1;i++){
        if(i < j)    swap(y[i],y[j]);
        k = len/2;
        while(j >= k){
            j = j - k;
            k = k/2;
        }
        if(j < k)    j+=k;
    }
}
void fft(Complex y[],int len,int on){
    change(y,len);
    for(int h = 2;h <= len;h<<=1){
        Complex wn(cos(on*2*PI/h),sin(on*2*PI/h));
        for(int j = 0;j < len;j += h){
            Complex w(1,0);
            for(int k = j;k < j + h/2;k++){
                Complex u = y[k];
                Complex t = w*y[k + h/2];
                y[k] = u + t;
                y[k + h/2] = u - t;
                w = w*wn;
            }
        }
    }
    if(on == -1){
        for(int i = 0;i < len;i++){
            y[i].x /= len;
        }
    }
}
class BigInt
{
#define Value(x, nega) ((nega) ? -(x) : (x))
#define At(vec, index) ((index) < vec.size() ? vec[(index)] : 0)
    static int absComp(const BigInt &lhs, const BigInt &rhs)
    {
        if (lhs.size() != rhs.size())
            return lhs.size() < rhs.size() ? -1 : 1;
        for (int i = lhs.size() - 1; i >= 0; --i)
            if (lhs[i] != rhs[i])
                return lhs[i] < rhs[i] ? -1 : 1;
        return 0;
    }
    using Long = long long;
    const static int Exp = 9;
    const static Long Mod = 1000000000;
    mutable std::vector<Long> val;
    mutable bool nega = false;
    void trim() const
    {
        while (val.size() && val.back() == 0)
            val.pop_back();
        if (val.empty())
            nega = false;
    }
    int size() const { return val.size(); }
    Long &operator[](int index) const { return val[index]; }
    Long &back() const { return val.back(); }
    BigInt(int size, bool nega) : val(size), nega(nega) {}
    BigInt(const std::vector<Long> &val, bool nega) : val(val), nega(nega) {}

public:
    friend std::ostream &operator<<(std::ostream &os, const BigInt &n)
    {
        if (n.size())
        {
            if (n.nega)
                putchar('-');
            for (int i = n.size() - 1; i >= 0; --i)
            {
                if (i == n.size() - 1)
                    printf("%lld", n[i]);
                else
                    printf("%0*lld", n.Exp, n[i]);
            }
        }
        else
            putchar('0');
        return os;
    }
    friend BigInt operator+(const BigInt &lhs, const BigInt &rhs)
    {
        BigInt ret(lhs);
        return ret += rhs;
    }
    friend BigInt operator-(const BigInt &lhs, const BigInt &rhs)
    {
        BigInt ret(lhs);
        return ret -= rhs;
    }
    BigInt(Long x = 0)
    {
        if (x < 0)
            x = -x, nega = true;
        while (x >= Mod)
            val.push_back(x % Mod), x /= Mod;
        if (x)
            val.push_back(x);
    }
    BigInt(const char *s)
    {
        int bound = 0, pos;
        if (s[0] == '-')
            nega = true, bound = 1;
        Long cur = 0, pow = 1;
        for (pos = strlen(s) - 1; pos >= Exp + bound - 1; pos -= Exp, val.push_back(cur), cur = 0, pow = 1)
            for (int i = pos; i > pos - Exp; --i)
                cur += (s[i] - '0') * pow, pow *= 10;
        for (cur = 0, pow = 1; pos >= bound; --pos)
            cur += (s[pos] - '0') * pow, pow *= 10;
        if (cur)
            val.push_back(cur);
    }
    BigInt &operator=(const char *s){
        BigInt n(s);
        *this = n;
        return n;
    }
    BigInt &operator=(const Long x){
        BigInt n(x);
        *this = n;
        return n;
    }
    friend std::istream &operator>>(std::istream &is, BigInt &n){
        string s;
        is >> s;
        n=(char*)s.data();
        return is;
    }
    BigInt &operator+=(const BigInt &rhs)
    {
        const int cap = std::max(size(), rhs.size()) + 1;
        val.resize(cap);
        int carry = 0;
        for (int i = 0; i < cap - 1; ++i)
        {
            val[i] = Value(val[i], nega) + Value(At(rhs, i), rhs.nega) + carry, carry = 0;
            if (val[i] >= Mod)
                val[i] -= Mod, carry = 1;
            else if (val[i] < 0)
                val[i] += Mod, carry = -1;
        }
        if ((val.back() = carry) == -1) //assert(val.back() == 1 or 0 or -1)
        {
            nega = true, val.pop_back();
            bool tailZero = true;
            for (int i = 0; i < cap - 1; ++i)
            {
                if (tailZero && val[i])
                    val[i] = Mod - val[i], tailZero = false;
                else
                    val[i] = Mod - 1 - val[i];
            }
        }
        trim();
        return *this;
    }
    friend BigInt operator-(const BigInt &rhs)
    {
        BigInt ret(rhs);
        ret.nega ^= 1;
        return ret;
    }
    BigInt &operator-=(const BigInt &rhs)
    {
        rhs.nega ^= 1;
        *this += rhs;
        rhs.nega ^= 1;
        return *this;
    }
    friend BigInt operator*(const BigInt &lhs, const BigInt &rhs)
    {
        int len=1;
        BigInt ll=lhs,rr=rhs;
        ll.nega = lhs.nega ^ rhs.nega;
        while(len<2*lhs.size()||len<2*rhs.size())len<<=1;
        ll.val.resize(len),rr.val.resize(len);
        Complex x1[len],x2[len];
        for(int i=0;i<len;i++){
            Complex nx(ll[i],0.0),ny(rr[i],0.0);
            x1[i]=nx;
            x2[i]=ny;
        }
        fft(x1,len,1);
        fft(x2,len,1);
        for(int i = 0 ; i < len; i++)
            x1[i] = x1[i] * x2[i];
        fft( x1 , len , -1 );
        for(int i = 0 ; i < len; i++)
            ll[i] = int( x1[i].x + 0.5 );
        for(int i = 0 ; i < len; i++){
            ll[i+1]+=ll[i]/Mod;
            ll[i]%=Mod;
        }
        ll.trim();
        return ll;
    }
    friend BigInt operator*(const BigInt &lhs, const Long &x){
        BigInt ret=lhs;
        bool negat = ( x < 0 );
        Long xx = (negat) ? -x : x;
        ret.nega ^= negat;
        ret.val.push_back(0);
        ret.val.push_back(0);
        for(int i = 0; i < ret.size(); i++)
            ret[i]*=xx;
        for(int i = 0; i < ret.size(); i++){
            ret[i+1]+=ret[i]/Mod;
            ret[i] %= Mod;
        }
        ret.trim();
        return ret;
    }
    BigInt &operator*=(const BigInt &rhs) { return *this = *this * rhs; }
    BigInt &operator*=(const Long &x) { return *this = *this * x; }
    friend BigInt operator/(const BigInt &lhs, const BigInt &rhs)
    {
        static std::vector<BigInt> powTwo{BigInt(1)};
        static std::vector<BigInt> estimate;
        estimate.clear();
        if (absComp(lhs, rhs) < 0)
            return BigInt();
        BigInt cur = rhs;
        int cmp;
        while ((cmp = absComp(cur, lhs)) <= 0)
        {
            estimate.push_back(cur), cur += cur;
            if (estimate.size() >= powTwo.size())
                powTwo.push_back(powTwo.back() + powTwo.back());
        }
        if (cmp == 0)
            return BigInt(powTwo.back().val, lhs.nega ^ rhs.nega);
        BigInt ret = powTwo[estimate.size() - 1];
        cur = estimate[estimate.size() - 1];
        for (int i = estimate.size() - 1; i >= 0 && cmp != 0; --i)
            if ((cmp = absComp(cur + estimate[i], lhs)) <= 0)
                cur += estimate[i], ret += powTwo[i];
        ret.nega = lhs.nega ^ rhs.nega;
        return ret;
    }
    friend BigInt operator/(const BigInt &num,const Long &x){
        bool negat = ( x < 0 );
        Long xx = (negat) ? -x : x;
        BigInt ret;
        Long k = 0;
        ret.val.resize( num.size() );
        ret.nega = (num.nega ^ negat);
        for(int i = num.size() - 1 ;i >= 0; i--){
            ret[i] = ( k * Mod + num[i]) / xx;
            k = ( k * Mod + num[i]) % xx;
        }
        ret.trim();
        return ret;
    }
    bool operator==(const BigInt &rhs) const
    {
        return nega == rhs.nega && val == rhs.val;
    }
    bool operator!=(const BigInt &rhs) const { return nega != rhs.nega || val != rhs.val; }
    bool operator>=(const BigInt &rhs) const { return !(*this < rhs); }
    bool operator>(const BigInt &rhs) const { return !(*this <= rhs); }
    bool operator<=(const BigInt &rhs) const
    {
        if (nega && !rhs.nega)
            return true;
        if (!nega && rhs.nega)
            return false;
        int cmp = absComp(*this, rhs);
        return nega ? cmp >= 0 : cmp <= 0;
    }
    bool operator<(const BigInt &rhs) const
    {
        if (nega && !rhs.nega)
            return true;
        if (!nega && rhs.nega)
            return false;
        return (absComp(*this, rhs) < 0) ^ nega;
    }
    void swap(const BigInt &rhs) const
    {
        std::swap(val, rhs.val);
        std::swap(nega, rhs.nega);
    }
};
BigInt ba,bb;
int main(){
    cin>>ba>>bb;
    cout << ba + bb << '\n';//和
    cout << ba - bb << '\n';//差
    cout << ba * bb << '\n';//积
    BigInt d;
    cout << (d = ba / bb) << '\n';//商
    cout << ba - d * bb << '\n';//余
    return 0;
}

二分图最大匹配

题目链接：https://www.luogu.com.cn/problem/P3386

#include<cstdio>
#include<cstring>
using namespace std;

const int maxvertex=503<<1;
const int maxedge=5e4+3;
int tot,n,m,e,ans;
int head[maxvertex],match[maxvertex>>1];
struct Edge{int v,next;}edge[maxedge];
bool vis[maxvertex>>1];

void addedge(int x,int y){
    edge[++tot].v=y;
    edge[tot].next=head[x];
    head[x]=tot;
}

bool dfs(int x){
    for(int i=head[x],y;i;i=edge[i].next){
        if(!vis[y=edge[i].v]){
            vis[y]=true;
            if((!match[y]) || dfs(match[y])){
                match[y]=x;
                return true;
            }
        }
    }
    return false;
}

int main(){
    scanf("%d%d%d",&n,&m,&e);
    for(int i=1;i<=e;i++){
        int x,y; scanf("%d%d",&x,&y);
        addedge(x,y);
    }

    for(int i=1;i<=n;i++){
        memset(vis,false,sizeof(vis));
        if(dfs(i)){ans++;}
    }
    printf("%d",ans);
    return 0;
}

字典树 (Trie)

本文章的 Trie 内容参考自 oi-wiki.org/string/trie

结构体封装的模板：

struct trie {
  int nex[100000][26], cnt;
  bool exist[100000];  // 该结点结尾的字符串是否存在

  void insert(char *s, int l) {  // 插入字符串
    int p = 0;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) nex[p][c] = ++cnt;  // 如果没有，就添加结点
      p = nex[p][c];
    }
    exist[p] = 1;
  }

  bool find(char *s, int l) {  // 查找字符串
    int p = 0;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) return 0;
      p = nex[p][c];
    }
    return exist[p];
  }
};

题目： https://www.luogu.com.cn/problem/P2580

#include <cstdio>

const int MAXN = 5e5+3;
char s[55];
int n,m,nex[MAXN][26],tag[MAXN],cnt=1;

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        int p = 1;
        for(int j=1;s[j];j++){
            int c = s[j]-'a';
            if(!nex[p][c])nex[p][c]=++cnt;
            p=nex[p][c];
        }
        tag[p] = 1;
    }
    scanf("%d",&m);
    while(m--){
        scanf("%s",s+1);
        int p = 1;
        for(int j=1;s[j];j++){
            int c = s[j]-'a';
            p=nex[p][c];
            if(!p)break;
        }
        if(tag[p]==1){
            tag[p]=2;
            puts("OK");
        }
        else if(tag[p]==2) puts("REPEAT");
        else puts("WRONG");
    }
    return 0;
}

01-Trie

题面： https://www.luogu.com.cn/problem/P4551

注意：以下按数位权值从高到低建立trie。

#include <cstdio>
#define MAX(a,b) ((a)>(b)?(a):(b))
using namespace std;

const int maxn = 1e5+3;
const int maxm = maxn-1;
struct Edge{int v,w,next;}edge[maxm<<1];
int head[maxn],tot,dis[maxn];
int n,m,ans,cnt=1,nex[maxn<<5][2];

inline void addedge(int x,int y,int z){
    edge[++tot].v=y;
    edge[tot].w=z;
    edge[tot].next=head[x];
    head[x]=tot;
}

void insert(int x){
    for(int i=30,p=1;~i;i--){
        int c = ((x>>i)&1); //二进制从（权值）高位向低位取
        if(!nex[p][c])nex[p][c]=++cnt;
        p=nex[p][c];
    }
}

void get(int x){
    int res = 0;
    for(int i=30,p=1;~i;i--){
        int c = ((x>>i)&1);
        if(nex[p][c^1]){  //贪心
            p=nex[p][c^1];
            res |= (1<<i);  //第i位（从低权位向高权位数）置1
        }
        else p=nex[p][c];
    }
    ans=MAX(ans,res);
}

void dfs(int x, int fa){
    insert(dis[x]);
    get(dis[x]);
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].v;
        if(y==fa)continue;
        dis[y]=dis[x]^edge[i].w;
        dfs(y,x);
    }
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        addedge(x,y,z);
        addedge(y,x,z);
    }

    dfs(1,0);

    printf("%d",ans);
    return 0;
}

维护异或和

注意：以下按权值从低位到高位建立trie。

对于每一个节点，记录以下三个量：

• ch[o][0/1] 指节点 o 的两个儿子，ch[o][0]指下一位是 0，同理ch[o][1]指下一位是 1。
• w[o]指节点 o 到其父亲节点这条边上数值的数量（权值）。每插入一个数字x，x二进制拆分后在 trie 上路径的权值都会+1。
• xorv[o]指以 o 为根的子树维护的异或和。

void maintain(int o){
    w[o] = xorv[o] = 0;
    if(ch[o][0]){
        w[o] += w[ch[o][0]];
        xorv[o] ^= xorv[ch[o][0]] << 1; //挪位置，末位补0，对应o到ch[o][0]这条边
    }
    if(ch[o][1]){
        w[o] += w[ch[o][1]];
        xorv[o] ^= (xorv[ch[o][1]] << 1) | (w[ch[o][1]] & 1); 
    } //因为ch[o][1]是经过1从o下来的，所以这个“经过的1”的这一位的异或和就是w[ch[o][1]]的奇偶性
    w[o] = w[o] & 1; //这句话删掉也可以？因为上文就只利用了他的奇偶性。
}

插入和删除，只需要修改叶子节点的w[]即可，在回溯的过程中一路维护：

namespace trie {
const int MAXH = 21;
int ch[_ * (MAXH + 1)][2], w[_ * (MAXH + 1)], xorv[_ * (MAXH + 1)];
int tot = 0;  // 这里的 _ 是一个 int 型

int mknode() {
  ++tot;
  ch[tot][1] = ch[tot][0] = w[tot] = xorv[tot] = 0;
  return tot;
}

void maintain(int o) {
  w[o] = xorv[o] = 0;
  if (ch[o][0]) {
    w[o] += w[ch[o][0]];
    xorv[o] ^= xorv[ch[o][0]] << 1;
  }
  if (ch[o][1]) {
    w[o] += w[ch[o][1]];
    xorv[o] ^= (xorv[ch[o][1]] << 1) | (w[ch[o][1]] & 1);
  }
  w[o] = w[o] & 1;
}

void insert(int &o, int x, int dp) { //看懂过，没时间别再看
  if (!o) o = mknode();
  if (dp > MAXH) return (void)(w[o]++);
  insert(ch[o][x & 1], x >> 1, dp + 1);
  maintain(o);
}

void erase(int o, int x, int dp) {
  if (dp > 20) return (void)(w[o]--);
  erase(ch[o][x & 1], x >> 1, dp + 1);
  maintain(o);
}
}  // namespace trie

注意：这里的MAXH指 trie 的深度，也就是强制让每一个叶子节点到根的距离为MAXH。对于一些比较小的值，可能有时候不需要建立这么深（例如：如果插入数字4，分解成二进制后为100，从根开始插入001这三位即可），但是我们强制插入MAXH位。这样做的目的是为了便于全局+1时处理进位。例如：如果原数字是3（11），递增之后变成4（100），如果当初插入3时只插入了2位，那这里的进位就没了。