算法

高精度算法

高精度+高精度

1、建立两个整型数组、设立初值、设定长度（给定数字的情况下，直接用length，不是给定的话，在if（x）里也会对长度进行自增，直接设定为1也可以）

1
2
3
4
5
6
7
8
9
int a[200],b[200];  
memset(a,0, sizeof(a));
memset(b, 0, sizeof(b));
//给定数字
int lena = num1.length();
int lenb = num2.length();
//多个数字，或者未给定
int lena = 1;
int lenb = 1;

2、输入高精度数（根据题目要求来进行,有时还需要先去除前导零（倒序））

1
2
3
4
//去除前导零
for (int i = 0; i < lena; i++) {
	a[i] = num1[lena-1-i]-'0';
}

3、核心代码，将两者相加（那就是题目要求有多个高精度数相加），或者使用另一个数组c来接收结果,还是看题目要求怎么加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//x为进位
int x = 0;
int len = max(lena, lenb);
for (int i = 0; i < len; i++) {
	c[i] = a[i]+b[i] + x;
	x = c[i] / 10;
	c[i] = c[i] % 10;
}
if (x > 0) {
	c[len] = x;
    //这里的x = x / 10;可以不加，因为如果是加法的话，是不会存在加到最高位时，x超过两位数的情况
    x = x / 10;
	len++;
}

4、去除前导0

1
2
3
4
//lena - 1 > 0是为了在最后一位等于0时，保留这个0
while (c[len - 1] == 0 && len - 1 > 0) {
	len--;
}

5、输出

1
2
3
4
//倒序输出
for (int i = len - 1; i >= 0; i--) {
	cout << c[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
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;

int main() {
	string num1;
	string num2 ;
	int a[200],b[200],c[200];

	cin >> num1 >> num2;
	memset(c, 0, sizeof(c));
	memset(a,0, sizeof(a));
	int lena = num1.length();
	//为什么倒序取该数组 
	//因为num前面会有0出现，这样才能从a[0]开始取各个位置与b相加
	for (int i = 0; i < lena; i++) {
		a[i] = num1[lena-1-i]-'0';
	}

	memset(b, 0, sizeof(b));
	int lenb = num2.length();
	//为什么倒序取该数组 
	//因为num前面会有0出现，这样才能从a[0]开始取各个位置与b相加
	for (int i = 0; i < lenb; i++) {
		b[i] = num2[lenb - 1 - i] - '0';
	}

	int x = 0;

	int len = max(lena, lenb);
    
	//高精度+高精度核心代码
	for (int i = 0; i < len; i++) {
		c[i] = a[i]+b[i] + x;
		x = c[i] / 10;
		c[i] = c[i] % 10;
	}
	//判断最高位
	if (x > 0) {
		c[len] = x;
		len++;
	}
	//去除前导0
	//lena - 1 > 0是为了在最后一位等于0时，保留这个0
	while (c[len - 1] == 0 && len - 1 > 0) {
		len--;
	}
	for (int i = len - 1; i >= 0; i--) {
		cout << c[i];
	}
	return 0;
}

1173：阶乘和（估计考）

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
#include<bits/stdc++.h>
using namespace std;
void chen(int b[], int& lenb, int n) {
	int x = 0;
	for (int i = 0; i < lenb; i++) {
		b[i] = b[i] * n + x;
		x = b[i] / 10;
		b[i] = b[i] % 10;
	}

	while (x != 0) {
		b[lenb] = x % 10;
		x = x / 10;
		lenb++;
	}
}

void jia(int a[], int& lena, int b[], int lenb) {
	lena = max(lena, lenb);
	int x = 0;
	for (int i = 0; i < lena; i++) {
		a[i] = a[i] +b[i] + x;
		x = a[i] / 10;
		a[i] = a[i] % 10;
	}

	if (x) {
		a[lena] = x;
		lena++;
	}
}
int main() {
	int n;
	cin >> n;
	int a[10000];
	memset(a, 0, sizeof(a));

	a[0] = 0;
	int lena = 1;

	int b[10000];
	memset(b, 0, sizeof(b));
	b[0] = 1;
	int lenb = 1;

	for (int i = 1; i <=n; i++) {
		chen(b, lenb, i);
		jia(a, lena, b,lenb);
	}
	

	while (a[lena - 1] == 0 && lena - 1 > 0) {
		lena--;
	}
	for (int i = lena - 1; i >= 0; i--) {
		cout << a[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
#include<bits/stdc++.h>
using namespace std;

int main() {
	string num = "00000000000011111111112321321312312312321";
	int b = 1234;
	int a[100];

	memset(a,0, sizeof(a));
	int lena = num.length();
	//为什么倒序取该数组 
	//因为num前面会有0出现，这样才能从a[0]开始取各个位置与b相加
	for (int i = 0; i < lena; i++) {
		a[i] = num[lena-1-i]-'0';
	}

	int x = 0;
	a[0] = a[0] + b;

	//做进位，以及把各个位置相加，流程结束会得到num与b相加的结果，只对低精度部分进行变化
	//更高位，直接逆序输出即可
	for (int i = 0; i < lena; i++) {
		a[i] = a[i] + x;
		x = a[i] / 10;
		a[i] = a[i] % 10;
	}
	//为了意外的情况，高精度的位数没有低精度的位数高，比如1（高精度）+10000（低精度）
	while (x != 0) {
		a[lena] = x % 10;
		x = x / 10;
		lena++;
	}
	//去除前导0
	//lena - 1 > 0是为了在最后一位等于0时，保留这个0
	while (a[lena - 1] == 0 && lena - 1 > 0) {
		lena--;
	}
	for (int i = lena - 1; i >= 0; i--) {
		cout << a[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
#include<bits/stdc++.h>
using namespace std;

int main() {
	string num1 = "11111111111111111111111112";
	int num2 = 112;
	int a[200], b[200], c[200];
 

	memset(a, 0, sizeof(a));
	int lena = num1.length();
	//倒序取得数组a
	for (int i = 0; i < lena; i++) {
		a[i] = num1[lena - 1 - i] - '0';
	}

	//第一位减去低精度数后，后续的位数就只需要减去所借的x
	int x = 0;
	a[0] = a[0] - num2 - x;


	////以下是高精度-低精度数乘法的核心代码
	for (int i = 0; i < lena; i++) {
		//该位数减去所借的x
		a[i] = a[i] - x;
		//上面已经把所借的x减去，所以x要归零
		x = 0;
		//借位，如果不够减，就需要多借一位
		while (a[i] < 0) {
			x++;
			//该位得到所借得的10
			a[i] = a[i] + 10;
		}
	}



	//去除前导0
	//lena - 1 > 0是为了在最后一位等于0时，保留这个0
	while (a[lena - 1] == 0 && lena - 1 > 0) {
		lena--;
	}
	for (int i = lena - 1; i >= 0; i--) {
		cout << a[i];
	}
	return 0;
}

高精度-高精度

1、建立两个整型数组、设立初值、设定长度（给定数字的情况下，直接用length，不是给定的话，在if（x）里也会对长度进行自增，直接设定为1也可以）

1
2
3
4
5
6
7
8
9
int a[200],b[200];  
memset(a,0, sizeof(a));
memset(b, 0, sizeof(b));
//给定数字
int lena = num1.length();
int lenb = num2.length();
//多个数字，或者未给定
int lena = 1;
int lenb = 1;

2、输入高精度数（根据题目要求来进行,有时还需要先去除前导零（倒序））

1
2
3
4
//去除前导零
for (int i = 0; i < lena; i++) {
	a[i] = num1[lena-1-i]-'0';
}

3、核心代码，将两者相加（那就是题目要求有多个高精度数相加），或者使用另一个数组c来接收结果,还是看题目要求怎么加

1
2
3
4
5
6
7
8
9
10
11
12
13
//x为进位
int x = 0;
int len = max(lena, lenb);
//当第一次减去的值为负数时，则需要减去进位，比如第二位要还第一位的向它借的1
for (int i = 0; i < len; i++) {
	c[i] = a[i] - b[i] - x;
	x = 0;
	//以下借位的步骤，每次循环如果a[i]还是小于0，则需要继续往前一位借1
	while (c[i] < 0) {
		x++;
		c[i] = c[i] + 10;
	}
}

4、去除前导0

1
2
3
4
//lena - 1 > 0是为了在最后一位等于0时，保留这个0
while (c[len - 1] == 0 && len - 1 > 0) {
	len--;
}

5、输出

1
2
3
4
//倒序输出
for (int i = len - 1; i >= 0; i--) {
	cout << c[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
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;

int main() {
	string num1;
	string num2;
	int a[200], b[200], c[201];

	cin >> num1 >> num2;

	memset(a, 0, sizeof(a));
	memset(b, 0, sizeof(b));
	memset(c, 0, sizeof(c));

	int lena = num1.length();
	//倒序取得数组a
	for (int i = 0; i < lena; i++) {
		a[i] = num1[lena - 1 - i] - '0';
	}

	//倒序取得数组b
	int lenb = num2.length();
	for (int i = 0; i < lenb; i++) {
		b[i] = num2[lenb - 1 - i] - '0';
	}

	//先取得第一次所减去的值
	//a[0]=2,减去num2之后就是-1，要进行借位
	int x = 0;
	//len=等于lena与lenb之主的最大值
	int len = max(lena, lenb);
	//当第一次减去的值为负数时，则需要减去进位，比如第二位要还第一位的向它借的1
	for (int i = 0; i < len; i++) {
		c[i] = a[i] - b[i] - x;
		x = 0;
		//以下借位的步骤，每次循环如果a[i]还是小于0，则需要继续往前一位借1
		while (c[i] < 0) {
			x++;
			c[i] = c[i] + 10;
		}
	}

	//去除前导0
	//lena - 1 > 0是为了在最后一位等于0时，保留这个0
	while (c[len - 1] == 0 && len - 1 > 0) {
		len--;
	}
	//倒序输出
	for (int i = len - 1; i >= 0; i--) {
		cout << c[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
#include<bits/stdc++.h>
using namespace std;

int main() {
	string num = "00000000000011111111112321321312312312321";
	int b = 100;
	int a[100];

	memset(a, 0, sizeof(a));
	int lena = num.length();
	//倒序取数组a
	for (int i = 0; i < lena; i++) {
		a[i] = num[lena - 1 - i] - '0';
	}

	int x = 0;

	//以下是高精度*低精度数乘法的核心代码
	for (int i = 0; i < lena; i++) {
		a[i] = a[i] * b + x;
		x = a[i] / 10;
		a[i] = a[i] % 10;
	}
	//一定要用while，因为可能a[i]的位数大于一位，比如200，那就得一直进位
	while (x != 0) {
		a[lena] = x % 10;
		x = x / 10;
		lena++;
	}
	//去除前导0
	//lena - 1 > 0是为了在最后一位等于0时，保留这个0
	while (a[lena - 1] == 0 && lena - 1 > 0) {
		lena--;
	}
	for (int i = lena - 1; i >= 0; i--) {
		cout << a[i];
	}
	return 0;
}

1170：计算2的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
#include<bits/stdc++.h>
using namespace std;

int main() {
	string num = "1";
	int b;
	int a[100];

	cin >> b;
	memset(a, 0, sizeof(a));
	int lena = num.length();
	//倒序取数组a
	for (int i = 0; i < lena; i++) {
		a[i] = num[lena - 1 - i] - '0';
	}

	int x = 0;
	for (int s = 0; s < b; s++) {
		//以下是高精度*低精度数乘法的核心代码
		for (int i = 0; i < lena; i++) {
			a[i] = a[i] * 2 + x;
			x = a[i] / 10;
			a[i] = a[i] % 10;
		}
		//一定要用while，因为可能a[i]的位数大于一位，比如200，那就得一直进位
		while (x != 0) {
			a[lena] = x % 10;
			x = x / 10;
			lena++;
		}
	}
	
	//去除前导0
	//lena - 1 > 0是为了在最后一位等于0时，保留这个0
	while (a[lena - 1] == 0 && lena - 1 > 0) {
		lena--;
	}
	for (int i = lena - 1; i >= 0; i--) {
		cout << a[i];
	}
	return 0;
}

求10000以内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
#include<bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    // 初始化数组,数组要开的足够大
    int num[100000] = { 0 };
    num[0] = 1;
    int len = 1; // len 表示当前数组中存储的数的位数

    // 计算阶乘
    for (int i = 2; i <= n; i++) {
        int carry = 0; // 进位标志
        for (int j = 0; j < len; j++) {
            int temp = num[j] * i + carry; // 当前位乘以i并加上进位
            num[j] = temp % 10; // 更新当前位的值
            carry = temp / 10; // 计算进位
        }
        // 处理剩余进位，进位没有处理完，就继续处理+1
        while (carry) {
            //此处增加了num的长度len
            num[len++] = carry % 10;
            carry /= 10;
        }
    }

    // 从高位向低位输出数组
    for (int i = len - 1; i >= 0; i--) {
        cout << num[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;

int main() {
	string num1;
	string num2;
	int a[100], b[100], c[400];

	cin >> num1 >> num2;
	memset(c, 0, sizeof(c));
	memset(a, 0, sizeof(a));
	int lena = num1.length();
	//倒序取数组a
	for (int i = 0; i < lena; i++) {
		a[i] = num1[lena - 1 - i] - '0';
	}

	memset(b, 0, sizeof(b));
	int lenb = num2.length();
//倒序取数组b
	for (int i = 0; i < lenb; i++) {
		b[i] = num2[lenb - 1 - i] - '0';
	}



	int len = lena + lenb;
	//以下是高精度*高精度数乘法的核心代码
	for (int i = 0; i < lena; i++) {
		//每一趟，x都要清零
		int x = 0;
		for (int j = 0; j < lenb; j++) {
			//每一个得到的数都来自于多趟数字相加
			c[i + j] = c[i + j] + a[i] * b[j] + x;
			//x为下一个数字的进位
			x = c[i + j] / 10;
			//此处的c[i + j]为该位的输出
			c[i + j] = c[i + j] % 10;
		}
		//第i趟结束时，进位存在本趟的最高位
		c[i + lenb] = x;
	}

	//去除前导0
	//lena - 1 > 0是为了在最后一位等于0时，保留这个0
	while (c[len - 1] == 0 && len - 1 > 0) {
		len--;
	}
	for (int i = len - 1; i >= 0; i--) {
		cout << c[i];
	}
	return 0;
}

高精度/单精度

1、建立两个整型数组、设立初值、设定长度（给定数字的情况下，直接用length，不是给定的话，在if（x）里也会对长度进行自增，直接设定为1也可以）

1
2
3
4
5
6
7
8
9
int a[200],b[200];  
memset(a,0, sizeof(a));
memset(b, 0, sizeof(b));
//给定数字
int lena = num1.length();
int lenb = num2.length();
//多个数字，或者未给定
int lena = 1;
int lenb = 1;

2、输入高精度数（根据题目要求来进行,有时还需要先去除前导零（倒序））

1
2
3
4
//除法的高精度是唯一不需要倒序取的算法
for (int i = 0; i < lena; i++) {
	a[i] = num[i] - '0';
}

3、核心代码，将两者相加（那就是题目要求有多个高精度数相加），或者使用另一个数组c来接收结果,还是看题目要求怎么加

1
2
3
4
5
6
7
8
9
10
int x = 0, t = 0;
int flag = 0;

//t为新的被除数，c[i]为商的每一位，x为余数
//比如我们130除以13，第一次循环a[0]为0*10+1=1，c[0]=1/13=0,x=1%13=0
for (int i = 0; i < len; i++) {
	t = x * 10 + a[i];
	c[i] = t / b;
	x = t % b;
}

4、去除前导0+输出

1
2
3
4
5
6
7
8
//下面的代码作用为将前导0删除
for (int i = 0; i < len; i++) {
	//首先使用一个for循环遍历结果数组c，如果当前位不为0或者之前已经输出过一位数字（flag为1），则输出该位数字，并将flag设置为1，表示最高位已经输出。
	if (c[i] != 0 || flag == 1) {
		cout << c[i];
		flag = 1;
	}
}
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;

int main() {
	string num ;
	int b = 13;
	int a[100],c[100];

	cin >> num;
	memset(a, 0, sizeof(a));
	int lena = num.length();
	//除法的高精度是唯一不需要倒序取的算法
	for (int i = 0; i < lena; i++) {
		a[i] = num[i] - '0';
	}
	memset(c, 0, sizeof(c));
	int len = lena;

	int x = 0, t = 0;
	int flag = 0;

	//t为新的被除数，c[i]为商的每一位，x为余数
    //比如我们130除以13，第一次循环a[0]为0*10+1=1，c[0]=1/13=0,x=1%13=0
	for (int i = 0; i < len; i++) {
		t = x * 10 + a[i];
		c[i] = t / b;
		x = t % b;
	}


	//下面的代码作用为将前导0删除
	for (int i = 0; i < len; i++) {
		//首先使用一个for循环遍历结果数组c，如果当前位不为0或者之前已经输出过一位数字（flag为1），则输出该位数字，并将flag设置为1，表示最高位已经输出。
		if (c[i] != 0 || flag == 1) {
			cout << c[i];
			flag = 1;
		}
		
	}
	cout << endl;
	//最后需要判断flag的值，如果为0，说明结果为0，需要输出一个0。否则就已经将结果输出完毕了，直接结束程序即可。
	if (flag == 0) {
		cout << 0;
		cout << endl;
	}
	cout << x;
	return 0;
}

1171：大整数的因子(估计考，可能性最大)

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
#include<bits/stdc++.h>
using namespace std;

int main() {
	string a;
	int c[31],len,t,x,flag;
	flag = 0;
	cin >> a;
	len = a.size();
	memset(c, 0, sizeof(c));
	for (int i = 0; i < len; i++) {
		c[i] = a[i] - '0';
	}

	for (int s = 2; s <= 9; s++) {
		x = 0;
		for (int i = 0; i < len; i++) {
		
			t = x * 10 + c[i];
			x = t % s;
		
		}
		if (x == 0) {
			cout << s << " ";
			flag = 1;
		}
	}
	if (flag == 0) {
		cout << "none";
	}
	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
#include<bits/stdc++.h>
using namespace std;

//如果余数d比除数b大，则返回true
bool big(int d[], int lend, int b[], int lenb) {
    
    //下面是lenb、lend相等的情况
    for (int i = lend - 1; i >= 0; i--) {
        ////这里的条件很关键，d[lend - 1]!=0这个条件如果不加，就会出现d数组取值={0,0}，但是lend为2大于lenb为1，返回了ture，而不断减去b，导致错误（QAQ这个条件卡了三个半小时）
		if (lend > lenb&&d[lend - 1]!=0) return true;
		if (lend < lenb) return false;
        if (d[i] > b[i]) { 
            return true;
        }
        else if (d[i] < b[i]) {
            return false;
        }
        //重复循环
        else {
            continue;
        }
    }
    //每一位相等的情况下，则返回false
    return true;
}

//将余数d-除数b，执行减法后，d的长度将改变，必须通过引用(&)传递出来
void jianfa(int d[], int& lend, int b[]) {
    //x是借位，初始第0位是没有借位的
    int x = 0;
	//这里是正序的因为减法从原本数字的最低位开始，而数组是逆序存放数字的
    for (int i = 0; i < lend; i++) {
        d[i] = d[i] - b[i] - x;
        if (d[i] < 0) {
            d[i] += 10;
            x = 1;
        }
        else {
            x = 0;
        }
		
    }
    //修改余数d的长度
    while (d[lend - 1] == 0 && lend - 1 > 0) {
        lend--;
    }
}


int main() {
	string num1;
	string num2;
	//a数组是被除数，b数组是除数，c数组是商，d数组是余数
	int a[300], b[300], c[300],d[300];

	cin >> num1 >> num2;
	int lena = num1.length();
	int lenb = num2.length();
	memset(a, 0, sizeof(a));
	memset(b, 0, sizeof(b));
	memset(c, 0, sizeof(c));
	memset(d, 0, sizeof(d));
	
	//倒序取数组a
	for (int i = 0; i < lena; i++) {
		a[i] = num1[lena - 1 - i] - '0';
	}
	//倒序取数组b
	for (int i = 0; i < lenb; i++) {
		b[i] = num2[lenb - 1 - i] - '0';
	}

	//余数长度为0
	int lend = 0;
	//从被除数的最高位开始
	for (int i = lena - 1; i >= 0; i--) {
		//1.将余数全部位数向右移动一位,因为一次循环后，相当于有一位已经完成了除法，所以有余数的话，向后退一位，而先前的那一位，后面会塞下新的a[i]，相当于把余数放大10倍（等同于高精度除单精度中的x*10步骤）
		for (int j = lend - 1; j >= 0; j--) {
			d[j + 1] = d[j];
		}
		//2.获得余数的新第0位
		d[0] = a[i];
		//3.余数的位数多加一位，因为上面最前面多加了一位
		lend++;
		//4.将余数d和除数b相减，每减一次，则第i位商+1
		while (big(d, lend, b, lenb)) {
			jianfa(d, lend, b);
			c[i]++;
		}
	}
	//商c的长度不超过被除数a的长度
	int lenc = lena;
	//去除前导0
	while (c[lenc - 1] == 0 && lenc - 1 > 0) {
		lenc--;
	}
	while (d[lend - 1] == 0 && lend - 1 > 0) {
		lend--;
	}
	for (int i = lenc - 1; i >= 0; i--) {
		cout << c[i];
	}
	cout << endl;
	for (int i = lend - 1; i >= 0; i--) {
		cout << d[i];
	}

	return 0;
}

排序

冒泡排序

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//冒泡算法
void bubble_sort(int a[], int n) {
    for (int i = 0; i < n; i++) {
        int flag = false;
        //j从0开始，但是要小于n-i-1，是因为无序区元素个数为n-i，而一共要比较n-i-1次
        for (int j = 0; j < n - i - 1; j++) {
            //此处为小于，所以为递增
            if (a[j] < a[j + 1]) {
                swap(a[j], a[j + 1]);  
                flag = true;
            }
        }
        //全程无交换，则说明本来就是有序的，不需要浪费时间进行循环，直接跳出循环
        if (!flag) {
            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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;

void print(int a[], int n) {
    for (int i = 0; i < n; i++) {
        cout << a[i]<<" ";
    }
}

//冒泡算法
void bubble_sort(int a[], int n) {
    for (int i = 0; i < n; i++) {
        int flag = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (a[j] < a[j + 1]) {
                swap(a[j], a[j + 1]);  
                flag = true;
            }
        }
        //全程无交换，则说明本来就是有序的，不需要浪费时间进行循环，直接跳出循环
        if (!flag) {
            break;
        }
    }
}

int main() {
    int a[10] ;
    int n=10;

    for (int i = 0; i < n; i++) {
        cin >>  a[i];
    }

    bubble_sort(a,n);

    print(a,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
#include<bits/stdc++.h>
using namespace std;

void print(int a[], int n) {
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
}

void bubble_sort(int a[], int n) {
    for (int i = 0; i < n; i++) {
        int flag = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (a[j] < a[j + 1]) {
                swap(a[j], a[j + 1]);
                flag = true;
            }
        }
        //全程无交换，跳出循环
        if (!flag) {
            break;
        }
    }
}
void bubble_sort2(int a[], int n) {
    for (int i = 0; i < n; i++) {
        int flag = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                flag = true;
            }
        }
        //全程无交换，跳出循环
        if (!flag) {
            break;
        }
    }
}

int main() {
    int a[10], b[10], c[10], cnt = 0, cntc = 0;
    int n = 10;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        if (a[i] % 2 == 1) {
            b[cnt++] = a[i];
        }
        else {
            c[cntc++] = a[i];
        }
    }

    bubble_sort(b, cnt);
    bubble_sort2(c, cntc);



    print(b, cnt);
    print(c, cntc);
    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
#include<bits/stdc++.h>
using namespace std;

void print(int a[], int n) {
    //为了题目格式要求，对输出函数做一点改变
    cout << a[0];
    for (int i = 1; i < n; i++) {
        cout << "," << a[i];
    }
}

void bubble_sort(int a[], int n) {
    for (int i = 0; i < n; i++) {
        int flag = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                flag = true;
            }
        }
        //全程无交换，跳出循环
        if (!flag) {
            break;
        }
    }
}

int main() {
    int a[500], b[500], cnt = 0;
    int n;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        if (a[i] % 2 == 1) {
            b[cnt++] = a[i];
        }
    }

    bubble_sort(b, cnt);



    print(b, cnt);
    return 0;
}

插入排序

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void insertsort(int a[], int n) {
    //注意这个循环范围，因为第一个无序区的元素下标为1，而最后一个下标为n-1
    for (int i = 1; i < n; i++) {
        int j = i - 1;
        //t为需要排序的数组a的元素
        int t = a[i];
        //t找位置的过程，在过程中数组t前面的元素位置往后撤
        //此处大于，所以为递增
        while (j >= 0 && a[j] > t) {
            a[j + 1] = a[j];
            j--;
        }
        //t通过不断前移找到正确的位置
        //而a[j+1]要么是第一个位置，j=-1时,a[j+1]=a[0]
        //要么此时a[j]<t了，排序就已经按照递增来排序了
        a[j + 1] = t;
    }
}
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;

void print(int a[], int n) {
    for (int i = 0; i < n; i++) {
        cout <<  a[i]<<" ";
    }
}

void insertsort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int j = i - 1;
        //t为需要排序的数组a的元素
        int t = a[i];
        //t找位置的过程，在过程中数组t前面的元素位置往后撤
        while (j >= 0 && a[j] > t) {
            a[j + 1] = a[j];
            j--;
        }
        //t找到正确的位置
        a[j + 1] = t;
    }
}

int main() {
    int a[500], b[500], cnt = 0;
    int n;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    insertsort(a, n);

    print(a, 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
#include <bits/stdc++.h>
using namespace std;

const int Max = 1e6 + 4;
int a[Max] = {}; // 存储输入序列的数组
int b[Max]; // 存储归并排序过程中的临时数组
long long num = 0; // 用于存储逆序对的数量

// 归并排序中的归并操作，将两个已排序的数组合并成一个有序的数组
void merge(int l, int mid, int r) {
    int i = l; // 左半部分数组的下标
    int j = mid + 1; // 右半部分数组的下标
    int k = l; // 临时数组的下标
    while (i <= mid && j <= r) { // 比较左右两部分数组中的元素，合并为一个有序的数组
        if (a[i] > a[j]) { // 如果左边元素大于右边元素，说明存在逆序对
            b[k++] = a[j++]; // 将右边元素存储在临时数组中
            num += mid - i + 1; // 统计逆序对数量，注意这里的统计方式
        }
        else { // 如果左边元素小于等于右边元素，不需要统计逆序对
            b[k++] = a[i++]; // 将左边元素存储在临时数组中
        }
    }

    while (i <= mid) { // 如果左半部分数组有剩余元素，将其存储在临时数组中
        b[k++] = a[i++];
    }
    while (j <= r) { // 如果右半部分数组有剩余元素，将其存储在临时数组中
        b[k++] = a[j++];
    }
    for (i = l; i <= r; i++) { // 将归并排序过程中得到的有序数组覆盖原始数组
        a[i] = b[i];
    }
}

// 归并排序，对序列进行排序
void mergeSort(int l, int r) {
    int mid;
    if (l < r) { // 递归终止条件，当左右下标相等时表示已经排好序
        mid = l + ((r - l) /2); // 计算中间位置，避免溢出
        mergeSort(l, mid); // 对左半部分数组进行归并排序
        mergeSort(mid + 1, r); // 对右半部分数组进行归并排序
        merge(l, mid, r); // 归并操作
    }
}

int main() {
    int n;
    cin >> n; // 输入序列长度
    int i;
    for (i = 0; i < n; i++) { // 输入序列
        cin >> a[i];
    }

    mergeSort(0, n - 1); // 对序列进行归并排序

    cout << num ; // 输出逆序对数量

    return 0;
}

快速排序+结构体(考)

1176：谁考了第k名

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;

struct student {
    int id;
    float score;
}s[100];

//按照分数由小到大排序
bool cmp(student a,student b) {
    //如果前面学生的分数大于后面学生的分数，则不交换
    if (a.score > b.score) {
        return true;
    }
    else {
        return false;
    }
}
//也可以这么写，理解为前面的始终大于后面的
bool cmp(Student a, Student b) {
	return a.grade > b.grade;
}

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> s[i].id >> s[i].score;
    }
    sort(s,s+n,cmp);

    cout << s[k-1].id << " " << s[k-1].score;
    return 0;
}

1178：成绩排序

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;

struct student {
    string name;
    float score;
}s[100];

//按照分数由小到大排序
bool cmp(student a,student b) {
    //如果前面学生的分数大于后面学生的分数，则是正确的排序方法（true），则不交换
    if (a.score > b.score) {
        return true;
    }
    //如果前面学生的分数等于后面学生的分数，则比较名字的大小
    else if(a.score == b.score) {
        if (a.name < b.name) {
            return true;
        }
        else {
            return false;
        }
    }
    else if (a.score < b.score) {
        return false;
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s[i].name >> s[i].score;
    }
    sort(s,s+n,cmp);
    for (int i = 0; i < n; i++) {
        cout << s[i].name << " " << s[i].score << endl;
    }
    
    return 0;
}

1182：合影效果

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
//1、cmp结构体的优化写法：直接返回：return a.height < b.height;
//2、string类型的字符可以直接通过：a.gender == "male"进行比较
//3、流操作符 fixed，它表示浮点输出应该以固定点或小数点表示法显示，当它与 setprecision 操作符一起使用时，它将指定浮点数字的小数点后要显示的位数：cout<<fixed << setprecision(2)
#include<bits/stdc++.h>
using namespace std;

// 定义一个结构体表示每个人的信息
struct Person {
    string gender; // 性别
    double height; // 身高
}people[40];

// 排序规则：男生从矮到高，女生从高到矮
// 这里的a和b就比较像左边和右边的关系了，实际上a和b根据题目还可以引申为先后之类的关系
bool cmp(const Person& a, const Person& b) {
    if (a.gender == "male" && b.gender == "male") {
        return a.height < b.height;
    }
    else if (a.gender == "female" && b.gender == "female") {
        return a.height > b.height;
    }
    else if (a.gender == "male" && b.gender == "female") {
        return true; // 男生在左边，女生在右边
    }
    else {
        return false;
    }
}

int main() {
    int n;
    cin >> n;

    // 定义一个数组存储每个人的信息
    for (int i = 0; i < n; i++) {
        cin >> people[i].gender >> people[i].height;
    }

    // 排序
    sort(people, people + n, cmp);

    // 输出每个人的身高
    for (int i = 0; i < n; i++) {
        cout << fixed << setprecision(2) << people[i].height << " ";
    }

    return 0;
}

1183：病人排队

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
//1、如果在cmp函数中没有覆盖所有的情况，就会导致报错：无效的比较器
//2、可以用过order变量记录前后顺序，避免了用string类型的id来进行前后顺序比较
#include<bits/stdc++.h>
using namespace std;

// 定义一个结构体表示每个人的信息
struct Person {
    string id;
    int age;
    int order; // 记录每个人的登记顺序，这个变量是因为id为string类型，可能存在英文，不能用id大小来比较前后顺序
}people[100];

// 排序规则：
// 1、老年人（年龄 >= 60岁）比非老年人优先看病。
// 2、老年人按年龄从大到小的顺序看病，年龄相同的按登记的先后顺序排序。
// 3、非老年人按登记的先后顺序看病。
bool cmp(const Person& a, const Person& b) {
    //1、
    if (a.age >= 60 && b.age < 60) {
        return true;
    }
    else if (a.age < 60 && b.age >= 60) {
        return false;
    }
    //2、
    else if (a.age >= 60 && b.age >= 60) {
        if (a.age == b.age) {
            return a.order < b.order;
        }
        else {
            return a.age > b.age;
        }
    }
    //3、
    else {
        return a.order < b.order;
    }
}

int main() {
    int n;
    cin >> n;

    // 定义一个数组存储每个人的信息
    for (int i = 0; i < n; i++) {
        cin >> people[i].id >> people[i].age;
        people[i].order = i;
    }

    // 排序
    sort(people, people + n, cmp);

    // 输出每个人的ID
    for (int i = 0; i < n; i++) {
        cout << people[i].id << 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>
#include <algorithm>
using namespace std;
struct node//建立结构体
{
    int name, mark;//name为编号、mark为成绩
}pp[5005];
bool cmp(node a, node b)//建立结构体a和b;
{
    if (a.mark == b.mark)//如果成绩相同
    {
        return a.name < b.name;//编号小的靠前
    }
    else
    {
        return a.mark > b.mark;//否则成绩高的靠前
    }
}
int main()
{
    int n, m, need, sum = 0;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> pp[i].name >> pp[i].mark;//输入编号和成绩
    }
    sort(pp, pp + n, cmp);
    need = m * 1.5;
    for (int i = 0; pp[need - 1].mark <= pp[i].mark; i++)
    {
        sum++;
    }
    cout << pp[need - 1].mark << " " << sum << "\n";
    for (int i = 0; i < sum; i++)
    {
        cout << pp[i].name << " " << pp[i].mark << "\n";
    }
    return 0;
}

递推

做递推的关键在于找到递推式

1190：上台阶

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
//1、使用大数组来进行递推（推荐递推变量）
//2、输入时碰到0则停止：while (cin >> n && n != 0)
#include<bits/stdc++.h>
using namespace std;

long long a[72];

long long zlt(int n) {
    //走第0级有1种方法
    a[0] = 1;
    //走第1级有1种方法
    a[1] = a[0];
    //走第2级有2种方法
    a[2] = a[1]+a[0];
    //走第3级有4种方法
    a[3] = a[2]+a[1]+a[0];
    for (int i = 4; i <= n; i++) {
        a[i] = a[i - 1] + a[i - 2] + a[i - 3];
    }
    return a[n];
}

int main() {
    int n;
    //输入到0停止
    while (cin >> n && n != 0) {
        long long res = zlt(n);
        cout << res << endl;
    }

    return 0;
}

1661: 递推求斐波那契数列（高精度，感觉不可能结合考）

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
//1、数组作为递推变量的使用方法
//2、将一个数组赋值给另一个数组的方法，用于：memcpy(a, b, sizeof(b))
//3、复习一遍高精度加高精度
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 10010;  // 数组的大小

int a[MAXN], b[MAXN], c[MAXN];  // 数组，用于存储斐波那契数列中的三个数

// 加法函数，将数组 a 和 b 相加，结果存储在数组 c 中
void add(int a[], int b[], int c[]) {
    int carry = 0;  // 进位
    for (int i = 0; i < MAXN; i++) {
        c[i] = a[i] + b[i] + carry;  // 计算 c[i]，等于 a[i] + b[i] + 进位
        carry = c[i] / 10;  // 计算进位，即 c[i] 除以 10 的商
        c[i] %= 10;  // 取个位数，即 c[i] 除以 10 的余数
    }
}

// 计算斐波那契数列的第 n 项
void fbnq(int n) {
    // 初始化，将数组 a 和 b 的所有元素都赋值为 0，数组 c 的第一个元素赋值为 1
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    memset(c, 0, sizeof(c));
    a[0] = b[0] = 1;

    // 从第三项开始计算，依次计算出第 3 到第 n 项
    for (int i = 3; i <= n; i++) {
        add(a, b, c);  // 计算下一个数，将 a 和 b 相加，结果存储在数组 c 中
        memcpy(a, b, sizeof(b));  // 用 b 更新 a，将数组 b 的所有元素复制到数组 a 中
        memcpy(b, c, sizeof(c));  // 用 c 更新 b，将数组 c 的所有元素复制到数组 b 中
    }

    // 输出结果，逆序输出数组 c 中的元素，即为斐波那契数列的第 n 项
    int pos = MAXN - 1;  // pos 初始值为数组的最后一个元素的下标
    while (pos > 0 && c[pos] == 0) pos--;  // 找到最高位，即从后往前第一个非零元素的下标
    for (int i = pos; i >= 0; i--) {
        cout << c[i];  // 逆序输出数组 c 中的元素
    }
    cout << endl;
}

int main() {
    int n;
    cin >> n;
    fbnq(n);
    return 0;
}

1196：踩方格

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
//这种走方位的题目，当然也可以用递归或者深搜来做

//找规律做法：
#include<iostream>

using namespace std;

int main()
{
    int a[21];
    int n;
    cin >> n;
    a[1] = 3;
    a[2] = 7;
    for (int i = 3; i <= n; i++)
    {
        //找规律
        a[i] = 2 * a[i - 1] + a[i - 2];
    }
    cout << a[n] << endl;
    return 0;
}

//正常递推做法：
#include<iostream>

using namespace std;

int f[21];
int l[21], r[21], u[21];

int main()
{
    
    int n;
    cin >> n;
    l[1] = 1;
    r[1] = 1;
    u[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        //最后一步向左走的走法
        l[i] = l[i - 1] + u[i - 1];
        //最后一步向右的走法
        r[i] = r[i - 1] + u[i - 1];
        //最后一步向上走的走法
        u[i] = l[i - 1] + u[i - 1]+r[i - 1];
        //总的走法
        f[i] = l[i ] + u[i]+ r[i];
    }
    cout << f[n];
    return 0;
}

1314：过河卒（模拟考过）

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
//1、先找到递推式（dp[i][j]=dp[i-1][j]+dp[i][j-1]），再找到递推式的多种初始值（边界初始化），最后再找需要排除的条件（马的控制点）
#include<bits/stdc++.h>
using namespace std;
long long dp[21][21]={0},g[21][21]={0};
int main()
{
	int n,m,x,y,i,j;
	cin >> n >> m >> x >> y;
	dp[0][0]=1;//初始化出发点 
	g[x][y]=1;//标注卒
	//判断卒可走的点是否越界 并标注不能走的马的控制点
	if(x-2>=0&&y-1>=0)g[x-2][y-1]=1; 
	if(x-1>=0&&y-2>=0)g[x-1][y-2]=1; 
	if(x+1<=n&&y-2>=0)g[x+1][y-2]=1; 
	if(x+2<=n&&y-1>=0)g[x+2][y-1]=1; 
	if(x+2<=n&&y+1<=m)g[x+2][y+1]=1; 
	if(x+1<=n&&y+2<=m)g[x+1][y+2]=1; 
	if(x-1>=0&&y+2<=m)g[x-1][y+2]=1; 
	if(x-2>=0&&y+1<=m)g[x-2][y+1]=1; 
	//初始化边界，按照边界走就只有一种走法，所以初始化为1
	for(i=1;i<=n;i++)
		if(g[i][0]==0) dp[i][0]=dp[i-1][0];
	for(i=1;i<=m;i++)
		if(g[0][i]==0) dp[0][i]=dp[0][i-1];
	//递推公式
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++){
			if(g[i][j]==1)dp[i][j]=0;
			if(g[i][j]==0)dp[i][j]=dp[i-1][j]+dp[i][j-1];
		}	
	cout << dp[n][m];
	return 0;
}



//老师的方法，但是疑惑的是我必须用!in(c)才能正确，但是老师是in(c)正确，不过就逻辑上来讲也应该是in(c)，但是找不到我不同的原因
#include<bits/stdc++.h>
using namespace std;
long long dp[100][100];

bool b[100][100]={false};

int n, m;
struct point
{
	int x;
	int y;
};

//从马点前进的距离方位
int dir[8][2] = { {2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1} };

bool in(point p) {
	if (p.x >= 0 && p.x <= n && p.y >= 0 && p.y <= m) {
		return true;
	}
	else {
		return false;
	}
}

void horse(point c) {
	if (!in(c)) {
		b[c.x][c.y] = true;
	}

	for (int i = 0; i < 8; i++) {
		point t;
		t.x = c.x + dir[i][0];
		t.y = c.y + dir[i][1];
		if (!in(t)) {
			b[t.x][t.y] = true;
		}
	}
}

int main()
{
	int n, m, x, y;
	point p;
	cin >> n >> m >> p.x >> p.y;

	horse(p);

	dp[0][0] = 1;//初始化出发点 

	//初始化边界，按照边界走就只有一种走法，所以初始化为1
	for (int i = 1; i <= n; i++) {
		if (!b[i][0]) {
			dp[i][0] = dp[i - 1][0];
		}
		else {
			dp[i][0] = 0;
		}
	}

	for (int j = 1; j <= m; j++) {
		if (!b[0][j]) {
			dp[0][j] = dp[0][j - 1];
		}
		else {
			dp[0][j] = 0;
		}
	}

	//递推公式
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (!b[i][j]) {
                //到达位置 (i, j) 的方案数量等于到达其上方位置 (i - 1, j) 的方案数量与到达其左方位置 (i, j - 1) 的方案数量之和。
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
			}
			else {
				dp[i][j] = 0;
			}
		}
	}

	cout << dp[n][m];

	return 0;
}

1194：移动路线(考过)

上面过河卒题目的没有条件的简单版本

注意这个循环的起始点，我一开始做的时候没有考虑我决定以dp1,1为起点，导致双重循环起点都写为了1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int m, n,dp[21][21];
    memset(dp, 0, sizeof(dp));
    //起点的初始条件别忘了
    dp[1][1] = 1;
    cin >> m >> n;
    for (int i = 1; i <= n;i++) {
        dp[i][1] = 1;
    }
    for (int i = 1; i <= m; i++) {
        dp[1][i] = 1;
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= m; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    cout << dp[n][m];
    return 0;
}

1191：流感传染(模拟考过)

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
#include<bits/stdc++.h>
using namespace std;


int main()
{
    int n,m,count=0,sum=0;
    char num[101][101],b[101][101];
    memset(b, 0, sizeof(b));
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >>num[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            b[i][j]= num[i][j];
        }
    }
    cin >> m;

    while(count < m-1) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (num[i][j] == '@' ) {
                    if (j + 1 < n && num[i][j+1] != '#') {
                        //引入第二个数组储存结果，防止一直感染下去
                        b[i][j + 1] = '@';
                    }
                    if (j - 1 >= 0 && num[i][j-1] != '#') {
                        b[i][j - 1] = '@';
                    }
                    if (i + 1 < n && num[i+1][j] != '#') {
                        b[i + 1][j] = '@';
                    }
                    if (i - 1 >= 0 && num[i-1][j] != '#') {
                        b[i - 1][j] = '@';
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                num[i][j] = b[i][j];
            }
        }
        count++;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (num[i][j] == '@') {
                sum++;
            }
        }
    }
    cout << sum;
    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
#include<bits/stdc++.h>

using namespace std;

//定义一种新的变量类型：节点node类型 

struct node {

	//data是节点的数据域 

	int data;

	//lchild是节点的左指针（可以理解为左绳子） 

	node* lchild;

	//rchild是节点的左指针（可以理解为右绳子） 

	node* rchild;

};
//创建一个节点变量 

node* createNode(int v) {

	//从内存系统申请一个匿名node对象，并用绳子p牵着这个匿名node对象 

	node* p = new node;

	//绳子p所牵对象的data域赋值 

	p->data = v;

	//绳子p所牵对象的lchild域为NULL，表示不牵其他匿名node对象 

	p->lchild = NULL;

	//绳子p所牵对象的rchild域为NULL，表示不牵其他匿名node对象 

	p->rchild = NULL;

	return p;

}

int main() {

	//定义二叉树的根节点 

	node* root = NULL;

	//生成第1个node内存单元，并用绳子root牵着第1个node内存单元 

	root = createNode(5);

	//生成第2个node内存单元，并用绳子l牵着第2个node内存单元

	node* l = createNode(3);

	//生成第3个node内存单元，并用绳子r牵着第3个node内存单元 

	node* r = createNode(4);

	//将根节点变量root的左节点绳子牵向绳子l所牵的内存单元，即两根绳子都牵着第2个node内存单元 

	root->lchild = l;

	//将根节点变量root的右节点绳子牵向绳子r所牵的内存单元，即两根绳子都牵着第3个node内存单元 

	root->rchild = r;

	//生成第4个node内存单元，并用绳子l重新牵着第4个node内存单元，注意：绳子l不再牵着第2个node内存单元 

	l = createNode(2);

	//生成第5个node内存单元，并用绳子r重新牵着第5个node内存单元，注意：绳子r不再牵着第3个node内存单元 

	r = createNode(4);

	//将根节点变量root的左节点的左节点绳子牵向绳子l所牵的内存单元，即两根绳子都牵着第4个node内存单元 

	root->lchild->lchild = l;

	//将根节点变量root的左节点的右节点绳子牵向绳子r所牵的内存单元，即两根绳子都牵着第5个node内存单元 

	root->lchild->rchild = r;

	//生成第6个node内存单元，并用绳子l重新牵着第6个node内存单元，注意：绳子l不再牵着第4个node内存单元 

	l = createNode(3);

	//生成第7个node内存单元，并用绳子r重新牵着第7个node内存单元，注意：绳子r不再牵着第5个node内存单元 

	r = createNode(2);

	//将根节点变量root的右节点的左节点绳子牵向绳子l所牵的内存单元，即两根绳子都牵着第6个node内存单元 

	root->rchild->lchild = l;

	//将根节点变量root的右节点的右节点绳子牵向绳子r所牵的内存单元，即两根绳子都牵着第7个node内存单元 

	root->rchild->rchild = r;

}

1316：数的计数（模拟考过）

此题的关键是通过数组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
//csdn写法
#include<bits/stdc++.h>

long long ans;
using namespace std;
void dfs(int n) //统计m所扩展出的数据个数
{
	int i;
	ans++;      //每出现一个原数，累加器加 1;
	for (i = 1; i <= n / 2; i++)  //左边添加不超过原数一半的自然数，作为新原数,终止条件为i=1
		dfs(i);
}
int main()
{
	int n;
	cin>>n;
	dfs(n);
	cout<<ans;
	return 0;
}

//老师写法
#include<bits/stdc++.h>
using namespace std;

int ans[1000];

int dfs(int n)
{	
	//此处是防止超时的如果计算过，则直接返回结果 ans[n]，节约了时间和空间
	if (ans[n]) {
		return ans[n];
	}
	//根节点自己是一个数
	int cnt = 1;
	for (int i = 1; i <= n; i++) {
		//剪枝(超过前一个自然数一半的情况)
		if (i > n / 2) {
			break;
		}
		else {
			//叶子结点
			if (i == 1) {
				cnt++;
			}
			//非叶子结点
			else {
				int j = dfs(i);
				cnt += j;
			}
		}
	}
	//用于保存已计算的数的拆分数量，节约了时间和空间
	ans[n] = cnt;
	return cnt;
}
int main()
{
	int n;
	cin >> n;
	int cnt = dfs(n);
	cout << cnt;
	return 0;
}

1200：分解因数(模拟考过)

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
//下面的写法在模拟给的数据中会出现内存超限
//叶子写在for循环外面
#include<bits/stdc++.h>
using namespace std;

int ans;

void dfs(int n,int s)
{
	//叶子结点,分解方式ans+1，直接返回，不再执行
	if (n == 1) {
		ans++;
		return;
	}

	for (int i = s; i <= n; i++) {
		//非叶子结点(通过dfs(n / i, i)进行递归)
		if (n%i==0) {
			dfs(n / i, i);
		}
		//剪枝(n%i!=0的情况)
		else {
			continue;
		}
	}
	return;
}
int main()
{
	int n,m;
	cin>>n;
	
	for (int i = 1; i <= n; i++) {
		ans = 0;
		cin >> m;
		dfs(m, 2);
		cout << ans << endl;
	}
	
	
	return 0;
}

1204：爬楼梯(考过)

想复杂了，这类题还是找规律

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

using namespace std;

int f(int n)   //递归算法
{
    if (n == 1)
    {
        return 1;
    }
    if (n == 2)
    {
        return 2;
    }
    return f(n - 1) + f(n - 2);
}

int main()
{
    int n;
    while (cin >> n)
    {
        cout << f(n) << endl;
    }
    return 0;
}

1199：全排列(模拟考过)

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;

bool b[1001];//标记 
char s[1001], as[1001]; //s存储原字符串 as存储排序方案 
int len;
void dfs(int i)
{
	for (int j = 0; j < len; j++) {
		if (!b[s[j]]) {//判断是否用过 
			b[s[j]] = 1;
			as[i] = s[j];
			if (i == len - 1) {
				cout << as<<endl;
			}else {
				dfs(i + 1);//否则取下一个长度 
			}
            //实际上下面的这行代码只有在i == len - 1后才会运行，因为不满足长度时，会一直进行dfs的递归
			b[s[j]] = 0;//标记取消 
		}
	}
}
int main()
{
	cin>>s;
	len = strlen(s);
	dfs(0);//从长度0开始搜索 
	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
#include<bits/stdc++.h>
using namespace std;

int n;
int a[100];
int tmp[100];

void print() {
	for (int i = 0; i < n; i++) {
		cout << a[i] << " ";
	}
	cout << endl;
}
void merge(int L1, int R1, int L2, int R2) {
	int i = L1;
	int j = L2;
	int k = L1;
	while (i<=R1&&j<=R2)
	{
		if(a[i]<=a[j]){
			tmp[k++] = a[i];
		}
		else {
			tmp[k++] = a[j];
		}
	}
	//男生多
	while (i<=R1)
	{
		tmp[k++] = a[i++];
	}while (j <= R2)
	{
		tmp[k++] = a[i++];
	}
	for (int i = L1; i <= R2; i++) {
		a[i] = tmp[i];
	}
}
void mergesort(int l, int r) {
	if (l == r) {
		return;
	}
	int m = (l + r) / 2;
	mergesort(l, m);
	mergesort(m+1,r);
	merge(l, m, m + 1, r);
}
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	cout << "排序前:" << endl;
	print();
	mergesort(0, n - 1);
	cout << "排序后:" << endl;
	print();
	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
#include <bits/stdc++.h>
using namespace std;

const int Max = 1e6 + 4;
int a[Max] = {}; // 存储输入序列的数组
int b[Max]; // 存储归并排序过程中的临时数组
long long num = 0; // 用于存储逆序对的数量

// 归并排序中的归并操作，将两个已排序的数组合并成一个有序的数组
void merge(int l, int mid, int r) {
    int i = l; // 左半部分数组的下标
    int j = mid + 1; // 右半部分数组的下标
    int k = l; // 临时数组的下标
    while (i <= mid && j <= r) { // 比较左右两部分数组中的元素，合并为一个有序的数组
        if (a[i] > a[j]) { // 如果左边元素大于右边元素，说明存在逆序对
            b[k++] = a[j++]; // 将右边元素存储在临时数组中
            num += mid - i + 1; // 统计逆序对数量，注意这里的统计方式
        }
        else { // 如果左边元素小于等于右边元素，不需要统计逆序对
            b[k++] = a[i++]; // 将左边元素存储在临时数组中
        }
    }

    while (i <= mid) { // 如果左半部分数组有剩余元素，将其存储在临时数组中
        b[k++] = a[i++];
    }
    while (j <= r) { // 如果右半部分数组有剩余元素，将其存储在临时数组中
        b[k++] = a[j++];
    }
    for (i = l; i <= r; i++) { // 将归并排序过程中得到的有序数组覆盖原始数组
        a[i] = b[i];
    }
}

// 归并排序，对序列进行排序
void mergeSort(int l, int r) {
    int mid;
    if (l < r) { // 递归终止条件，当左右下标相等时表示已经排好序
        mid = l + ((r - l) /2); // 计算中间位置，避免溢出
        mergeSort(l, mid); // 对左半部分数组进行归并排序
        mergeSort(mid + 1, r); // 对右半部分数组进行归并排序
        merge(l, mid, r); // 归并操作
    }
}

int main() {
    int n;
    cin >> n; // 输入序列长度
    int i;
    for (i = 0; i < n; i++) { // 输入序列
        cin >> a[i];
    }

    mergeSort(0, n - 1); // 对序列进行归并排序

    cout << num ; // 输出逆序对数量

    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;

int a[100];
int k;
bool flag;

void dfs(int l, int r) {
	cout << "dfs(" << l << "," << r << ")" << endl;
	if (l > r) {
		return;
	}
	int m = (l + r) / 2;
	if (a[m] < k) {
		dfs(m + 1, r);
	}
	else if (a[m] > k) {
		dfs(l, m - 1);
	}
	else if (a[m] == k) {
		cout << m;
		flag = true;
		return;
	}
}
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	cin >> k;
	dfs(0, n - 1);
	if (!flag) {
		cout << "-1";
	}
	return 0;
}

回溯算法

1213：八皇后问题

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
//下面是四皇后
#include<bits/stdc++.h>
using namespace std;

int hx[4] = { 0 };
int sx[4] = { 0 };
int zxx[7] = { 0 };
int fxx[7] = { 0 };

char maze[4][4];
int cnt = 1;

void print() {
	cout << "No." << cnt++ << endl;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			cout << maze[i][j];
		}
	}
}
void dfs(int i) {
	cout << "第" << i << "行放置皇后" << endl;
	for (int j = 0; j < 4; j++) {
		if (!hx[i] && !sx[j] && zxx[i + j] && !fxx[i - j + 3]) {
			cout << " 第" << i << "行，第(" << j << "列位置" << i << "," << j << ")放置皇后" << endl;

			if (i == 3) {
				maze[i][j] = 'Q';
				print();
				maze[i][j] = 0;
			}
			else {
				hx[i] = 1;
				sx[j] = 1;
				zxx[i+j] = 1;
				fxx[i-j+3] = 1;
				maze[i][j] = 'Q';

				dfs(i+1);

				hx[i] = 0;
				sx[j] = 0;
				zxx[i + j] = 0;
				fxx[i - j + 3] = 0;
				maze[i][j] = 0;
			}
		
		}
		else {
			cout << " 第" << i << "行，第(" << j << "列位置" << i << "," << j << ")剪枝，不能放置皇后" << endl;
		}
	}
	cout << "第" << i << "行全部4列位置已经遍历" << endl;
}
int main()
{
	
	dfs(0);
	return 0;
}

1215：迷宫

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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
//CSDN:
#include <bits/stdc++.h>
using namespace std;
int n, m, n1, m1, n2, m2, d = 0;//n行m列 
char a[100][100];//保存二维数组
int e[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };//分别表示上下左右
void fun(int x, int y)
{
	if (d == 1)
	{
		return;
	}
	if (x == n2 && y == m2)
	{
		d = 1;
		return;
	}
	for (int i = 0; i < 4; i++)//循环判断上下左右 
	{
		int x1 = x + e[i][0];//计算下一个点的坐标 
		int y1 = y + e[i][1];//计算下一个点的坐标 
		if (x1 >= 0 && y1 >= 0 && x1 < n && y1 < n && a[x1][y1] != '#')//判断边界，判断是否访问过，判断是否可以通过 
		{
			a[x1][y1] = '#';//走过就标记为不能走 
			fun(x1, y1);//进入下一个点
		}
	}
}
int main()
{
	cin >> m;
	while (m--)
	{
		cin >> n;
		for (int i = 0; i < n; i++)
		{
			for (int k = 0; k < n; k++)
			{
				cin >> a[i][k];
			}
		}
		cin >> n1 >> m1 >> n2 >> m2;
		d = 0;
		if (a[n1][m1] == '#' || a[n2][m2] == '#')
		{
			cout << "NO" << endl;
			continue;
		}
		fun(n1, m1);
		if (d == 1)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
	return 0;
}



//老师的dfs：
#include <bits/stdc++.h>
using namespace std;
int n;
char a[101][101];//保存二维数组
int dir[4][2] = { {-1,0},{0,-1},{1,0},{0,1} };//分别表示上下左右
bool vis[101][101];
struct point
{
	int x; 
	int y;
};
point a1;
point a2;
bool flag;

bool in(point k) {
	if (k.x < n && k.x >= 0 && k.y < n && k.y >= 0) {
		return true;
	}
	else {
		return false;
	}
}

void dfs(point k){
	for (int i = 0; i < 4; i++)//循环判断上下左右 
	{
		//终止条件，剪枝,防止超时
		if (flag) {
			return;
		}
		point t;
		t.x = k.x + dir[i][0];//计算下一个点的坐标 
		t.y = k.y + dir[i][1];//计算下一个点的坐标 
		if (in(t)&&!vis[t.x][t.y]&&a[t.x][t.y]=='.'){//判断边界，判断是否访问过，判断是否可以通过 
			vis[t.x][t.y] = true;

			if (t.x == a2.x && t.y == a2.y) {
				flag = true;
				return;
			}else {
				dfs(t);
			}

		}
	}
}
int main(){
	int t;
	cin >> t;
	for(int i=0;i<t;i++){
		cin >> n;
		for (int i = 0; i < n; i++){
			for (int j = 0; j < n; j++){
				cin >> a[i][j];
			}
		}
		cin >> a1.x >> a1.y >> a2.x >> a2.y;

		flag=false;
		memset(vis, 0, sizeof(vis));

		if (a[a1.x][a1.y] == '#' || a[a2.x][a2.y] == '#')
		{
			cout << "NO" << endl;
			continue;
		}
		else {
			dfs(a1);
			if (!flag) {
				cout << "NO" << endl;
			}else {
				cout << "YES" << endl;
			}
		}
	}
	return 0;
}


//根据老师改的bfs：
//bfs:
//1、建立队列queue<point> q;
//2、队尾插入传入元素q.push(k);
//3、队列不为空while (!q.empty())
//4、队首元素传入point k = q.front();
//5、队尾插入新的元素q.push(t);（相当于dfs的dfs（t））
//6、队首元素删除q.pop();（放在while层的下一级与for同级）
#include <bits/stdc++.h>
using namespace std;
int n;
char a[101][101];//保存二维数组
int dir[4][2] = { {-1,0},{0,-1},{1,0},{0,1} };//分别表示上下左右
bool vis[101][101];
struct point
{
	int x;
	int y;
};
point a1;
point a2;
bool flag;

bool in(point k) {
	if (k.x < n && k.x >= 0 && k.y < n && k.y >= 0) {
		return true;
	}
	else {
		return false;
	}
}

void bfs(point k) {
	queue<point>q;
	q.push(k);
	while (!q.empty()) {
		point k = q.front();
		//循环判断上下左右
		for (int i = 0; i < 4; i++){
			//终止条件，剪枝,防止超时
			if (flag) {
				return;
			}
			point t;
			t.x = k.x + dir[i][0];//计算下一个点的坐标 
			t.y = k.y + dir[i][1];//计算下一个点的坐标 
			if (in(t) && !vis[t.x][t.y] && a[t.x][t.y] == '.') {//判断边界，判断是否访问过，判断是否可以通过 
				vis[t.x][t.y] = true;
				q.push(t);

				if (t.x == a2.x && t.y == a2.y) {
					flag = true;
					return;
				}

			}
		}
		q.pop();
	}
	
}
int main() {
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> n;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin >> a[i][j];
			}
		}
		cin >> a1.x >> a1.y >> a2.x >> a2.y;

		flag = false;
		memset(vis, 0, sizeof(vis));

		if (a[a1.x][a1.y] == '#' || a[a2.x][a2.y] == '#')
		{
			cout << "NO" << endl;
			continue;
		}
		else {
			bfs(a1);
			if (!flag) {
				cout << "NO" << endl;
			}
			else {
				cout << "YES" << endl;
			}
		}
	}
	return 0;
}

1216：红与黑

下面有深搜法和广搜法

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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
//自己写的dfs：
#include <bits/stdc++.h>
using namespace std;
int x, y;

char a[21][21];//保存二维数组
int dir[4][2] = { {-1,0},{0,-1},{1,0},{0,1} };//分别表示上下左右
bool vis[21][21];
struct point{
	int x; 
	int y;
};

point a1;
point a2;
bool flag;
int num = 0;

//判断是否在棋盘的界内
bool in(point k) {
	if (k.x < y && k.x >= 0 && k.y < x && k.y >= 0) {
		return true;
	}
	else {
		return false;
	}
}

void dfs(point k){
	//循环判断上下左右 
	for (int i = 0; i < 4; i++) {
		point t;
		t.x = k.x + dir[i][0];//计算下一个点的x坐标 
		t.y = k.y + dir[i][1];//计算下一个点的y坐标 


		//判断边界，判断是否访问过，判断是否可以通过 
		if (in(t)&&!vis[t.x][t.y]&&a[t.x][t.y]=='.'){
			//走过的就不能再走一遍了，所以数组标记true
			vis[t.x][t.y] = true;
			num++;
			dfs(t);
		}
	}
}

int main(){
	
	//外层的while循环是因为可能存在多组数据，需要持续输出
	while (true) {
		cin >>x>>y;
		//当在一行中读入的是两个零时，表示输入结束，这里的return 0来跳出while循环
		if (x == 0 && y == 0) {
			return 0;
		}
		//循环输入棋盘的具体情况，这里注意i<y而不是i<x，原因是i指代的应该是列数
		for (int i = 0; i < y; i++) {
			for (int j = 0; j < x; j++) {
				cin >> a[i][j];
				//遇到'@'，记录出现的位置，进行深度搜索
				if (a[i][j] == '@') {
					a1.x = i;
					a1.y = j;
				}
			}
		}
		//注意重置vis语句的位置，因为后续还可能有新一组的输入
		memset(vis, 0, sizeof(vis));
		//这里是因为题目中要求：记数时包括初始位置的瓷砖
		num = 1;

		dfs(a1);

		cout << num<<endl;
	}
	return 0;
}


//自己改的bfs：
//bfs:
//1、建立队列queue<point> q;
//2、队尾插入传入元素q.push(k);
//3、队列不为空while (!q.empty())
//4、队首元素传入point k = q.front();
//5、队尾插入新的元素q.push(t);（相当于dfs的dfs（t））
//6、队首元素删除q.pop();（放在while层的下一级与for同级）
#include <bits/stdc++.h>
using namespace std;
int x, y;

char a[21][21];//保存二维数组
int dir[4][2] = { {-1,0},{0,-1},{1,0},{0,1} };//分别表示上下左右
bool vis[21][21];
struct point {
	int x;
	int y;
};

point a1;
point a2;
bool flag;
int num = 0;

//判断是否在棋盘的界内
bool in(point k) {
	if (k.x < y && k.x >= 0 && k.y < x && k.y >= 0) {
		return true;
	}
	else {
		return false;
	}
}

void bfs(point k) {
	queue<point> q;
	q.push(k);
	//循环判断上下左右 
	while (!q.empty()) {
		for (int i = 0; i < 4; i++) {
			point k = q.front();
			point t;
			t.x = k.x + dir[i][0];//计算下一个点的x坐标 
			t.y = k.y + dir[i][1];//计算下一个点的y坐标 


			//判断边界，判断是否访问过，判断是否可以通过 
			if (in(t) && !vis[t.x][t.y] && a[t.x][t.y] == '.') {
				//走过的就不能再走一遍了，所以数组标记true
				vis[t.x][t.y] = true;
				num++;
				q.push(t);
			}
		}
		q.pop();
	}
	
}

int main() {

	//外层的while循环是因为可能存在多组数据，需要持续输出
	while (true) {
		cin >> x >> y;
		//当在一行中读入的是两个零时，表示输入结束，这里的return 0来跳出while循环
		if (x == 0 && y == 0) {
			return 0;
		}
		//循环输入棋盘的具体情况，这里注意i<y而不是i<x，原因是i指代的应该是列数
		for (int i = 0; i < y; i++) {
			for (int j = 0; j < x; j++) {
				cin >> a[i][j];
				//遇到'@'，记录出现的位置，进行广度搜索
				if (a[i][j] == '@') {
					a1.x = i;
					a1.y = j;
				}
			}
		}
		//注意重置vis语句的位置，因为后续还可能有新一组的输入
		memset(vis, 0, sizeof(vis));
		//这里是因为题目中要求：记数时包括初始位置的瓷砖
		num = 1;

		bfs(a1);

		cout << num << endl;
	}
	return 0;
}

1219：马走日（考过）

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;

int dir[8][2]={ {2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1} };
int n, m,sum=0,visit[11][11],flag,step=0;

struct horse
{
    int x; 
    int y;
};

bool in(horse h3) {
    if (h3.x >= 0 && h3.x < n && h3.y >= 0 && h3.y < m) {
        return true;
    }
    else {
        return false;
    }
  
}

void dfs(horse h2,int step) {
    if (step==n*m) {
        sum++;
        return;
    }
    
    for (int i = 0; i < 8; i++) {
        horse t;
        t.x = h2.x + dir[i][0];
        t.y = h2.y + dir[i][1];

        if (in(t)&&visit[t.x][t.y]==0) {
            visit[t.x][t.y] = 1;
            dfs(t,step+1);
            //这里的visit[t.x][t.y] = 0;很关键，不然整个棋盘只能走一次,这点与1216:红与黑不同,红与黑是给定了起点和终点，只需要走一次
            visit[t.x][t.y] = 0;
        }
 
    }
}

int main() {
    int T;
    horse h1;
    cin >> T;
    for (int s = 0; s < T; s++) {
        sum = 0;
        memset(visit, 0, sizeof(visit));
        cin >> n >> m >> h1.x >> h1.y;

        visit[h1.x][h1.y] = 1;
        dfs(h1,1);
        cout << sum << endl;
    }
    
    return 0;
}

1217：棋盘问题（模拟考过）

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;

char a[9][9];
int n, k,sum=0,vis[9];


void dfs(int x,int y) {
    //
    if (y==k) {
        sum++;
        return;
    }
    
    for (int i = x; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j] == '#' && vis[j] == 0) {
                vis[j] = 1;
                dfs(i + 1, y + 1);
                vis[j] = 0;
            }
        }
 
    }
}

int main() {

    while (cin >> n >> k) {
        if (n == -1 && k == -1) {
            return 0;
        }
        else {
            sum = 0;
            memset(vis, 0, sizeof(vis));
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    cin >> a[i][j];
                }
            }
            dfs(0, 0);
            cout << sum << endl;;
        }
    }

    
    return 0;
}

动态规划

1267：【例9.11】01背包问题

记住下面的图，物品为i行，重量为j列

关键步：

1
2
3
4
5
6
7
8
9
10
for (int i = 1; i <= n; ++i)
      for (int j = 0; j <= m; ++j)
      {
          if (j >= w[i])
              //当前物品能够装进背包的情况下，还需要比较装上该物品后，和上一次i-1行对应的最优解的价值大小，如果更大，则更新新的更大的价值，反之维持上一步的最优解
               dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i]);
           else
               //当前物品不能够装进背包的情况下，维持上一步的最优解
               dp[i][j] = dp[i - 1][j];
       }
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
//未优化版本：
#include<bits/stdc++.h>
using namespace std;----
#define N 35
#define M 250
int dp[N][M], w[N], c[N];//dp[i][j]:在前i个物品中选择物品放入大小为j的背包能获得的最大价值 
int main()
{
    int m, n;
    cin >> m >> n;
    for (int i = 1; i <= n; ++i)
        cin >> w[i] >> c[i];
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= m; ++j)
        {
            if (j >= w[i])
                //当前物品能够装进背包的情况下，还需要比较装上该物品后，和上一次i-1行对应的最优解的价值大小，如果更大，则更新新的更大的价值，反之维持上一步的最优解
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i]);
            else
                //当前物品不能够装进背包的情况下，维持上一步的最优解
                dp[i][j] = dp[i - 1][j];
        }
    //最后答案就在所有循环结束后的最后一个数组里
    cout << dp[n][m];
    return 0;
}

屏幕截图(58)

最长连续字段和

关键步：

1
2
3
4
5
6
7
8
9
10
11
12
13
int maxsum = -1000;
dp[0] = w[0];
for(int i= 1;i<=n;i++){
    //如果上一个dp是正数，就直接加上当前的w，不管w是不是负数
	if (dp[i - 1] > 0) {
		dp[i] = dp[i - 1] + w[i];
	}
    //如果上一个dp是负数，就直接抛弃上一个dp，从这个dp开始重新计算
	else {
		dp[i] = w[i];
	}
	maxsum = max(maxsum, dp[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
#include<bits/stdc++.h>
using namespace std;

int dp[101],w[101];
int n;

int sum() {
	int maxsum = -1000;
	dp[0] = w[0];
    for(int i= 1;i<=n;i++){
        //如果上一个dp是正数，就直接加上当前的w，不管w是不是负数
		if (dp[i - 1] > 0) {
			dp[i] = dp[i - 1] + w[i];
		}
        //如果上一个dp是负数，就直接抛弃上一个dp，从这个dp开始重新计算
		else {
			dp[i] = w[i];
		}
		maxsum = max(maxsum, dp[i]);
	}
	
	return maxsum;
}

int main() {
	
	cin >>  n;
	for (int i = 0; i < n; i++) {
		cin >> w[i];
	}
    int sumup=sum();
	cout << sumup;
	return 0;
}

最长上升子序列(模拟考过)

关键步：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//注意下面j终点是i
int ans = 1;
for (int i = 1; i <= n; i++)//枚举子序列的终点
{
    dp[i] = 1;// 初始化为1，长度最短为自身9
    //注意下面j终点是i
    for (int j = 1; j < i; j++)//从头向终点检查每一个元素
    {
        if (a[i] > a[j])
        {
            dp[i] = max(dp[i], dp[j] + 1);  // 状态转移方程
        }
    }
    ans = max(ans, dp[i]);  // 比较每一个dp[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
#include<bits/stdc++.h>

using namespace std;

int a[10001], dp[10001];
// a数组为数据，dp[i]表示以a[i]结尾的最长递增子序列长度
int n;
int LIS() {
    int ans = 1;
    for (int i = 1; i <= n; i++)//枚举子序列的终点
    {
        dp[i] = 1;// 初始化为1，长度最短为自身9
        for (int j = 1; j < i; j++)//从头向终点检查每一个元素
        {
            if (a[i] > a[j])
            {
                dp[i] = max(dp[i], dp[j] + 1);  // 状态转移方程
            }
        }
        ans = max(ans, dp[i]);  // 比较每一个dp[i],最大值为答案
    }
    return ans;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++){
         cin >> a[i];
    }
    int ans = LIS();
    cout << ans << endl;

    return 0;
}

屏幕截图(64)

最长公共子串

关键步：

1
2
3
4
5
6
7
8
9
10
11
12
for (i = 1; i <= lena; i++){
    for (j = 1; j <= lenb; j++){
        //如果相等，则将表格斜上角的数据dp[i - 1][j - 1]+1
        if (a[i - 1] == b[j - 1]) {
            dp[i][j] = dp[i - 1][j - 1] + 1;
        }
        //如果不相等，则选择表格左边dp[i][j - 1]和上边dp[i - 1][j]最大的dp数据放入dp[i][j]
        else {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
}
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<bits/stdc++.h>

using namespace std;

char a[201], b[201];
int dp[201][201], lena, lenb,i,j;

void lcs()
{
    for (i = 1; i <= lena; i++)
    {
        for (j = 1; j <= lenb; j++)
        {
            //如果相等，则将表格斜上角的数据dp[i - 1][j - 1]+1
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            //如果不相等，则选择表格左边dp[i][j - 1]和上边dp[i - 1][j]最大的dp数据放入dp[i][j]
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
}

int main()
{
    while (cin >> a)
    {
        cin >> b;
        memset(dp, 0, sizeof(dp));
        lena = strlen(a);
        lenb = strlen(b);
        lcs();
        cout << dp[lena][lenb] << endl;
    }
    return 0;
}

1296：开餐馆

关键步

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
for (int i = 1; i <= n; i++) {
	cin >> w[i];   // n 个地点位置
}
for (int i = 1; i <= n; i++)
{
	cin >> c[i]; // n个地点的餐馆利润
	dp[i] = c[i];
}
for (int i = 1; i <= n; i++)
{
	// j为逆序，防止部分数据被冲掉（不清楚原因）
	for (int j = 1; j <= n; j++)
	{
		if (w[i] - w[j] > k)
		{									  // 餐馆之间的距离必须大于k
			dp[i] = max(dp[i], dp[j] + c[i]); // dp[i]表示前i个地点开餐馆的最大利润
		}
	}
}
// 这里的排序是为了找到利益的最大值
// 也可以使用for循环加max函数来求最大值
sort(dp + 1, dp + n + 1);
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;
int w[1001], c[1001], dp[1001];
int main() {
	int t;
	cin >> t;//测试数据组数
	for(int s=1;s<=t;s++)
	{
		int n, k;
		cin >> n >> k; //输入总数n和距离限制K
		for (int i = 1; i <= n; i++) {
			cin >> w[i];   // n 个地点位置
		}
		for (int i = 1; i <= n; i++){
			cin >> c[i];// n个地点的餐馆利润
			dp[i] = c[i];
		}
		for (int i = 1; i <= n; i++) {
            //j为逆序，防止部分数据被冲掉（不清楚原因）
			for (int j = 1; j <= n; j++) {
				if (w[i] - w[j] > k) {//餐馆之间的距离必须大于k
					dp[i] = max(dp[i], dp[j] + c[i]);//dp[i]表示前i个地点开餐馆的最大利润
				}
			}
		}
        //这里的排序是为了找到利益的最大值
        //也可以使用for循环加max函数来求最大值
		sort(dp + 1, dp + n + 1);
		cout << dp[n] << endl;
		
	}
	return 0;
}

1293：买书

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  dp[1001], c[5] = { 0,10,20,50,100 };

int main() {
	int n;
	cin >> n;
	dp[0] = 1;	//初始条件
	for (int i = 1; i <= 4; i++) {
		for (int j = c[i]; j <= n; j++) {
			if (dp[j-c[i]]) {
				dp[j] = dp[j] + dp[j - c[i]];  //状态转移方程
			}
		}
	}
	if (n == 0) {
		cout << 0;
	}else{
		cout << dp[n];
	}
	return 0;
}

1259：【例9.3】求最长不下降序列（模拟考过)

这个比较有意思的是最长不下降序列的输出

1
2
3
4
5
6
7
8
9
10
11
12
13
for (int i = n - 1; i >= 0; i--)
{
	if (dp[i] == ans)
	{
		b[cnt] = a[i];
		cnt++;
		ans--;
	}
}
for (int i = cnt - 1; i >= 0; i--)
{
	cout << b[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
#include <bits/stdc++.h>
using namespace std;
int n,ans=1,cnt=0;
int a[201],dp[201],b[201];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (a[i] >= a[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }
    cout << "max="<<ans<<endl;
    for (int i = n - 1; i >= 0; i--)
    {
        if (dp[i] == ans) {
            b[cnt] = a[i];
            cnt++;
            ans--;
        }
    }
    for (int i = cnt - 1; i >= 0; i--)
    {
        cout << b[i] << " ";
    }
    
    return 0;
}

1284：摘花生

关键在于这个dp的改变,从上一步推演而来，就是左边和上面

1
dp[i][j] = max(dp[i-1][j] ,dp[i][j-1])+M[i][j];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
int T,R,C,M[101][101],dp[101][101], res = 0;

int main() {
    memset(dp, 0, sizeof(dp));
    cin >> T;
    for (int s = 0; s < T; s++) {
        cin >> R >> C;
        for (int i = 1; i <=R; i++) {
            for (int j = 1; j <= C; j++) {
                cin >> M[i][j];
            }
        }
        for (int i = 1; i <= R; i++) {
            for (int j = 1; j <= C; j++) {
                dp[i][j] = max(dp[i-1][j] ,dp[i][j-1])+M[i][j];
            }
        }
        cout << dp[R][C] << endl;
    }
    return 0;
}

1258：【例9.2】数字金字塔

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
//此做法为自上而下
#include <bits/stdc++.h>
using namespace std;
int a[1005][1005];
int dp[1005][1005];

int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)//输入数塔
	{
		for (int j = 1; j <= i; j++){
            cin >> a[i][j];
        }
	}
	dp[1][1] = a[1][1];//粘贴过来
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + a[i][j];
			//cout << dp[i][j]<<" ";
			//状态转移方程：比较这一层dp的正上方与最上方右边一个哪个大
			//大的与正下方a相加，作为dp正下方的值
		}
		//cout << endl;
	}
	int maxv = 0;
	for (int i = 1; i <= n; i++)
	{
		maxv = max(maxv, dp[n][i]);//比较最后一行结果值
	}
	cout << maxv;
	return 0;
}