入门语法及STL容器

基本框架

1
2
3
4
5
6
7
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
	......
	return 0;
}
1
2
3
4
5
6
7
#include<bits/stdc++.h>
#define int long long 
using namespace std;
signed main(){
	......
	return 0;
}

输入

  • 整型或浮点数的输入

​    int a; cin >> a;

  • 不含空格的字符串输入(scanf或cin)

1.char数组

​    char str[100010]; scanf(“%s”,str) ; 或 cin >> s; （下标从0开始）

​    char str[100010]; scanf(“%s”,str+1) ; 或 cin >> s+1; （下标从1开始）

​    长度：strlen(s) / strlen(s+1)

2.string类型

    string s; cin>>s ;

    下标从1开始： s=” “+s;

     长度：s.size() 或 s.length()

  • 含空格的字符串输入 —— getline(cin,s) (天梯赛必学，其余不用学)

1.单行输入

​     string str; getline(cin,str);

2.多样例输入 （预先使用getchar()或cin.ignore()）

1
2
3
4
5
6
7
int t;string str;
cin>>t;
getchar();/cin.ignore();  //由于上面的cin>>t自动产生了回车，使用getchar()/cin.ignore()消除，否则会被吞一组循环
while(t--){
	getline(cin,str);
	...
}

输出

  • 整型或字符串输出

​ cout << ans1 <<’ ‘<< ans2 << ‘\n’ ;

​     PS: 换行记得使用‘\n’不要使用endl，前者速度远快于后者！

  • 浮点数

​     printf(“%.xlf”,sum); // 输出浮点数sum并保留x位小数

​     printf(“”%.xlf \n“,sum); //嵌套换行操作

常见系统函数

  • max(int a,int b) : 返回两者最大值 (以int类型为例)
  • min(int a,int b) : 返回两者最大值 (以int类型为例)
  • sqrt(double x) : 返回浮点数类型的开方值
  • pow(double x,double y) : 返回浮点数类型的 $x^y$
  • __gcd(int a,int b) : 返回两数的最大公因数 (比手写的慢)
  • to_string(int x): 将数字$x$转换为字符串
  • stoi(string str):将字符串$str$转换为int类的整数  stoll(string str):将字符串$str$转换为long long类的整数

排序

    直接调用系统API，选择函数sort()，不要手写！！！！！！手写一定没有系统的快

    要点：左闭右开

    给定数组$a_1 - a_n$ ，对该数组升序排序 [1,n+1)

sort(a+1，a+n+1) ;

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
#define int long long 
using namespace std;
int a[100010];
signed main(){
	int n;cin>>n;
	for(int i = 1; i < n + 1; i++)
		cin >> a[i];
	sort(a + 1, a + n + 1);
	for(int i = 1; i <= n; i++)
		cout << a[i] << ' ';
	return 0;
}

寻找最值

例：寻找数组元素的最小值

1
2
3
4
5
6
7
8
9
10
signed main(){
	int n;
	cin >> n ;
	for(int i = 1; i < n + 1; i++)
		cin >> a[i];
	int mn = 2e9; //找最小值理应初始化为无穷大，根据题意初始值高于最大的可能值，找最大值反之
	for(int i = 1; i <= n; i++)
		mn = min(mn, a[i]); // 核心语句
	return 0;
}

函数

<数据类型> <函数名>(<数据类型> <参数>){

​ ……

​ return <>;

}

  • 有返回值

例：函数含有参数x，函数运算得到的答案为ans

1
2
3
4
5
int/double/string solve(int x){
	int ans=0;
	...
	return ans;
}
  • 无返回值 (void)
  1. 不使用return返回任何值，函数只用于模拟功能
  2. 使用return; 用于退出函数 
1
2
3
4
5
6
7
void solve(int x){
	int ans=0;
	...
	return; //可用于退出函数
	...
	（不加return）
}

结构体及排序

结构体用struct表示，类似于含有多个属性的对象，即含有不同变量.

定义：

struct [结构体类型]{

​ // [数据类型1] [变量1]；

// [数据类型2] [变量2]；

​ …

} [变量名]；(可以定义为数组)

例：struct node{

​ string name;

​ int chn,mths,eng;

​ int sum;

} stu; / stu[10010] ;

  • 输入/赋值操作：cin >> stu[i].name; / stu.name = “” ; // stu[i].chn=100 ……

    结构体排序：书写bool类的比较函数 (“<”表示升序，”>”表示降序)

    例1：对总分成绩(sum)进行排序

1
2
3
4
bool cmp(node x,node y){
	1. return x.sum < y.sum; //升序
	2. return x.sum > y.sum; //升序
}

    例2：对总分成绩(sum)进行降序排序，若总成绩相同，则依次按照语文、数学、英语成绩降序排序（不存在两人成绩完全相同的情况）

1
2
3
4
5
6
7
8
9
10
bool cmp(node x,node y){
	if(x.sum != y.sum)
		return x.sum > y.sum;
	else if(x.chn != y.chn)
		return x.chn > y.chn;
	else if(x.mth != y.mth)
		return x.mth>y.mth;
	else
		return x.eng>y.eng;
}

    在处理完各个结构体元素和比较函数后，使用sort函数：

1
sort(stu+1,stu+n+1,cmp);

常见数学知识所用函数：

  1. 判断$x$是否为质数
1
2
3
4
5
6
7
bool isPrime(int x){
	if(x==1)return 0;
	for(int i=2;i*i<=x;i++)  //注意i只需遍历sqrt(x)即可
		if(x%i==0)
			return 0;
	return 1;
}
  1. 求$a$ 和 $b$ 的最大公因数（手写辗转相除法）
1
2
3
4
int gcd(int a,int b){
	if(b==0)return a;
	else return gcd(b,a%b);
}
  1. 求$a$ 和 $b$ 的最小公倍数 （前置需先求最大公因数）
1
2
3
int lcm(int a,int b){
	return a*b/gcd(a,b);
}
  1. 求$x$ 的因子总数
1
2
3
4
5
6
7
8
9
int calc(int x){
	int cnt=0;
	for(int i=1;i*i<=x;i++){
		if(x%i==0) // i为因子
			cnt++;
		if(i*i<x) // 排除平方数的最大因子，此时x/i也是因子
			cnt++;
	}
}
  1. 求$x$的数位和
1
2
3
4
5
6
7
8
int calc(int x){
	int sum=0;
	while(x>0){
    	sum+=x%10;
    	x/=10;
	}
	return sum;
}

常见STL容器

1. vector(动态数组)

    vector是一种动态数组，能够实现动态分配数组长度并对其下标进行随意访问.

定义：vector<[数据类型]> [变量名]

    例： vector< int> v;

  • v. push_back(x) : 末尾添加一个$x$

  • v. pop_back() : 删去一个末尾的值

  • v. size() : 输出容器的总长度

  • v[id] : 输出下标为id的值(默认下标从0开始)

  • sort(v.begin(), v.end()) : 对该容器的各个元素升序 $O(n \log n)$

  • 遍历操作（两种操作）：

1
2
3
4
5
for(int i=0;i<v.size();i++)
	cout<<v[i]<<' ';

for(auto it:v)
	cout<<it<<' ';

    注：所有使用auto进行遍历的，编译环境不得低于C++11

2. map(哈希表)

    map是一种映射关系，含有键和值，每个键对应一个值，其数据类型无限制.

定义：map<[键类型],[值类型]> [变量名]

    例：统计某字符串的出现次数，设map< string , int> mp; 键为string类型，值为int类型

  • 赋值操作等价于数组操作：mp[x]++ / mp[x] = y / ……

  • mp[x] :输出键为$x$时的值

  • mp.size() :输出容器中访问过的键值的数量

  • mp.count(x) :判断键为$x$是否访问过，若不存在返回false(0)，反之为1.

  • 遍历：
1
2
for(auto it: mp)
	cout<< it.first << ' ' << it.second << endl; // 顺序输出所有键和值

​     需注意，在遍历的过程中map按键的大小/字典序升序排列.

4.set(集合) /multiset(多元集合)

set表示一种集合，具有无异性的特征，每个元素只存在一种，即去重功能；同时，set元素内自动升序.

定义：set <[数据类型]> [变量名]

例：set< int> se;

  • se.insert(x) : 插入元素$x$

  • se.erase(x) : 删除元素$x$

  • *se.begin() : 输出集合的最小值

  • *se.rbegin() : 输出集合的最大值
  • 遍历：
1
2
for(auto it: se)
	cout << it << ' ';

    multiset是集合的拓展，表示多元集合，每个元素可多次出现，也有自动升序的功能，功能上完全平替优先队列(所以优先队列就不写了)，最大的作用就是以$O(\log n)$的时间复杂度得到最大最小值，并高效插入和删除.

例： multiset < int> se;

  • se.insert(x) : 插入元素$x$
  • se.erase(x) : 删除所有元素$x$

  • se.extract(x) : 删除单个元素$x$

  • *se.begin() : 输出集合的最小值

  • *se.rbegin() : 输出集合的最大值

  • 遍历：

1
2
for(auto it: se)
	cout << it << ' ';