/*1.分析已知与未知 2.数据定义
3.输入 4.算法实现 5.输出*/
#include<bits/stdc++.h>	//万能头
using namespace std;	//命名空间
int main() {			//主函数
	cout<<"授课笔记完整版";
	return 0;
}
一、基本数据类型
	int a1=6,a2=int(6.9999); //整型
	long long l=6666666666; //长整型 
	float f=3.14; //单精度 
	double d=3.1415926; //双精度 
	char c1='A',c2=char(90); //字符类型
	bool b1=false,b2=true; //true真 false假

二、变量的定义与使用 
	int _2a; //字母、数字、下划线
	数字不能开头;不能用关键字;
	变量的作用域：
	循环中定义的变量，只能在循环中用

三、运算符 
	//算术运算 加减乘除 整除 求余（模） 
	a+b;a-b;a*b;a/b;a%b; 
	//逻辑运算 与或非 
	与（有0则0，无0才1）
	或（有1则1，无1才0） 
	a&&b;a||b;!a;
	//关系运算 大于、小于、等于...
	a>b;a<b;a==b;a>=b;a<=b;a!=b;
	//自增自减
	a++;b--;
	i++;先用后加；
	++i;先加后用； 
	//三目运算 A？B:C
	//if(A) {B} else{C} 

四、基本语句
	int a; double b; char c;
	
	//输入输出语句 
	cin>>a>>b>>c;//>>向右是输入
	scanf("%d %f %c",&a,&b,&c);
	//格式串  d十进制整数，f浮点数，c字符 
	
	cout<<a<<b<<c;//<<向左是输出
	cout<<fixed<<setprecision(2)<<b;
	printf("%d %.2f %c",a,b,c);
	// %.2f 代表保留2位小数 
	
	//分支语句：条件"不重复 且 不遗漏"
	if...else...
	if...else if...
	
	switch(整数){
	case 1: 语句;break;
	case 2:	语句;break;
	default: 语句; 
	}
	从冒号:开始向下执行，遇break跳出  
	
	//循环语句 for while do...while
	循环三要素：条件、初始/步长、循环体
	for(初始i=1;条件i<n;步长i++){
		循环体 s++;
	}
	
	初始 
	while(条件){
		循环体;
		步长; 
	}
	
	初始 
	do{
		循环体;
		步长; 
	} while(条件)
	
	break;		跳出本层循环
	continue;	跳过本次循环
	 
	打表法解题：
	表头列出关键变量，纵向变量变化过程） 


五、数组：一维/二维/字符数组
	1.定义（初始化） 下标从0开始 
	类型  数组名[长度] ={元素1,元素2...}
	类型  数组名[行长][列长] ={元素1,元素2...}
	int a[5]={2,4,6,8,10}; 
	int b[5][5]={{1,2,3,4,5},{6,7,8},{}}
	char c[5]={'l','w','l','$'}
	
	2.引用
	数组名[下标]
	数组名[行号][列号]
	a[0]=666; 
	b[0][0]=888;
	b[1][3]=9; 
	c[0]='w';
	
	3.场景
	循环输入/输出 数组每个元素
	//一维数组：一层循环 
	for(int i=1;i<=5;i++){
		cin>>a[i];
		cout<<a[i]<<" ";
	} 
	//二维数组：二层循环 
	for(int i=1;i<=5;i++){
		for(int j=1;j<=5;j++){
			cin>>a[i][j];
			cout<<a[i][j]<<" ";
		}
	} 
	
六、字符数组 与 字符串类 
	1. 定义（初始化） 
	1)字符数组 写法： 
	char c[20]="Hello World "; //字符串 赋值
	cin.getline(字符串名,长度);//输入含空格字符串 
	cin.getline(c,5); 
	
	2)字符串类 写法：
	string c="Hello"; //字符串 赋值 默认尾部加'\0'
	getline(cin,字符串名);//输入含空格字符串
	getline(cin,c);
	
	2.相关函数与操作 
	1)字符数组 函数： 
	char c1[20]="hello",c2[20]="World"; 
	strcat(c1,c2);//拼接concatenate 
	strcpy(c1,c2);//复制copy 
	strcmp(c1,c2);//比较compare 
	strlen(c1);//字符串长度length 
	strlwr(c1);//转小写 low 非标准库函数 
	strupr(c1);//转大写 up 非标准库函数

	2)字符串类  操作 
	string s1,s2;
	s1=s1;//赋值
	s1+=s2;//拼接
	s1==s2;s1!=s2;//判断是否相等
	s1<s2;//判断大小
	s1.empty();//是否为空
	s.length() / s.size()    返回字符串长度    
	s.substr(pos, len)    截取子串（从 pos 开始 len 个字符）
	s.find(str)    查找子串位置，未找到返回 string::npos
	s.insert(pos, str)    在 pos 位置插入字符串
	s.erase(pos, len)    从 pos 开始删除 len 个字符
	s.replace(pos, len, str)    替换从 pos 开始的 len 个字符为 str    

七、函数 
（一）标准函数： 
abs() 求绝对值 	abs(-4) 返回4 
sqrt()	开平方根
max()	求最大值 max(5,6);   //返回6 
min()	求最小值 
ceil()	向上取整
floor() 向下取整
 
（二）自定义函数： 
	1.函数的定义： 
	返回类型  函数名（参数列表）{
		函数体    //执行语句
	}
	int add(int a,int b){
		return a+b;
	} 
	2.声明与引用；
	函数名(参数列表); 
	传值/传址；
	作用域

八、结构体与sort排序
	1.定义（初始化） 
	struct 结构体类型名{
		类型  要素1名;
		类型  要素2名;
		... 
	}; 
	struct stu{
		int num;
		char male;
	};
	stu j;
	2.引用  变量名.要素名
	j.num=666;
	
	3.场景 
	与sort排序结合运用 
	
	4.sort排序
	sort(数组起始下标,数组结束下标+1,自定义排序规则) 
	
	bool cmp(int a,int b){
		return a<b;
	}
	int a[6]={3,1,4,2,7,8};
	
	sort(a+0,a+5+1,cmp);

九、指针（变量）
	1. 定义（初始化）
	类型名 *变量名
	int *p=NULL; 
	int a;
	p=&a;	//&取地址 
	*p=20;	//*取值 
	
	2.引用
	
	3.场景（数组、字符串、函数...） 
	设有数组 a，指向 a 的指针变量为 pa，
	则有以下关系：
	pa、a、&a[0]均指向同一单元
	
	指针与字符串： 
	const char* s = "program";
    for (int i = 0; i < 7; i++)
	    cout << *(s + i);
	
十、进制转换
	（一）R进制>十进制：按权展开求和
	位高权重
	一个数的负数次幂=该数的正数次幂的倒数
	任何数的零次幂=1
	pow(x,y)=x的y次幂 
	(1101)2 = (13)10
	
	（二）十进制>R进制：整数(取余倒序) 
	异或  
	
	进制（满几进位） 
	
十一、算法：自然语言、流程图、伪代码
	赋值：箭头
	
十二、队列
	1.定义：只能一端插入另一端删除的线性表
	2.特点：先进先出 
	3. STL：
	声明：queue<数据类型>队名，
	例如：queue<int>q
	相关函数：
	q.push();        添加元素
	q.front();        获取队首元素
	q.pop();        删除队首元素
	q.size();        获取元素个数
	q.empty();    判断队列为空

	优先队列:
	priority_queue<数据类型> q;        //声明一个用来存某数据类型的优先队列，名字叫q
	相关函数（其他同队列）：
	q.top();    获取队首元素，队列用的是q.front();
	priority_queue<int>q;        //默认是大的先出来
	priority_queue<int,vector<int>,less<int> >q1;        //大的先出来
	priority_queue<int,vector<int>,greater<int> >q2;    //小的先出来
	
	4.自己写：（详见后附） 

十三、栈
	1.定义：只能一端插入或删除的线性表
	2.特点：先进后出 
	3. STL：
	声明：stack<数据类型>栈名，
	例如：stack<int>s
	相关函数：
	s.push();        元素入栈
	s.top();        获取栈顶元素
	s.pop();        删除栈顶元素
	s.size();        获取元素个数
	s.empty();    判断栈为空
	4.自己写： （详见后附）

十四、顺序表
//顺序表基本运算算法
#include <stdio.h>
#include <malloc.h>
#define MaxSize 50
typedef int ElemType; 
typedef struct 
{	ElemType data[MaxSize];		//存放顺序表元素
   	int length;					//存放顺序表的长度
} SqList; 						//顺序表的类型
void CreateList(SqList *&L,ElemType a[],int n)
//建立顺序表
{
	L=(SqList *)malloc(sizeof(SqList));
	for (int i=0;i<n;i++)
		L->data[i]=a[i];
	L->length=n;
}
void InitList(SqList *&L)
{
	L=(SqList *)malloc(sizeof(SqList));	//分配存放线性表的空间
	L->length=0;
}
void DestroyList(SqList *&L)
{
	free(L);
}
bool ListEmpty(SqList *L)
{
	return(L->length==0);
}
int ListLength(SqList *L)
{
	return(L->length);
}
void DispList(SqList *L)
{
	for (int i=0;i<L->length;i++)
		printf("%d ",L->data[i]);
	printf("\n");
}
bool GetElem(SqList *L,int i,ElemType &e)
{
	if (i<1 || i>L->length)
		return false;
	e=L->data[i-1];
	return true;
}
int LocateElem(SqList *L, ElemType e)
{
	int i=0;
	while (i<L->length && L->data[i]!=e) i++;
	if (i>=L->length)
		return 0;
	else
		return i+1;
}
bool ListInsert(SqList *&L,int i,ElemType e)
{
	int j;
	if (i<1 || i>L->length+1 || L->length==MaxSize)
		return false;
	i--;						//将顺序表位序转化为elem下标
	for (j=L->length;j>i;j--) 	//将data[i]及后面元素后移一个位置
		L->data[j]=L->data[j-1];
	L->data[i]=e;
	L->length++;				//顺序表长度增1
	return true;
}
bool ListDelete(SqList *&L,int i,ElemType &e)
{
	int j;
	if (i<1 || i>L->length)
		return false;
	i--;						//将顺序表位序转化为elem下标
	e=L->data[i];
	for (j=i;j<L->length-1;j++)	//将data[i]之后的元素前移一个位置
		L->data[j]=L->data[j+1];
	L->length--;				//顺序表长度减1
	return true;
}
 
十五、二分法
使用前提：有序性 

核心代码： 
mid=l+(r-l)/2; 	//取中点值
r=mid-1; 		//向左半找
l=mid+1; 		//向右半找

典型题目：
二分查找：P2249
二分答案： 
P1873 砍树
P2440 木材加工
P1577 切绳子
P1102 A-B数对
P1824 进击的奶牛
P1182 数列分段 Section II