基础

快读

1
2
ios::sync_with_stdio(false);
cin.tie(0);

数据结构

堆（重载运算符）

1
2
3
4
5
6
7
struct point{
int num,dis; 
bool operator < (const point &a)const{
    return dis>a.dis;
}
}p[maxn];
priority_queue <point> q;

树状数组O(nlog⁡n)O(n\log n)

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
#include<bits/stdc++.h> // 单点修改区间查询
using namespace std;
const int maxn = 1e6+5;
int c[maxn],a[maxn],n,m;
int lowbit(int x){
	return x&(-x);
}
int summ(int x){ // 求 0-x的和 
	int ret=0;
	while(x){
		ret += c[x];
		x -= lowbit(x);
	}
	return ret;
}
void addk(int x,int k){
	while(x<=n){
		c[x] += k;
		x += lowbit(x); 
	}
} 
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d", &a[i]);
		addk(i, a[i]);
	}
	for(int i=1;i<=m;i++){
		int t,x,y;
		scanf("%d%d%d",&t,&x,&y);
		if(t==1){
			addk(x,y);
		}
		else{
			printf("%d\n", summ(y)-summ(x-1));
		}
	}
	return 0;
}
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
#include<bits/stdc++.h> // 区间修改 单点查询
using namespace std;
int ai[500005*4],c[500005*4],sum[500005*4];int n,m;
int lowbit(int a){
	return a&(-a); 
}
int summ(int x){
	int ret=0;
	while(x){
		ret+=c[x];x-=lowbit(x);
	}
	return ret;
}
void add(int x,int d){
    while(x<=n){
		c[x]+=d;
		x+=lowbit(x);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&ai[i]);
    for(int i=1;i<=m;i++){
    	int a,b,c,d;
    	scanf("%d",&a);
    	if(a==1){
    		scanf("%d%d%d",&b,&c,&d);
	    	add(b,d);
	    	add(c+1,-d);
		}
    	if(a==2){
    		scanf("%d",&b);
		    printf("%d\n",summ(b)+ai[b]);
		}
	}
	return 0;
}
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
#include<bits/stdc++.h>
using namespace std;
const int maxn =300+5;
int n,m,x;
int sum[maxn][maxn][105];
int color[maxn][maxn];
int lowbit(int x){
	return x&(-x);
}
void addxy(int x, int y, int k, int color){
	for(int i=x;i<=n;i+=lowbit(i)){
		for(int j=y;j<=m;j+=lowbit(j)){
			sum[i][j][color] += k;
		}
	}
}
int sumxy(int x,int y,int color){
	int ans = 0;
	for(int i=x;i;i-=lowbit(i)){
		for(int j=y;j;j-=lowbit(j)){
			ans += sum[i][j][color];
		}
	}
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int c;
			scanf("%d",&c);
			addxy(i,j,1,c);
			color[i][j] = c;
		}
	}
	int q;
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		int t;
		scanf("%d", &t);
		if(t==1){
			int x,y,c;
			scanf("%d%d%d", &x,&y,&c);
			addxy(x,y,-1,color[x][y]);
			addxy(x,y,1,c);
			color[x][y]=c;
		}
		else{
			int x1,x2,y1,y2,c;
			scanf("%d%d%d%d%d", &x1,&x2,&y1,&y2,&c);
			int ans = sumxy(x2,y2,c) - sumxy(x2,y1-1,c) - sumxy(x1-1,y2,c) + sumxy(x1-1,y1-1,c);
			printf("%d\n",ans);
		}
	}
	return 0;
}

线段树

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n,m; long long mod=2e18+5;
long long a[maxn];
struct point{
	int l,r;
	long long add,sum;
}p[maxn*4];

void pushup(int o){
	p[o].sum = (p[o<<1].sum + p[o<<1|1].sum)%mod;
}
void pushdown(int o){
	p[o<<1].sum = (p[o<<1].sum + p[o].add*(p[o<<1].r-p[o<<1].l+1)%mod)%mod;
	p[o<<1].add = (p[o<<1].add+p[o].add)%mod;
	p[o<<1|1].sum = (p[o<<1|1].sum + p[o].add*(p[o<<1|1].r-p[o<<1|1].l+1)%mod)%mod;
	p[o<<1|1].add = (p[o<<1|1].add+p[o].add)%mod;
	p[o].add = 0;
}

void build(int o,int l,int r){
	p[o].l = l, p[o].r = r;
	p[o].add = 0;
	if(l==r){
		p[o].sum = a[l]%mod;
	}
	else{
		int mid= (l+r)/2;
		build(o<<1, l, mid);
		build(o<<1|1, mid+1, r);
		pushup(o);
	}
}


void addk(int o, int head, int rear, long long k){
	int l = p[o].l, r=p[o].r;
	if(head<=l && rear>=r){ // 查询到区间 
		p[o].add = (p[o].add + k)%mod;
		p[o].sum = (p[o].sum + k*(r-l+1))%mod;
		return;
	}
	// 向下查找 
	pushdown(o);
	int mid = (l+r)/2;
	if(head<=mid) addk(o<<1, head, rear, k);
	if(rear>mid) addk(o<<1|1, head, rear, k);
	// 回溯更新
	pushup(o);
}

long long query(int o,int head, int rear){
	long long res = 0;
	int l = p[o].l, r= p[o].r;
	if(head<=l&&r<=rear){
		return p[o].sum;
	}
	pushdown(o);
	// 向下查找 
	int mid = (l+r)/2;
	if(head<=mid) res += query(o<<1, head, rear);
	if(rear>mid) res += query(o<<1|1, head, rear);
	return res%mod;
}
int main(){
	scanf("%d%d", &n, &m);
	for(int i=1;i<=n;i++){
		scanf("%lld", &a[i]);
	}
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int t;
		scanf("%d", &t);
		if(t==1){
			long long x,y,k;
			scanf("%lld%lld%lld", &x, &y, &k);
			addk(1,x,y,k);
		}
		else{
			int x,y;
			scanf("%d%d", &x, &y);
			long long ans = query(1,x,y);
			printf("%lld\n", ans);
		} 
	}
}
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n,m,mod;
long long a[maxn];
struct point{
	int l,r;
	long long add,times,sum;
}p[maxn*4];
void build(int o,int l,int r){
	p[o].l = l, p[o].r = r;
	p[o].times = 1;
	p[o].add = 0;
	if(l==r){
		p[o].sum = a[l]%mod;
	}
	else{
		int mid= (l+r)/2;
		build(o<<1, l, mid);
		build(o<<1|1, mid+1, r);
		p[o].sum = (p[o<<1].sum + p[o<<1|1].sum)%mod;
	}
}
void update(int o){
	p[o].sum = (p[o<<1].sum + p[o<<1|1].sum)%mod;
}
void pushdown(int o){
	p[o<<1].sum = (p[o<<1].sum*p[o].times + p[o].add*(p[o<<1].r-p[o<<1].l+1)%mod)%mod;
	p[o<<1].times = (p[o<<1].times*p[o].times)%mod;
	p[o<<1].add = (p[o<<1].add*p[o].times+p[o].add)%mod;
	p[o<<1|1].sum = (p[o<<1|1].sum*p[o].times + p[o].add*(p[o<<1|1].r-p[o<<1|1].l+1)%mod)%mod;
	p[o<<1|1].times = (p[o<<1|1].times*p[o].times)%mod;
	p[o<<1|1].add = (p[o<<1|1].add*p[o].times+p[o].add)%mod;

	p[o].add = 0;
	p[o].times = 1;
}
void addk(int o, int head, int rear, long long k){
	int l = p[o].l, r=p[o].r;
	if(head<=l && rear>=r){ // 查询到区间 
		p[o].add = (p[o].add + k)%mod;
		p[o].sum = (p[o].sum + k*(r-l+1))%mod;
		return;
	}
	// 向下查找 
	pushdown(o);
	int mid = (l+r)/2;
	if(head<=mid) addk(o<<1, head, rear, k);
	if(rear>mid) addk(o<<1|1, head, rear, k);
	// 回溯更新
	update(o);
}
void timesk(int o, int head, int rear, long long k){
	int l = p[o].l, r=p[o].r;
	if(head<=l && rear>=r){ // 查询到区间 
		p[o].add = (p[o].add * k)%mod;
		p[o].times = (p[o].times*k)%mod;
		p[o].sum = (p[o].sum * k)%mod;
		return;
	}
	// 向下查找 
	pushdown(o);
	int mid = (l+r)/2;
	if(head<=mid) timesk(o<<1, head, rear, k);
	if(rear>mid) timesk(o<<1|1, head, rear, k);
	// 回溯更新
	update(o);
}

long long query(int o,int head, int rear){
	long long res = 0;
	int l = p[o].l, r= p[o].r;
	if(head<=l&&r<=rear){
		return p[o].sum;
	}
	pushdown(o);
	// 向下查找 
	int mid = (l+r)/2;
	if(head<=mid) res += query(o<<1, head, rear);
	if(rear>mid) res += query(o<<1|1, head, rear);
	return res%mod;
}
int main(){
	scanf("%d%d%d", &n, &m, &mod);
	for(int i=1;i<=n;i++){
		scanf("%lld", &a[i]);
	}
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int t;
		scanf("%d", &t);
		if(t==1){
			long long x,y,k;
			scanf("%lld%lld%lld", &x, &y, &k);
			timesk(1,x,y,k);
		}
		else if(t==2){
			long long x,y,k;
			scanf("%lld%lld%lld", &x, &y, &k);
			addk(1,x,y,k);
		} 
		else{
			int x,y;
			scanf("%d%d", &x, &y);
			long long ans = query(1,x,y);
			printf("%lld\n", ans);
		} 
	}
}
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
71
72
73
74
75
76
77
78
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n;
struct point{
	int l,r;
	long long sum,len;
}p[maxn*16];
struct line{
	int x1,x2,y,t;
}l[maxn*2];
int x[maxn*2];
void build(int o,int l,int r){
	p[o].l = l, p[o].r = r;
	if(l==r){
		return;
	}
	int mid= (l+r)/2;
	build(o<<1, l, mid);
	build(o<<1|1, mid+1, r);
}
void pushup(int o){
	int l = p[o].l, r= p[o].r;
	if(p[o].sum){
		p[o].len= x[r+1] - x[l];
	}
	else
		p[o].len = p[o<<1].len + p[o<<1|1].len;
}
void addk(int o, int head, int rear, long long k){
	int l = p[o].l, r=p[o].r;
	if(head<=x[l] && rear>=x[r+1]){ // 查询到区间 
		p[o].sum += k;
		pushup(o);
		return;
	}
	// 向下查找 
	int mid = (l+r)/2;
	if(head<=x[mid]) addk(o<<1, head, rear, k);
	if(rear>x[mid+1]) addk(o<<1|1, head, rear, k);
	// 回溯更新
	pushup(o);
}
int cmp(line x, line y){
	return x.y<y.y;
}
int main(){
	cin>>n;
	int head = 0, headl=0;
	for(int i=1;i<=n;i++){
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		x[++head]=x1;
		x[++head]=x2;
		l[++headl]={x1,x2,y1,1}; 
		l[++headl]={x1,x2,y2,-1}; 
	}
	sort(x+1,x+1+head);
	int tot = 1;
	for(int i=2;i<=head;i++){
		if(x[i]!=x[tot]){
			x[++tot] = x[i];
		}
	}
	build(1,1,tot-1);
	sort(l+1,l+1+headl,cmp);
	long long ans = 0;

	for(int i=1;i<headl;i++){
//		cout<<l[i].x1<<" "<<l[i].x2<<" "<<l[i].y<<" "<<l[i].t<<endl;
		addk(1,l[i].x1,l[i].x2,l[i].t);
//		cout<<p[1].len<<endl;
		ans+=p[1].len * ((long long)l[i+1].y - l[i].y);
//		cout<<ans<<endl;
	}
	printf("%lld",ans);

}
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int k,ves[maxn],fa[maxn][25],dep[maxn];
int n,m,cnt=0,sum[50*maxn],res[50*maxn],ls[50*maxn],rs[50*maxn];
int rt[maxn];
struct edge{
	int u,v,next;
}st[maxn*2];
void add(int u,int v){
	k++;
	st[k].u=u;
	st[k].v=v;
	st[k].next=ves[u];
	ves[u]=k;
}
void init(int u,int f){
	dep[u]=dep[f]+1;
	fa[u][0]=f;
	for(int i=1;i<=20;i++){
		fa[u][i]=fa[fa[u][i-1]][i-1];
	}
	for(int i=ves[u];i;i=st[i].next){
		int v=st[i].v;
		if(v==f)continue;
		init(v,u);
	}
}
int lca(int u,int v){
	if(dep[u]<dep[v])swap(u,v);
	for(int i=20;i>=0;i--){
		if(dep[fa[u][i]]<dep[v])continue;
		u=fa[u][i];
	}
	if(u==v)return u;
	for(int i=20;i>=0;i--){
		if(fa[u][i]==fa[v][i])continue;
		u=fa[u][i],v=fa[v][i];
	}
	return fa[u][0];
}
void update(int x){
	if(sum[ls[x]]<sum[rs[x]]){
		res[x]=res[rs[x]];
		sum[x]=sum[rs[x]];
	}
	else {
		res[x]=res[ls[x]];
		sum[x]=sum[ls[x]];
	}
}
int merge(int a,int b,int x,int y){
	if(!a)return b;
	if(!b)return a;
	if(x==y){
		sum[a]+=sum[b];
		return a;
	}
	int mid=(x+y)/2;
	ls[a]=merge(ls[a],ls[b],x,mid);
	rs[a]=merge(rs[a],rs[b],mid+1,y);
	update(a);
	return a;
}
int add(int id,int x,int y,int col,int val){
	if(!id)id=++cnt;
	if(x==y){
		sum[id]+=val;
		res[id]=col;
		return id;
	}
	int mid=(x+y)/2;
	if(col<=mid){
		ls[id]=add(ls[id],x,mid,col,val);
	}
	else rs[id]=add(rs[id],mid+1,y,col,val);
	update(id);
	return id;
}
int ans[maxn];
void dfs(int u,int f){
	for(int i=ves[u];i;i=st[i].next){
		int v=st[i].v;
		if(v==f)continue;
		dfs(v,u);
		rt[u]=merge(rt[u],rt[v],1,100000);
	}
	ans[u]=res[rt[u]];
	if(sum[rt[u]]==0)ans[u]=0;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}

	init(1,0);
	for(int i=1;i<=m;i++){
		int x,y,z,lc;
		scanf("%d%d%d",&x,&y,&z);
		int l=lca(x,y);
		rt[x]=add(rt[x],1,100000,z,1);
		rt[y]=add(rt[y],1,100000,z,1);
		rt[l]=add(rt[l],1,100000,z,-1);
		rt[fa[l][0]]=add(rt[fa[l][0]],1,100000,z,-1);
	}
	dfs(1,0);

	for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
	return 0;
}
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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6+5;
int cnt=0,n,m;
struct point{
	int l,r;
	int maxx;
}p[maxn*4];
int a[maxn];
void pushup(int o){
	p[o].maxx=max(p[o<<1].maxx,p[o<<1|1].maxx);
}
void build(int o,int l,int r){
	p[o].l=l; p[o].r=r;
	if(l==r){
		p[o].maxx=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(o<<1,l,mid);
	build(o<<1|1,mid+1,r);
	pushup(o);
}
int query(int o,int head, int rear, int k){
	int l=p[o].l, r=p[o].r;
	if(l==r){
		if(p[o].maxx<=k) return -1;
		return r;
	}
	if(head<=l&&r<=rear){
		if(p[o].maxx<=k) return -1;
	}
	int mid = (l+r)/2;
	int res = -1;
	if(head<=mid) res = query(o<<1,head,rear,k);
	if(res==-1 && rear>mid) res = query(o<<1|1,head,rear,k);
	return res;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int l,r,k;
		cin>>l>>r>>k;
		cout<<query(1,l,r,k)<<endl;
	}
	return 0;
}

单调队列/滑动窗口

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
#include<bits/stdc++.h>
using namespace std;
int x[3000005],y[1000005];
int main(){
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>x[i];
	}int head=1,rear=0;
	for(int i=1;i<=n;i++){
    	while(head<=rear&&i-y[head]>=k)head++;
    	while(head<=rear&&x[i]<=x[y[rear]])rear--;
    	y[++rear]=i;
    	if(i>=k)cout<<x[y[head]]<<" "; 
	}
	cout<<endl;
	head=1,rear=0;
    for(int i=1;i<=n;i++){
    	while(head<=rear&&i-y[head]>=k)head++;
    	while(head<=rear&&x[i]>=x[y[rear]])rear--;
    	y[++rear]=i;
    	if(i>=k)cout<<x[y[head]]<<" "; 
	}
    return 0; 
}

分块 O(nn)O(n\sqrt{n})

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=50005;
int n;
int a[maxn],head[maxn],rear[maxn],add[maxn],lie[maxn];
void init(){
    int size=sqrt(n);
    for(int i=1;i<=size;i++){
        head[i]=(i-1)*size+1;
        rear[i]=i*size;
    }
    if(rear[size]<=n){
        head[size+1]=rear[size]+1;
        rear[++size]=n;
    }
    for(int i=1;i<=size;i++){
        for(int j=head[i];j<=rear[i];j++){
            lie[j]=i;
        }
    }
}
void change(int l,int r,int k){
    if(lie[l]==lie[r]){
        for(int i=l;i<=r;i++){
            a[i]+=k;
        }
    }
    else{
        for(int i=lie[l]+1;i<=lie[r]-1;i++)add[i]+=k;
        for(int i=l;i<=rear[lie[l]];i++)a[i]+=k; 
        for(int i=head[lie[r]];i<=r;i++)a[i]+=k;
    }
}
int query(int l,int r){
    int ans=0;
    return a[r]+add[lie[r]];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    init();
    for(int i=1;i<=n;i++){
        int opt,l,r,c;
        scanf("%d%d%d%d",&opt,&l,&r,&c);
        if(!opt)change(l,r,c);
        else printf("%d\n",query(l,r));
    }
    return 0;
}

可持久化

可持久化线段树

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
struct point {
	int l,r,sum;
	int ls,rs;
}st[(maxn<<5)];
int rt[maxn],a[maxn],n,m,cnt,len;
int idx[maxn];
int getid(const int &val) {  // 离散化
  return lower_bound(idx + 1, idx + len + 1, val) - idx;
}
int build(int l,int r){
	int o = ++cnt;
	st[o].l=l;
	st[o].r=r;
	if(l==r) return o;
	int mid = (l+r)/2;
	st[o].ls = build(l,mid);
	st[o].rs = build(mid+1,r);
	st[o].sum = 0;
	return o;
}
int add(int rt,int k){
	int o = ++cnt;
	int l = st[o].l = st[rt].l, r = st[o].r = st[rt].r;
	st[o].ls=st[rt].ls;
	st[o].rs=st[rt].rs;
	st[o].sum=st[rt].sum+1;
	if(l==r)
		return o;
	int mid = (l+r)/2;
	if(k<=mid)
		st[o].ls = add(st[rt].ls, k);
	else
		st[o].rs = add(st[rt].rs, k);
	return o;
}
int query(int l, int r, int k){
	if(st[l].l == st[l].r)
		return st[l].l;
	int ls_num = st[st[r].ls].sum - st[st[l].ls].sum;
	if(k<=ls_num)
		return query(st[l].ls, st[r].ls, k);
	else
		return query(st[l].rs, st[r].rs, k-ls_num);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	// 离散化 
	memcpy(idx,a,sizeof(idx));
	sort(idx+1,idx+n+1);
	len = unique(idx+1,idx+1+n) - idx -1;
	rt[0] = build(1,len);
	for(int i=1;i<=n;i++)
		rt[i] = add(rt[i-1], getid(a[i]));

	for(int i=1;i<=n;i++){
		int l,r,k;
		cin>>l>>r>>k;
		cout<<idx[query(rt[l-1], rt[r], k)]<<endl;
	}
	return 0;
}

可持久化0/1Trie

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 6e5+5;
int n,q,a[maxn],m;
struct Trie{
	int rt[maxn],cnt;
	int ch[maxn*31][2],val[maxn*31];;
	// 可持久化 0/1 Trie 
	void add_root(int i, int x){
		rt[i] = ++cnt;
		insert(rt[i], rt[i-1], x);
	}
	void insert(int o,int rt, int x){
		for(int i=30;i>=0;i--){
			val[o] = val[rt] + 1;
			bool k = (x&(1<<i));
			if(!ch[o][k]) 
				ch[o][k] = ++cnt;
			ch[o][k^1] = ch[rt][k^1];
			o = ch[o][k];
			rt = ch[rt][k];
		}
		val[o] = val[rt] + 1;
	}
	int query(int l, int r, int x){
		l = rt[l-1], r = rt[r]; 
		int ans = 0;
		for(int i=30;i>=0;i--){
			bool k = (x&(1<<i));
			int num = val[ch[r][k^1]] - val[ch[l][k^1]];
			if(num){
				ans += (1<<i);
				l = ch[l][k^1];
				r = ch[r][k^1];
			}
			else{
				l = ch[l][k];
				r = ch[r][k];
			}
		}
		return ans;
	}
}st;
char s[100];
int main(){
    cin>>n>>m;
    st.cnt=0;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
    	a[i] = a[i]^a[i-1];
    	st.add_root(i, a[i-1]);
	}
	for(int i=1;i<=m;i++){
		cin>>s;
		int l,r,x;
		if(s[0] == 'A'){
			n++;
			cin>>a[n];
			a[n] = a[n]^a[n-1];
			st.add_root(n, a[n-1]);
		}
		else{
			cin>>l>>r>>x;
			cout<<st.query(l,r,a[n]^x)<<endl;
		}
	} 
    return 0;
}

图论

最短路O((n+m)log⁡m)O((n+m)\log m)

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int n,m,s;
int vis[maxn],ves[maxn],k,dep[maxn],fa[maxn][23],dis[maxn];
struct ss{
	int u,v,next,w;
}st[maxn*2];
void add(int a,int b,int c){
	k++;
	st[k].u=a;
	st[k].v=b;
	st[k].w=c;
	st[k].next=ves[a];
	ves[a]=k;
}
struct point{
    int num,dis; 
    bool operator < (const point &a)const{
    	return dis>a.dis;
	}
}p[maxn];
priority_queue <point> q;
void dij(int u){
	for(int i=1;i<=n;i++){
		p[i].num=i;
		dis[i]=p[i].dis=1e9;
	}
	p[u].dis=0;
	dis[u]=0;
	q.push(p[u]);
	while(!q.empty()){
		int head=q.top().num;
		q.pop();
		if(vis[head])continue;
		vis[head]=1;
		for(int i=ves[head];i;i=st[i].next){
			int v=st[i].v;
			if(dis[v]>=dis[head]+st[i].w){
				p[v].dis=dis[head]+st[i].w;
				dis[v]=p[v].dis;
				q.push(p[v]);
			}
		}
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=m;i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
	}
	dij(s);
	for(int i=1;i<=n;i++){
		printf("%d ",dis[i]);
	}
	return 0;
}

差分约束O(VE)O(VE)

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e3+5;
struct edge{
	int u,v,w,next;
}st[maxn*4];
int ves[maxn],vis[maxn],tim[maxn],k,n,m;
int dis[maxn];
void adde(int u,int v,int w){
	k++;
	st[k].u=u;
	st[k].v=v;
	st[k].w=w;
	st[k].next=ves[u];
	ves[u]=k;
}
bool spfa(int s){
	for(int i=1;i<=n;i++){
		dis[i]=1e9;
		tim[i]=0;
	}
	dis[s]=0;
	tim[s]=0;
	queue<int> q;
	q.push(s);
	vis[s]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=ves[u];i;i=st[i].next){
			int v=st[i].v;
			if(dis[v]>dis[u]+st[i].w){
				dis[v]=dis[u]+st[i].w;
				if(!vis[v]){
					vis[v]=1,tim[v]++;
					// 判负环 n+1个点 
					if(tim[v]==n+1)return false; 
					q.push(v);
				} 
			}
		}
	
	}
	return true;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0); 
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		adde(n+1,i,0);
	}
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		adde(v,u,w);
	}
	if(!spfa(n+1)){
		cout<<"NO"<<endl;
	}
	else{
		for(int i=1;i<=n;i++){
			cout<<dis[i]<<" ";
		}
	}
	return 0;
}

并查集 O(1)O(1)

1
2
3
4
int find(int a){
	if(a==fa[a])return fa[a]=a;
	else return fa[a]=find(fa[a]);
}

最小生成树

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
#include<bits/stdc++.h>
using namespace std;
int fa[5015],ans=0,k=0;
struct ss{
	int u,v;double w;
}st[1000005*2]; 
void cc(int a,int b,int c){
	k++;
	st[k].u=a;
	st[k].v=b;
	st[k].w=c;
}
int cmp(ss a,ss b){
	return a.w<b.w;
}
int find(int a) {
	if(a==fa[a])return fa[a]=a;
	else return fa[a]=find(fa[a]);
}
int main() {
    int n,m,l=0;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    	int a,b,c;
    	cin>>a>>b>>c;
    	cc(a,b,c);
	}
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	sort(st+1,st+1+m,cmp);
	for(int i=1;i<=m;i++){	
		int a=find(st[i].u),b=find(st[i].v);
		if(a==b)continue;
		if(l==n-1)break;
		l++;
		ans+=st[i].w;
		fa[a]=st[i].v;
	}
	cout<<ans;
	return 0;
}

强连通

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
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>
using namespace std;
int dp[10004],ves2[10003],ans,vis[10005],a1[10008],k,ves[10004],dep[10004],low[10004],x[10003],top,color[10005],step,color1,y[10004];
struct ss2{
	int u,v,next;
}st2[100004]; 
struct ss{
	int u,v,next;
}st[100004];
void cc(int a,int b){
	k++;
	st[k].u=a;
	st[k].v=b;
	st[k].next=ves[a];
	ves[a]=k;
}
void add(int a,int b){
	k++;
	st2[k].u=a;
	st2[k].v=b;
	st2[k].next=ves2[a];
	ves2[a]=k;
}
void tarjan(int a){
	dep[a]=++step;
	low[a]=step;
	x[++top]=a;
	vis[a]=1;
	for(int i=ves[a];i;i=st[i].next){
		if(dep[st[i].v]==0){
			tarjan(st[i].v);
			low[a]=min(low[a],low[st[i].v]);
		}
		else if(vis[st[i].v]==1)low[a]=min(low[a],dep[st[i].v]);
	}
	if(dep[a]==low[a]){
		color1++;
		while(1){
			int u=x[top--];
			vis[u]=2;
			color[u]=color1;
			dp[color1]+=a1[u];
			if(u==a)break;
		}
	}
}
int dp1(int a){
	int l=0;
	for(int i=ves2[a];i;i=st2[i].next){
		l=max(l,dp1(st2[i].v));
	}
	return dp[a]+l;
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
    	int b;
    	scanf("%d",&b);
    	a1[i]=b;
	}
	for(int i=1;i<=m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		cc(a,b);
	}
	for(int i=1;i<=n;i++){
		if(dep[i]==0)tarjan(i);
	}
	for(int i=1;i<=n;i++){
		for(int j=ves[i];j;j=st[j].next){
			if(color[i]!=color[st[j].v]){
		    	add(color[st[j].v],color[i]);
				y[color[i]]=1;
			}
		}
	}
	for(int i=1;i<=color1;i++){
		if(y[i]==0)ans=max(dp1(i),ans);
	}
	printf("%d",ans);
	return 0;
}

网络流

最大流 O(n2m)O(n^2m)（二分图匹配 O(mn)O(m\sqrt{n})）

最小割=最大流

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<bits/stdc++.h>
using namespace std;
const int Maxn=5005;
const int maxn=500;
const long long inf=1e18;
int vis[maxn],ves[maxn],d[maxn],head[maxn],n,m;
struct edge{
	long long u,v,flow,cap,next;
}st[Maxn*4];
int k=1;
void addedge(int u,int v,long long cap){
	k++;
	st[k].u=u;
	st[k].v=v;
	st[k].flow=0;
	st[k].cap=cap;
	st[k].next=head[u];
	head[u]=k;
}
void add(int u,int v,long long cap){
	addedge(u,v,cap);
	addedge(v,u,0);
}
int bfs(int s,int t){
	for(int i=1;i<=n;i++){
		vis[i]=0;
	}
	queue <int> q;
	q.push(s);
	d[s] = 0;
	vis[s]=1;
	ves[s]=head[s];
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=st[i].next){
			int v=st[i].v;
			if(!vis[v]&&st[i].cap>st[i].flow){
				vis[v]=1;
				d[v]=d[u]+1;
				ves[v]=head[v];
				q.push(v);
			}
		}
	}
	return vis[t];
}
long long dfs(int u,int t,long long now){
	if(u==t||now==0)return now;
	long long flow=0,f;
	for(int i=ves[u];i&&now;i=st[i].next){
		ves[u]=i; // 弧优化 
		int v=st[i].v;
		if(d[u]+1==d[v]&&(f=dfs(v,t,min(st[i].cap-st[i].flow,now)))>0){ 
			if(f==0) d[v]=inf;
			st[i].flow+=f;
			st[i^1].flow-=f;
			now-=f;
			flow+=f;
		}
	}
	return flow;
}
long long Dinic(int s,int t){
	long long flow=0;
	while(bfs(s,t)){
		flow+=dfs(s,t,inf);
	} 
	return flow;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); 
	int s,t;
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
	}
	long long ans=Dinic(s,t);
	cout<<ans;
	return 0;
}

最小费用最大流

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<bits/stdc++.h>
using namespace std;
const int Maxn=50005;
const int maxn=5005;
int INF=0x3f3f3f3f;
int vis[maxn],ves[maxn],dis[maxn], head[maxn],n,m,ret;
int q[maxn],l=1,r=0;
struct edge{
	int u,v,flow,cap,cost,next;
}st[Maxn*2];
int k=1;
void addedge(int u,int v,int cap, int cost){
	k++;
	st[k].u=u;
	st[k].v=v;
	st[k].flow=0;
	st[k].cap=cap;
	st[k].cost=cost;
	st[k].next=ves[u];
	ves[u]=k;
}
void add(int u,int v,int cap, int cost){
	addedge(u,v,cap, cost);
	addedge(v,u,0, -cost);
}

bool spfa(int s,int t){
	for(int i=1;i<=n;i++){
		vis[i]=0;
		dis[i]=INF;
	}
	r = (r+1)%maxn;
	q[r]=s;
	dis[s] = 0;
	vis[s] = 1;
	head[s] = ves[s];
	while((r+1)%maxn!=l){
		int u=q[l];
		for(int i=ves[u];i;i=st[i].next){
			int v=st[i].v;
			if(st[i].cap>st[i].flow&&dis[v]>dis[u]+st[i].cost){
				dis[v] = dis[u] + st[i].cost;
				if(!vis[v]){
					head[v] = ves[v];
					r = (r+1)%maxn;
					q[r]=v;
					vis[v]=1;
				}
			}
		}
		vis[u]=0;
		l = (l+1)%maxn;
	}
	return dis[t]!=INF;
}
int dfs(int u,int t,int now){
	if(u==t||now==0)return now;
	vis[u]=1;
	int flow=0,f;
	for(int i=head[u];i&&now;i=st[i].next){
		head[u]=i; // 弧优化 
		int v=st[i].v;
		if(!vis[v]&&dis[u]+st[i].cost==dis[v]&&(f=dfs(v,t,min(st[i].cap-st[i].flow,now)))>0){ 
			st[i].flow+=f;
			st[i^1].flow-=f;
			now-=f;
			flow+=f;
			ret += f*st[i].cost;
			if(now==0)break;
		}
	}
	vis[u]=0;
	return flow;
}
int Dinic(int s,int t){
	int flow=0;
	while(spfa(s,t)){
		int x;
		flow+=dfs(s,t,INF);
	} 
	return flow;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); 
	int s,t;
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++){
		int u,v,w,c;
		cin>>u>>v>>w>>c;
		add(u,v,w,c);
	}
	int ans=Dinic(s,t);
	cout<<ans<<" "<<ret;
	return 0;
}

动态规划

斜率优化

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+5;
struct rectangle{
	long long  w,l,t;
}st[maxn];
int q[maxn];
long long dp[maxn];
long double k[maxn];
int cmp(rectangle a,rectangle b){
	if(a.l==b.l)return a.w>b.w;
	return a.l>b.l;
} 
long double getk(int i,int j){
	return (dp[j-1]-dp[i-1])/(st[i].l-st[j].l);
}

int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&st[i].w,&st[i].l);
	}
	sort(st+1,st+1+n,cmp);
	int head=0;
	for(int i=1;i<=n;i++){
		if(st[head].w<st[i].w){
			st[++head]=st[i];
		}
	}
	n=head;
	int rear=0;head=1;
	for(int i=1;i<=n;i++){
		while(head<rear&&k[rear-1]>=getk(q[rear],i))rear--;
		k[rear]=getk(q[rear],i);
		q[++rear]=i;
		while(head<rear&&k[head]<=st[i].w)head++;
		dp[i]=st[q[head]].l*st[i].w+dp[q[head]-1];
	}
	printf("%lld\n",dp[n]);
	return 0;
}

树论

最近公共祖先（LCA）

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=600005;
int ves[maxn],k,dep[maxn],fa[maxn][23];
struct ss{
	int u,v,next;
}st[maxn*2];
void add(int a,int b){
	k++;
	st[k].u=a;
	st[k].v=b;
	st[k].next=ves[a];
	ves[a]=k;
}
void init(int u,int f){
	dep[u]=dep[f]+1;
	fa[u][0]=f;
	for(int i=1;i<=21;i++){
		fa[u][i]=fa[fa[u][i-1]][i-1];
	}
	for(int i=ves[u];i;i=st[i].next){
		int v=st[i].v;
		if(v==f)continue;
		init(v,u);
	}
}
int lca(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	for(int i=21;i>=0;i--){
		if(dep[fa[x][i]]<dep[y])continue;
		x=fa[x][i];
	}
	if(x==y)return x;
	for(int i=21;i>=0;i--){
		if(fa[x][i]==fa[y][i])continue;
		x=fa[x][i],y=fa[y][i];
	}
	return fa[x][0];
}
int main(){
	int n,m,s;
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<n;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
	}
	init(s,0);
	for(int i=1;i<=m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		printf("%d\n",lca(a,b));
	}
	return 0;
}

树链剖分

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+4;
int k,n,m,r,mod,w[maxn],ves[maxn];
struct ss{
    int u,v,next;
}st[maxn*2]; 
void cc(int a,int b){
    k++;
    st[k].u=a;
    st[k].v=b;
    st[k].next=ves[a];
    ves[a]=k;
}
 // ----------------------------- 以下初始化 --------------------------
int dep[maxn],fa[maxn],size[maxn],son[maxn];
void dfs1(int a,int f){
    dep[a]=dep[f]+1;
    fa[a]=f;
    size[a]=1;
    int maxson=-1;
    for(int i=ves[a];i;i=st[i].next){
        if(st[i].v==f)continue;
        dfs1(st[i].v,a);
        size[a]+=size[st[i].v];
        if(size[st[i].v]>maxson)son[a]=st[i].v,maxson=size[st[i].v];
    }
}
int num,id[maxn],top[maxn],newa[maxn];
void dfs2(int a,int topfa){
    id[a]=++num;
    newa[num]=w[a];
    top[a]=topfa;
    if(son[a]==0)return;
    dfs2(son[a],topfa);
    for(int i=ves[a];i;i=st[i].next){
        if(st[i].v!=fa[a]&&st[i].v!=son[a])dfs2(st[i].v,st[i].v);
    }
}
 // ----------------------------- 以上初始化 ---------------------------
 // ----------------------------- 以下线段树 ---------------------------
int sum[maxn*6],lazy[maxn*6];
void pushdown(int o,int len){
    lazy[o*2]+=lazy[o];
    lazy[o*2+1]+=lazy[o];
    sum[o*2]+=lazy[o]*(len-(len/2));
    sum[o*2+1]+=lazy[o]*(len/2);
    sum[o*2]%=mod;
    sum[o*2+1]%=mod;
    lazy[o]=0;
}
void build(int o,int l,int r){
    if(l==r){
       sum[o]=newa[l]%mod;
       return;
    }
    int mid=(l+r)/2;
    build(o*2,l,mid);
    build(o*2+1,mid+1,r);
    sum[o]=(sum[o*2]+sum[o*2+1])%mod;
}
void change(int o,int l,int r,int head,int rear,int add){
    if(head<=l&&rear>=r){
        lazy[o]=(lazy[o]+add)%mod;
        sum[o]=(sum[o]+add*(r-l+1))%mod; 
    } 
    else {
        int mid=(l+r)/2;
        if(lazy[o])pushdown(o,r-l+1);
        if(head<=mid)change(o*2,l,mid,head,rear,add);
        if(rear>mid)change(o*2+1,mid+1,r,head,rear,add);
        sum[o]=(sum[o*2]+sum[o*2+1])%mod;
    }
}
int _ans=0;
void query(int o,int l,int r,int head,int rear){
    int mid=(l+r)/2;
    if(head<=l&&rear>=r)_ans=(_ans+sum[o])%mod;
    else {
        if(lazy[o])pushdown(o,r-l+1);
        if(head<=mid)query(o*2,l,mid,head,rear);
        if(rear>mid)query(o*2+1,mid+1,r,head,rear);
    }
}
 // -------------------- 以上线段树 ------------------------------------
int query1(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        _ans=0;
        query(1,1,n,id[top[x]],id[x]);
        ans=(ans+_ans)%mod;
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    _ans=0;
    query(1,1,n,id[x],id[y]);
    ans=(ans+_ans)%mod;
    return ans;
}
void change1(int x,int y,int add){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        change(1,1,n,id[top[x]],id[x],add);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    change(1,1,n,id[x],id[y],add);
}
 // ---------------------------- 特殊处理条链操作 ----------------------
int main(){
    scanf("%d%d%d%d",&n,&m,&r,&mod);
    for(int i=1;i<=n;i++)scanf("%d",&w[i]) ;
    for(int i=1;i<n;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        cc(a,b);
        cc(b,a);
    }
    dep[r]=1;
    dfs1(r,0);
    dfs2(r,r); 
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int type=0,a,b,c;
        scanf("%d",&type);
        if(type==1){
            scanf("%d%d%d",&a,&b,&c);
            change1(a,b,c);
        }
        if(type==2){
            scanf("%d%d",&a,&b);
            printf("%d\n",query1(a,b));
        }
        if(type==3){
            scanf("%d%d",&a,&b);
            change(1,1,n,id[a],id[a]+size[a]-1,b);
        }
        if(type==4){
            scanf("%d",&a);
            _ans=0;
            query(1,1,n,id[a],id[a]+size[a]-1);
            printf("%d\n",_ans);
        }
    }
    return 0;
}

点分治O(nlog⁡n)O(n\log n)

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
const int inf=10000000;
int n,m,q[1005];
struct edge {
	int u,v,next,w;
} st[maxn*2];
int rem[maxn],ves[maxn],k=0;
int maxv[maxn],siz[maxn],vis[maxn],dis[maxn];
int x[maxn];
bool judge[10000005],test[10000005];
void add(int u,int v,int w) {
	k++;
	st[k].u=u;
	st[k].v=v;
	st[k].w=w;
	st[k].next=ves[u];
	ves[u]=k;
}
int sum,rt;
void findrt(int u,int f) {
	siz[u]=1;
	maxv[u]=0;
	for(int i=ves[u]; i; i=st[i].next) {
		int v=st[i].v;
		if(v==f||vis[v])continue;
		findrt(v,u);
		maxv[u]=max(maxv[u],siz[v]);
		siz[u]+=siz[v];

	}
	maxv[u]=max(maxv[u],sum-siz[u]);
	if(maxv[u]<maxv[rt])rt=u;
}
void getdis(int u,int f) {
	rem[++rem[0]]=dis[u];
	for(int i=ves[u]; i; i=st[i].next) {
		int v=st[i].v;
		if(v==f||vis[v])continue;
		dis[v]=dis[u]+st[i].w;
		getdis(v,u);
	}
	return ;
}
void calc(int u) {
	int head=0;
	for(int i=ves[u]; i; i=st[i].next) {
		int v=st[i].v;
		if(vis[v])continue;
		rem[0]=0;
		dis[v]=st[i].w;
		getdis(v,u);
		for(int j=rem[0]; j; j--) {
			for(int k=1; k<=m; k++) {
				if(q[k]>=rem[j]){
					test[k]|=judge[q[k]-rem[j]];
				}
			}
		}
		for(int j=rem[0]; j; j--) {
			if(rem[j]>inf)continue;
			judge[rem[j]]=1;
			x[++head]=rem[j];
		}
	}
	for(int i=1; i<=head; i++) {
		judge[x[i]]=0;
	}
}

void dfs(int u) {
	vis[u]=judge[0]=1;
	calc(u);
	for(int i=ves[u]; i; i=st[i].next) {
		int v=st[i].v;
		if(vis[v])continue;
		sum=siz[v];
		maxv[rt=0]=n;
		findrt(v,0);
		dfs(rt);
	}
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1; i<n; i++) {
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
		add(b,a,c);
	}
	for(int i=1; i<=m; i++) {
		scanf("%d",&q[i]);
	}
	rt=0;
	sum=maxv[0]=n;
	findrt(1,0);
	dfs(rt);
	for(int i=1; i<=m; i++) {
		if(test[i])printf("AYE\n");
		else printf("NAY\n");
	}
	return 0;
}

字符串

哈希Hash

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
ull base=131;
ull a[10010];
char s[10010];
int n,ans=1;
ull mod=212370440130137957ll;
ull hashs(char s[])
{
    int len=strlen(s);
    ull ans=0;
    for (int i=0;i<len;i++)
        ans=(ans*base+(ull)s[i])%mod;
    return ans;
}
main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        {
            scanf("%s",s);
            a[i]=hashs(s);
        }
    sort(a+1,a+n+1);
    for (int i=2;i<=n;i++)
        if (a[i]!=a[i-1])
            ans++;
    printf("%d\n",ans);
}
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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
ull base=131;
struct data
{
ull x,y;
}a[10010];
char s[10010];
int n,ans=1;
ull mod1=19260817;
ull mod2=19660813;
ull hash1(char s[])
{
    int len=strlen(s);
    ull ans=0;
    for (int i=0;i<len;i++)
        ans=(ans*base+(ull)s[i])%mod1;
    return ans;
}
ull hash2(char s[])
{
    int len=strlen(s);
    ull ans=0;
    for (int i=0;i<len;i++)
        ans=(ans*base+(ull)s[i])%mod2;
    return ans;
}
bool comp(data a,data b)
{
    return a.x<b.x;
}
main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        {
            scanf("%s",s);
            a[i].x=hash1(s);
            a[i].y=hash2(s);
        }
    sort(a+1,a+n+1,comp);
    for (int i=2;i<=n;i++)
        if (a[i].x!=a[i-1].x || a[i-1].y!=a[i].y)
            ans++;
    printf("%d\n",ans);
}

KMP / 最长公共前缀O(n+m)O(n+m)

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
char s1[maxn],s2[maxn];
int next[maxn];
void getnext(char *p, int *next){
	// 模板串预处理
	int len = strlen(p);
	next[0]=0,next[1]=0; 
	for(int i=1;i<len;i++){
		int j = next[i];
		while(j&&p[i]!=p[j])
			j=next[j];
		next[i+1]=p[i]==p[j]?j+1:0;
	}
}
void kmp(char *s, char *p,int *next){
	// p 在 s 中出现的次数 
	int len1=strlen(s), len2=strlen(p);
	getnext(p,next);
	int j=0;
	for(int i=0;i<len1;i++){
		while(j&&p[j]!=s[i]) j=next[j];
		if(p[j]==s[i]) j++;
		if(j==len2){
			// 找到 p 
			printf("%d\n",i-len2+1+1); 
		    j=next[j];
		}
	}
}
int main(){
	scanf("%s%s",&s1,&s2);
	kmp(s1,s2,next);
	int a=strlen(s2);
	for(int i=1;i<=a;i++){
		printf("%d ",next[i]);
	}
	return 0;
}

manacherO(n)O(n)

回文串个数和最大长度

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=4e7+20;
char s[maxn],s1[maxn];
int p[maxn];
int len;
void manacher(){
	len=strlen(s);
	int r = 0, mid = 0;
	for(int i=0;i<len;i++) s1[(i<<1)+2]=s[i],s1[(i<<1)+3]='#';
	len=(len<<1)+2,s1[0]='@',s1[1]='#'; 
	for(int i=1;i<len;i++){
		if(i<r) p[i]=min(p[(mid<<1)-i], r-i);
		else p[i] = 1;
		while(s1[i-p[i]]==s1[i+p[i]]) ++p[i];
		if(i+p[i]>r) r = i+p[i], mid = i;
	}
}
int main(){
	scanf("%s",s);
	manacher();
	int ans = 0;
	for(int i=1;i<len;i++){
		ans = max(ans,p[i]-1);
	}
	printf("%d",ans);
	return 0;
}

AC自动机O(n)O(n)

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e6+3;
const int maxntext=2e6+5;
const int size=27;
int ch[maxn][size],val[maxn],last[maxn],ans=0,f[maxn],vis[maxn],num[maxn],times[maxn],limit[maxn];
int sz=1;
int idx(char c){return c-'a';}
char s1[maxntext];
char s2[maxn];
void insert(char *s,int v){
	int u=0,n=strlen(s);
	for(int i=0;i<n;i++){
	    int c=idx(s[i]);
		if(!ch[u][c]){
			memset(ch[sz],0,sizeof(ch[sz]));
			val[sz]=0;
			ch[u][c]=sz++;
		} 
		u=ch[u][c];
	} 
	if(val[u]){
		val[u]=v;
	}
	num[v]=u;
	val[u]=v;
}
void acbuild(){
	queue <int> q;
	f[0]=0;
	for(int c=0;c<size;c++){
		int u=ch[0][c];
		if(u){
		   f[u]=0;
		   q.push(u);
		   last[u]=0;
		}
    }
	while(!q.empty()){
		int r=q.front();q.pop();
		for(int c=0;c<size;c++){
			int u=ch[r][c];
			if(!u){
				ch[r][c]=ch[f[r]][c];
				continue;
			}
			q.push(u);
			int v=f[r];
			while(v&&!ch[v][c]) v=f[v];
			f[u]=ch[v][c];
			if(val[f[u]]){
		    	last[u]=f[u];
				limit[f[u]]++;//有边跳到此处，入度加一； 
			}
			else {
		    	last[u]=last[f[u]];
			    limit[last[f[u]]]++;//同上 
			}
		}
	}
}
queue <int> q1; 

void print(){//统计用拓扑排序优化 
	for(int i=0;i<=sz;i++){
		if(!limit[i])q1.push(i);
	}
	while(!q1.empty()){
		int head=q1.front();q1.pop();
		vis[head]+=times[head];
		limit[last[head]]--;
		times[last[head]]+=times[head];
		if(!limit[last[head]])q1.push(last[head]);
	}
}
void find(char* t){
	int n=strlen(t);
	int j=0;
	for(int i=0;i<n;i++){
	    int c=idx(t[i]);
	    j=ch[j][c];
	    if(val[j])times[j]++;//先打上标记。 
	    else if(last[j])times[last[j]]++;
	} 
	print(); 
}
int main(){ 
	// 每个模式串 s2 在 s1 中出现的次数。
	// O(模式串总长+len(s1))
	int n;
	scanf("%d",&n);
    sz=1;ans=0;
	for(int i=1;i<=n;i++){
		num[i]=i;
		scanf("%s",&s2);
		insert(s2,i);
	}
	acbuild();
	scanf("%s",&s1);
	find(s1);
	for(int i=1;i<=n;i++)
		printf("%d\n",vis[num[i]]);
	return 0;
}

回文自动机O(n)O(n)

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
char s[maxn];
struct Palindrome_Automaton {
	int ch[maxn][26], fail[maxn], len[maxn], sum[maxn], cnt, last;
	Palindrome_Automaton() {
		cnt = 1;
		fail[0] = 1, fail[1] = 1, len[1] = -1;
	}
	int getfail(int x, int i) {
		while(i - len[x] - 1 < 0 || s[i - len[x] - 1] != s[i]) x = fail[x];
		return x;
	}
	void insert(char c, int i) {
		int x = getfail(last, i), w = c - 'a';
		if(!ch[x][w]) {
			len[++cnt] = len[x] + 2;
			int tmp = getfail(fail[x], i);
			fail[cnt] = ch[tmp][w]; // cnt 的最长回文后缀
			sum[cnt] = sum[fail[cnt]] + 1; // cnt 结尾的回文串个数 
			ch[x][w] = cnt; 
		}
		last = ch[x][w]; 
		// 本质不同的回文串的个数 cnt - 2
		// 如果要统计每个回文串的出现次数，还要从叶子节点向根遍历一遍
	}

} PAM;
int main() {
	scanf("%s", s + 1);
	int len = strlen(s + 1);
	int ans = 0;
	for(int i = 1; i<=len; i++) {
		// 第 i 个字符结尾的回文子串个数
		s[i] = (s[i] - 97 + ans) % 26 + 97;
		PAM.insert(s[i], i);
		printf("%d ", ans = PAM.sum[PAM.last]);
	}
	return 0;
}

数学

组合数学

卡特兰数列

f(n)=f(n−1)×(4n−2)n+1f(n)=\dfrac{f(n-1)\times (4n-2)}{n+1}

Lucas定理——求Cn+mn%pC^n_{n+m} \%p

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
#include<bits/stdc++.h>
using namespace std;
long long powny(long long a,long long b,long long mod){
	long long s=1;
	while(b){
		if(b&1)s=(s*a)%mod;
		b>>=1,a=(a*a)%mod;
	}
	return s;
}
long long getc(int n,int m,int mod){
	if(n<m)return 0;
	if(m>n-m)m=n-m;
	long long s1=1,s2=1;
	for(int i=0;i<m;i++){
		s1=s1*(n-i)%mod;
		s2=s2*(i+1)%mod;
	}
	return s1*powny(s2,mod-2,mod)%mod; 
}
long long lucas(int n,int m,int mod){
	if(m==0)return 1;
	return getc(n%mod,m%mod,mod)*lucas(n/mod,m/mod,mod)%mod;
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n,m,p;
		scanf("%d%d%d",&n,&m,&p);
		printf("%lld\n",lucas(m+n,n,p));
	}
	return 0;
}

数论

素数相关定理

唯一分解定理

对于一个整数a(a>1)a(a>1)那么aa一定可以表示为若干个素数的乘积且形式唯一。即a=p1k1×p2k2×⋯×pikia=p_1^{k_1}\times p_2^{k_2}\times\cdots\times p_i^{k_i}。

例1260=22×32×5×71260=2^2\times3^2\times5\times7。

约数个数与约数和公式

约数个数 =(1+k1)×(1+k2)×⋯×(1+ki)=(1+k_1)\times(1+k_2)\times\cdots\times(1+k_i)（这显然可以通过乘法原理计算）

约数和=(1+p11+p12+⋯+p1k1)×(1+p21+p22+⋯+p2k2)×⋯×(1+pi1+pi2+⋯+piki)=(1+p_1^1+p_1^2+\cdots+p_1^{k_1})\times(1+p_2^1+p_2^2+\cdots+p_2^{k_2})\times\dots\times(1+p_i^1+p_i^2+\cdots+p_i^{k_i})

威尔逊定理

若pp为素数，则(p−1)!≡−1(modp)(p-1)!\equiv -1\pmod p（n!n!表示nn的阶乘）

逆定理同样成立 ，若(p−1)!≡−1(modp)(p-1)!\equiv -1\pmod p则pp为素数）

费马定理

若pp为质数，aa为整数，且p,ap,a互质，则a(p−1)≡1(modp)a^{(p-1)}\equiv 1\pmod p

费马小定理：ap≡a(modp)a^p\equiv a\pmod p
（两边同时成aa得到）。

因此在模pp意义下aa的逆元是ap−2a^{p-2}，直接快速幂计算即可。

欧拉函数

定义：对于正整数nn，欧拉函数是小于等于nn的树中与nn互质的数的数目 ，记为ϕ(n)\phi(n).

引理：

  1. 如果pp为质数，则：ϕ(p)=p−1\phi(p)=p-1。
  2. 如果pp为质数，则：$\phi(pa)=(p-1)*p{a-1} $。
  3. 如果a,ba,b互质，则：ϕ(a×b)=ϕ(a)×ϕ(b)\phi(a\times b)=\phi(a)\times\phi(b)（所以欧拉函数是积性函数）

当p∣ip\mid i时ϕ(i×p)=p×ϕ(i)\phi(i\times p)=p\times \phi(i)

当p∤ip\nmid i 时ϕ(i×p)=(p−1)×ϕ(i)\phi(i\times p)=(p-1)\times \phi(i) 。

计算公式：ϕ=n×(1−1p1)×(1−1p2)×⋯×(1−1pi)\phi=n\times(1-\frac{1}{p_1})\times(1-\frac{1}{p_2})\times\cdots\times(1-\frac{1}{p_i})

欧拉定理：若aa与mm互质则aϕ(m)≡1(modm)a^{\phi(m)}\equiv 1\pmod m

扩展欧拉定理
对于任意的a,ma,m满足: 当b≥ϕ(m)b\ge \phi(m)时a(b%ϕ(m)+ϕ(m))≡ab(modm)a^{(b\%\phi (m)+\phi(m))}\equiv a^b\pmod m

线性筛

1
2
3
4
5
6
7
8
9
10
11
12
13
void make_prime(){
	memset(x,1,sizeof(x));
	x[0]=false;
	x[1]=false;
	int head=0;
	for(int i=2;i<=n;++i){
		if(x[i])y[++head]=i;
		for(int j=1;j<=head&&i*y[j]<=n;++j){
			x[i*y[j]]=false;
			if(!(i%y[j]))break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void init(){
	mu[1]=1;
	phi[1]=1;
	int cnt=0;
	for(int i=2;i<maxn;i++){
		if(!vis[i]){
			prime[cnt++]=i;
			mu[i]=-1;
			phi[i]=i-1;
		}
		for(int j=0;j<cnt&&i*prime[j]<maxn;j++){
			vis[i*prime[j]]=1;
			if(i%prime[j]){
			    mu[i*prime[j]]=-mu[i];
			    phi[i*prime[j]]=phi[i]*(prime[j]-1);
			}
			else {
				mu[i*prime[j]]=0;
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
		}
	}
}

数论基础

整除

如果存在一个整数qq使得b=a×qb=a\times q，那么称
bb可被aa整除 ，记作a∣ba|b，且称bb是aa的倍数，即aa是bb的因子 。

整除具有如下性质：

  1. 如果a∣ba\mid b、b∣cb\mid c，那么a∣ca\mid c.
    2.a∣ba\mid b、a∣ca\mid c等价于对于任意整数xx和yy，有a∣(b×x+c×y)a\mid (b \times x+c \times y)。
  2. 设m≠0m \ne 0， 那么a∣ba\mid b等价于(a×m)∣(b×m)(a\times m)\mid(b\times m)。
  3. 设整数xx和yy满足下式：a×x+b×y=1a\times x+b\times y=1，且a∣na\mid n、b∣nb\mid n，那么(a×b)∣n(a\times b)|n。
  4. 若b=q×d+cb=q\times d+c那么d∣bd\mid b的充要条件是d∣cd\mid c.

（以下均为整数运算）

若aa、bb两个整数，他们的差可以被mm整除，那么我们称aa和bb关于模数mm同余 ，记为：
a≡b(modm)a\equiv b \pmod{m}
也就意着a−b=m×k(k∈Z)a-b=m\times k(k\in Z)

同余

同余有如下性质：

  1. 自反性：a≡a(modm)a \equiv a\pmod{m}
  2. 对称性：a≡b(modm)⇒b≡a(modm)a \equiv b\pmod{m}\Rightarrow b \equiv a\pmod{m}
  3. 传递性：a≡b(modm)&b≡c(modm)⇒a≡c(modm)a \equiv b\pmod{m} \And b\equiv c\pmod{m}\Rightarrow a\equiv c\pmod {m}
  4. 同加性：a≡b(modm)⇒a+c≡b+c(modm)a \equiv b\pmod{m}\Rightarrow a+c \equiv b+c\pmod{m}
  5. 同乘性：a≡b(modm)⇒a×c≡b×c(modm)a≡b(modm)&c≡d(modm)⇒a×c≡b×d(modm)\begin{aligned}&a \equiv b\pmod{m}\Rightarrow a\times c \equiv b\times c\pmod{m} \\& a \equiv b\pmod{m} \And c\equiv d\pmod{m}\Rightarrow a\times c\equiv b\times d\pmod {m}\end{aligned}
  6. 同幂性：a≡b(modm)⇒an≡bn(modm)a\equiv b\pmod{m}\Rightarrow a^n\equiv b^n \pmod{m}

最大公约数

gcd⁡(a,b)×lcm⁡(a,b)=a×b\gcd(a,b)\times \operatorname{lcm}(a,b)=a\times b

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;
int main(){
	long long a,b,c;
	cin>>a>>b;
	c=a%b;
	while (c!=0){
		a=b;
		b=c;
		c=a%b;
	}
    cout<<b;
	return 0;
}

扩展欧几里得

已知(a,b)(a,b)求解一组(p,q)(p,q)使得p×a+q×b=gcd⁡(a,b)p\times a+q\times b = \gcd(a,b)

     p×a+q×b=gcd⁡(a,b)=gcd⁡(b,a%b)=p×b+q×(a−a/b×b)=q×a+(p−a/b×q)∗b\boxed{\begin{aligned} & \ \ \ \ \ p\times a+q\times b \\& =\gcd(a,b) \\& =\gcd(b,a\%b) \\ & =p\times b+q\times (a-a/b\times b) \\ & =q\times a+(p-a/b\times q)*b\end{aligned} }

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=10005;
int x,y;
long long ty(int a,int b,int& x,int& y){
	int ret,tmp;
	if(!b){
		x=1;
		y=0;
		return a;
	}
	ret=ty(b,a%b,x,y);
	tmp=x;
	x=y;
	y=tmp-a/b*y;
	return ret;
}
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	int t=b/ty(a,b,x,y);
	x=(x%t+t)%t;
	printf("%d",x);
	return 0;
}

求解线性同余方程

同余方程如下:

x×a+y×b=c⇔a×x≡c(modb)x\times a+y\times b = c\Leftrightarrow a\times x\equiv c\pmod{b}

定理1：裴蜀定理

x×a+y×b=c,x∈N∗,y∈N∗x\times a+y\times b = c,x\in N^*,y\in N^*的充要条件是gcd⁡(a,b)∣c\gcd(a,b) \mid c

应用：a×x+b×y=c⇒agcd⁡(a,b)×x+bgcd⁡(a,b)×y=cgcd⁡(a,b)⇒agcd⁡(a,b)×x≡c(modbgcd⁡(a,b))a\times x+b\times y=c\Rightarrow \frac{a}{\gcd(a,b)}\times x+\frac{b}{\gcd(a,b)}\times y=\frac{c}{\gcd(a,b)}\Rightarrow \frac{a}{\gcd(a,b)}\times x\equiv c\pmod {\frac{b}{\gcd(a,b)}}

定理二

特殊的gcd⁡(a,b)=1&x0,y0\gcd(a,b)=1\And x_0,y_0为方程a×x+b×y=ca\times x+b\times y=c的一组解则$x=x_0+b\times t,y=y_0-a\times t,\forall _{t\in Z} $恒成立。

求最小整数解t=bgcd⁡(a,b),x=(x%t+t)%tt=\frac{b}{\gcd(a,b)},x=(x\%t+t)\%t

线性求乘法逆元

1
A[i]=(p-p/i)*A[p%i]%p;

中国剩余定理

设自然数m1,m2,⋯mnm_1,m_2,\cdots m_n两两互素，并记N=∏i=1nmiN=\prod\limits_{i=1}^n m_i则方程

{x≡b[1](modm1)x≡b[2](modm2)⋯x≡b[n](modmn)\begin{cases} x&\equiv b[1]\pmod{m_1}\\ x&\equiv b[2]\pmod{m_2}\\ &\cdots \\x&\equiv b[n]\pmod{m_n}\\ \end{cases}

在模NN同余的意义下有唯一解 。

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
#include<bits/stdc++.h>
using namespace std;
int  exgcd(long long a,long long b,long long&x,long long &y){
	if(!b){
		x=1;y=0;
		return a;
	}
	int gcd=exgcd(b,a%b,x,y);
	int t=x;
	x=y;
	y=t-a/b*y;
	return gcd; 
} 
long long w[100004],b[100004];long long summ=1,a;
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
        scanf("%d%d",&w[i],&b[i]);
        summ*=w[i];
	}
	for(int i=1;i<=n;i++){
		long long m=summ/w[i],x=1,y=0;
		exgcd(w[i],m,x,y);
		a=(a+(((y*m)%summ)*b[i])%summ)%summ;
	}
	a=(a%summ+summ)%summ;
	printf("%lld",a);
	return 0;
}
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
#include<bits/stdc++.h>
using namespace std;
long long exgcd(long long a,long long b,long long &x,long long&y){
	if(!b){
		x=1;y=0;
		return a;
	}
	long long gcd=exgcd(b,a%b,x,y);
	long long tmp=x;
	x=y;
	y=tmp-a/b*y;
	return gcd;
}
long long mul(long long a,long long b,long long mod){
	long long s=1,ans=0;
	while(b!=0){
		if(b%2==1)ans=(ans+a)%mod;
		b=(b/2);
		a=(a*2)%mod;
	}
	return ans;
}
int main(){
	int n;long long m,ans,lcm;
	scanf("%d%lld%lld",&n,&lcm,&ans);
	n--;
	while(n--){
		long long a,b,x,y,k=lcm;
		scanf("%lld%lld",&a,&b);
		long long a1=((b-ans)%a+a)%a;
		long long gcd=exgcd(lcm,a,x,y);
		x=(mul(x%(a/gcd),a1/gcd%(a/gcd),a/gcd)+(a/gcd))%(a/gcd);
		lcm=lcm*(a/gcd),ans=(ans+mul(k,x,lcm))%lcm;
	}
	printf("%lld",(ans%lcm+lcm)%lcm);
	return 0;
}

BSGS/高次剩余定理O(C)O(\sqrt C)

Ax≡B(modC)(0≤x<C)A^x\equiv B\pmod C (0\le x<C)C 为质数 求 xx

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
#include<bits/stdc++.h>
using namespace std;
const int hashmod=1000003;
long long hash[hashmod+100],val[hashmod+100];
int next[hashmod+100],point[hashmod+100],top=0,p;
void insert(long long x,long long v){
	int n=x%hashmod;
	++top;next[top]=point[n];point[n]=top;val[top]=x,hash[top]=v;
}
long long find(long long x){
	int n=x%hashmod;
	for(int i=point[n];i;i=next[i])
	    if(val[i]==x)return hash[i];
	return -1;
}
long long ksm(long long a,long long b,long long p){
	long long s=1;
	while(b){
		if(b&1)s=(s*a)%p;
		b>>=1,a=(a*a)%p;
	}
	return s;
}
long long bsgs(long long a,long long b,long long p){
	if(a%p==0)return -1;
	top=0;
	memset(point,0,sizeof(point));
	long long m=ceil((sqrt(p)));
	long long d=ksm(a,m,p);
	for(int j=0;j<=m;j++)insert(b,j),b=(b*a)%p;
	long long mul=1;
	for(int i=1;i<=m;i++){
		mul=mul*d%p;
		long long t=find(mul);
		if(t!=-1)return i*m-t;
	}
	return -1;
}

int main(){
    int b,n,p,ans=0;
    scanf("%d%d%d",&p,&b,&n);
    ans=bsgs(b,n,p);
    if(ans==-1)printf("no solution");
    else printf("%lld",ans);
	return 0;
}

杜教筛

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=2000005;
bool vis[maxn];
int mu[maxn],summu[maxn],phi[maxn];long long sumphi[maxn],prime[maxn];
void init(){
	mu[1]=1;
	phi[1]=1;
	int cnt=0;
	for(int i=2;i<maxn;i++){
		if(!vis[i]){
			prime[cnt++]=i;
			mu[i]=-1;
			phi[i]=i-1;
		}
		for(int j=0;j<cnt&&i*prime[j]<maxn;j++){
			vis[i*prime[j]]=1;
			if(i%prime[j]){
			    mu[i*prime[j]]=-mu[i];
			    phi[i*prime[j]]=phi[i]*(prime[j]-1);
			}
			else {
				mu[i*prime[j]]=0;
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
		}
	}
	for(int i=1;i<=maxn;i++)summu[i]=summu[i-1]+mu[i],sumphi[i]=sumphi[i-1]+phi[i];
}
map <int,int> ans_mu;
map <int,long long> ans_phi;
long long ansu(int n){
	if(n<maxn-2)return summu[n];
	if(ans_mu[n])return ans_mu[n];
	long long ans=1;
	for(long long head=2,rear=0;head<=n;head=rear+1){
		rear=n/(n/head);ans-=(rear-head+1)*ansu(n/head);
	}
	return ans_mu[n]=ans;
}
long long ansphi(long long n){
	if(n<maxn-2)return sumphi[n];
	if(ans_phi[n])return ans_phi[n];
	long long ans=n*(n+1)/2;
	for(long long head=2,rear=0;head<=n;head=rear+1){
		rear=n/(n/head);ans-=(rear-head+1)*ansphi(n/head);
	}
	return ans_phi[n]=ans;
}
int main(){
	init();
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		printf("%lld %lld\n",ansphi(n),ansu(n));
	}
	return 0;
}

数论分块

求解∑i=1n⌊ni⌋\sum\limits_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor，策略： 将相同的值合并求解

也就是说我们需要找到最大的jj满足⌊ni⌋=⌊nj⌋\left\lfloor\frac{n}{i}\right\rfloor = \left\lfloor\frac{n}{j}\right\rfloor， j=⌊n⌊ni⌋⌋j=\left\lfloor\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor

每次我们对区间[i,j][i,j]求解即可。时间复杂度为O(n)O(\sqrt n)

1
2
for(int head=1,rear=0;head<=n;head=rear+1){
    rear=n/(n/head);ans+=(rear-head+1)*(n/head);

莫比乌斯反演

#####DirichletDirichlet卷积
(f∗g)(n)=∑d∣nf(d)g(nd)(f * g) (n)=\sum\limits_{d|n}f(d)g(\frac{n}{d})

常见积性函数

  1. 单位原ϵ(n)=[n=1]\epsilon(n)=[n=1]
  2. 常函数1(n)=11(n)=1
  3. 恒等函数id(n)=nid(n)=n
  4. 欧拉函数ϕ(n)=∑i=1n[gcd⁡(i,n)=1]\phi(n)=\sum\limits_{i=1}^n[\gcd(i,n)=1]（nn以内与nn互质的数）
  5. 莫比乌斯函数μ(n)={1x=1(−1)kk为本质不同的质因子的个数0otherwises\mu(n)=\begin{cases}1&x=1 \\ (-1)^k &k\text{为本质不同的质因子的个数}\\0 & \text{otherwises}\end{cases}
常用的卷积式

μ∗1=ϵ\mu * 1=\epsilon莫比乌斯反演

ϕ∗ 1=Id\phi * \ 1=Id

μ∗Id=ϕ\mu * Id = \phi

∑d∣nμ(d)=[n=1]\sum\limits_{d|n}\mu(d)=[n=1]

常见公式推导

1.$\sum\limits_{i=1}n\sum\limits_{m=1}mf(i)g(j)\Rightarrow\sum\limits_{i=1}^n f(i) \sum\limits_{j=1}^m g(j) 2. 2.[ \gcd(i,j)=1 ]\Rightarrow \epsilon(\gcd(i,j))\Rightarrow \sum\limits_{d|\gcd{(i,j)}}! ! \mu(d)3. 3.\sum\limits_{i=1}n\sum\limits_{j=1}m[d\mid i,d\mid j]\Rightarrow \sum\limits_{i=1}{\left\lfloor\frac{n}{d}\right\rfloor}\sum\limits_{j=1}{\left\lfloor\frac{m}{d}\right\rfloor}1\Rightarrow\left\lfloor\frac{n}{d}\right\rfloor\left\lfloor\frac{m}{d}\right\rfloor4. 4.[k\mid\gcd(i,j)]\Rightarrow [k\mid i,k\mid j]$

解题示例

∑p∈prime∑i=1n∑j=1m[gcd⁡(i,j)=p]\sum\limits_{p\in prime}\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=p]

∑p∈prime∑i=1⌊np⌋∑j=1⌊mp⌋[gcd⁡(i,j)=1]\sum\limits_{p\in prime}\sum\limits_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{p}\right\rfloor}[\gcd(i,j)=1]

∑p∈prime∑i=1⌊np⌋∑j=1⌊mp⌋∑d∣gcd⁡(i,j) ⁣ ⁣μ(d)\sum\limits_{p\in prime}\sum\limits_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{p}\right\rfloor}\sum\limits_{d|\gcd{(i,j)}}\! \! \mu(d)

∑p∈prime∑i=1⌊np⌋∑j=1⌊mp⌋∑dμ(d)[d∣i,d∣j]\sum\limits_{p\in prime}\sum\limits_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{p}\right\rfloor}\sum\limits_{d}\mu(d)[d\mid i,d\mid j]

∑p∈prime∑d=1μ(d)∑i=1⌊np⌋∑j=1⌊mp⌋[d∣i,d∣j]\sum\limits_{p\in prime}\sum\limits_{d=1}\mu(d)\sum\limits_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{p}\right\rfloor}[d\mid i,d\mid j]

∑p∈prime∑d=1μ(d)∑i=1⌊npd⌋∑j=1⌊mpd⌋1\sum\limits_{p\in prime}\sum\limits_{d=1}\mu(d)\sum\limits_{i=1}^{\left\lfloor\frac{n}{pd}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{pd}\right\rfloor}1

∑p∈prime∑d=1μ(d)⌊npd⌋⌊mpd⌋\sum\limits_{p\in prime}\sum\limits_{d=1}\mu(d)\left\lfloor\frac{n}{pd}\right\rfloor\left\lfloor\frac{m}{pd}\right\rfloor

设T=pdT=pd

∑T=1∑p∣Tμ(Tp)⌊nT⌋⌊mT⌋\sum\limits_{T=1}\sum\limits_{p\mid T}\mu(\frac{T}{p})\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor

写好看一点

∑T=1min⁡(n,m)⌊nT⌋⌊mT⌋(∑p∣Tμ(Tp))\sum\limits_{T=1}^{\min(n,m)}\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor\bigg(\sum\limits_{p\mid T}\mu(\frac{T}{p})\bigg)

使用线性筛预处理所有∑p∣Tμ(Tp)\sum\limits_{p\mid T}\mu(\frac{T}{p})

配合上整除分块算⌊nT⌋⌊mT⌋\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor

线性代数

矩阵快速幂

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
const int mod=1e9+7;
struct jz{
	int n,m;
	long long x[maxn][maxn];
	jz(){memset(x,0,sizeof x);}
};
jz operator * (const jz &a,const jz &b){
	jz c;
	if(a.m!=b.n)return c;
	c.n=a.n,c.m=b.m; 
	for(int i=1;i<=c.n;++i){
		for(int j=1;j<=c.m;++j){
			for(int k=1;k<=c.n;++k){
				c.x[i][j]=((long long)c.x[i][j]+a.x[i][k]*b.x[k][j]%mod)%mod;
			}
		}
	}
	return c;
}
jz ksm(jz l,long long k){
	jz s;s.n=s.m=l.n;
	for(int i=0;i<=s.n;++i)s.x[i][i]=1;
	while(k){
		if(k&1)s=s*l;
		l=l*l,k>>=1; 
	}
	return s;
}
int main(){
	long long n,k;
	scanf("%lld%lld",&n,&k);
	jz l;l.n=l.m=n;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			cin>>l.x[i][j];
		}
	}
	l=ksm(l,k);
	for(int i=1;i<=l.n;++i){
		for(int j=1;j<=l.m;++j){
			printf("%lld ",l.x[i][j]);
		}
		printf("\n");
	}
	return 0;
}

线性基

// 除了最大值，其余的有待验证

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
71
72
73
74
75
76
77
#include<bits/stdc++.h>
using namespace std;
const int last=62;
const int maxn=55;
long long a[maxn],p[last+5],cnt, zero;
void insert(long long x){
	for(int i=last;i>=0;i--){
		if(x&(1ll<<i)){
			if(!p[i]){
				p[i]=x;
				return;
			}
			else x^=p[i];
		}
	}
	zero=1;
}
bool check(long long x){
	for(int i=last;i>=0;i--){
		if(x&(1ll<<i))
			if(!p[i]) return false;
			else x^=p[i]; 
	}
	return true;
}
long long query_max(){
	long long res = 0;
	for(int i=last;i>=0;i--){
		res = max(res,res^p[i]);
	}
	return res;
}
long long query_min(){
	if(zero)return 0;
	for(int i=0;i<=last;i++){
		if(p[i])return p[i];
	}
}
void rebulid(){
	cnt =0;
	for(int i=last;i>=0;i--){
		for(int j=i-1;j>=0;j--){
			if(p[i]&(1ll<<j)) p[i]^=p[j];
		}
	}
}
long long query_kmin(int k){
//	rebulid();
	k=k-zero;
	if(k==0)return 0;
	if(k<=(1ll<<cnt)) return -1;
	long long ans = 0;
	for(int i=last;i>=0;i--){
		if(k&(1ll<<i)) ans^=p[i];
	}
	return ans;
}
int rank(long long x){
//	rebuild()
	int ans=0;
	for(int i=cnt-1;i>=0;i--){
		if(x>=p[i]) ans+=(1<<i), x^=p[i];
	}
	return ans+zero;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n; 
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		insert(a[i]);
	}
	cout<<query_max()<<endl;
	return 0;
}

计算几何

多点最小球覆盖

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
const double eps=1e-8;//精度 
int n,m; 
struct point {
double x,y,z;
}p[maxn];
double dis(point a,point b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.z-b.z)*(a.z-b.z)+(a.y-b.y)*(a.y-b.y));
}
double solve(){
    double  t=1000;
    point ansp={0,0,0};
    double ans=1e9;
    while(t>eps){
        point maxp=p[1];
        for(int i=2;i<=n;i++){
            if(dis(ansp,p[i])>dis(ansp,maxp)){
                maxp=p[i];
            }
        }
        ans=min(ans,dis(maxp,ansp));
        ansp.x+=(maxp.x-ansp.x)/1000*t;
        ansp.y+=(maxp.y-ansp.y)/1000*t;
        ansp.z+=(maxp.z-ansp.z)/1000*t;
        t*=0.97;
    }
    return ans;
}
int main(){

    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z);
    }
    printf("%.10lf",solve());
    return 0;
}

凸包

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 maxn=1e5+5;
struct xl{
	long double x,y;
	long double operator * (const xl &p){
		return x*p.y - y*p.x;
	}
	double get_k(){
		return atan2(y,x);
	}
}; 
struct point{
	long double x,y;
	xl operator - (const point &p){
		xl k;
		k.x=x-p.x;
		k.y=y-p.y;
		return k;
	}
	long double operator | (const point &p){
		long double dis = (x-p.x)*(x-p.x)+(y-p.y)*(y-p.y);
		return sqrt(dis);
	}
	 
}p[maxn],tb[maxn];
void swap_p(point x,point y){
	swap(x.x,y.x);
	swap(x.y,y.y);
}
int n;
int cmp(point x,point y){
	if((x-p[1]).get_k() == (y-p[1]).get_k()){
		return (x|p[1]) < (y|p[1]);
	}
	return (x-p[1]).get_k() < (y-p[1]).get_k();
}
int cmp1(point x,point y){
	if(x.y == y.y)
		return x.x<y.x;
	return x.y<y.y;
}
int cnt=0;
void get_tb(){
	sort(p+1,p+1+n,cmp1);
	sort(p+2,p+1+n,cmp);
	tb[++cnt] = p[1];
	for(int i=2;i<=n;i++){
		while(cnt>1&&(tb[cnt-1]-tb[cnt])*(tb[cnt]-p[i])<=0){
			cnt--;
		}
		tb[++cnt]=p[i];
	}
	tb[++cnt] = p[1];
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;

	for(int i=1;i<=n;i++){
		cin>>p[i].x>>p[i].y;
	}
	get_tb();
	long double ans=0;
	for(int i=1;i<cnt;i++)
		ans+= (tb[i]|tb[i+1]);
	printf("%.2Lf",ans);
	return 0;
}

旋转卡壳

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
struct xl{
	long double x,y;
	long double operator * (const xl &p){
		return x*p.y - y*p.x;
	}
	double get_k(){
		return atan2(y,x);
	}
	long double get_len(){
		return sqrt(x*x+y*y);
	}

}; 
struct point{
	long double x,y;
	xl operator - (const point &p){
		xl k;
		k.x=x-p.x;
		k.y=y-p.y;
		return k;
	}
	long double operator | (const point &p){
		long double dis = (x-p.x)*(x-p.x)+(y-p.y)*(y-p.y);
		return sqrt(dis);
	}
	 
}p[maxn],tb[maxn];
void swap_p(point x,point y){
	swap(x.x,y.x);
	swap(x.y,y.y);
}
long double get_dis(point x,point p1, point p2){
	long double S=abs((x-p1)*(p2-p1));
	long double len2 = (p1-p2).get_len();
	if(len2==0) return 0;
	return S/sqrt(len2);
}
int n;
int cmp(point x,point y){
	if((x-p[1]).get_k() == (y-p[1]).get_k()){
		return (x|p[1]) < (y|p[1]);
	}
	return (x-p[1]).get_k() < (y-p[1]).get_k();
}
int cmp1(point x,point y){
	if(x.y == y.y)
		return x.x<y.x;
	return x.y<y.y;
}
int cnt=0;
void get_tb(){
	sort(p+1,p+1+n,cmp1);
	sort(p+2,p+1+n,cmp);
	tb[++cnt] = p[1];
	for(int i=2;i<=n;i++){
		while(cnt>1&&(tb[cnt-1]-tb[cnt])*(tb[cnt]-p[i])<=0){
			cnt--;
		}
		tb[++cnt]=p[i];
	}
}
long double get_d(){
	long double ans = 0;
	int now=2;
	if(cnt==2)
		return (tb[1] - tb[2]).get_len();
	for(int i=1;i<=cnt;i++){
		while(get_dis(tb[now],tb[i],tb[i%cnt+1]) <= get_dis(tb[now%cnt+1],tb[i],tb[i%cnt+1])){
			now = now%cnt+1;
		}
		ans = max(ans, max((tb[now] - tb[i]).get_len(), (tb[now] - tb[i%cnt+1]).get_len()));
	}
	return ans;
}
long double get_C(){
	long double ans=0;
	for(int i=1;i<=cnt;i++)
		ans+= (tb[i]|tb[i%cnt+1]);
	return ans;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>p[i].x>>p[i].y;
	}
	get_tb();
	long double ans = get_d(); 
	printf("%.0Lf",ans*ans);
	return 0;
}

最小矩形覆盖

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int pi=3.1415926;
struct xl{
	long double x,y;
	long double operator * (const xl &p){
		return x*p.y - y*p.x;
	}
	double get_k(){
		return atan2(y,x);
	}
	long double get_len(){
		return sqrt(x*x+y*y);
	}
	long double operator ^(const xl &p){
		return p.x*x+p.y*y;
	}
	xl operator ~(){
		xl line = {-y,x};
		return line;
	}
}; 
struct point{
	long double x,y;
	xl operator - (const point &p){
		xl k;
		k.x=x-p.x;
		k.y=y-p.y;
		return k;
	}
	long double operator | (const point &p){
		long double dis = (x-p.x)*(x-p.x)+(y-p.y)*(y-p.y);
		return sqrt(dis);
	}
	 
}p[maxn],tb[maxn];
struct line{
	point p;
	double k;
}ll[5],ansl[5];
void swap_p(point x,point y){
	swap(x.x,y.x);
	swap(x.y,y.y);
}
long double get_s(point x,point p1, point p2){
	long double S=abs((x-p1)*(p2-p1));
	return S;
}
int n;
int cmp(point x,point y){
	if((x-p[1]).get_k() == (y-p[1]).get_k()){
		return (x|p[1]) < (y|p[1]);
	}
	return (x-p[1]).get_k() < (y-p[1]).get_k();
}
int cmp1(point x,point y){
	if(x.y == y.y)
		return x.x<y.x;
	return x.y<y.y;
}
int cnt=0;
void get_tb(){
	sort(p+1,p+1+n,cmp1);
	sort(p+2,p+1+n,cmp);
	tb[++cnt] = p[1];
	for(int i=2;i<=n;i++){
		while(cnt>1&&(tb[cnt-1]-tb[cnt])*(tb[cnt]-p[i])<=0){
			cnt--;
		}
		tb[++cnt]=p[i];
	}
	tb[cnt+1]=p[1];
}
point cross(line l1,line l2){
	long double A1 = -sin(l1.k), B1=cos(l1.k), C1=l1.p.y*cos(l1.k)-l1.p.x*sin(l1.k);
	long double A2 = -sin(l2.k), B2=cos(l2.k), C2=l2.p.y*cos(l2.k)-l2.p.x*sin(l2.k);
	point p12 = {(B2*C1-B1*C2)/(A1*B2-A2*B1), (A1*C2 - A2*C1)/(A1*B2 - A2*B1)} ;
	return p12;
}
long double cal_S(point x1, point x2, point top, point l, point r){
	ll[1].k = (x2-x1).get_k();
	ll[1].p = x1;
	ll[4].k = (~(x2-x1)).get_k();
	ll[4].p = r;
	ll[3].k = (x2-x1).get_k();
	ll[3].p = top;
	ll[2].k = (~(x2-x1)).get_k();
	ll[2].p = l;
	point p12 = cross(ll[1],ll[2]), p23 = cross(ll[2],ll[3]), p34 = cross(ll[3],ll[4]);
	return (p12-p23).get_len()*(p23-p34).get_len();
}
long double get_ans(){
	long double ans = 1e9;
	if(cnt==2)
		return (tb[1] - tb[2]).get_len();
	for(int i=1,now=2,x=2,y=2;i<=cnt;i++){
		while(get_s(tb[now],tb[i],tb[i%cnt+1]) <= get_s(tb[now%cnt+1],tb[i],tb[i%cnt+1])){
			now = now%cnt+1;
		}
		y = max(y,now);
		while(x!=now&&((tb[i+1]-tb[i])^(tb[x+1]-tb[x]))>-1e-6) x = x%cnt+1;
		while(y!=i&&((tb[i+1]-tb[i])^(tb[y+1]-tb[y]))<1e-6) y = y%cnt+1;
		long double S = cal_S(tb[i], tb[i+1], tb[now], tb[x], tb[y]);
		if(S<ans){
			ans = S;
			for(int i=1;i<=4;i++)
				ansl[i]=ll[i];
		}
	}
	return ans;
}
long double get_C(){
	long double ans=0;
	for(int i=1;i<=cnt;i++)
		ans+= (tb[i]|tb[i%cnt+1]);
	return ans;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>p[i].x>>p[i].y;
	}
	get_tb();
	long double ans = get_ans(); 
	printf("%Lf\n",ans);
	for(int i=1;i<=4;i++){
		point c = cross(ansl[i],ansl[i%4+1]);
		printf("%Lf %Lf\n", c.x, c.y);
	}
	return 0;
}

其他

STL容器

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
#include<map>
map<string,int> mp;
map<typename1, typename2>::iterator it; // 迭代器访问

mp[]=;
mp.insert(pair<key,int>("Alan",100));
mp.erase(key); // 函数会删除键为 key 的 所有 元素。返回值为删除元素的数量。
mp.erase(pos); // 删除迭代器为 pos 的元素，要求迭代器必须合法。
mp.erase(first,last); // 删除迭代器在 [first,last) 范围内的所有元素。
mp.clear(); // 函数会清空整个容器


#include<set> 
set <int> a;
set <int,cmp> a2;
multiset <int> b; // 可重复元素
set<typename>:: iterator s; // 迭代器访问
for(s=a.begin();s!=a.end();s++) // 枚举

a.insert(x); // 插入
a.erase(x); // 删除
a.erase(pos) // 删除迭代器为 pos 的元素，要求迭代器必须合法
a.erase(first,last) // 删除迭代器在 [first,last) 范围内的所有元素
a.count(x) // 返回 set 内键为 x 的元素数量
a.find(x); // 若容器内存在键为 x 的元素，会返回该元素的迭代器；否则返回end()
a.lower_bound(x); // 返回指向首个不小于给定键的元素的迭代器
a.upper_bound(x); // 返回指向首个大于给定键的元素的迭代器
a.empty();
a.size();

vector<int> vec;
vec.push_back(7);
int x = vec[0];
vec.clear();
vec.size();
for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::cout << *it << " ";
}

模拟退火

求函数最小值

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
struct node{
int x,y,w;  
}p[maxn];
int n;
double ansx,ansy,answ;
double energy(double x,double y){
    double r=0,dx,dy;
    for(int i=1;i<=n;i++){
        dx=x-p[i].x;
        dy=y-p[i].y;
        r+=sqrt(dx*dx+dy*dy)*p[i].w;
    }   
    return r;
}
void sa(){ // 模拟退火 
    double t=3000,eps=1e-15; // 初始温度和精度 
    while(t>eps){
        double ex=ansx+(rand()*2-RAND_MAX)*t;
        double ey=ansy+(rand()*2-RAND_MAX)*t;
        double ew=energy(ex,ey);
        double de=ew-answ;
        if(de<0){
            ansx=ex,ansy=ey,answ=ew;
        }
        else if(exp(-de/t)*RAND_MAX>rand()){
            ansx=ex,ansy=ey;
        }
        t*=0.996;
    }   
}
int main (){

    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].w);
        ansx+=p[i].x,ansy+=p[i].y; 
    }
    ansx/=n;
    ansy/=n;
    answ=energy(ansx,ansy);
    sa();sa();sa();sa();
    printf("%.3lf %.3lf",ansx,ansy);
    return 0;
}

三分法

单峰函数最值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
while (r - l > eps){
    mid = (l + r) / 2;
    double fl = f(mid - eps), fr = f(mid + eps);
    if (fl < fr)
        l = mid; 
    else r = mid;
}
void findans(int head,int rear){
    while(head<rear){
        int mid1=head+(rear-head)/3,mid2=rear-(rear-head)/3;
        long double fl=energy(mid1),fr=energy(mid2);      
        if(fl<fr)rear=mid2-1;
        else head=mid1+1;   
    }
    ans1=energy(head);
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章

快来参与讨论吧~