基本语法回顾

语句与字符串

在c/c++/java中，一个语句一般是以分号结尾，而python中，语句之前由换行进行控制。

语句有以下几种：

  • 表达式语句

    • a=3;
    • b/=2;

  • 函数调用语句

    • printf("123"); a=Math.max(a,b); a=input().split('')
    • dfs1(1,-1);

  • 控制语句

    • 条件：if(a<b)....
    • 循环：while(t--)....
    • 转向：break;

  • 复合语句

    • a=1,b=2;
1
2
3
4
while(x<3){
    x++;
    printf(“%d\n”,&x);
}
  • 空语句
    • if(x>0);

需要注意的关键点：

  1. 所有符号一定要用半角符号（英文符号）！

  2. =表赋值，==表相等

  3. 无论什么情况，所有括号必须匹配！（包括小括号中括号大括号）

  4. 不要丢失语句结尾的分号（除了选择和循环语句以外的所有语句）

顺序、选择、循环

  • 顺序结构

    • 语句1;
    • 语句2;

  • 选择结构

1
2
3
if(判断条件){
    语句;
}
  • 循环结构
1
2
3
while(判断条件){
    语句;
}

需要注意的点：

  1. 一定要考虑到语句的先后次序

  2. 使用具体什么样的语句没有好坏之分，根据自己的习惯和具体情况

1
2
3
4
5
6
7
8
9
if(a==1)....
else if(a==3)....
else...
//等价于
switch(a){
case 1:... break;
case 3:... break;
default:... break;
}

变量、数组、结构体

  • 变量是程序中可以变化的量
1
2
int x;
double y;

任何情况下，变量必须先声明再使用！！！

  • 数组是很多同类变量的列表
1
2
3
例如：
	int a[10];
	我们就有a[0],a[1],a[2]...a[9]这10个int型变量

重要！！！不要越界！！！！

  • 结构体是自己定义的变量类型，可以拥有很多属性
1
2
3
4
5
6
7
8
9
例如：
	struct people{
			int high;
			string name;
	};

 	people p1;
	p1.high=160;
	p1.name=”ranko”;
  • 结构体也可以开数组。使用和普通数组是一样的。
1
2
3
4
5
6
例如：
	people p[10];
	for(i=0;i<10;i++){
			p[i].high=i;
			p[i].name=”123”;
	}

函数和递归

函数为一些语句的集合，可以调用函数来执行这些语句。

函数有两种，带返回值的和无返回值的。

1
2
3
4
5
6
7
8
9
例如：
	int add(int a,int b){
		return a+b;
	}
	int main(){
		int a=1,b=2,c=4;
		a=add(b,c);
		...
	}

函数也是必须先声明再使用，所以我们一般把函数写在main函数的上面。

递归指函数调用自己。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
例如：
	int f(int x){
		if(x==0)return 1;
				return f(x-1)*2;
		}
	//该函数职能上等价于：
	int f(int x){
		int res=1;
		while(x>0){
				res*=2;
				x--;
    }
		return res;
  }

请注意函数的作用范围！

1
2
3
4
5
6
7
8
9
10
int y=5;
void f(int x,int y){
    x++;
    y--;
}
int main(){
    int x=1;
    f(x,y);
    cout<<x<<" "<<y;
}

STL

pair

二元组。可以看成是如下定义:

1
2
3
struct pair{
		int first,second;
};

一般 pair 型变量定义的方式是：

1
2
pair<int,int>p;
pair<double,double>a[222];

pair 数组默认排序的依据是：优先按 first 升序进行排序。若 first 相等则按 second 升序进行排序。

vector

可变长度的数组。

主要用法如下：

  • vector<int>a; // vector 的定义
  • a.push_back(x); //在 a 的最后新增一个数 x
  • a[i]; //调用 a 的下标 i 对应的数
  • sort(a.begin(),a.end()); //对 a 数组(升序)排序

重点：使用vector建图的技巧

要求：第一行输入 n 和 m，代表点数和边数。 接下来的 m 行，每行输入两个数 x 和 y，代表 x 和 y 有一条无向(有向)边

【样例输入】

45
12
23
42
14
34

建图的代码（请务必理解记忆，如果不能理解那么就当模板记下来）:

1
2
3
4
5
6
7
8
9
vector<int>a[100010]; //建议 vector 数组开大点
    int n,m;
    cin>>n>>m; //n 代表顶点数量，m 代表边数量 
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x); //如果是有向边，该行省略
    }

stack/queue/deque/priority_queue

stack，即栈。

  • stack<int>s; // 栈的定义
  • s.push(x); // 将 x 压入栈顶
  • int tp=s.top(); // 拿到栈顶元素(但不出栈)
  • s.pop(); // 栈顶元素出栈
  • s.empty(); // 返回一个bool型，若栈为空返回 ture，否则返回 false

queue，即队列。

  • queue<int>s; // 队列的定义
  • s.push(x); // x入队
  • int tp=s.front(); // 拿到队首元素(即将出队的元素)，但不出队
  • s.pop(); //队首出队

deque，即双端队列，也叫双向队列。deque 的功能包含了栈和队列的功能，强烈建议大家掌握并熟练使用。

  • deque<int>s;
  • s.push_back(x); // 队列末尾插入 x
  • s.push_front(x); // 队列开头插入 x
  • s.pop_back(); // 队列末尾弹出
  • s.pop_front(); // 队列开头弹出
  • int ed=s.back(); // 获取队列末尾的值，但不弹出
  • int op=s.front(); // 获取队列开头的值，但不弹出

priority_queue，即优先队列。作用和最大(小)堆一样，可以 O(logn) 复杂度插入一个数/弹出一个当前所有数最大(小)值。

  • priority<int>q; // 优先队列的定义
  • priority_queue<int,vector<int>,greater<int>>q; //弹出最小值的优先队列的定
  • q.push(x); // x 压入优先队列
  • int max=q.top(); // 返回最大值，但不弹出
  • q.pop(); //弹出最大值

结构体优先队列的使用:

两种方法:

  1. 重载小于号
1
2
3
4
5
struct node{ 
		//...
    bool operator<(const node& a)const{...} 
};
priority<node>q;
  1. 重写仿函数
1
2
3
4
5
6
7
struct node{ 
		//结构体
};
struct cmp{
    bool operator()(node a,node b){...} 
};
priority<node,vector<node,cmp>q;

第一种方法适用于只需要一种优先队列。

如果需要多种优先队列，则用第二种方法(可以用多种 cmp 定义不同的优先队列)。

map

map 提供一对一的哈希。map 的调用/赋值均为 O(logn) 复杂度。

  • map<int,int>m; // 前一个为 key，后一个为 value
  • m[1]=2; // 将键值为 1 的 value 赋值为 2
  • m[99999999]=3; // 将键值为 99999999 的 value 赋值为 3

set/multiset

set：集合。每种元素最多出现一次。可以 O(logn) 插入/删除/查询。

  • set<int>s; // 定义一个set
  • s.insert(1); //往set里添加一个1
  • s.erase(1); //将set里的1删除
  • if(s.count(x)).... // 判断set里是否有x。由于set无重复，所以count的值只有可能1或0

迭代器

迭代器有多种用法：容器的遍历，二分等

set 的遍历:

1
2
3
4
set<int>s;
for(set<int>::iterator it = s.begin(); it!=s.end(); it++){
		cout<<(*it); 
}

map 的遍历：

1
2
3
4
5
map<string,char>m;
for(map<string,char>::iterator it = m.begin(); it!=m.end(); it++){
    cout<<(*it).first<<endl; //输出 key
    cout<<(*it).second<<endl; //输出 value 
}