doovvv
0%

算法模板

Posted on Edited on Valine:

自用算法模板

树

线段树

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>

using namespace std;

const int N = 1e5+5;
int a[N];
struct Node{
    int l,r,sum,add;
}tree[N<<2];
void up(int i){
    tree[i].sum = tree[i<<1].sum+tree[i<<1|1].sum;
}
void down(int i){
    if(tree[i].add){
        tree[i<<1].sum += (tree[i<<1].r-tree[i<<1].l+1)*tree[i].add;
        tree[i<<1|1].sum += (tree[i<<1|1].r-tree[i<<1|1].l+1)*tree[i].add;
        tree[i<<1].add += tree[i].add;
        tree[i<<1|1].add += tree[i].add;
        tree[i].add = 0; //下放之后，父节点的add要修改为0
    }
}
void build(int l,int r,int i){
    if(l == r){
        tree[i] = {l,r,a[l],0};
    }
    else{
        int mid = (l+r) >> 1;
        build(l,mid,i << 1);
        build(mid+1,r,i<<1 | 1);
        tree[i].l = tree[i<<1].l;
        tree[i].r = tree[i<<1|1].r;
        tree[i].add = 0;
        up(i);
    }
}
void update(int i,int p,int x){ //单点修改
    if(tree[i].l == p && tree[i].r  == p){
        tree[i].sum += x;
        return;
    }
    int mid = (tree[i].l+tree[i].r) >> 1;
    if(p <= mid) update(i<<1,p,x);
    else update(i<<1|1,p,x);
    up(i);

}
void update(int i,int jobl,int jobr,int x){ //区间修改
    if(jobl <= tree[i].l && tree[i].r <= jobr){
        tree[i].sum += (tree[i].r-tree[i].l+1)*x;
        tree[i].add += x;
        return;
    }
    int mid = (tree[i].l+tree[i].r)>>1;
    down(i);
    if(jobl<=mid) update(i<<1,jobl,jobr,x);
    if(jobr>mid) update(i<<1|1,jobl,jobr,x);
    up(i);
}
int query(int i,int jobl,int jobr){ //区间查询
    if(jobl <= tree[i].l && tree[i].r <= jobr){
        return tree[i].sum;
    }
    down(i);
    int mid = (tree[i].l+tree[i].r) >> 1;
    int sum = 0;
    if(jobl <= mid) sum+=query(i<<1,jobl,jobr);
    if(jobr>mid) sum+=query(i<<1|1,jobl,jobr);
    return sum;
}

树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
inline int lowbit(int x){
    return x & (-x);
}
void add(int p,int x){
    while(p<N){
        b[p] += x;
        p += lowbit(p);
    }
}
//注意返回值可能要开ll
int count(int p){//前缀和
    int result = 0;
    while(p){
        result += b[p];
        p -= lowbit(p);
    }
    return result;
}

动态规划

0-1背包

1
2
3
4
5
//dp[i][j]为在只能放前 i 个物品的情况下，容量为 j 的背包所能达到的最大总价值。
//由于dp[i][j]只依赖dp[i-1]，于是省略第一维，节约空间。
//注意j的遍历顺序,每个物品只能拿一次
for (int i = 1; i <= n; i++)
  for (int j = W; j >= w[i]; j--) dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

完全背包

1
2
3
for (int i = 1; i <= n; i++)
  for (int j = 0; j <= W - w[i]; j++)
    dp[j + w[i]] = max(dp[j] + v[i], dp[j + w[i]]);

多重背包

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
38
39
40
41
42
43
44
/*多重背包也是 0-1 背包的一个变式。与 0-1 背包的区别在于每种物品有 k_i 个，而非一个。

一个很朴素的想法就是：把「每种物品选 k_i 次」等价转换为「有 k_i 个相同的物品，每个物品选一次」。*/
for (int i = 1; i <= n; i++) {
  for (int weight = W; weight >= w[i]; weight--) {
    // 多遍历一层物品数量
    for (int k = 1; k * w[i] <= weight && k <= cnt[i]; k++) {
      dp[weight] = max(dp[weight], dp[weight - k * w[i]] + k * v[i]);
    }
  }
}

//二进制分组优化
	int cnt=0;
	for(int i=1; i<=N; i++) {
		int wi,vi,s;
		cin>>wi>>vi>>s;
		
		int k=1;		
		while(k<=s) {
			cnt++;
			w[cnt]=wi*k;
			v[cnt]=vi*k;
			s-=k;
			k*=2;
		}
		
		if(s>0) {
			cnt++;
			w[cnt]=wi*s;
			v[cnt]=vi*s;
		}
	}
 
	N=cnt;
	for(int i=1; i<=N; i++) {
		for(int j=V; j>=w[i]; j--)
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
	}
//二进制优化，当dp的值只有0/1的时候
bitset<m> s;
s.set(0,1);
for(int i=1;i<=n;i++)
s|=(s<<a[i]);

数学

快速幂

1
2
3
4
5
6
7
8
9
10
11
int binpow(int a,int b){//注意开long long
    int ans = 1;
    while(b >0){
        if(b &1){
            ans = ans*a% mod;
        }
        a = a*a%mod;
        b /= 2;
    }
    return ans;
}

组合数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void pre(long long n,vector<long long>& big, vector<long long>& inv_big){
    big[0] = 1;
    inv_big[0] = 1;
    for(long long i=1;i<=n;i++){
        big[i] = big[i-1]*i;
        big[i] %= mod;
    }
    inv_big[n] = binpow(big[n],mod-2)%mod;
    for(long long i = n-1;i>=1;i--){
        inv_big[i] = inv_big[i+1]*(i+1)%mod;
    }
}//阶乘数组和逆阶乘数组（用到快速幂）
long long C(long long n,long long k,vector<long long>& big, vector<long long>& inv_big){
    if(n < k){
        return 0;
    }
    return (big[n]*inv_big[k]%mod*inv_big[n-k])%mod;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> pri;
bool not_prime[N];

void pre(int n) {
  for (int i = 2; i <= n; ++i) {
    if (!not_prime[i]) {
      pri.push_back(i);
    }
    for (int pri_j : pri) {
      if (i * pri_j > n) break;
      not_prime[i * pri_j] = true;
      if (i % pri_j == 0) {
        // i % pri_j == 0
        // 换言之，i 之前被 pri_j 筛过了
        // 由于 pri 里面质数是从小到大的，所以 i 乘上其他的质数的结果一定会被
        // pri_j 的倍数筛掉，就不需要在这里先筛一次，所以这里直接 break
        // 掉就好了
        break;
      }
    }
  }
}

数据结构

链表

1
2
3
4
5
struct Node {
  int value;
  Node *left;
  Node *right;
};

其他

快读快写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}
void write(int x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}