1. 首页
  2. 文章中心
  3. C++

【蓝桥杯比赛】视频教程（入门学习+算法辅导）部分代码笔记题型01 介绍蓝桥杯02 字符串和日期讲解03 字符串和日期练习04 使用sort排序讲解（c++）05 使用sort排序练习（c++）06 快速提升代码能力07 枚举算法讲解08 枚举算法练习09 常用STL讲解10 常用STL练习11栈和递归讲解13 深度优先搜索讲解14 深度优先搜索练习15 抽象深度优先搜索讲解17 深搜的剪枝策略讲解19 广度优先搜索讲解22 动态规划入门讲解24 常见动态规划模型26 背包问题讲解34 状态压缩动

83 阅读 0 评论
我是靠谱客的博主 奋斗白开水，这篇文章主要介绍【蓝桥杯比赛】视频教程（入门学习+算法辅导）部分代码笔记题型01 介绍蓝桥杯02 字符串和日期讲解03 字符串和日期练习04 使用sort排序讲解（c++）05 使用sort排序练习（c++）06 快速提升代码能力07 枚举算法讲解08 枚举算法练习09 常用STL讲解10 常用STL练习11栈和递归讲解13 深度优先搜索讲解14 深度优先搜索练习15 抽象深度优先搜索讲解17 深搜的剪枝策略讲解19 广度优先搜索讲解22 动态规划入门讲解24 常见动态规划模型26 背包问题讲解34 状态压缩动，现在分享给大家，希望可以做个参考。

写在前面，截图和题解均来源于B站视频【蓝桥杯比赛】视频教程（入门学习+算法辅导）不妥删。
图片因为防盗链机制无法上传，就把代码做参考吧。

题型

  • 结果填空
  • 代码填空
  • 编程大题
    不会及时评测，结束后才会跑测试点。

01 介绍蓝桥杯

在这里插入图片描述
在这里插入图片描述
可以用写程序来算，但手算更简单。
在这里插入图片描述
'’的ascii码是0，也可以填i<5等等。

循环节长度

注意引入的函数

注意v.end()返回的是尾指针（null），find找不到就返回v.end()

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//n是被除数，m是除数   注意不是看商！！是看余数（余数相同除数相同->商相同），否则循环节为1231234时有问题
public static int f(int n, int m) {
        n = n % m;//获取余数
        Vector v = new Vector();//动态数组大小的数据容器   
		for (;;) {
        	v.add(n);//v.push_back()也可以，在尾部增加
        	n *= 10;
        	n = n % m;//取新的余数 不在意商
        	if (n == 0)//整除的情况
            	return 0;
        	if (v.indexOf(n) >= 0)//含不含这个数 也可用find函数
            	return v.size() - v.indexOf(n);//该题为11 6 8 2 7 5 (11)
    	}
	}`

不要输入输出多余的东西，好像可以用万能头。数组开大一点。

复杂度

注意O(n!)>O(n^3)

map：报的数映射到报的次数
以空间换时间

02 字符串和日期讲解

string(个数，字符)

注意c++不像c的printf(“%c”) 需要强制类型转换成char 先增后减分两个循环即可

通过n m找规律即可

字符串处理

注意字符串数组结尾一定要有’’，与字符数组区别

把第二个字符串复制到第一个字符串

把第二个字符串拼接到第一个 创建数组注意清零

<0 第一个串小 通过字典序比较

长度：strlen 注意每次都会找 O(n) 所以一般先用一个数存着 不要写i<strlen(str)

观察：res = 旧res + 新字母 + 旧res 通过strcat复制到res + len + 1开始的位置上

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<stdio.h>//递归写法

void act(int i)
{
    if (i)
    {
        act(i-1);
        printf("%c",'A'-1+i);
        act(i-1);
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    act(n);
    return 0;
}

寻找字符串

STL中，cstdio == stdio.h cstring == string.h

gets省略换行 但容易异常 fgets下windows两个换行(n) linux下一个换行(n)

日期计算

闰年的影响从3月开始

1年1月1日是星期一 按年月日顺序处理 注意这里weekday[0]是星期一

给天数算日期：

y m d存结果 根据闰年调整2月天数 d++因为和day[m]+1比较 根据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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//计算一年间双休+节假日的放假天数
#include<cstdio>
int mm[10] = {1, 5, 10, 10, 10, 12};//将阳历节假日定义出来
int dd[10] = {1, 1, 1, 2, 3, 25};
int day[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
void nextday(int& y, int& m, int& d){//利用 引用 相当于传指针
    d++;
    if(d == day[m] + 1){//如果超过了月的天数
        d = 1;
        m++;//不用担心超过12 正好跳出循环
    }
}
int main(){
    int y, w, m, d, sf, ans;
    scanf("%d", &y);//今年的年份
    for(int i = 6; i <= 9; i++){//4个阴历节假日的阳历日期
        scanf("%d%d", &mm[i], &dd[i]);
    }//结束后mm dd就是全部节假日的月和日
    scanf("%d", &w);//1月1日是星期几
    if((y % 100 != 0 && y % 4 ==0 ) || y % 400 == 0){//如果今年是闰年
        day[2] = 29;//2月有29天了
    } 
    m = 1;//月份的初始
    d = 1;//日期的初始
    sf = 0;//标识在不在春节里 因为除了3天的春节其他已经标好
    ans = 0;//一年总共的放假天数
    while(m < 13){
        if(m == mm[6] && d == dd[6]){//如果是春节
            ans++;
            sf = 2;
        }else if(sf){//保证春节3天都加上
            ans++;
            sf--;
        }else if(w == 6 || w == 7){//判断双休 注意不与节假日重复
            ans++;
        }else{
            for(int i = 0; i < 10; i++){//前面处理了春节，剩下的节假日都是1天
                if(m == mm[i] && d == dd[i]){
                    ans++;
                    break;
                }
            }
        }
        nextday(y, m, d);//需要休息的情况没了 增加1天
        w++;//表示星期几 下面取模
        if(w == 8){
            w = 1;
        }
    }
    printf("%d", ans);
    return 0;
}

03 字符串和日期练习

1、看字符串中A的个数

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<cstdio>
#include<cstring>
char s[101];
int main(){
	fgets(s, 100, stdin);//也可用scanf("%s", s); 
	int ans = 0;
	int len = strlen(s);
	for(int i = 0; i < len; i++){
		if(s[i] == 'A')ans++;
	}
	printf("%d", ans);
	return 0;
}

2、最长的名字

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>
#include<cstring>
char s[101];
char max[101];
int main(){
	int n;
	int maxLen = 0;
	scanf("%d", &n);
	while(n > 0){
		scanf("%s", s);
		if(strlen(s) > maxLen){
			maxLen = strlen(s);
			strcpy(max, s);
		}
		n--;
	}
	printf("%s", max);
	return 0;
}

3、把字符变成后一个字符

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<cstdio>
#include<cstring>
char s[1005];
int main(){
	scanf("%s", s);
	int len = strlen(s);
	for(int i = 0; i < len; i++){
		if((s[i] >= 'a' && s[i] < 'z') || s[i] >= 'A' && s[i] < 'Z'){
			s[i] = s[i] + 1;
		}else if(s[i] == 'z'){
			s[i] = 'a';
		}else if(s[i] == 'Z'){
			s[i] = 'A';
		}
	}
	printf("%s", s);
	return 0;
}

4、判断是否为偶数

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<cstdio>
#include<cstring>
char s[10005];
int main(){
	scanf("%s", s);
	int len = strlen(s);
	int n = s[len - 1] - '0';
	if(n % 2 == 0){
		printf("YESn");
	}else{
		printf("NOn");
	} 
	return 0;
}

5、反转字符串

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<cstdio>
#include<cstring>
char s[10005];
char res[10005];
int main(){
	scanf("%s", s);
	int len = strlen(s);
	for(int i = 0; i < len; i++){
		res[i] = s[len - i - 1];
	}
	printf("%s", res);
	return 0;
}

6、返回一个字符串最后一个单词的长度

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<cstdio>
#include<cstring>
char s[10005];
int main(){
	int ans = 0;
	//scanf("%s", s);//不对 scanf和cin遇到空格就停下来了  可用gets 
	gets(s);
	int len = strlen(s);
	for(int i = len - 1; i >= 0; i--){
		if(s[i] != ' '){
			ans++;
		}else{
			break;
		}
	}
	printf("%d", ans);
	return 0;
}

更简单的方法：不断地用scanf读 如果读到文件尾会返回EOF

复制代码
1
2
3
4
5
6
7
8
9
#include<cstdio>
#include<cstring>
char s[10005];
int main(){
	while(scanf("%s", s) != EOF);//这里devc++运行不出来 不知道为什么
	printf("%d", strlen(s));
	return 0;
}

7、

十字图在这里插入图片描述

复制代码
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<iostream>
#include<cstdio>
#include<string> 
using namespace std;
char map[150][150];//30最多也只有125*125 
void print(int n){//打印图形 
	for(int i=0;i<4*n+5;i++){//我们找到了规律,层数为n,边长为4*n+5 
		for(int j=0;j<4*n+5;j++){
			cout<<map[i][j];
		}
		printf("n");
	}
}
int main(){	
	int n;
	cin>>n;
	int edge=4*n+5;//图形的长和宽 
	for(int i=0;i<4*n+5;i++){//先全部赋值为小黑点 
		for(int j=0;j<4*n+5;j++){
			map[i][j]='.';
		}
	}
	int center=edge/2;//找到中间 
	map[center][center]='$';//四分之一图像右下角的那三个小方块 
	map[center-1][center]='$';
	map[center][center-1]='$';
	
	int space=center-2;//用于for循环来更改map地图里面的位置
	 
	for(int i=0;i<n;i++){//总共要执行n此这个操作,B部分打印 
		map[space][space]='$';
		map[space-1][space]='$';
		map[space][space-1]='$';
		space-=2;
	}
	
	space=center-2;//转到AC部分打印 
	map[space][center]='$';//先打印三角形的那个小角 
	map[center][space]='$';
	space-=2;
	int count=2,temp=2;
	
	for(int i=0;i<n;i++){//执行n次此操作  
		while(count>=0){
			map[space][center-count]='$';//A部分打印 
			map[center-count][space]='$';//C部分打印 
			count--;	
		}
		space-=2;//变换位置 
		count=temp+2;//用count记录每次多打印两个小方块
		temp=count;//因为count前面会减减变化，用temp记录count的值 
	}
	
	for(int i=edge - 1; i>center ;i--){//上面复制  关于center上下翻转 
		for(int j=0;j<=center;j++){
			map[i][j]=map[4*n+5-i-1][j];
		}
	}
	for(int i=edge - 1; i>center ;i--){//左右复制  关于center左右翻转 
		for(int j=0; j<edge ;j++){
			map[j][i]=map[j][4*n+5-i-1];
		}
	}
	print(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
//法二：一条一条边的画  不断往里
#include<cstdio>
char s[150][150];
int main(){
    int n, x, y;
    scanf("%d", &n);
    x = 0;
    y = 0;
    for(int i = 0; i < 4*n + 5; i++){
        for(int j = 0; j < 4*n + 5; j++){
            s[i][j] = '.';
        }
    }
    for(int i = 0; i < n + 1; i++){//不断从最外层向里画'$' 最里就是十字
        for(int j = y + 2; j <= y + 4*(n - i) + 2; j++){//长度为4*(n-i)+1
          s[x][j] = '$';  
        }
        for(int j = x; j <= x + 2; j++){//左边竖着的
            s[j][y + 2] = '$';
        }
        for(int j = x; j <= x + 2; j++){//画十字时左右会重合
            s[j][y + 4*(n - i) + 2] = '$';
        }
        for(int j = y; j <= y + 2; j++){//左边横着的
            s[x + 2][j] = '$';
        }
        for(int j = y + 4*(n - i) + 2; j <= y + 4*(n - i) + 4; j++){
            s[x + 2][j] = '$';
        }
        for(int j = x + 2; j <= x + 4*(n - i) + 2; j++){//左边竖着的
            s[j][y] = '$';
        }
        for(int j = x + 2; j <= x + 4*(n - i) + 2; j++){
            s[j][y + 4*(n - i) + 4] = '$';
        }
        for(int j = y; j <= y + 2; j++){//左边横着的
            s[x + 4*(n - i) + 2][j] = '$';
        }
        for(int j = y + 4*(n - i) + 2; j <= y + 4*(n - i) + 4; j++){
            s[x + 4*(n - i) + 2][j] = '$';
        }
        for(int j = x + 4*(n - i) + 2; j <= x + 4*(n - i) + 4; j++){//左边竖着的
            s[j][y + 2] = '$';
        }
        for(int j =  x + 4*(n - i) + 2; j <= x + 4*(n - i) + 4; j++){
            s[j][y + 4*(n - i) + 2] = '$';
        }
        for(int j = y + 2; j <= y + 4*(n - i) + 2; j++){//横着的
            s[x + 4*(n - i) + 4][j] = '$';
        }
        x += 2;
        y += 2;
    }
    for(int i=0;i<4*n+5;i++){//我们找到了规律,层数为n,边长为4*n+5 
		for(int j=0;j<4*n+5;j++){
			printf("%c", s[i][j]);
		}
		printf("n");
	}
	return 0;
}

04 使用sort排序讲解（c++）

从大到小排序：

1、前k名的平均数

通过“排序方法”来控制升序/降序：注意不要写等号

除3余数小的排前面：

结构体的构造函数

可以有默认参数

结构体的排序：

05 使用sort排序练习（c++）

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
#include<iostream>
#include<algorithm> 
#include<cmath>
using namespace std;
const double EPSILON = 1e-6;
double num[105];
bool cmp(double a, double b){
	double da = fabs(a - round(a));//fabs:给浮点数取绝对值 round:四舍五入
	double db = fabs(b - round(b));
	if(fabs(da - db) < EPSILON){//看作浮点数ab相等，按照浮点数大小排序 
		return a < b; 
	} 
	return da < db; 
}
int main(){	
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		scanf("%lf", &num[i]);
	}
	sort(num, num + n, cmp);
	for(int i = 0; i < n; i++){
		if(i != n - 1){
			printf("%lf ", num[i]);
		} else{
			printf("%lfn", num[i]);
		}
	}
	return 0;
}

2、分数线和获奖人数

3、一段升序一段降序

4、字符串按照字典序排列，输出可以串成的手链数量

5、每个数字的和

6、成绩排序

复制代码
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
#include<iostream>
#include<algorithm> 
#include<cmath>
using namespace std;
struct Student{
	int num;
	int score;
};
bool cmp(Student a, Student b){
	return a.score > b.score; 
}
int main(){	
	Student stu[105];
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		stu[i].num = i + 1;
		scanf("%d", &stu[i].score);
	}
	sort(stu, stu + n, cmp);
	for(int i = 0; i < n; i++){
		if(i != n -1)printf("%d ", stu[i].num);
		else printf("%dn", stu[i].num);
	}
	return 0;
}

7、摘气球（跳的矮的先摘）

复制代码
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<iostream>
#include<algorithm> 
#include<cmath>
using namespace std;
struct Children{
	int a;//跳起来的高度
	int id;
};
Children child[100005];
int h[100005];//记录气球的高度 
int ans[100005];//记录每个小朋友所摘的气球数量
bool used[1005];//记录气球有没有被摘过 
bool cmp(Children a, Children b){
	return a.a < b.a; 
}
int main(){	
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i = 0; i < n; i++){
		scanf("%d", &child[i].a);
		child[i].id = i;
	}
	for(int i = 0; i < m; i++){
		scanf("%d", &h[i]);
	} 
	sort(child, child + n, cmp);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if(!used[j] && h[j] <= child[i].a){
				ans[child[i].id]++;
				used[j] = true;
			}
		} 
	}
	for(int i = 0; i < n; i++){
		printf("%dn", ans[i]);
	}
	return 0;
}

降低复杂度：删除used数组，通过将气球排序来看能否摘到气球

复制代码
1
2
3
4
5
6
7
8
9
int p = 0;//记录摘到第几个气球
sort(h, h + m);
for(int i = 0; i < n; i++){
	while(p < m && h[p] <= child[i].a){//可以摘到
        ans[child[i].id]++;
        p++;
    }
}

06 快速提升代码能力

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
#include<iostream>
using namespace std;
char ans[105];
int main(){	
	int N, R, m, now;
	cin >> N >> R;//N是整数 R是进制 
	if(N < 0){//如果输入了负数 
		cout << '-';
		N = -N;
	} 
	m = 0;//是转换后的位数 
	while(N){
		now = N % R;//存每一位的数 
		if(now <= 9){//0-9 
			ans[m++] = '0' + now;
		}else{//A-F
			ans[m++] = 'A' + now - 10;
		}
		N /= R;
	}
	if(m == 0){
		cout << 0;
	}
	for(int i = m - 1; i >= 0; i--){//倒着输出 
		cout << ans[i];
	}
	cout << endl;
	return 0;
}

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
#include<iostream>
using namespace std;
int dx[4] = {0, -1, 0, 1};//把方向用数组规定出来，就很灵活，方向是这题的难点 
int dy[4] = {1, 0, -1, 0};
char op[15];
int main(){	
	int n, d, x, nowx, nowy;
	cin >> n;//表示机器人移动多少步 
	d = 3;//起始朝向x轴正方向 
	nowx = 0;
	nowy = 0;
	for(int i = 0; i < n; i++){
		cin >> op >> x;
		if(op[0] == 'b'){//back：向后转 
			d = (d + 2) % 4; 
		}else if(op[0] == 'l'){//left：向左转 
			d = (d + 1) % 4;
		}else if(op[0] == 'r'){//right：向右转 
			d = (d + 3) % 4;
		}
		nowx += dx[d] * x;//方向*距离 
		nowy += dy[d] * x;
	}
	cout << nowx << " " << nowy << endl;
	return 0;
}

07 枚举算法讲解

1、比儿子大27岁，可能的解的个数

2、水仙花数

3、n-m之间的质数 注意swap()是c++自带的函数 注意可以把复杂度降到O(根号n)

4、枚举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
#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
char op[15];
int main(){	
	srand(time(NULL));//利用系统时间，返回随机数 提供新的种子 
	char s[10];//如果是读入要给''留位子 这里不用 
	for(int i = 0; i < 10; i++){
		s[i] = (char)(65 + rand() % 26);//随机产生一个10位的字符串 
		printf("%c", s[i]);
	}
	printf("n");
	for(int i = 0; i < 10; i++){//复杂度26*10 纯枚举 
		for(int j = 0; j < 26; j++){
			if(s[i] == (char)(65 + j)){
				cout << (char)(65 + j);
				break;
			}
		}
	}
	return 0;
}

5、回文数 并限定和

6、四叶玫瑰数：注意少用pow 比较奇怪 返回的是double

7、吹蜡烛：从某一岁开始吹

8、不含4

9、所有解

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
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<iostream>
using namespace std;
int main(){	
	int a1, a2, a3, a4, a5, a6, a7, a8;//枚举左边8个数 
	int vis[14] = {0};//记录数字是否被使用
	int tot = 0;//记录结果
	for(a1 = 1; a1 <= 13; a1++){
		vis[a1] = 1;
		for(a2 = 1; a2 <= 13; a2++){
			if(a1 + a2 > 13 || vis[a2]){//不符合条件，剪枝 
				continue;
			}
			vis[a2] = 1;
			vis[a1 + a2] = 1;
			for(a3 = 1; a3 <= 13; a3++){
				if(vis[a3]){
					continue;
				}
				vis[a3] = 1;
				for(a4 = 1; a4 <= 13; a4++){
					if(a3 - a4 <= 0 || a3 - a4 >= 14 || vis[a4] || vis[a3 - a4] || a4 == a3 - a4){//注意不能重复 
						continue; 
					}
					vis[a4] = 1;
					vis[a3 - a4] = 1;
					for(a5 = 1; a5 <= 13; a5++){
						if(vis[a5]){
							continue;
						}
						vis[a5] = 1;
						for(a6 = 1; a6 <= 13; a6++){
							if(a5 * a6 > 13 || vis[a6] || vis[a5 * a6] || a6 == a5 * a6){
								continue;
							}
							vis[a6] = 1;
							vis[a5 * a6] = 1;
							for(a7 = 1; a7 <= 13; a7++){
								if(vis[a7]){
									continue;
								}
								vis[a7] = 1;
								for(a8 = 1; a8 <= 13; a8++){
									if(vis[a8] || a7 < a8 || a7 % a8 != 0 || vis[a7 / a8] || a8 == a7 / a8){
										continue;
									}
									tot++;
								}
								vis[a7] = 0;//不断清0 
							}
							vis[a6] = 0;
							vis[a5 * a6] = 0;
						}
						vis[a5] = 0;
					}
					vis[a4] = 0;
					vis[a3 - a4] = 0;
				}
				vis[a3] = 0;
			}  
			vis[a2] = 0;
			vis[a1 + a2] = 0;
		}
		vis[a1] = 0;
	} 
	 printf("%d", tot);
	return 0;
}

08 枚举算法练习

1、字典序最小 枚举abc 算出来d

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
#include<iostream>
using namespace std;
int a[1005];
int main(){	
	int n, sum, ans;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i];
	} 
	sum = 0;
	ans = 0;
	for(int i = 0; i < n; i++){
		sum = 0;
		for(int j = i; j < n; j++){
			sum += a[j];
			if(sum > ans){
				ans = sum;
			}
		}
	}
	printf("%dn", ans);
	return 0;
}

3、双节棍 最大的差

09 常用STL讲解

动态数组vector

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include<vector> 
using namespace std;
int main(){	
	vector<int> vec;//可填入float double等不同数据类型
	vec.push_back(1);
	vec.push_back(3);//在尾部添加元素 
	for(int i = 0; i < vec.size(); i++){//用size()获取vector长度 
		cout << v[i] << endl;
	} 
	vec.pop_back();//从尾部删除元素
	vec.clear();//清空vector 但不清空内存
	vector<int> v;
	vector<int>().swap(v);//可以清空内存：与空的vector交换 
	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
#include<iostream>
#include<vector> 
using namespace std;
int main(){	
	//构造函数：定义长度和初始值
	int n = 10;
	vector<int> vec(n, 1);//10个数都是1 如果不写默认是1
	//二维数组
	n = 5;
	vector<vector<int> > vec2;
	for(int i = 0; i < n; i++){
		vector<int> x(i + 1, 1);
		vec2.push_back(x);
	} 
	for(int i = 0; i < n; i++){
		for(int j = 0; j < vec2[i].size(); j++){
			cout << vec2[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}

n个vector 其中每个vector有m个0 注意初始化

选正确的：123对 4错因为要传vector不能传0 1写法不好：前面5个都是0 push_back从第5个开始

乘法表

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<vector> 
using namespace std;
int main(){	
	vector<vector<int> > v2d;
	for(int i = 0; i < 5; i++){//5行 
		v2d.push_back(vector<int>());
	} 
	for(int i = 0; i < v2d.size(); i++){
		for(int j = 0; j <= i; j++){//第一行：1个 第二行：2个 2*1 2*2 
			v2d[i].push_back((i + 1) * (j + 1));
		}
	}
	for(int i = 0; i < v2d.size(); i++){
		for(int j = 0; j < v2d[i].size(); j++){
			cout << i + 1 << " * " << j + 1 << " = " << v2d[i][j] << "t";
		}
		cout << 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
#include<iostream>
#include<vector>
using namespace std;
vector<int> mat[10005];//这是开10005个vector动态数组的意思，代表每一行 
int main(){	
	int n, m, x, y;
	cin >> n >> m;
	for(int i = 0; i < m; i++){
		cin >> x >> y;
		mat[x].push_back(y);
	}
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < mat[i].size(); j++){
			if(j != mat[i].size() - 1){
				cout << mat[i][j] << " ";
			}else{
				cout << mat[i][j];
			}
		}
		cout << endl;
	}
	return 0;
}

集合set（有结构体时必须重载）

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<set> 
using namespace std;
int main(){	
	set<string> country;
	//插入、删除、查找都是对数复杂度 
	country.insert("China");//若插入重复元素，不会变
	country.erase("England");//若集合不存在该元素，删除也不会变
	if(country.count("China")){//如果集合存在该元素，返回1，不然返回0 
		cout << "China belong to country" << endl;
	} 
	//set<T>::iterator cit定义了一个指向set<T>这种集合的迭代器it 
	for(set<string>::iterator it = country.begin(); it != country.end(); it++){//用!=做结尾 
		cout << *it << endl;//注意从小到大遍历 
	} 
	cout << country.size() << endl;//获取大小 O(1) 
	country.clear(); //清空 O(n) 
	return 0;
}

重载< 否则insert时不知道前面怎么排序的

复制代码
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
//示例：重载< 让坐标从小到大排序
#include<iostream>
#include<set> 
using namespace std;
struct Point{
	int x, y;
	bool operator <(const Point &rhs) const{//重载从小到大 
		if(x == rhs.x){
			return y < rhs.y;
		}else{ 
			return x < rhs.x;//优先x，再比y 
		} 
	}
};
int main(){	
	int n;
	set<Point> v;
	cin >> n;
	for(int i = 0; i < n; i++){
		Point temp; 
		cin >> temp.x >> temp.y;
		v.insert(temp); 
	} 
	for(set<Point>::iterator it = v.begin(); it != v.end(); it++){
		cout << it -> x << " " << it -> y << 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
40
41
#include<iostream>
#include<set>
using namespace std;
struct people{
	int h;
	int w;
	int age;
	people(int _h, int _w, int _age){//写构造函数，不用定义再逐个赋值，较简单 
		h = _h;
		w = _w;
		age = _age;
	}
	bool operator<(const people &rhs) const{//这里各种情况都要写全，否则会 
		if(h != rhs.h){
			return h < rhs.h;
		} 
		if(w != rhs.w){
			return w < rhs.w;
		}
		return age < rhs.age;
	}
};
set<people> s; 
int main(){	
	int n, m, h, w, age;
	cin >> n >> m;
	for(int i = 0; i < n; i++){
		cin >> h >> w >> age;
		s.insert(people(h, w, age));//人的特征不重复
	}
	for(int i = 0; i < m; i++){
		cin >> h >> w >> age;
		if(s.count(people(h, w, age))){//样例输出可以不连续输出 看找没找到罪犯
			cout << "yes" << endl;
		}else{
			cout << "no" << endl;
		}
	}
	return 0;
}

映射表map

如果key存在了，再次insert，不会有任何改变 可用pair保存

访问：用数组访问 常用下标访问插入映射，而且可以更改
dict.count(“Mary”)

遍历：iterator

清空：clear()

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<string>
#include<map> 
using namespace std;

int main(){	
	map<string, int> dict;
	dict["Tom"] = 1;
	dict["Jone"] = 2;
	dict["Mary"] = 1;
	if(dict.count("Mary")){
		cout << "Mary is in class " << dict["Mary"] << endl;
		dict["Mary"] = 5;
	}
	for(map<string, int>::iterator it = dict.begin(); it != dict.end(); it++){
		cout << it -> first << " is in class " << it -> second << endl;
	}
    dict.clear();
	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
#include<iostream>
#include<string>
#include<map> 
using namespace std;

int main(){	
	map<int, map<string, int> > info;
	int n;
	cin >> n;
	for(int i = 0; i < n; i++){
		int class_id;
		string name;
		cin >> class_id >> name;
		info[class_id][name]++;
	}
	for(map<int, map<string, int> >::iterator it1 = info.begin(); it1 != info.end(); it1++){
		for(map<string, int>::iterator it2 = it1 -> second.begin(); it2 != it1 -> second.end(); it2++){
			cout << "There are " << it2 -> second << " people named " << it2 -> first << " in class " << it1 -> first << endl; 
		}
	}
	return 0;
}

10 常用STL练习

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
#include <cstdio>
#include <vector>
using namespace std;
vector<int> v[10005];//10005个长度不限的数组
int main(){//归并排序的过程中求逆序对
    int n, m, a, b;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++){
        v[i].push_back(i);
    }
    for(int i = 0; i < m; i++){
        scanf("%d%d", &a, &b);
        if(a == b){
            continue;
        }
        for(int j = 0; j < v[b].size(); j++){
            v[a].push_back(v[b][j]);//把b位置所有积木移上去即可
        }
        vector<int>().swap(v[b]);//把v[b]清掉
    }
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < v[i].size(); j++){
            if(j != v[i].size() - 1){
                printf("%d ", v[i][j]);
            } else{
                printf("%d", v[i][j]);
            }
        }
    }
    return 0;
}

2、求并集 用集合即可insert iterator

3、依然注意set 插入用insert 找有没有元素用count

4、求出现次数最多的数：用map记录

5、嵌套的map

11栈和递归讲解

栈：先进后出

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct Stack{//自行实现
    int data[10000];
    int top = -1;
    void push(int x) {
        top++;
        if (top < 10000) {
            data[top] = x;
        } else {
            top--;
            cout << "stack overflow" << endl;
        }
    }
    void pop(){
        if(top >= 0){
            top--;
        }
    }
    int topval(){
        if(top >= 0){
            return data[top];
        }
    }
};

STL：stack

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <stack>
using namespace std;
int main(){
    stack<string> s;
    s.push("123456");
    cout << s.size() << endl;
    while(!s.empty()){
        cout << s.top() << endl;
        s.pop();
    }
    return 0;
}

题1：火车出入站

题2：括号匹配

题3：给一个n个数的排列a，和一个栈，判断出栈顺序是否可以是排列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
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<int> a(n);//这是期望的排列
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    //如果不是a[0] 一直push 直到a[0]pop出来 如此循环
    stack<int> s;
    int cur = 1;
    bool f = 1;//1代表可以 否则不行
    for(int i = 0; i < n; i++){
        //注意s为空时，s.top()会访问越界
        while((s.empty() || s.top() != a[i]) && cur <= n){
            s.push(cur);
            cur++;
        }
        if(s.empty() || s.top() != a[i]){//说明跳出条件是cur>n
            f = 0;//没有没有符合的排列
            break;
        } else{
            s.pop();//弹出期望的值
        }
    }
    if(f){
        cout << "legal" << endl;
    }else{
        cout << "illegal" << endl;
    }
    return 0;
}

13 深度优先搜索讲解

1、路径选择：看上下左右4个方向走不走得通 更简单：顺逆时针

复制代码
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
#include <iostream>
#include <string>
using namespace std;
int n, m;
string maze[110];
bool vis[110][110];
bool in(int x, int y){
    return x >= 0 && x < n && y >= 0 && y < m;
}
bool dfs(int x, int y){
    if(maze[x][y] == 'T')return true;//到达终点
    vis[x][y] = 1;//记录成访问到
    maze[x][y] = 'm';
    int tx = x - 1, ty = y;//左
    if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){
        if(dfs(tx, ty))return true;
    }
    tx = x, ty = y - 1;//下
    if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){
        if(dfs(tx, ty))return true;
    }
    tx = x + 1, ty = y;//右;
    if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){
        if(dfs(tx, ty))return true;
    }
    tx = x, ty = y + 1;//上
    if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){
        if(dfs(tx, ty))return true;
    }
    vis[x][y] = 0;
    maze[x][y] = '.';//说明前面都走不通 还原
    return false;

}
int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> maze[i];//一共有n行
    }
    int x, y;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(maze[i][j] == 'S'){
                x = i, y = j;//遍历找到起点，赋值坐标
            }
        }
    }
    if(dfs(x, y)){
        for(int i = 0; i < n; i++){
            cout << maze[i] << endl;
        }
    } else{
        cout << "NO!" << endl;
    }

    return 0;
}

2、改进：用逆时针方向访问 新建数组来表示xy移动

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int dir[4][2] = {{-1, 0}, {0, -1},{1, 0}, {0, 1}};
bool dfs(int x, int y){
    if(maze[x][y] == 'T')return true;//到达终点
    vis[x][y] = 1;//记录成访问到
    maze[x][y] = 'm';
    for(int i = 0; i < 4; i++){
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){
            if(dfs(tx, ty))return true;
        }
    }
    vis[x][y] = 0;
    maze[x][y] = '.';//说明前面都走不通 还原
    return false;
}

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
#include <cstdio>
char s[10][10];//棋盘
int dir[8][2] = {{2, 1}, {1, 2},{-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}};
bool vis[10][10];
bool f;
bool in(int x, int y){
    return x >= 0 && x < 10 && y >= 0 && y < 9;
}
void dfs(int x, int y){
    if(f)return;
    if(s[x][y] == 'T'){
        f = true;
        return;
    }
    vis[x][y] = true;
    for(int i = 0; i < 8; i++){
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if(in(tx, ty) && s[tx][ty] != '#' && !vis[tx][ty]){
            dfs(tx, ty);
        }
    }
    //找路径，或求所有解，要取消路径
    //这里只用找一条路径 所以不用取消路径
}
int main(){
    int x, y;
    for(int i = 0; i < 10; i++){
        scanf("%s", s[i]);
    }
    for(int i = 0; i < 10; i++){
        for(int j = 0; j < 9; j++){
            if(s[i][j] == 'S'){
                x = i, y = j;//遍历找到起点，赋值坐标
            }
        }
    }
    dfs(x, y);
    if(f){
        printf("Yes");
    } else{
        printf("No");
    }
    return 0;
}

4、找第一题中的最小路径：新增step 每次比较：注意一定要还原路径！！！！

复制代码
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
#include <iostream>
#include <string>
using namespace std;
int n, m;
string maze[110];
bool vis[110][110];
int dir[4][2] = {{-1, 0},{0, -1},{1, 0},{0, 1}};
int ans = 1000000000;
bool in(int x, int y){
    return x >= 0 && x < n && y >= 0 && y < m;
}
void dfs(int x, int y, int step){
    if(maze[x][y] == 'T'){
        if(step < ans){
            ans = step;
        }
    }
    vis[x][y] = 1;
    for(int i = 0; i < 8; i++){
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){
            dfs(tx, ty, step + 1);
        }
    }
    vis[x][y] = 0;
    //找路径，或求所有解，要取消路径
}
int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> maze[i];
    }
    int x, y;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(maze[i][j] == 'S'){
                x = i, y = j;//遍历找到起点，赋值坐标
            }
        }
    }
    dfs(x, y, 0);
    cout << ans << endl;
    return 0;
}

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>
char mp[1005][1005];
bool vis[1005][1005];
int n, m;
int cnt;//存当前情况的
int ans;//存最大连续的#个数
void dfs(int x, int y){
    if(x < 0 || x >= n || y < 0 || y >= m || vis[x][y] || mp[x][y] == '.'){
        return;
    }
    vis[x][y] = true;//不用还原 因为找完这个片区就不用再找一次了
    cnt++;
    dfs(x - 1, y);
    dfs(x + 1, y);
    dfs(x, y  - 1);
    dfs(x, y + 1);
}
int main(){
//    找#连起来最大的路
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++){
        scanf("%s", mp[i]);
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(!vis[i][j] && mp[i][j] == '#') {
                cnt = 0;
                dfs(i, j);
                if(cnt > ans){
                    ans = cnt;
                }
            }
        }
    }
    printf("%dn", ans);
}

4、x y说明x是y的父母 输出每个点的子女数

复制代码
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 <cstdio>
#include <vector>
using namespace std;
vector<int> son[100005];
bool f[100005];
int ans[100005];
int dfs(int u){
    int ret = 0;
    for(int i = 0; i < son[u].size(); i++){
        ret += dfs(son[u][i]);//直系后代是每个后代的直系后代之和
    }
    ans[u] = ret;//将后代数存到数组里
    return ret + 1;
}
int main(){
    int n, x, y, u;
    scanf("%d", &n);//此题有n个人
    for(int i = 0; i < n - 1; i++){
        scanf("%d%d", &x, &y);
        son[x].push_back(y);
        f[y] = true;//说明不是根节点
    }
    for(int i = 1; i <= n; i++){
        if(!f[i]){
            u = i;//找到根节点
            break;
        }
    }
    dfs(u);
    for(int i = 1; i <= n; i++){
        printf("%dn", ans[i]);
    }
    return 0;
}

5、马可以走到的位置

复制代码
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>
using namespace std;
char s[105][105];
int n, m;
int dir[8][2] = {{-2, -1}, {-2, 1}, {2, -1}, {2, 1},{1, 2}, {1, -2},{-1, 2},{-1, -2}};
void dfs(int x, int y, int step){
    if(step > 3)return;
    if(x < 0 || x >= n || y < 0 || y >= m){
        return;
    }
    s[x][y] = '#';
    for(int i = 0; i < 8; i++){
        dfs(x + dir[i][0], y + dir[i][1], step + 1);
    }

}
int main(){
    int x, y;
    scanf("%d%d%d%d", &n, &m, &x, &y);//此题有n个人
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            s[i][j] = '.';
        }
    }
    dfs(x - 1, y - 1, 0);//把马的初始位置传入
    for(int i = 0; i < n; i++){
        printf("%sn", s[i]);
    }
    return 0;
}

14 深度优先搜索练习

1、需要几个人搜草丛：看草丛的数量

5 6
.#…
…#…
…#…#
…##.
.#…

复制代码
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>
char mp[105][105];
bool vis[105][105];
int n, m;
void dfs(int x, int y){//会把连起来的#一次性访问，形成草地
    if(x < 0 || x >= n || y < 0 || y >= m || vis[x][y] || mp[x][y] == '.'){
        return;
    }
    vis[x][y] = true;
    dfs(x - 1, y);
    dfs(x + 1, y);
    dfs(x, y  - 1);
    dfs(x, y + 1);
}
int main(){
    int cnt = 0;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++){
        scanf("%s", mp[i]);
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(!vis[i][j] && mp[i][j] == '#'){
                dfs(i, j);
                cnt++;
            }
        }
    }
    printf("%dn", cnt);
}

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
37
#include <cstdio>
char mp[15][15];
bool vis[15][15];
int n, m, x, y;
int ans;
void dfs(int x, int y){
    if(x < 0 || x >= n || y < 0 || y >= m || vis[x][y] || mp[x][y] == '#'){
        return;
    }
    if(mp[x][y] == 'e'){
        ans++;
        return;
    }
    vis[x][y] = true;
    dfs(x - 1, y);
    dfs(x + 1, y);
    dfs(x, y  - 1);
    dfs(x, y + 1);
    vis[x][y] = false;//记得还原
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++){
        scanf("%s", mp[i]);
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(mp[i][j] == 's'){
                x = i;
                y = j;
            }
        }
    }
    dfs(x, y);
    printf("%dn", ans);
}

15 抽象深度优先搜索讲解

1、N个数，选k个数，和为N 复杂度为O(2^n)

方法一：其实有点像递归 是否选择第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
#include <iostream>
using namespace std;
int n, k, sum, ans;
int a[40];
void dfs(int i, int cnt, int s){
    //i：搜素到第几层 cnt:用了几个数 s:sum
    if(i == n){
        if(cnt == k && s == sum){
            ans++;
        }
        return;
    }
    dfs(i + 1, cnt, s);//不选这个数
    dfs(i + 1, cnt + 1, s + a[i]);//选这个数
}
int main(){
    cin >> n >> k >> sum;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    ans = 0;//方案数
    dfs(0, 0, 0);
    cout << ans << endl;
    return 0;
}

方法二：从剩下的数中选择一个数 依然是遍历 注意恢复xuan[]

结果是方法一的k!倍 因为这里把235 253 这样的算不同的方法 复杂度为O(n^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
#include <iostream>
using namespace std;
int n, k, sum, ans;
int a[40];
bool xuan[40];
void dfs(int s, int cnt){
    //cnt：个数 s:sum
        if(cnt == k && s == sum){
            ans++;
        }
        for(int i = 0; i < n; i++){
            if(!xuan[i]){
                xuan[i] = 1;
                dfs(s + a[i], cnt + 1);
                xuan[i] = 0;
            }
        }
        return;
    }
int main(){
    cin >> n >> k >> sum;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    ans = 0;//方案数
    dfs(0, 0);
    cout << ans << endl;
    return 0;
}

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
37
38
39
#include <cstdio>
int n, sum = 0;
bool f;//标记能不能构成等边三角形
bool vis[15];//标记每根木棍有没有被选
int p[15];
void dfs(int cnt, int s){
    if(f)return;
    if(cnt == 3){//cnt：记录边数
        f = true;
        return;
    }
    if(s == sum / 3){//s：记录当前的和
        dfs(cnt + 1, 0);
        return;
    }
    for(int i = 0; i < n; i++){
        if(!vis[i]){
            vis[i] = true;
            dfs(cnt, s + p[i]);//从剩下的数中选择一个数的方法
            vis[i] = false;
        }
    }
}
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", &p[i]);
        sum += p[i];
    }
    if(sum % 3 != 0){//凑等边三角形 显然要是3的倍数
        printf("no");
    } else{
        dfs(0, 0);
        if(f)printf("yes");
        else printf("no");
    }
    return 0;
}

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
#include <iostream>
using namespace std;
int ans = 0;//记录可能性
bool col[10], x1[20], x2[20];//分别是 列 正对角线 反对角线 20：因为记录的是行+列的值
bool check(int r, int i){
    return !col[i] && !x1[r + i] && !x2[r - i + 8];
}
void dfs(int r){//r是行数
    if(r == 8){
        ans++;
        return;
    }
    for(int i = 0; i < 8; i++){//这里的棋盘是8*8 分别看与现有的8行是否冲突
        if(check(r, i)){
            col[i] = x1[r + i] = x2[r - i + 8] = true;// r - i可能为负数，所以加8
            dfs(r + 1);
            col[i] = x1[r + i] = x2[r - i + 8] = false;
        }
    }

}
int main(){
    dfs(0);//从第1行开始
    cout << ans << endl;
    return 0;
}

17 深搜的剪枝策略讲解

1、把不可能的去掉

2、最优解：不可能得到比当前更优的解，就减掉

3、重复性剪枝：123 132这样的全排列不需要

解决：选择时按位置递增来选

4、奇偶性剪枝：走过的位置会塌陷，不能走多次；并判断能否在时间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
40
41
42
43
44
45
46
47
48
49
#include <iostream>
using namespace std;
const int N = 10;
int n, m, T;
char mat[N][N];//迷宫
bool vis[N][N];//标识是否走过
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
bool ok;//标识能不能走
void dfs(int x, int y, int t){//t记录时间
    if(ok)return;
    if(t == T){
        if(mat[x][y] == 'D') ok = true;
        return;
    }
    vis[x][y] = true;
    for(int i = 0; i < 4; i++){//4个方向都试一下
        int tx = x + dx[i];
        int ty = y + dy[i];
        if(tx < 0 || tx >= n || ty < 0 || ty >= m || mat[tx][ty] == 'X' || vis[tx][ty])
            continue;//无效的情况
        dfs(tx, ty, t + 1);
    }
    vis[x][y] = false;//恢复
}
int main(){
    cin >> n >> m >> T;
    for(int i = 0; i < n; i++){
        cin >> mat[i];
    }
    int sx, sy, ex, ey;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(mat[i][j] == 'S') sx = i, sy = j;//起点
            if(mat[i][j] == 'D') ex = i, ey = j;//终点
        }
    }
    //奇偶性剪枝 颜色一样->偶数步->T为偶 颜色不同->奇数步->T为奇
    if((sx + sy + ex + ey + T) % 2 != 0)cout << "NO" <<endl;
    else{
        ok = false;
        dfs(sx, sy, 0);
        if(ok) cout << "yes" << endl;
        else cout << "no" << endl;
    }

    return 0;
}

5、引爆炸弹 注意行列只用看一遍

复制代码
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 <iostream>
#include <stdio.h>
using namespace std;
int n, m;
char mat[1010][1010];//迷宫
bool row[1010], col[1010];//标识是否走过 注意每行每列都只用看一遍！！！
void boom(int x,int y){//每个格子只检查一遍
    mat[x][y] = 0;//指没有炸弹
    if(!row[x]){
        row[x] = true;
        for(int i = 0; i < m; i++){
            if(mat[x][i] == '1') boom(x, i);
        }
    }
    if(!col[y]){
        col[y] = true;
        for(int i = 0; i < n; i++){
            if(mat[i][y] == '1') boom(i, y);
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        scanf("%s", mat[i]);
    }
    int cnt = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(mat[i][j] == '1'){
                cnt++;
                boom(i, j);
            }
        }
    }
    cout << cnt <<endl;
    return 0;
}

6、生日蛋糕没看 利用数学关系剪枝

19 广度优先搜索讲解

1、队列queue的使用

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <queue>
#include <iostream>
using namespace std;
int main(){
    queue<int> q;
    q.push(1);//向队尾插入元素
    cout << q.front() << endl;//获取队首元素
    q.pop();//队首元素出队
    q.empty();//判断队列是否为空
    //注意队列没有clear()方法 所以要循环
    while (!q.empty()){
        q.pop();
    }
    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 <queue>
#include <iostream>
using namespace std;
int main(){
    int n, m;
    cin >> n >> m;
    queue<int> q;
    for(int i = 1; i <= n; i++){
        q.push(i);
    }
    int cur = 1;
    while (q.size() > 1){
        int x = q.front();
        q.pop();
        if(cur == m){//如果是就正好pop出去了
            cur = 1;
        }else{//如果不是就从队首移到队尾
            q.push(x);
            cur++;
        }
    }
    cout << q.front() << endl;
    return 0;
}

2、bfs：一层层搜 优先搜索离起点最近的点 所以要借助队列

迷宫游戏：因为是走一步、走两步的顺序，所以只要到终点就一定是最短的

复制代码
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 <iostream>
#include <string>
#include <queue>
using namespace std;
int n, m;
string maze[110];
bool vis[110][110];
int dir[4][2] = {{-1, 0},{0, -1},{1, 0},{0, 1}};
int ans = 1000000000;
bool in(int x, int y){
    return x >= 0 && x < n && y >= 0 && y < m;
}
struct node{//定义结构体，存xy坐标和步数
    int x, y, d;
    node(int xx, int yy, int dd){
        x = xx;
        y = yy;
        d = dd;
    }
};
int bfs(int sx, int sy){
    queue<node> q;
    q.push(node(sx, sy, 0));
    vis[sx][sy] = true;
    while (!q.empty()){
        node now = q.front();
        q.pop();
        for(int i = 0; i < 4; i++){
            int tx = now.x + dir[i][0];
            int ty = now.y + dir[i][1];
            if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){
                if(maze[tx][ty] == 'T'){
                    return now.d + 1;//到达终点，当前步数+1
                } else{
                    vis[tx][ty] = true;
                    q.push(node(tx, ty, now.d + 1));
                }
            }
        }
    }
    return -1;
}
int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> maze[i];
    }
    int x, y;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(maze[i][j] == 'S'){
                x = i, y = j;//遍历找到起点，赋值坐标
            }
        }
    }
    cout << bfs(x, y) << endl;
    return 0;
}

3、坐标轴：感觉就是把每种情况push进队列 不断的搜索

复制代码
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
#include <cstdio>
#include <queue>
using namespace std;
queue<pair<int, int>> q;
bool vis[5005];//坐标轴上的坐标
int main(){
    int n, A, B, now, step;//坐标轴长度 起点 终点
    scanf("%d%d%d", &n, &A, &B);
    q.push(make_pair(A, 0));
    vis[A] = true;
    while (!q.empty()){
        now = q.front().first;
        step = q.front().second;
        q.pop();
        if(now == B){
            printf("%d", step);
        }
        if(now + 1 <= n && !vis[now + 1]){//向前一步
            q.push(make_pair(now + 1, step + 1));
            vis[now + 1] = true;
        }
        if(now - 1 >= 0 && !vis[now - 1]){//向后一步
            q.push(make_pair(now - 1, step + 1));
            vis[now - 1] = true;
        }
        if(now * 2 <= n && !vis[now * 2]){//两倍
            q.push(make_pair(now * 2, step + 1));
            vis[now * 2] = true;
        }
    }
    return 0;
}

22 动态规划入门讲解

1、错排公式 F(1)=0 F(2)=1

2、斐波拉契 用typedef long long 不错

3、杨辉三角：所有数字init()

4、马踏过河卒 用dp标记路径数即可

复制代码
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
#include <iostream>
using namespace std;
int dir[8][2] = {{2, 1}, {1, 2},{-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}};
bool d[30][30];//标记马的控制点
long long dp[30][30];//从(0,0)到该点的路径条数
int main(){//A:(0,0) B:(n,m) 需算出A到B的路径条数 马在(cx,cy)
    int n, m, cx, cy;
    cin >> n >> m >> cx >> cy;
    d[cx][cy] = true;//马的位置
    for(int i = 0; i < 8; i++){
        int tx = cx + dir[i][0];
        int ty = cy + dir[i][1];
        if(tx >= 0 && tx <= n && ty >= 0 && ty <= m){
            d[tx][ty] = true;//把马的8个位置都标记出来
        }
    }
    dp[0][0] = 1;
    for(int i = 0; i <= n; i++){//要到(n,m)
        for(int j = 0; j <= m; j++){
            if(d[i][j] == false){//如果该点不受马控制
                if(i){//如果i >= 1 
                    dp[i][j] += dp[i - 1][j];//向下走
                }
                if(j){
                    dp[i][j] += dp[i][j - 1];//向右走
                }
            }
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

动态规划：多阶段->单阶段(子问题)寻找最优解 状态转移

  • 最优化原理：最优的子策略也是最优的
  • 无后效性：以后的发展不影响前面

注意处理一下边界点即可

5、从山底走到山顶：

如果倒着走：山顶就是答案，简单

6、三维：其实就是fijk += min(fi-1jk, fij-1k, fijk-1)；

24 常见动态规划模型

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
#include <algorithm>
#include <iostream>
using namespace std;
const int inf = 0x7fffffff;
int num[101];
int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> num[i];
    }
    int ans = -inf;
    for(int i = 0; i < n; i++){
        ans = max(ans, num[i]);//这里可以找到数组中的最大值
    }
    if(ans <= 0){//说明都是负数，最大字段和就是最小的负数
        cout << ans << endl;
    } else{
        int sum = 0;
        for(int i = 0; i < n; i++){
            if(sum + num[i] < 0){
                sum = 0;
            } else{
                sum += num[i];
            }
            ans = max(ans, sum);//存最大数
        }
        cout << ans << endl;
    }
}

2、最大上升子序列 没转移：初始值为1 dpi = max(dpi, dp[j] + 1)

3、最大公共子序列：lcs[i] [j]：S1前i个字符和S2前j个字符的最大公共子序列

4、编辑距离：最小的步数是两个字符串相近 用’-'补齐，使字符串对齐

复制代码
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 <iostream>
#include <string>
using namespace std;
int dp[110][110];
string a, b;
int main(){
    cin >> a >> b;
    int lena = a.size();
    int lenb = b.size();
    //处理边界情况
    for(int i = 1; i <= lena; i++){
        dp[i][0] = i;
    }
    for(int i = 1; i <= lenb; i++){
        dp[0][i] = i;
    }
    //运用递推式
    for(int i = 1; i <= lena; i++){
        for(int j = 1; j <= lenb; j++){
            if(a[i - 1] == b[j - 1]){
                dp[i][j] = dp[i - 1][j - 1];
            } else{
                dp[i][j] = min(min(dp[i][j - 1],  dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
            }
        }
    }
    cout << dp[lena][lenb] << endl;
    return 0;
}

26 背包问题讲解

1、背包问题：第一种是不放，第二种是放 dp表示计算到第i件物品，总重量为v的最大价值

倒着来：保证是之前的值，没被更新过

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
int dp[21][1010];
int w[21], c[21];
int main(){
    int N, V;
    cin >> N >> V;
    for(int i = 1; i <= N; i++){
        cin >> w[i] >> c[i];
    }
    for(int i = 1; i <= N; i++){
        for(int j = 0; j <= V; j++){
            if(j >= c[i]){//放这个物体
                dp[i][j] = max(dp[i - 1][j - c[i]] + w[i], dp[i - 1][j]);
            } else{//不放这个物体
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    cout << dp[N][V] << endl;
    return 0;
}
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
int dp[1010];
int w[21], c[21];
int main(){
    int N, V;
    cin >> N >> V;
    for(int i = 1; i <= N; i++){
        cin >> w[i] >> c[i];
    }
    //这里要从大到小，才能保证更新的顺序正确
    for(int i = 1; i <= N; i++){
        for(int j = V; j >= c[i]; j--){
            dp[j] = max(dp[j - c[i]] + w[i], dp[j]);
        }
    }
    cout << dp[V] << endl;
    return 0;
}

2、多重背包：物品除了价值和体积，增加了个数

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
int dp[21][1010];
int w[21], c[21], n[21];
int main(){
    int N, V;
    cin >> N >> V;
    for(int i = 1; i <= N; i++){
        cin >> w[i] >> c[i] >> n[i];
    }
    for(int i = 1; i <= N; i++){
        for(int j = 0; j <= V; j++){
            for(int k = 0; k <= n[i]; k++){
                if(j >= c[i]*k){
                    dp[i][j] = max(dp[i - 1][j - c[i]*k] + w[i]*k, dp[i][j]);
                }
            }
        }
    }
    cout << dp[N][V] << 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
#include <iostream>
using namespace std;
int dp[1010];
int w[21], c[21], n[21];
int main(){
    int N, V;
    cin >> N >> V;
    for(int i = 1; i <= N; i++){
        cin >> w[i] >> c[i] >> n[i];
    }
    for(int i = 1; i <= N; i++){
        for(int j = V; j >= 0; j--){
            for(int k = 0; k <= n[i]; k++){
                if(j >= c[i]*k){
                    dp[j] = max(dp[j - c[i]*k] + w[i]*k, dp[j]);
                }
            }
        }
    }
    cout << dp[V] << endl;
    return 0;
}

3、物品是无限的，但也可以转换成多重

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
int dp[21][1010];
int w[21], c[21];
int main(){
    int N, V;
    cin >> N >> V;
    for(int i = 1; i <= N; i++){
        cin >> w[i] >> c[i];
    }
    for(int i = 1; i <= N; i++){
        for(int j = 0; j <= V; j++){
            if(j >= c[i]){//拿这一次的更新？
                dp[i][j] = max(dp[i][j - c[i]] + w[i], dp[i - 1][j]);
            }else{
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    cout << dp[N][V] << endl;
    return 0;
}
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
int dp[1010];
int w[21], c[21];
int main(){
    int N, V;
    cin >> N >> V;
    for(int i = 1; i <= N; i++){
        cin >> w[i] >> c[i];
    }
    for(int i = 1; i <= N; i++){
        for(int j = c[i]; j <= V; j++){
            dp[j] = max(dp[j - c[i]] + w[i], dp[j]);
        }
    }
    cout << dp[V] << endl;
    return 0;
}

二进制没有懂。

34 状态压缩动态规划讲解

1、二进制枚举子集：忽略最高位

2、从n个数中凑出x个数：

复制代码
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 <iostream>
using namespace std;
int main(){
    int n, x, ans = 0, a[30];
    cin >> n >> x;
    for(int i = 0; i < n; i++){
        cin >> a[i];//输入n个数
    }
    //类比dp[1 << n] 开了dp[2^n] 这样开n维数组变成开1维
    for(int i = 0; i < (1 << n); i++){//遍历i，i把n位组合都取到
        int num = 0;
        for(int j = 0; j < n; j++){
            if(i & (1 << j)){//代表是否选择了第j个整数
                num += a[j];
            }
        }
        if(num == x){
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
int dist[20][20];
int dp[1 << 16][20];//第1位：经过了哪些人的手(最多16人) 第2位：现在在谁手上
int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> dist[i][j];
            if(dist[i][j] == -1) dist[i][j] = INF;
        }
    }
    //如果是Floyd:每个点不一定只经过一遍，所以赋值成最短路径即可，不用管中间怎么走
    for(int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[1][0] = 0;//因为是一个环，所以从哪里开始不重要
    for(int s = 0; s < (1 << n); s++){
        for(int i = 0; i < n; i++){
            if(s & (1 << i)){
                for(int j = 0; j < n; j++){
                    if(j != i && (s & (1 << j))){
                        dp[s][i] = min(dp[s][i], dp[s ^ 1 << i][j] + dist[j][i]);//^相当于做减法
                    }
                }
            }
        }
    }
    int ans = INF;
    for(int i = 1; i < n; i++) {//不知道从谁开始传代价最小，所以遍历
        ans = min(ans, dp[(1 << n) - 1][i] + dist[i][0]);
    }
    if(ans == INF) ans = -1;
    cout << ans << endl;
    return 0;
}

36 二分法讲解

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
#include <iostream>
using namespace std;
const int N = 1e4 + 9;
int a[N], n, m;
int binary_search(int x){
    int l = 0, r = n - 1;
    while(l <= r){
        int mid = (l + r) >> 1;//除以2
        if(a[mid] == x)return mid;
        if(a[mid] < x){
            l = mid + 1;
        } else{
            r = mid - 1;
        }
    }
    return -1;
}
int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    cin >> m;
    while(m--){
        int x;
        cin >> x;
        cout << binary_search(x) << endl;
    }
    return 0;
}

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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
int a[20][20];
int dp[1 << 16][20];//第1位：经过了哪些人的手(最多16人) 第2位：现在在谁手上
int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> a[i][j];
        }
    }
    memset(dp, 0x3f, sizeof(dp));
    for(int i = 0; i < n; i++){
        dp[1 << i][i] = 0;//初始状态
    }
    for(int i = 0; i < (1 << n); i++){
        for(int j = 0; j < n; j++){
            if(i & (1 << j)){//如果传过了这个人的手
                for(int k = 0; k < n; k++){
                    if(!(i & (1 << k))){
                        //状态转移方程：j传球给k
                        dp[i | 1 << k][k] = min(dp[i | 1 << k][k], dp[i][j] + a[j][k]);
                    }
                }
            }
        }
    }
    int ans = INF;
    for(int i = 0; i < n; i++) {//不知道从谁开始传代价最小，所以遍历
        ans = min(ans, dp[(1 << n) - 1][i]);
    }
    cout << ans << endl;
    return 0;
}

3、求根号

4、方程的近似解

复制代码
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
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const double eps = 1e-3;
double f(double x){
    return pow(x, 4) + 5 * pow(x, 3) + 6 * pow(x, 2) + 7 * x + 4;
}
double cal(double y){
    if(f(0) > y || f(100) < y){//因为这里是单增的
        return -1;
    }
    double l = 0, r = 100;
    while (r - l > eps){
        double mid = (l + r) / 2;
        if(f(mid) > y) r = mid;
        else l = mid;
    }
    return l;
}
int main(){
    double y;
    cin >> y;
    printf("%.3fn", cal(y));
    return 0;
}

5、快速求解x ^ y % p：y&1判断y是不是奇数，如果是奇数要多乘一个x

6、实现二分答案：将一串数组至多分为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
35
36
37
38
39
40
#include <iostream>
using namespace std;
const int N = 1e3 + 9;
const int inf = 0x3f3f3f3f;
int n, k, a[N];
bool check(int x){//当最大数为x时，有几组
    int now = 0, cnt = 0;
    for(int i = 0; i < n; i++){
        if(now + a[i] > x){
            cnt++;
            now = a[i];
        } else{
            now += a[i];
        }
    }
    return cnt <= k;
}
int cal(int l, int r){//最大数肯定在l-r之间取
    while(l < r){
        int mid = (l + r) >> 1;
        if(check(mid)){
            r = mid;//是合法的，可以继续找
        }else{
            l = mid + 1;
        }
    }
    return l;
}
int main(){
    int ma = -inf, sum = 0;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        ma = max(ma, a[i]);
        sum += a[i];
    }
    cout << cal(ma, sum) << endl;
    return 0;
}

7、给出n个物品，每个物品有两个属性a和b，选择n-k个元素，询问∑ai/∑bi的最大值。

复制代码
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 <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 1e3 + 9;
const double eps = 1e-7;
int n, k;
double a[N], b[N], tmp[N];
double g(double v){//f=比值=v ∑ai-v∑bi>=0 对v进行二分
    for(int i = 0; i < n; i++){
        tmp[i] = a[i] - v * b[i];
    }
    sort(tmp, tmp + n);
    double sum = 0;
    for(int i = k; i < n; i++){//选择最大的n-k个进行求和
        sum += tmp[i];
    }
    return sum;
}
double cal(){//找比值的最大值
    double l = 0, r = 1e10;
    while (r - l > eps){
        double mid = (l + r) / 2;
        if(g(mid) > 0){//当前的v小了
            l = mid;
        } else{//当前的v太大了
            r = mid;
        }
    }
    return l;
}
int main(){
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    for(int i = 0; i < n; i++){
        cin >> b[i];
    }
    printf("%.2fn", cal());
    return 0;
}

最后

以上就是奋斗白开水最近收集整理的关于【蓝桥杯比赛】视频教程（入门学习+算法辅导）部分代码笔记题型01 介绍蓝桥杯02 字符串和日期讲解03 字符串和日期练习04 使用sort排序讲解（c++）05 使用sort排序练习（c++）06 快速提升代码能力07 枚举算法讲解08 枚举算法练习09 常用STL讲解10 常用STL练习11栈和递归讲解13 深度优先搜索讲解14 深度优先搜索练习15 抽象深度优先搜索讲解17 深搜的剪枝策略讲解19 广度优先搜索讲解22 动态规划入门讲解24 常见动态规划模型26 背包问题讲解34 状态压缩动的全部内容，更多相关【蓝桥杯比赛】视频教程（入门学习+算法辅导）部分代码笔记题型01内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(55)

相关文章

计算机组成原理--mooc第六章 中央处理器
计算机组成原理--mooc第六章 中央处理器
为什么20根地址线的寻址范围是1M，但是一根地址线却不是一个字节？
为什么20根地址线的寻址范围是1M，但是一根地址线却不是一个字节？
计算机组成原理第三章
计算机组成原理第三章
五、垃圾回收五、垃圾回收
五、垃圾回收五、垃圾回收
【蓝桥杯比赛】视频教程（入门学习+算法辅导）部分代码笔记题型01 介绍蓝桥杯02 字符串和日期讲解03 字符串和日期练习04 使用sort排序讲解（c++）05 使用sort排序练习（c++）06 快速提升代码能力07 枚举算法讲解08 枚举算法练习09 常用STL讲解10 常用STL练习11栈和递归讲解13 深度优先搜索讲解14 深度优先搜索练习15 抽象深度优先搜索讲解17 深搜的剪枝策略讲解19 广度优先搜索讲解22 动态规划入门讲解24 常见动态规划模型26 背包问题讲解34 状态压缩动
【蓝桥杯比赛】视频教程（入门学习+算法辅导）部分代码笔记题型01 介绍蓝桥杯02 字符串和日期讲解03 字符串和日期练习04 使用sort排序讲解（c++）05 使用sort排序练习（c++）06 快速提升代码能力07 枚举算法讲解08 枚举算法练习09 常用STL讲解10 常用STL练习11栈和递归讲解13 深度优先搜索讲解14 深度优先搜索练习15 抽象深度优先搜索讲解17 深搜的剪枝策略讲解19 广度优先搜索讲解22 动态规划入门讲解24 常见动态规划模型26 背包问题讲解34 状态压缩动
计算机组成原理（主存储器）
计算机组成原理（主存储器）
HTML和CSS基础学习一、HTML二、CSS三、JS基础四、webpack
HTML和CSS基础学习一、HTML二、CSS三、JS基础四、webpack
计算机组成原理中wr是什么,计算机组成原理复习例题.doc
计算机组成原理中wr是什么,计算机组成原理复习例题.doc

评论列表共有 0 条评论

立即
投稿
返回
顶部