CSP赛前复习总结

还有一两天就CSP了，特此为近期的复习进行总结。

时空复杂度分析

对于时空复杂度分析是算法竞赛中一个非常重要的环节，因为我们可以通过题目所给的时间限制去推导实现该题目所需要用的算法内容。
下面举几个例子：
当 $n$ 是一个非常小常数时， $30$ 以下的 $n$ 一般时间复杂度就是指数级别的，类似的算法有状压dp。
当 $n\le k\times 10^2(k\le 500)$ 时，可能就是 $\Theta (n^3)$ 的算法实现，例如一些dp和弗洛伊德算法。
当 $n\le 10^{3or4}$ 的时候，该算法的时间复杂度一般是 $\Theta (n^2)$，例如dp和匈牙利算法（匈牙利算法虽然理论上应该是 $\Theta (n^3)$ 但是实则却能跑出平方甚至更低的时间复杂度）等。
当 $n\le 10^6$ 左右时一般都是 $\Theta (nlogn)$ 的算法，此事件复杂的的算法有很多，例如求最短路的dijkstra堆优化和SPFA，还有线段树和树状数组都是（树状数组所带的常数要小于线段树）。
……
然而平时考试的也不需要怎么考虑空间限制，只要不把数组开的指数级别或者是递归爆栈应该没什么。
综上所述，分析时空复杂度是一个很重要的东西。

算法回顾

基础算法

最近复习了一些基础算法，包括贪心，二分，双指针之类的。

贪心

删数问题

题目描述

键盘输入一个高精度的正整数 $N$（不超过 $250$ 位），去掉其中任意 $k$ 个数字后剩下的数字按原左右次序将组成一个新的非负整数。编程对给定的 $N$ 和 $k$，寻找一种方案使得剩下的数字组成的新数最小。

输入格式

输入两行正整数。
第一行输入一个高精度的正整数 $n$。
第二行输入一个正整数 $k$，表示需要删除的数字个数。

输出格式

输出一个整数，最后剩下的最小数。

样例输入

175438 
4
1
2

样例输出

13
1

这道题的意思就是给定一个数字，求删除 $k$ 个数之后的最小值，很明显这是一道很简单的贪心，贪心的主要过程如下

for (int i = 1; i <= n; i++) {
	a[i] = num[i - 1] - '0';
}
rest = n - k;
while (cnt < rest) {
	minp = t;
	for (int i = t; i <= k + t; i++) {
		if (a[minp] > a[i]) {
			minp = i;
		}
	}
	if (a[minp]) {
		flag = 1;
	}
	if (flag) {
		cout << a[minp];
	}
	k -= minp - t;
	t = minp + 1;
	cnt++;
}
if (!flag) {
	cout << 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

贪心问题的具体应用

贪心问题中最经典对的运用就是哈夫曼树（哈夫曼树是优先队列来实现的）
哈夫曼树的主要建树思路如下

知道了如何建树之后，代码就显而易见了。

#include
using namespace std;
priority_queue<int, vector<int>, greater<int> >q;
int n, a[10005];
int huffman(int x) {
	int res = 0;
	for (int i = 0; i < n - 1; i++) {
		int x = q.top();
		q.pop();
		int y = q.top();
		q.pop();
		int add = x + y;
		res += add;
		q.push(add);
	}
	return res;
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		q.push(a[i]);
	}
	cout << huffman(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

双指针

双指针最广泛被人们所知的应用就是快速排序

void qsort(int *arr, int begin, int end) {
	if (begin > end)
		return;
	int tmp = arr[begin];
	int i = begin;
	int j = end;
	while (i != j) {
		while (arr[j] >= tmp && j > i) {
			j--;
		}
		while (arr[i] <= tmp && j > i) {
			i++;
		}
		if (j > i) {
			int t = arr[i];
			arr[i] = arr[j];
			arr[j] = t;
		}
	}
	arr[begin] = arr[i];
	arr[i] = tmp;
	qsort(arr, begin, i - 1);
	qsort(arr, i + 1, end);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

二分

例题

数列分段题目传送门
数列分段也是二分+贪心运用的一道著名例题

#include
using namespace std;
const int MAX = 1000005;
long long n, m, a[MAX], maxn = LONG_LONG_MIN;
long long sum, ans;
bool check(long long mid) {
	int cnt = 1, sum_c = 0;
	for (int i = 1; i <= n; i++)
		if (a[i] + sum_c > mid)
			sum_c = a[i], cnt++;
		else sum_c += a[i];
	return cnt <= m;
}
int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		sum += a[i];
		maxn = max(maxn, a[i]);
	}
	long long l = maxn, r = sum, mid;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (check(mid)) {
			r = mid - 1;
			ans = mid;
		} else {
			l = mid + 1;
		}
	}
	cout << ans << 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

分治

分治思想运用到了很多地方，例如线段树等，这一道分治的例题时我们之前学校的一个周考原题，名字叫做摧毁基地，在洛谷上有原题，现在忘记叫什么了，反正就是一道很经典的分治

#include
using namespace std;
long long n, k, a, b, em[100005];
long long solve(long long l, long long r) {
	long long tot;
	long long i = lower_bound(em + 1, em + k + 2, l) - em;
	long long j = upper_bound(em + 1, em + k + 2, r) - em;
	j--;
	if (j < i) {
		return a;
	}
	tot = b * (j - i + 1) * (r - l + 1);
	if (l == r) {
		return tot;
	}
	long long mid = (l + r) >> 1;
	return min((solve(l, mid) + solve(mid + 1, r)), tot);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> k >> a >> b;
	for (int i = 1; i <= k; i++) {
		cin >> em[i];
	}
	sort(em + 1, em + k + 1);
	em[k + 1] = INT_MAX;
	cout << solve(1, 1 << 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

……还有很多复习了的算法，我现在就只列举一些自己已经复习的了算法。

数据结构

数据结构千千万，只不过现在不多了，数据结构就不梳理了，以后会专门整理目前已经学了的数据结构。

做题经历（低级错误）

接下来是一些奇葩的低级错误。

先从周考题说起

First

多米诺骨牌涂色一题中，我把模数少写了个0（悲），经历此事，再也没犯

if(s1[i]==s2[i]){
	if(s1[i-1]==s2[i-1]){
		ans=(ans*2)%1000000007;
	}
}else{
	if(s1[i-1]==s2[i-1]){
		ans=(ans*2)%1000000007;
	}else{
		ans=(ans*3)%1000000007;
	}
	i++;
}
1
2
3
4
5
6
7
8
9
10
11
12

没错，就是少写了个0！！！

Second

在能力测试一题中，我输出，没有输出完。。。。

cout << "Case " << ++p << ": the next three subject joint examination occurs in ";
cout << i << " days." << endl;
1
2

我只写了++p和i，其他的都没写。。。

Third

还有很多低级错误现在没时间汇总，到时候在整理

写在最后

祝自己和大家CSP RP+=INF！！！