备战蓝桥杯第一天---拒绝假努力

1，填空题只能输入数字或字符串

2，编程大题一定不能忘记  return 0

算法：
枚举 排序 搜索 计数 贪心 动态规划 图论 数论 

数据结构：
数组 对象/结构 字符串 队列 栈 树 图 堆 

储存单位 ：bit B KB MB GB TB PB EP ZP YB BB NB DB .....

位bit (比特）： 存放一位二进制数，即0或1，最小的存储单位。
字节byte:           8个二进制为一个字节（B)

1Byte(B)=8bit
1kB=1024B
1MB=1024KB

256*1024*1024*8/32=67108864

 计算机小知识注重积累

分为【时间复杂度】【空间复杂度】

【时间复杂度】：指执行当前算法所消耗的时间

【空间复杂度】：是指执行当前算法需要占用多少内存空间

在main函数外面定义数组，可以节约空间

 O 表示正比例关系

常数阶O(1)

无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)，如：

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

上述代码在执行的时候，它消耗的时候并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用O(1)来表示它的时间复杂度。

线性阶O(n)

for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

这段代码，for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度。

对数阶O(logN)

int i = 1;
while(i 
 
从上面代码可以看到，在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。我们试着求解一下，假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2^n
 也就是说当循环 log2^n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(logn)
 
 
线性对数阶O(nlogN)
 
 
线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。
 
 
就拿上面的代码加一点修改来举例：
 
 
for(m=1; m 
 
平方阶O(n²)
 
把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。
 举例：
 
 
for(x=1; i<=n; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}
 
 
这段代码其实就是嵌套了2层n循环，它的时间复杂度就是 O(n*n)，即 O(n²)
 如果将其中一层循环的n改成m，即：
 
 
for(x=1; i<=m; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}
 
 
那它的时间复杂度就变成了 O(m*n)
 
 
立方阶O(n³)、K次方阶O(n^k)
 
 
参考上面的O(n²) 去理解就好了，O(n³)相当于三层n循环，其它的类似。
 
 
除此之外，其实还有 平均时间复杂度、均摊时间复杂度、最坏时间复杂度、最好时间复杂度 的分析方法，有点复杂，这里就不展开了。
 
 
空间复杂度 O(1)
 
如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)
 举例：
 
 
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
 
 
代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)
 
 
空间复杂度 O(n)
 
我们先看一个代码：
 
 
int[] m = new int[n]
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}
 
 
这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n）
 
 
原文链接
 
 
算法的时间与空间复杂度（一看就懂） - 知乎 (zhihu.com)
 

 ●上述代码2中第2个for循环的复杂度为n（即计算次数），结果为n!

●时间复杂度是指代码执行的次数

考虑最优算法：

● O（n+q）表示n个人，q次询问。

●map把一个数映射为一个数（n）的几次

辗转相除法：

欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。

例如：假如需要求 100 和18 两个正整数的最大公约数,用欧几里得算法，是这样进行的：

100 / 18 = 5 (余 10)

18 / 10= 1(余8)

10 / 8 = 1(余2)

8 / 2 = 4 (余0)

至此，最大公约数为2

以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 100 和 18 的最大公约数2。

#include

int main(){

int a,b,x,y;

scanf("%d %d",&a,&b);

x = a; //备份a,b，为了计算 最大公倍数

y = b;

if(ab

int n = a % b;

while(n!=0){

    a = b;

    b = n;

    n = a % b;

}

printf("最小公倍数：%d,最大公约数:%d",x*y/b,b);

return 0;

核心式子：

while(n!=0){

    a = b;

    b = n;

    n = a % b;

}

printf("最小公倍数：%d,最大公约数:%d",x*y/b,b);
 

两数相乘=他们的最小公倍数乘最大公约数

#include
#include
using namespace std;
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		{
			string space=string(n-i,' ');
			string ch=string(2*i-1,'A'+i-1);
			cout< 
 
 
升级版三角形 
 
 
 
#include
#include
using namespace std;
int main()
{ 
	char c;
	cin>>c;
	if(c>='A'&&c<='Z'){
		for(int i=1;i<=c-'A'+1;i++){//c-'A'+1为总行数，
			for(int j=1;j<=c-'A'+1-i;j++){
				cout<<" ";//前方空格数等于总行数-所在行数
			}
			for(int n=1;n<=i;n++){
				cout<<(char)('A'+n-1);
			}
			for(int n=i-1;n>=1;n--){//这个n前要写int，虽然前面已经定义过 
				cout<<(char)('A'+n-1);
			}
		cout<=1;n--){//这个n前要写int，虽然前面已经定义过 
				cout<<(char)('1'+n-1);
			}
		cout< 
建房子 

 
 
 
 
循环输出就行
 
 
 
#include
#include
using namespace std;
int main()
{ 
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cout<<"+-";
		}
		cout<<"+"< 
 
 
 
 
 对称字符串 
 
 
 
 可以看出规律是每一行都是在前一行基础上加个字母，在把前一行又接到后面
 
 
#include
#include
char res[5000000];
int main()
{ 
	int n;
	scanf("%d",&n);
	int len=0;
	for(int i=1;i<=n;++i){
		strcat(res+len+1,res);//加1，是因为留个位置加新字母
		res[len]='A'+i-1;
		len=strlen(res); 
	}
	printf("%sn",res);	
	return 0;
} 
 
寻找字符串 
 
 
 
 
#include
#include
char s1[1005],s2[1005];
char res[5000000];
int main()
{ 
	
	fgets(s1,1004,stdin);
	fgets(s2,1004,stdin);
	//输入两个字符串 
	int len1 =strlen(s1)-1,len2=strlen(s2)-1;//这里减一是因为fgets吃了换行 
	int ans=0;
	for(int i=0;i+len2-1 
 
 
●第五行，不用scanf,是因为它读到空格就会结束。
 
 
 
 
●gets没有规定最多读多少，不安全，在c++里删了
 
 
 
 
●gets会吃进最后的换行，而fgets不会吃
 
 

 年月日 
 
 
生日日期  
 
思路：循环得出y年一月1日是星期几，再循环得出m月1日是星期几，再是m月d日、循环处理都是ans+=天数%7，ans%=7;       
 
#include
#include
using namespace std;
string weekday[7]={"1"，“2”，“3”，“4”，“5”，“6”，“7”};
int  whatday(int y,int m, int t){
	int ans=0;//得出来的是遍历天数的下一天
	for(int i=1;i>y>>m>>d;
	cout< 
 
 
 
纪念日 
题目：输入四个数，年 月 日 整数k
 
输出的是 该年月日k天后  的年月日。
 
 
判断大数奇偶性 
 
 
 
 
 注意8里面的len-1
 
 
 
 
 
最后一个单词 
 
 
这个题可以用很特殊方法解