0%

Dirt030的ACM板子

发表于 更新于

一点一点地攒板子吧——

数论

线性筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//1至MAXN范围内的质数
#define MAXN 100007;//筛的范围 
int prime[MAXN];//顺序质数表，计算结束以后用实际数量代替MAXN避免MLE
int prime_tot=0;//质数实际数量
bool check[MAXN];//判断用质数表
void prime_get(){
	memset(check,0,sizeof(check));
	check[0]=check[1]=1;
	int i,j;
	for(i=2;i<=MAXN;i++){
		if (check[i]==0) prime[prime_tot++]=i;
		for(j=0;j<prime_tot&&i*prime[j]<=MAXN;j++){
			check[i*prime[j]]=1;
			if (i%prime[j]==0) break;
		}
	}
}

最大公约数（GCD）

1
2
3
4
5
//a和b的最大公约数
ll gcd(ll a,ll b){
	if (!b) return a;
	return gcd(b,a%b);
}

快速幂

1
2
3
4
5
6
7
8
9
10
//a的b次方对m取模
ll binaryPow(ll a,ll b,ll m){
	ll ans=1;
	while(b>0){
		if(b&1) ans=(ans*a)%m;
		a=(a*a)%m;
		b>>=1; 
	}
	return ans;
}

数据结构

树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//区间求和，单点修改
//建树用修改操作就行
//这玩意儿从f[1]开始的，因为lowbit(0)会有问题
//求最低的为1的位
int lowbit(int x){
    return x&(-x);
}
//询问a[1]+a[2]+……+a[x]的值
int query(int x){
    int sum=0;
    while(x!=0){
        sum+=sum+f[x];
        x-=lowbit(x);
    }
    return sum;
}
//修改a[x]增加d
void modify(int x,int d){
    while(x<=n){
        f[x]+=d;
        x+=lowbit(x);
    }
}

线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//区间最值，单点修改
//递归建树，x为当前结点位置，l、r为范围
void build(int x,int l,int r){
    if(l==r) f[x]=a[l];
    else{
        int mid=(l+r)/2;
        build(x*2,l,mid);
        build(x*2+1,mid+1,r);
        f[x]=max(f[x*2],f[x*2+1]);
    }
}
//修改a[pos]增加d
void modify(int x,int l,int r,int pos,int d){
    if(l==r) f[x]+=d;
    else{
        int mid=(l+r)/2;
        if(pos<=mid) modify(x*2,l,mid,pos,d);
        else modify(x*2+1,mid+1,r,pos,d);
        f[x]=max(f[x*2],f[x*2+1]);
    }
}
//询问a[ql]、a[ql+1]……a[qr]的最大值
int query(int x,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr) return f[x];
    else{
        int mid=(l+r)/2;
        int s=INT_MIN;
        if(ql<=mid) s=max(s,query(x*2,l,mid,ql,qr));
        if(mid+1<=qr) s=max(s,query(x*2+1,mid+1,r,ql,qr));        
        return s;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//区间最值，区间修改
//建树略
//下传标记
void downtag(int x){
    if(tag[x]==0) return;
    tag[x*2]+=tag[x];
    f[x*2]+=tag[x];
    tag[x*2+1]+=tag[x];
    f[x*2+1]+=tag[x];
    tag[x]=0;
}
//修改a[ll]、a[ll+1]……a[rr]增加d
void modify(int x,int l,int r,int ll,int rr,int d){
    if(ll<=l&&r<=rr){
        f[x]+=d;
        tag[x]+=d;
    }
    else{
        downtag(x);
        int mid=(l+r)/2;
        if(ll<=mid) modify(x*2,l,mid,ll,rr,d);
        if(rr>=mid+1) modify(x*2+1,mid+1,r,ll,rr,d);
        f[x]=max(f[x*2],f[x*2+1]);
    }
}
//询问a[ql]、a[ql+1]……a[qr]的最大值
int query(int x,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr) return f[x];
    else{
        downtag(x);
        int mid=(l+r)/2;
        int s=INT_MIN;
        if(ql<=mid) s=max(s,query(x*2,l,mid,ql,qr));
        if(mid+1<=qr) s=max(s,query(x*2+1,mid+1,r,ql,qr));        
        return s;
    }
}

区间最值查询（RMQ）

ST算法（倍增）（静态）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//f[i][j]为从第i位开始的2^j位中的最大值
//f[i][0]为给定数据
#define MAXN 1000006
#define LOG2MAXN 20
int f[MAXN][LOG2MAXN];//MAXN为数据范围，LOG2MAXN为MAXN对2取对数
//预处理
void preST(int len){
    int m=log(len)/log(2)+1;
    for(int j=1;j<m;j++)
        for(int i=0;i<=(len-(1<<j)+1);i++)
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
//查询f[l][0]、f[l+1][0]、……、f[r][0]的RMQ
int searchST(int l,int r){
    int k=log(r-l+1)/log(2);
    return max(f[l][k],f[r-(1<<k)+1][k]);
}

最长上升子序列（LIS）

单调性+二分（nlgn）

1
2
3
4
5
6
7
8
9
10
11
12
13
//有DP和Sort+LCS的做法，但我懒得写了
//最长单调不下降子序列
#define MAXN 1000006//数据范围
int a[MAXN],f[MAXN];
int calcLIS(int n){
	int pos,len=0;
	for(int i=0;i<n;i++){
		pos=lower_bound(f,f+len,a[i])-f;//其他类型的序列需要重写二分函数
		f[pos]=a[i];
		if(pos==len) len++;
	}
	return len;
}

*二维带权最长上升子序列

1
2
//ICPC Latin American Regional – 2017
//Problem F – Fundraising