备战蓝桥笔记

太过爱你忘了你带给我的痛 2023-07-13 10:59 5阅读 0赞

### 一，基础知识 ###

*  **网站地址推荐：**

1.  洛谷： [https://www.luogu.org/][https_www.luogu.org]
2.  ACM： [https://icpc.baylor.edu/][https_icpc.baylor.edu]
3.  UVaOJ： [https://uva.onlinejudge.org/][https_uva.onlinejudge.org] （最著名，Firefox浏览器）
4.  ZOJ： [http://acm.zju.edu.cn/onlinejudge/showRuns.do?contestId=1][http_acm.zju.edu.cn_onlinejudge_showRuns.do_contestId_1]
5.  重交： [http://10.1.74.121/acm/contest\_submit.jsp?problemID=2840&contestID=2][http_10.1.74.121_acm_contest_submit.jsp_problemID_2840_contestID_2]
6.  POJ： [http://poj.openjudge.cn/?message=%E6%B3%A8%E5%86%8C%E6%88%90%E5%8A%9F][http_poj.openjudge.cn_message_E6_B3_A8_E5_86_8C_E6_88_90_E5_8A_9F]

*  **评判结果准则：（ACM）**

1.  WA： 答案错/Wrong Answer 
2.  PE： 输出格式错/Presentation Error 
3.  TLE： 超时/Time Limit Exceeded 
4.  RE： 运行错/Runtime Error

*  **输入四大类：（ACM）**

1.    输入数据中第一行表明测试数据的个数；
2.   输入数据中有标明输入结束的数据；
3.   输入数据一直到文件尾； **while( scanf("%d %d", &m, &n)!=EOF )** //  EOF值为-1
4.    没有输入，这种情 形罕见

*  **ACM经验总结**

1.  代码嵌套，变量同名，里覆盖外 
2.  变量需赋值 （全局变量默认初始化）
3.  多组数据输出变量需重置（循环体内定义，每次使用会初始化）
4.  输入，输出要求严格： 回车结束 每行 ，行首/ 字符之间 是否有空格，行末空格可多余  
5.  从文件输入输出 freopen( "b.in", "r", stdin );   freopen( "estdout.pc2", "w", stdout );

*  **蓝桥经验总结**

1.  共10题，累积函数使用
2.  2.8.16进制转化
3.  日历时间问题点电脑日历，灵活
4.  暴力求解很重要
5.  看题仔细，多方验证，不要乘除，继续终结不分
6.  开始测试机器暴力求解学会
7.  9个查找排序的方法
8.  了解并熟练深度有先，全排列函数

*  **经验总结**

1.  尽量避免浮点数运算
2.  使用标准输入输出系统，main()函数必须返回0
3.  不及时反馈数据结果，可多次提交以最后一次结果为准
4.  分为：结果填空题，代码填空题（只一条，无注释），程序设计题

*  **经验总结**

1.  利用伪代码，编写注释， 查错看中间结果，留意“当前行”的跳转，看题仔细
2.  a/b=c全整即整，有浮则浮
3.  字典序：abc比bcd小  hi比history小 
4.  暂停结果 ： system("pause"）/ cin.get( );  
5.  ASCII  0-9 48-57  a-z 65-90   A-Z 97-122
6.  break（结束循环） return（退出函数） continue（跳出本次循环，执行下一次）
7.  不知道输入个数---------while(scanf("%d", &x) == 1/！EOF)
8.  \* 素数：比1大且只被1和自己除，0，1不是，2是
9.  \* 求三角形对应角的大小：a^2=b^2+c^2-2\*b\*c\*cos<b,c>;

1.  1e-6 （ 0.000001/10^-6)
2.  \_\_int64   printf( "%I64d\\n")
3.  a\[\]="sdf"; strlen(a)=3=sizeof(a)/sizeof(int);
4.  char a; a='a'； a=a-32;   int b=a-'0'; //a='A';
5.  int m = floor(sqrt(n) + 0.5);    //小数的四舍五入
6.  判断浮点数小数部分是否为0   if(ab-(int)ab==0)
7.  求最大公因数： int gcd(int a,int b) \{if(a%b==0)return b; else return gcd(b,a%b); \} 大前小后，返回同小b
8.  最小公倍数：t=gcd(a,b); t=a\*b/t;
9.  \+-\*的表达式除以正整数n的余数，可以在每步计算之后对n取余，结果不变 
10. cos(a)得到的是弧度，角度为： int l=(int)((acos(sum)/M\_PI)\*180+0.03);

1.  定义一维动态数组:   int \*q=new int\[n\];
2.  定义m\*m的数组：  int  \*\*p；   p=new int\*\[m\];
3.  定义n\*m的数组：   int n;     int (\*p)\[2\] = new int \[n\]\[2\];
4.  定义n\*m的二维数组   float \*\*tt = new float\*\[n\];  f or (int i=0; i<n; ++i) tt\[i\] = new float\[m\];

### 二，头文件 ###

*  **\#include <bits/stdc++.h> using namespace std; **

1.  所有头文件声明

*  **\#include<iostream> using namespaced std;**

1.  cin>>a;  while(n--)   0假/正
2.  cout<<"I"<<"LOVE"<<"SUA"<<endl;

*  **常数声明（值不可变**

1.  \#const  double PI=3.14
2.  \#define  PI  3.14  //优先使用
3.  \#define INF 1000000000----- min = INF, max = -INF

*  **\#include<cstdio>**

1.  while(scanf(" %d",&tmp)==1) //未知输入个数
2.  scanf("%d%s", &a, &s\[i\]);   // 读取整数a，读取第i个字符串， 遇到 空白字符会停下来
3.  printf("a= %06d（o.x） \\n", a);//输出6十 (八.十六） 进制整数 左边补0
4.  printf( " %0.3f \\n ", len );    //输出小数点后3位 数，自动补零（不可换成@），换行

*  **\#include <iomanip>**

1.  cout<<setw(5)<<255<<endl;  // 预设宽度，输出 空空255
2.  cout<<setfill('@')<<setw(5)<<255<<endl;  //输出 @@255
3.  cout<<fixed<<setprecision(2)<<cc;  //输出小数点后两位
4.  cout<<setiosflags(ios::fixed)（自动补零）<<setprecision(3)<<a;  //保留小数点后3位+自动补零

*  **\#include<cmath>**

1.  double cos(double);// 该函数返回弧度角（double 型）的余弦。
2.  double log(double);// 该函数返回参数的自然对数。
3.  double pow (double, double);//（  x， y）返回 x 的 y 次方。
4.  double **hypot** (double, double);//（直角三角型a>b,c)(b,c)->a
5.  double sqrt(double);/// 该函数返回参数的平方根。
6.  int abs(int);// 该函数返回整数的绝对值。
7.  double fabs(double);// 该函数返回任意一个十进制数的绝对值。
8.  **double floor(double);//** **该函数返回一个小于或等于传入参数的最大整数**

*  **\#include <c** **s** **tring>**

1.  strlen(s);//返回字符串s中 结束标记之前的字符个数( 结束标记“\\0” )
2.  memset( ticket, 0, sizeof(ticket) ); //对ticket数组清零，初始化赋值0，1,2不行哦
3.  memcpy（b，a，sizeof（a））// 数组a全部复制到数组b
4.  memcpy（b，a，sizeof（int） \* k） // 从数组a复 制k个元素到数组b
5.  strcpy/ strcmp/s trcat(a,  b)  字符串“赋值”“比较/0相等/>0前大后”“连接”
6.  getline(a，b);//读取一行数据
7.  getchar(s);// 从标准输入读取一个字符(包括空格和换行"\\n") 可用于判断是否换行

*  **\#include<cstdlib>**

1.  srand();rand()//随机数
2.  atof(s)/atoi() //把一个字符串形式的数转换为double/int型的
3.  **对结构体的一级排序**
4.  struct  In\{ int a，int b\}c\[100\]； 
5.  int  cmp(const void \*a，const void \*b) \{return \*(In\*)a-\*(In\*)b;\}
6.  qsort(b,strlen(b),sizeof(c\[0\]/struct ln),cmp);
7.  **对结构体的二级排序**
8.  struct  In\{ int a，int b\}c\[100\]；
9.  int  cmp(const void \*a，const void \*b) \{ 
10. struct In \*c=(In \*)a;  struct In \*d=(In \*)b;  
11. if(c->y!=d->y)  return d->x - c->x;  //前-后，从小到大
12. else  return c->x - d->x; \}         //y相等时，x从大到小
13. qsort(b,strlen(b),sizeof( c\[0\]/struct ln),cmp);

### 三，**STL** ###

**STL（ 标准模板库Standard Template Library）**

**基础知识**

1.  通用实体：容器，迭代器，算法。
2.  容器是一种数据结构，用来存储结点
3.  \* STL中常用的容器有：vector:向量   stack：栈   queue：队列  priority\_queue：优先队列........
4.  STL中的容器是用类模板实现

**STL模板的算法（** **\#include<algorithm>  using namespace std;** **）**

1.  find(a,a+len,对象)//找到返回该元素，没找到返回尾指针；
2.  int  \*i=find(a,a+strlen(a),9);  vector<int> a=\{1,2,3,4,5\}  find(a.begin( ),a.end( ),4\}
3.  swap(a\[0\],a\[4\]); 交换下标为0和4的元素；
4.  **sort(a,a+10)**//把数组a中 **前10**的元素按 **从小到大**排序 **（注：a+几，排前几的元素）**
5.  sort(a,a+10,compare)    bool compare(int a,int b)\{  return a>b; \}//降序，compare比较规则
6.  max\{maxline1,maxline2\};   min\{minline1,minline2\}; //求数maxline1,2的最大/小值；
7.  \*max\_element(a,a+len);  len=sizeof(a)/sizeof(int);  \*max\_element(v.begin(),v.end())  //返回比较从数组a到b处的最大值，若有相同，则为第一个。
8.  以二分法思想在一个有序数组a（从小到大）中找比b小的有多少个元素：lower\_\_bound(a,a+n,b\[i\]);

**STL中的向** **量（** **\#include <vector>  using namespace std;** **）**

*  **定义：**

1.  vector<char> v1;  //向量中的元素为字符
2.  vector<int> v2;   //向量中的元素为整型数据
3.  vector<point> v3; //向量中的元素为自定义结构体point变量
4.  vector< vector<结构体名称> > v4;  //可定义链表

*    **vector的成员函数：**

1.  push\_back：往向量的末端插入新的结点；
2.  pop\_back：删除向量末端的结点；
3.   begin：返回最前面结点的迭代器(指针)；
4.  end：返回最末端结点的迭代器(指针)

**STL中的栈（** **\#include <stack> ** **using namespace std;** **）**

*  **定义:  **

1.  stack<char> S1;  //栈中的结点为字符
2.  stack<pos> S3; //栈中的结点为自定义结构体pos变量

*  **stack的成员函数：**

1.  push：压栈，参数为需要压入栈的结点；
2.  pop：出栈，返回值为出栈的结点；
3.  top：取得栈顶结点，返回值为栈顶结点，该操作并不会弹出栈顶结点；
4.   empty：判断栈是否为空，返回值为bool型。
5.  size：计算栈中结点的个数。

**STL中的队列(** **\#include <queue>  ** **using namespace std;** **)**

*  **定义：**

1.  queue<char> Q1;  //队列中的结点为字符型数据
2.  queue<int> Q2;   //队列中的结点为整型数据
3.  queue<pos> Q3;  //队列中的结点为pos变量(自定义数据类型)

*  **queue的成员函数：**

1.  push：入队列，参数为需要入队列的结点；
2.  pop：出队列，返回值为出队列的结点；
3.  front：取得队列头结点，返回值为队列头结点，该操作并不会使得队列头结点出队列；
4.  empty：判断队列是否为空，返回值为bool型。
5.  size：计算队列中结点的个数。

**STL中的集合** **(** **  \#include<set>** **  using namespce std;)**

*  set中的元素都是排好序的，没有重复的元素
 *  set<结构体名/int/>  a;
 *  **set的成员函数：**

1.  begin() 　　 返回set容器的第一个元素的地址
2.  end() 　　　　 返回set容器的最后一个元素地址
3.  clear() 　　 删除set容器中的所有的元素
4.  empty() 　　　 判断set容器是否为空
5.  max\_size() 　 返回set容器可能包含的元素最大个数
6.  size() 　　　　 返回当前set容器中的元素个数
7.  erase(it) 删除迭代器指针it处元素
8.  insert(a) 插入某个元素

**STL中的集合****(****  \#include<map>****  using namespce std;)**

*  **定义:  **

1.  map<k, v>  mp;    // map<char, int> pr = \{ \{ '+', 1 \},\{ '-', 1 \},\{ '\*', 2 \},\{ '/', 2 \},\{ '(', 0 \} \};
2.

*  **stack的成员函数：**

1.  end();  //结尾，mp.end();
2.  begin();  //开头，mp.begin();
3.  insert();  //插入    m.insert(e)
4.  mp.erase(0);  //删除元素0，返回删除个数   mp.erase(mp.begin());
5.  map<int, int>::iterator it；    for (it = mp.begin(); it != mp.end(); it++)\{   cout<<it->first<<it->second;\}

[https_www.luogu.org]: https://www.luogu.org/
[https_icpc.baylor.edu]: https://icpc.baylor.edu/
[https_uva.onlinejudge.org]: https://uva.onlinejudge.org/
[http_acm.zju.edu.cn_onlinejudge_showRuns.do_contestId_1]: http://acm.zju.edu.cn/onlinejudge/showRuns.do?contestId=1
[http_10.1.74.121_acm_contest_submit.jsp_problemID_2840_contestID_2]: http://10.1.74.121/acm/contest_submit.jsp?problemID=2840&contestID=2
[http_poj.openjudge.cn_message_E6_B3_A8_E5_86_8C_E6_88_90_E5_8A_9F]: http://poj.openjudge.cn/?message=%E6%B3%A8%E5%86%8C%E6%88%90%E5%8A%9F