【PAT乙级】一百一十道真题刷后大汇总——C/C++

避免精度丢失

所有的计算最后都是转换成二进制进行计算的，所以浮点计算时候，有时会出现精度流失的问题。
解决方法：
尽量转换成long型计算，最后再换成浮点型输出结果。

刷题时候测试点也不一定会考察这方面，但当很多个浮点型数据运算时候丢失精度就更明显了。当题目中告诉我们每个数的小数点最高几位的时候，我们还是最好先转换成long型最后再换回来，这样更为准确。

查询数据是否存在

如果可以在set和map中进行查询find，就别在vector容器中查询用find，因为vector中的find的algorithm的find，时间复杂度是O(n)，而set和map是自带的函数，内部结构是红黑树。
但是如果是set和map的话，用count就可以了，因为他们内部都不是重复的。时间复杂度和find一样是(logn)；
用map.count(key)是否大于0查找数据应该是用的比较多的。

容器之间的比较是否相等

有时需要把答案放在容器内，然后把所写的放另一个容器里，比较是否与答案相等，这个时候就有必要用到容器之间是否相等。
容器之间比较内部所有元素是否相等，可以直接用**==**
如果两个容器的长度相同且对应位置元素都相等，则两个容器就相等，否则不等。

和Java中重写equals后用equals方法有点像。

缓存区中字符残留问题

使用cin输入数据后，会残留空格或者回车符在缓存区中；
使用getline输入数据后，不会有回车在缓存区中。

#include
#include
using namespace std;

int main(){
char ch;
string s,s1;
cin >> s;
getline(cin,s1);

cout << s << endl;
cout << s1 << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

输入：
a b
输出：
a
 b
输入：
 ab

输出：
ab

1
2
3
4
5
6
7
8
9
10
11

出现需要处理字符的原因：
是因为cin遇到空格或者回车字符时，是作为结束符的，但是其本身还是存留在缓冲中，遇到要么作为结束符要么就是直接跳过。既然在缓冲中，如果不需要就需要将其除去；

解决方法：

1. 使用scanf读取掉那个字符；
2. 使用getchar()读取掉那个字符；
3. 有必要的话用getline读取掉也许。
   例子：
   
   输入后要输入字符串，可以先去清楚缓冲区

巧妙输入

cin肯定是比scanf方便的，但有很多时候还是用scanf比较的好。
比如要输入年：月：日用cin肯定是不好实现的，用scanf("%d:%d:%d",&year,&month,&day);肯定会方便简洁。
并且学会输入数据的同时，处理数据，这样可以达到简洁代码，防止代码重复。
下面就是个好例子：

巧妙使用hash数组

使用数组达到hash的目的是比使用map要方便很多的，我们可以利用它的索引以及对应的值表示不同的含义。
比如：
索引表示学号，值表示排名；
索引表示学号，值表示是否存在；
索引表示时间，值表示数据量；
索引表示某字符的ASCII码，值表示是否存在等等。
通过hash数组，可以让我们查询结果更快，效率更高！

简单数学

质数

bool is_prim(int n){
	if(n<2) return false;
	for(int i=2;i*i<=n;++i){
	if(n%i==0) return false;
}
	return true;
}
1
2
3
4
5
6
7

俩数最大公约与最小公倍

假设有俩数a和b，最大公约数gcd和最小公倍数lcm的乘积应该为a*b；
最大公约数：

//a大于b
int gcd(int a,int b){
	return a%b==0?b:gcd(b,a%b);
}
1
2
3
4

数因子

void ff(int n,vector<int> &res){
	for(int i=1;i<=n;++i){
	if(n%i==0)
		res.push_back(i);
}
}
1
2
3
4
5
6

常用的头文件及其内部函数

只说用的部分函数，咋用这里木得

< map >

map_name.count(key);//这个可以用来判断某个数是否存在
map_name.find(key)!=map.end();//和上面一样
map_name[key] = value;//插入某对键值对
map_name.erase(key);//删除为key的键值对
1
2
3
4

< set >

set_name.count(x);//这个可以用来判断x是否存在
set_name.find(x)!=map.end();//和上面一样
set_name.insert(x);//向set容器内插入数据x
1
2
3

< pair >

这没啥，就相当于下面的结构体：

struct node{
	数据类型 first;
	数据类型 second;
}
1
2
3
4

< string >

string_name.substr(startIndex,length)//从startIndex下标开始截取length长度的字符串
string_name.erase(pos)//删除pos下表的字符
string_name.insert(pos,n,ch)//在pos处插入n个ch字符
❤️int res = stoi(string_name);//字符串转换成十进制
❤️string res = to_string(int val);//转换成字符串里面可以是各种基本数据类型的变量
string_name.c_str();//string与const char*指针之间了转换
1
2
3
4
5
6

< vector >

这个动态数组就不说了，没啥需要特指的，还有stack和queue容器，这里不列举。

< algorithm >

stl中的这个好用的函数太多了

max(x,y)
min(x,y)
swap(x,y)
abs(x)//x是整型的
reverse(it1,it2)//这里的it1和it2是指迭代器
fill()//填充
sort()
1
2
3
4
5
6
7

< cctype >

isalpha()
isdigit()
islower()
isupper()
1
2
3
4

还有什么toupper、tolower这样的，想转换我们直接ch ^= 32;用异或解决即可。

< iomanip >

setw()//域宽
setfill()//域填充
setbase()//进制
1
2
3

这里有俩好用的函数，用于字符串匹配：

int sscanf(const char *str, const char *format, …)
int sprintf(char *str, const char *format, …)

sscanf是将str字符串转换成对应的数据的，是从左到右按字符串匹配得到转换的操作；
sprintf是将数据转换成字符串，是从右到左匹配的一个转换操作；
如果使用这个想用到string，那么可以使用string中的c_str()函数，也可以对其进行操作了。

#include
#include
#include
using namespace std;

int main(){
char ch;
string s,s1;
getline(cin,s);
double f = 0.0;
char x[10];
sscanf(s.c_str(),"%lf",&f);
cout << f << endl;
sprintf(x,"%.2lf",f);
cout << x << endl;
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

输入：
66
输出：
66
66.00

输入：
89.356
输出：
89.356
89.36

输入：
3.23
输出：
3.23
3.23

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

注意：里面的首个参数是char*指针，用string时可以通过c_str()函数使用sscanf，而用sprintf要用char类型数组。
sscanf和sprintf成功的话会有返回值的，整型的，如果成功会返回1；
例子：

常见的一些问题

上面说的俩函数是不能用的，to_string可以转换成string类型的，然后再调用c_str()也是可以达到那个itoa的效果的，所以不能用也没关系。

1. 浮点错误：运行时发生浮点错误，比如遇到了除以 0 的情况；
2. 段错误：一般发生在数组越界了；
3. 输出超时，运行超时：先去看看存不存在死循环；
4. 格式错误：检查自己输出是否符合要求，比如空格什么的。

最后总结

1. 写题还是要仔细，比如看清要输入的字符串是否包含空格，没说包含一般就是有空格的，此时使用cin有些测试点就会出问题了；
2. 看清题目给的范围或者说是几位，有的时候给的学号就会说几位，巧妙利用所给的条件；
3. 认真看输出条件防止格式错误，比如末尾不留空格（经常），末尾不留回车符（有，但比较少）等等；
4. 还是说认真读题的问题，什么怎么输入啊，什么条件下该干什么呀这样的；
5. 每个题设计出来肯定都会有其解决算法的（当然每题可用的算法可能会有多种，尽量想最方便自己的），先想再动笔，这样一不容易出错，二会提高速度；
6. 也别轻易的去提交，先过样例再去提交，别求速度求稳；
7. 最后希望过几天的考试可以多考几分吧，希望这110题没有白刷，加油。