算法题整理——差分和前缀和

发表于 | 分类于 |

差分

POJ3263_Tallest Cow

描述

Farmer John 有N头牛排列成一排，当两头牛i，j之间的牛身高都小于它们时，这两头牛可以看到对方。

现在，知道最高的牛的编号是I，身高为H，以及R对可以相互看到对方的牛的编号。

在让每头牛都尽可能高的情况下，求出所有牛的身高。

数据范围

1 ≤ N ≤ 10,000

1 ≤ H ≤ 1,000,000

0 ≤ R ≤ 10,000

思路

一开始，我们不妨让所有牛的身高都相等。

每当我们得知，牛i可以看到牛j时，我们知道区间[i+1,j-1]之内的所有牛的身高都小于牛i，牛j的身高，为了让每头牛的身高都尽可能地大，我们不妨给这个区间内的所有牛的身高减1。

先建立一个数组来存储身高的差分，这样每次知道i，j相互看见时，只需要执行两次就可以了。

这道题的坑在于：相互看到的信息有可能是重复的。比如1能看到2，这条信息可能会被输入多次，而我们只需要减去一次1就可以了。由于数据规模较大，我们不能使用二维数组来存储某条信息是否已经处理过，而是使用map。

解决

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 <cstdio>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

const int M = 1e4 + 5;

int d[M + 1];
int a[M + 1];
map<pair<int, int>, bool> v;

int main(){
	memset(d, 0, sizeof(d));
	
	int N, H, I, R;
	scanf("%d %d %d %d", &N, &I, &H, &R);
	
	int l, r;
	for(int i = 0; i < R; ++i){
		scanf("%d %d", &l, &r);
		if(l > r)swap(l, r);
		if(v[make_pair(l, r)])continue;
		v[make_pair(l, r)] = 1;
		--d[l];
		++d[r - 1];
	}
	
	a[0] = d[0];
	for(int i = 1; i < N; ++i){
		a[i] = a[i - 1] + d[i];
	}
	
	int dlt = H - a[I - 1];
	
	for(int i = 0; i < N; ++i){
		printf("%d\n", a[i] + dlt);
	}
	
	return 0;
}

前缀和

CH2101_可达性统计

描述

给定一张N个点M条边的有向无环图，分别统计从每个点出发能够到达的点的数量。N,M≤30000。

思路

拓扑排序，然后按逆序走，记录每一个点能到达的节点。

为了使那么多点可以存得下，使用bitset

拓扑排序

有向图的拓扑排序实在是太经典的算法了，而且似乎还挺常见。记得我最后一次CSP的C题就是拓扑排序，点亮数字人生。

做法是，统计每个点的入度di并维护一个栈，如果di是0，进栈。

栈不空时，取出栈顶进入队列，栈顶的所有后继点j，进行dj-1，如果dj变成了0，进栈，同理。

最后得到的队列就是拓扑排序的结果。

bitset

bitset真是神奇的数据结构，它可以存储一堆1位的比特，常用的函数有：

reset(x)将每一位都设为x

count()统计1的个数

然后，bitset可以支持按位与，或，异或，非等操作，也支持下标访问。

解决

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
#include <stack>
#include <bitset>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 3e4 + 5;

bitset<N> visit[N];

struct edge{
	int node;
	int next;
}es1[N], es2[N];

int head1[N], tail1[N], head2[N], tail2[N], d[N], q[N];

int n, m, v1, v2, tot1 = 0, tot2 = 0, conq = 0;

void dfs(int i){
	visit[i].reset();
	visit[i][i] = 1;
	for(int j = head1[i]; j != -1; j = es1[j].next){
		visit[i] |= visit[es1[j].node];
	}
}

int main(){
	memset(visit, 0, sizeof(visit));
	memset(head1, -1, sizeof(head1));
	memset(tail1, -1, sizeof(tail1));
	memset(head2, -1, sizeof(head2));
	memset(tail2, -1, sizeof(tail2));
	memset(d, 0, sizeof(d));
	scanf("%d %d", &n, &m);
	
	for(int i = 0; i < m; ++i){
		scanf("%d %d", &v1, &v2);
		++d[v1];
		if(head1[v1] == -1){
			tail1[v1] = head1[v1] = tot1;
			es1[tot1].next = -1;
			es1[tot1].node = v2;
		}else{
			es1[tail1[v1]].next = tot1;
			tail1[v1] = tot1;
			es1[tot1].next = -1;
			es1[tot1].node = v2;
		}
		if(head2[v2] == -1){
			tail2[v2] = head2[v2] = tot2;
			es2[tot2].next = -1;
			es2[tot2].node = v1;
		}else{
			es2[tail2[v2]].next = tot2;
			tail2[v2] = tot2;
			es2[tot2].next = -1;
			es2[tot2].node = v1;
		}
		++tot1;
		++tot2;
	}
	
	stack<int> s;
	for(int i = 1; i <= n; ++i){
		if(!d[i]) s.push(i);
	}
	
	while(!s.empty()){
		int cur = s.top();
		s.pop();
		q[conq++] = cur;
		for(int i = head2[cur]; i != -1; i = es2[i].next){
			--d[es2[i].node];
			if(!d[es2[i].node]) s.push(es2[i].node);
		}
	}
	/*
	for(int i = 0; i < n; ++i) printf("%d ", q[i]);
	printf("\n");
	*/
	for(int i = 0; i < n; ++i){
		dfs(q[i]);
	}
	
	for(int i = 1; i <= n; ++i){
		printf("%d\n", visit[i].count());
	}
	
	return 0;
}

备注

这题没有用bitset的时候，用的是整形变量来存储可达性，可能for循环开销太大了吧，不如内置的count和位运算好用，总之一直超时。

结果后面数独的搜索题，我用bitset又反倒不如整形好了，可能抽象类型建立和析构开销太大了吧，内置的东西，咱也不知道。

总之挺离谱的，有时候好用有时候就不行。