算法题整理——一些思维题和杂题

发表于 | 分类于 |

CH0102_64位整数乘法

描述

求a乘b对p取模的值，其中1≤a,b,p≤10^18。

思路

一位一位地做乘法，从b的最高位开始取，如果是1就加a，一位一位地取模可以避免溢出。

解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cstdio>

using namespace std;

long long a, b, p, ret = 0;

int main(){
	scanf("%lld %lld %lld", &a, &b, &p);
	for(unsigned long long i = 0x8000000000000000; i; i /= 2){
		ret <<= 1;
		if(b & i){
			ret += a;
		}
		ret %= p;
	}
	printf("%lld\n", ret);
	return 0;
}

反思和坑

不能分治，因为模数也是1e18的，分治之后恢复数位也相当于一次高位乘法。

POJ1958_Strange Towers of Hanoi

描述

4根柱子的汉诺塔问题，要求输出n=1到12的最小移动次数。

思路

首先使用四柱模式移动k个盘子到B柱。

然后使用三柱模式移动n-k个盘子到D柱。

最后使用四柱模式移动k个盘子到D柱。

多柱汉诺塔问题都可以用类似的思路解决。

解决

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 <cstdio>

using namespace std;

int d[13];
int r[13];

void init(){
	d[0] = 0;
	d[1] = 1;
	for(int i = 2; i <= 12; ++i){
		d[i] = 1 + 2 * d[i - 1];
	}
	r[0] = 0;
}

int solve(int n){
	init();
	if(n == 1) return r[1] = 1;
	int t;
	r[n] = 0x7fffffff;
	for(int i = 0; i < n; ++i){
		t = r[i] * 2 + d[n - i];
		r[n] = r[n] > t ? t : r[n];
	}
	return r[n];
}

int main(){
	for(int i = 1; i <= 12; ++i){
		printf("%d\n", solve(i));
	}
	return 0;
}

CH0301_递归实现指数型枚举

描述

给出一个小于等于16的数n，求出在小于等于n的正整数中，任意地选取某些数字的所有选择方法。按照一定的顺序输出它们。如n=3，则输出：

1
2
3
4
5
6
7
8

3
2
2 3
1
1 3
1 2
1 2 3

思路

题目中是递归实现指数型枚举，实际上，一个集合的幂集中所有的元素可以对应到二进制数中，所以我并没有使用递归，而是直接使用二进制数+译码器的方式做出的。

解决

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
#include <cstdio>

using namespace std;

int n;

int temp[30];

int f(int nxt){
	switch(nxt){
		case 0x1:
			return 1;
		case 0x2:
			return 2;
		case 0x4:
			return 3;
		case 0x8:
			return 4;
		case 0x10:
			return 5;
		case 0x20:
			return 6;
		case 0x40:
			return 7;
		case 0x80:
			return 8;
		case 0x100:
			return 9;
		case 0x200:
			return 10;
		case 0x400:
			return 11;
		case 0x800:
			return 12;
		case 0x1000:
			return 13;
		case 0x2000:
			return 14;
		case 0x4000:
			return 15;
		case 0x8000:
			return 16;
	}
}

int main(){
	scanf("%d", &n);
	printf("\n");
	int total = (1 << n) - 1;
	for(int i = 1; i <= total; ++i){
		int con = 0;
		int ti = i;
		while(ti){
			int nxt = ti & (-ti);
			temp[con++] = n + 1 - f(nxt);
			ti ^= nxt;
		}
		printf("%d", temp[con - 1]);
		for(int j = con - 2; j >= 0; --j){
			printf(" %d", temp[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
#include <cstdio>
#include <vector>

using namespace std;

int n;

void print(vector<int> &v){
	if(!v.empty()){
		vector<int>::iterator i = v.begin();
		printf("%d", *i);
		++i;
		while(i != v.end()){
			printf(" %d", *i);
			++i;
		}
	}
	printf("\n");
}

void cal(vector<int> &v, int num){
	if(num == n){
		print(v);
	}else{
		cal(v, num + 1);
		v.push_back(num + 1);
		cal(v, num + 1);
		v.pop_back();
	}
}

int main(){
	scanf("%d", &n);
	vector<int> v;
	cal(v, 0);
	return 0;
}

CH0303_递归实现排列型枚举

描述

把1~n这n(n<10)个整数排成一行后随机打乱顺序，输出所有可能的次序

解决

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

using namespace std;

int n;

int vis[11];

void print(vector<int> &v){
	printf("%d", v[0]);
	for(int i = 1; i < n; ++i){
		printf(" %d", v[i]);
	}
	printf("\n");
}

void cal(vector<int> &v){
	if(v.size() == n){
		print(v);
		return;
	}
	for(int i = 0; i < n; ++i){
		if(!vis[i]){
			vis[i] = 1;
			v.push_back(i + 1);
			cal(v);
			vis[i] = 0;
			v.pop_back();
		}
	}
}

int main(){
	scanf("%d", &n);
	memset(vis, 0, sizeof(vis));
	vector<int> v;
	cal(v);
	return 0;
}

CH0302_递归实现组合型枚举

描述

从1~n这n个整数中随机选出 m 个，输出所有可能的选择方案。n>0,0<=m<=n,n+(n-m)<=25。

思路

同0301，加一个限定条件即size是3，并且情况数逆序输出就行了。

解决

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 <cstdio>
#include <vector>

using namespace std;

int n, m;

void print(vector<int> &v){
	if(!v.empty()){
		vector<int>::iterator i = v.begin();
		printf("%d", *i);
		++i;
		while(i != v.end()){
			printf(" %d", *i);
			++i;
		}
	}
	printf("\n");
}

void cal(vector<int> &v, int num){
	if(num == n){
		if(v.size() == m) print(v);
	}else{
		v.push_back(num + 1);
		cal(v, num + 1);
		v.pop_back();
		cal(v, num + 1);
	}
}

int main(){
	scanf("%d %d", &n, &m);
	vector<int> v;
	cal(v, 0);
	return 0;
}

CH0201_费解的开关

描述

25盏灯排成一个5x5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。

最终要得到所有灯都打开的状态，求所需要的最小操作数是多少？如果总共操作数大于6，则输出-1。

思路

必须看出这样的事实：

1、任意一个点最多操作一次，这很显然。

2、操作的先后顺序是任意的。

3、如果操作是一行一行地做的，可以发现固定一行之后，剩下的操作只能有一种。假设在第一行的操作都已经执行完毕，且第一行的灯状态是01100，那么显然第二行一定要点击1，4，5三个位置使得第一行的灯全亮。

所以，能改变的只有第一行的操作位置，最多有32种操作方法。

模拟或递归方法来做。

解决

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
#include <cstdio>

using namespace std;

int maze[5][5];

int n;

void print(int t[5][5]){
	for(int i = 0; i < 5; ++i){
		for(int j = 0; j < 5; ++j){
			printf("%d ", t[i][j]);
		}
		printf("\n");
	}
}

int cal(int t[5][5]){
	int ret = 0;
	for(int i = 1; i < 4; ++i){
		for(int j = 0; j < 5; ++j){
			ret += (!t[i - 1][j]);
		}
		if(ret > 6) return 7;
		t[i][0] ^= (t[i - 1][0] ^ t[i - 1][1]);
		for(int j = 1; j < 4; ++j){
			t[i][j] ^= (t[i - 1][j - 1] ^ t[i - 1][j] ^ (!t[i - 1][j + 1]));
		}
		t[i][4] ^= (t[i - 1][3] ^ t[i - 1][4]);
		for(int j = 0; j < 5; ++j){
			t[i + 1][j] ^= (!t[i - 1][j]);
		}
	}
	
	for(int j = 0; j < 5; ++j){
		ret += (!t[3][j]);
	}
	
	if(ret > 6) return 7;
	
	t[4][0] ^= (t[3][0] ^ t[3][1]);
	for(int j = 1; j < 4; ++j){
		t[4][j] ^= (t[3][j - 1] ^ t[3][j] ^ (!t[3][j + 1]));
	}
	t[4][4] ^= (t[3][3] ^ t[3][4]);
	
	for(int j = 0; j < 5; ++j){
		if(t[4][j] == 0){
			return 7;
		}
	}
	
	return ret;
}

int main(){
	scanf("%d", &n);
	while(n--){
		char input[6];
		for(int i = 0; i < 5; ++i){
			scanf("%s", &input);
			for(int j = 0; j < 5; ++j){
				maze[i][j] = input[j] - '0';
			}
		}
		
		int ret = 7;
		
		for(int mask = 0; mask < 32; ++mask){
			int temp[5][5];
			for(int i = 0; i < 5; ++i){
				for(int j = 0; j < 5; ++j){
					temp[i][j] = maze[i][j];
				}
			}
			
			int tm = 0;
			for(int i = 0; i < 5; ++i){
				if(mask & (1 << i)){
					if(i == 0){
						temp[0][0] = !temp[0][0];
						temp[0][1] = !temp[0][1];
					}else if(i == 4){
						temp[0][3] = !temp[0][3];
						temp[0][4] = !temp[0][4];
					}else{
						temp[0][i - 1] = !temp[0][i - 1];
						temp[0][i] = !temp[0][i];
						temp[0][i + 1] = !temp[0][i + 1];
					}
					temp[1][i] = !temp[1][i];
					++tm;
				}
			}
			
			//printf("%d %d\n", mask, tm);
			//print(temp);
			
			tm += cal(temp);
			ret = ret > tm ? tm : ret;	
		}
		
		if(ret <= 6) printf("%d\n", ret);
		else printf("-1\n");
	}
	return 0;
}