蓝桥杯——练习（3.1）

蓝桥杯——练习（3.1）

基础练习 FJ的字符串

题目链接：http://lx.lanqiao.cn/problem.page?gpid=T63

资源限制

时间限制：1.0s 内存限制：512.0MB

问题描述

FJ在沙盘上写了这样一些字符串：
　　A1 = “A”
　　A2 = “ABA”
　　A3 = “ABACABA”
　　A4 = “ABACABADABACABA”
　　… …
　　你能找出其中的规律并写所有的数列AN吗？

输入格式

仅有一个数：N ≤ 26。

输出格式

请输出相应的字符串AN，以一个换行符结束。输出中不得含有多余的空格或换行、回车符。

样例输入

3

样例输出

ABACABA

解题思路

• 当为1的时候只有A输出，为2的时候为ABA，可以写一个函数，然后递归调用即可。

• x为1的时候输出A，不为1的时候先(x-1)作为参数传递过去调用函数，输出相应的字母，接着调用以x-1为参数调用函数。在main函数中直接调用函数即可。

代码

#include<iostream>
#include<cstdio>
using namespace std;
void display(int x)
{
	if(x==1)
		cout<<"A";
	else
	{
		display(x-1);
		cout<<(char)('A'+x-1);
		display(x-1); 
	}
}
int main()
{
	int n;
	cin>>n;
	display(n);
	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

视频学习——常用STL视频讲解（C++版）

视频链接：https://www.bilibili.com/video/BV1jE411g76D?p=9

学习心得

• vector动态数组，可以在不知道数组的长度的情况下使用，即在想开辟一个数组但却不知道开多大长度的数组合适的情况下使用，此时我们需要用到的数组可能会根据情况变动，这种情况下我们就需要用到动态数组。

• 什么是动态数组？动态数组就是不定长数组，数组的长度可以根据我们的需要动态改变，动态数组的实现不难，C++标准模板库实现了集合、映射表、栈、队列等数据结构和排序、查找等算法。我们可以很方便的调用标准库来减少我们的代码量。

• 本质上来看，vector使用动态分配数组来存储它的元素。当新的元素插入的时候，这个数组需要被重新分配大小为了增加存储空间。方法是：分配一个新的数组，然后将全部的元素移到这个数组。就时间而言，这是一个相对代价高的任务，每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。

• vector分配空间的策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。

• push_back在插入期间可能会进行扩容，vector中扩容的机制是按照1.5倍的方式进行扩容在，在linux下是按照3倍的机制进行扩容的。

• 扩容的具体操作是申请空间，拷贝元素，释放旧的空间，随着元素的不断增多，每次扩容的成本都很高，因此在插入期间，尽量避免扩容，那么，提前给好空间的大小就可以了，在插入的期间就不会去进行扩容的操作了。

题目练习 算法训练 最大获利

题目链接：http://lx.lanqiao.cn/problem.page?gpid=T574

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

Chakra是一位年轻有为的企业家，最近他在进军餐饮行业。他在各地开拓市场，共买下了N个饭店。在初期的市场调研中，他将一天划分为M个时间段，并且知道第i个饭店在第j个时间段内，会有Aij位服务员当值和Bij位客户光临。他还分析了不同饭店不同时间段客户的需求，得到第i个饭店在第j个时间段内，平均每位客户消费Cij元。为了创设品牌形象，Chakra决定每个饭店每天只选择一个时间段营业，每个服务员至多接待一位顾客（若顾客数多于服务员数，超过部分的顾客当天就无法在该店消费了）。
　　企业家的目的终究还是获利。请你安排营业时间，并告诉Chakra每天消费总额最多为多少。

输入格式

第一行两个整数，N、M。
第二行开始依次给出三个矩阵A(NM)、B(NM)、C(N*M)。

输出格式

一行一个整数，最大消费总额。

样例输入

2 3
1 2 3
3 2 1
3 2 1
1 2 3
4 5 2
3 1 6

样例输出

16

数据规模和约定

1 <= M,N <= 100
1 <= Aij, Bij <= 5000
0 <= Cij <= 10^9

代码

#include<iostream>
using namespace std;
int main()
{
	int n,m;
	cin>>n>>m;
	long long  a[n][m];
	long long  b[n][m];
	long long  c[n][m];
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++) 	
		{
			cin>>a[i][j];
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin>>b[i][j];
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin>>c[i][j]; 
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(a[i][j]<b[i][j])
			{
				c[i][j]*=a[i][j];
			}
			else{
				c[i][j]*=b[i][j];
			}
		} 
	}
	long long sum=0;
	for(int i=0;i<n;i++)
	{
		long long max=0;
		for(int j=0;j<m;j++)
		{
			if(c[i][j]>max)
				max=c[i][j];
		}
		sum+=max;
	}
	cout<<sum<<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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57