PAT总结
以下均使用C++语言，请保证C++11特性和相应头文件支持
刷题模板
为了解决PAT刷题过程中每次都要敲头文件，并且要对测试示例进行输入测试，特使用模板来提高效率。一方面，模板包含了基本所有能用到的头文件；另一方面，模板使用文件的方式引入输入的测试点数据，让输入测试更加便捷。
模板直接使用即可，在中间按插入解题所用代码，以及需要定义的变量；在cpp文件所在的同一文件夹下创建1.txt
#include<iostream> //输入输出流头文件
#include<stdio.h> //标准输入输出
#include<stdlib.h>
#include<math.h> //数学函数
#include<string.h> //C语言字符数组的字符串
#include<algorithm> //C++标准模板库的函数
#include<map> //map映射容器
#include<unordered_map> //无序的map映射容器
#include<vector> //变长数组容器
#include<queue> //队列
#include<stack> //栈
#include<string> //C++string类
#include<set> //set集合
using namespace std; //标准命名空间
//可以加入全局变量或者其他函数
int main(){ //主函数
#ifdef ONLINE_JUDGE //如果有oj系统（在线判定），则忽略文件读入，否则使用文件作为标准输入
#else
freopen("1.txt", "r", stdin); //从1.txt输入数据
#endif
//加入自己的代码
return 0; //返回0，如果不返回0，PAT会报错
}或者：
#include<bits/stdc++.h>
using namespace std;
int main(){
#ifdef ONLINE_JUDGE
#else
freopen("1.txt", "r", stdin);
#endif
return 0;
}输入与输出
格式化输入输出
printf和scanf
printf输出
printf用于格式化的输出，包括类型转换说明符和，输出数值参数。printf()函数是有返回值的，其返回值为printf(“fafkdsafkld")
//printf的基本格式
printf("%d",a);- 类型转换说明
| 转换说明 | 输出 |
|---|---|
| %a | 浮点数，十六进制和p记数法 c99/c11 |
| %A | 浮点数，十六进制和p记数法 c99/c11 |
| %c | 单个字符 |
| %d | 有符号十进制数 |
| %e | 浮点数，e记数法 |
| %E | 浮点数，E记数法 |
| %f | 浮点数，十进制计数法 |
| %g | 根据值的不同，自动选择%f或者%e，%e格式用于指数小于-4或者大于或者等于精度时 |
| %i | 根据值的不同，自动选择%f或者%E，%E格式用于指数小于-4或者大于或者等于精度时 |
| %o | 有符号十进制数，和%d相同 |
| %p | 指针 |
| %s | 字符串 |
| %u | 无符号十进制整数 |
| %x | 无符号十六进制整数，使用格式0f |
| %X | 无符号十六进制整数，使用格式0F |
| %% | 打印一个百分号% |
- 常用转换说明的修饰符
| 修饰符 | 含义 |
|---|---|
| 标记 | 使用多种标记，来限制格式 |
| 数字 | 表示输出的最小宽度 如果该修饰小于实际需要打印的字符长度，则自动使用更宽的字段 |
| .数字 | 精度 对于%e、%E、%f表示小数点右边的数字的位数 示例:"%5.2f"表示打印一个浮点数，整数部分宽度为5，小数部分宽度为2 |
| h | 和整型转换说明一起使用，表示short int或者unsigned short int |
| hh | 和整型转换说明一起使用，表示short cahr或者unsigned short char |
| j | 和整型转换说明一起使用，表示intmax_t或者uintmax_t类型的值，这些类型定义在stdllib.h中 |
| l （一个小写的L） |
和整型转换说明一起使用，表示long int或者unsigned long int |
| ll （两个小写的L） |
和整型转换说明一起使用，表示long long int或者unsigned long long int |
| L | 和浮点数转换说明一起使用，表示long double类型的值 |
| t | 和整型转换说明一起使用，表示ptrdiff_t类型的值，ptrdiff_t类型是两个指针差值的类型 |
| z | 和整型转换说明一起使用，表示size_t类型的值，即sizeof的返回类型 |
- printf的修饰标记
| 标记 | 含义 |
|---|---|
| - | 打印采用左对齐方式，即从字段的左侧开始打印 |
| + | 显示符号，如果是正数，显示正号+ ；如果是负数，显示负号 - |
| 空格 | 如果是正数，显示一个空格；如果是负数，显示负号- |
| * | 字符宽度的通配符，使用变量指定字符宽度，示例: printf("%*d",w,num); 输出宽度为w的数字num |
| 0 | 对于指定宽度的字符，使用0填充以达到要求的宽度 |
- printf打印较长的字符串
//对于较长的字符串可以分开几段调用printf，也可以在printf的参数中分段，但是每一个分段必须用双引号”“ 包裹起来
//方法一 直接打印
printf("Here is one way to print a long string.\n");
//方法二 分开打印
printf("Here is one ");
printf("way to print ");
printf("print a long string.\n");
//方法三 分段打印
printf("Here is one "
"way to print "
"a long string.\n"); //分段用引号隔开，中间用空白字符分割scanf输入
scanf用于标准输入，包含转换说明和指定的输入对象等参数。scanf（）函数是有返回值的，其返回值为成功读入的项数，当遇到输入不匹配时，返回0，如果到了读取到了文件的末尾，则返回EOF（定义在stdlib.h中的特殊值，用于表示文件末尾），根据返回值可以进行输入匹配的检查。
scanf()的参数中，除了字符串（即c风格字符数组）以外都需要加上取地址符&，示例如下：
//常规读取
int num;
scanf("%d",&num);
//c风格字符串
char s[100];
scanf("%s",s);
%s的转换会自动在字符数组的末尾加上'\0' 作为字符串的结尾标记- 类型转换说明
| 转换说明 | 含义 |
|---|---|
| %c | 把输入解释成字符 |
| %d | 把输入解释成有符号十进制整数 |
| %e、%f、%g、%a | 把输入解释成浮点数（C99增加了%a） |
| %E、%F、%G、%A | 把输入解释成浮点数（C99增加了%A） |
| %i | 把输入解释成有符号十进制整数 |
| %o | 把输入解释成有符号八进制整数 |
| %p | 把输入解释成指针（地址） |
| %s | 把输入解释成字符串，从第一个非空白字符开始，到下一个非空白字符之前的所有字符都是输入 |
| %u | 把输入解释成无符号十进制整数 |
| %x%x | 把输入解释成有符号十六进制整数 |
- 转换说明的修饰符
| 修饰符 | 含义 |
|---|---|
| * | 抑制赋值 示例：scanf("%*d %d",&b); 则跳过第一个输入，把第二个赋值给b |
| 数字 | 读入的最大字段宽度，到达指定宽度时停止，或者在第一次遇到空白字符时停止 |
| hh | 把整数作为signed char 或者unsigned char类型读取 |
| ll （两个小写L） |
把整数作为long long或者unsigned long long类型读取 |
| h、l或者L （大写或者小写的L） |
%hd和%hi表示把值储存为short int型 %ho和%hx和%hu表示把值储存为unsigned short int型 %ld和%li表示储存为long 类型 %lo和%lx和%lu表示储存为unsigned long类型 %le和%lf和%lg便是把值存储为double类型，如果此三种改为大写的L修饰，则表示存储为long double类型 如果没有修饰符，d、i、o、x表示储存为int类型，f和g表示存储为float类型 |
| j | 和整型转换说明一起使用，表示intmax\_t或者uintmax\_t类型的值，这些类型定义在stdllib\.h中 |
| z | 和整型转换说明一起使用，表示size\_t类型的值，即sizeof的返回类型 |
| t | 和整型转换说明一起使用，表示ptrdiff\_t类型的值，ptrdiff\_t类型是两个指针差值的类型 |
- scanf使用技巧之————判定文件结尾
//可以根据返回值判断是否正确读入，或者到了文件末尾，适用于事先不知道有多少输入的情况
while(scanf("%d",&num)==1){ //当成功读入一个整数时，继续循环
}
while(scanf("%d",&num)!=EOF){ //当未读到文件末尾时，继续循环
}字符独有的输入输出
字符也有专用的输入输出函数，常用的有单字符输入输出和字符串的输入输出，如下所示的gtchar()、putchar()、gets()、puts()等，其中gets不够安全，但是不影响常规的使用：
-
单字符输入输出
char ch; //定义单个字符 getchar(); //读入单个字符，不赋值 ch=getchar(); //读入单个字符，赋值给ch putchar(ch); //输出单个字符 //使用技巧之————过滤字符 //为了过滤掉空字符，如空格或者换行，可以使用getchar()的输入特性，吸收字符 while((ch=getchar())!='\n') //一个空循环，一直读到回车处结束 continue; -
字符串的输入和输出
//整行字符串的输入 char words[100]; //定义字符串 gets(words)； //读取整行输入，直至遇到换行符，然后丢掉换行符，储存其他字符，并在结尾加上'\0'的字符结尾标记 //整行字符串的输出 puts(words); //于gets相对应的puts输出一整个字符串，可以是字符变量，也可所以是"Here is a string."这样的字符串常量 //示例 puts("Here is a string."); //puts会自动加上回车换行
sprintf和sscanf
sprintf和sscanf前者可以把相应的字符打印到一个字符数组中，后者可以把一个字符数组按照相应的个数输入到变量中，使用示例如下：
char str[100];
int nun;
sprintf(str,"%d",n); //把n按照%d的格式打印到str中
sscanf(str,"%d",&n); //把str按照%d的格式输入到n中
//使用示例
str="2019/8/19";
int year,mon,day;
sscanf(str,"%d/%d/%d",&year,&mon,&day);
//如果是string类变量，可以使用string类的转化为c风格字符串使用以上函数
string s="2019/8/19";
sscanf(s.c_str(),"%d/%d/%d",&year,&mon,&day);标准输入输出流
cin和cout是c++的标准输入输出流，可以自动识别输入输出的对象，但是控制输入输出格式比较麻烦，且速度不如printf和scanf：
//cin和cout的使用
cin>>a>>b>>c; //多值输入
cout<<a<<b<<c<<'\n'<<' '<<d; //混合输出，包括字符等各种类型
//标准输入输出流的整行输入
//输入整行字符串到string类中，可用一下方式
string str;
getline(cin,str); //getline可以获得整行输入，通过调用cin输入流，把整行字符赋值给string类变量str
//此用法可以吸收掉行末的换行符stl的使用
C++中提供了丰富的stl模板，对于常见的类型或者容器，有了专门的类对象可供使用，这里总结一下容器类和函数类的stl使用方法和格式。stl的使用需要包含相应的头文件，并使用标准命名空间using namespace std
容器类
vector变长数组
vector容器可以认为是一个变长的数组，可以存放任何类型的元素，也可以嵌套使用构成多维数组，使用该类型的基本操作可以简化数据的存储和使用.
//vector数组的定义
//1.常规类型的定义
vector<typename> v; //直接用类型名字定义
//例如:
vector<int> v; //整型
vector<double> v; //浮点型
vector<Node> v; //结构体类型
//2.指定大小的定义
vector<int> v(n); //定义存放n个int型的vector容器
vector<int> v(n,15); //基本类型可以定义时，直接初始化为n个统一的值
//3.二维数组的定义的三种方法
vector<vector<int> > v; //v是包含了多个vect容器的vector容器，> >之间的空格不能省
vector<int> v[100]; //定义100个存放int型数据的变长数组，其中v[0]~v[99]都各是一个变长数组
//二维数组的第二种写法的以为长度已经固定为100，这是和第一种写法的区别
vector<vector<int> > v(m,vector<int> (n));
//定义一个m*n的二维数组
//vector数组的遍历
//vector数组的遍历可以采用常规数组的遍历方法，直接使用下标，或者使用迭代器（类似于指针）的方法
v[i]=0;
v.begin()+i;
//vector数组的常用函数操作，以int型数组为例
vector<int> v;
v.push_back(num); //将num插入到v的尾部，对结构体数组而言，该函数可以插入结构体类型的变量
v.pop_back(); //删除vector尾部的元素
v.size(); //返回数组v的大小
v.clear(); //将v清空
v.back(); //取容器尾部的元素
v.resize(n); //把容器大小需修改为n
v.reserve(n); //把容器的存储能力修改到n，但是size不变
vector<int>:: iterator it=v.begin()+3; //定义一个数组v的迭代器指向第三个位置
v.insert(it,13); //在迭代器it指向的位置插入元素13
v.erase(it); //删除迭代器指向的元素
v.erase(first,last); //删除迭代器[first,last) 左闭右开的区间内的元素
v1.assign(v2.begin(),v2.end()); //将v2数组赋值给v1，会清除v1以前的内容
v.insert(v.end(),v1.begin(),v1.end()); //将v1插入到v的后边set集合
set集合内部是一个自动有序且不包含重复元素的容器，使用方法如下：
//set的定义
set<typename> se; //定义方法于vector类似
set<typename> se[100]; //多维的set，从se[0]~se[99]都各是一个set容器
//set的常用函数
se.insert(x); //将x插入到set容器中给，自动递增排序并去重
se.find(value); //返回set杜勇value的迭代器
set<typename>:: iterator it; //定义一个set的迭代器变量it
se.erase(it); //删除迭代器it指向的元素
se.erase(value); //删除value元素
se.erase(first,last); //删除迭代器[first,last)左闭右开区间内的元素
se.size(); //返回set容器内的元素个数
se.clear(); //清空set中所有的元素map映射容器
map容器是一种反应映射关系的容器，可以映射各种类型，包括基本数据类型、结构体和STL容器，且map内部自动按照关键字升序排列，unordered_map是一种内部无序的map容器。
//map映射的定义
//map映射需要确定关键字key到值value的映射，因此需要确定两种类型
map<typename1,typename2> mp; //定义typename1类型到typename2类型的映射容器mp
map<int,string> mp;
//映射可以针对任意类型，包括结构体和容器
//map的访问和遍历
//mp的访问可以直接通过关键字key访问，或者使用迭代器
mp[342]="Hello"; //赋值一对映射关系
cout<<mp[342]; //直接使用key值访问
//正序遍历
map<int,string>:: iterator it; //正序遍历迭代器
for(it=mp.begin(),it!=mp.end();it++){
cout<<it->first<<' '<<it->second; //使用迭代器访问key和value的值，类似于指针的写法，it->first表示key值，it->second表示value的值
}
//逆序遍历
map<int,string>:: reverse_iterator it; //逆序遍历迭代器
for(it=mp.rbegin(),it!=mp.rend();it++){
cout<<it->first<<' '<<it->second; //使用逆序迭代器，起始迭代器变为mp.rbegin(),结束判定编程mp.rend();
}
//map的常用函数
mp.find(key); //在mp中查找key，如果存在返回迭代器，如果不存在返回mp.end()
mp.erase(it); //删除迭代器it指向的映射
mp.erase(key); //删除key的映射关系和元素
mp.size(); //返回mp的大小，即映射对儿的个数
mp.clear(); //清空mp容器C++11中的auto关键字
C++11特性中有自动类型，因此，这些迭代器的定义可以直接使用auto类型
for(auto it=mp.begin(),it!=mp.end();it++){
cout<<it->first<<' '<<it->second;
}queue队列
队列是一种先进先出的容器，其定义和使用与其他容器相似：
//队列的定义
queue<typename> q; //定义typename类型的队列
//queue的常用函数
q.push(x); //把x入队
q.pop(); //不需要参数，把队头元素出队
q.front(); //读取队头元素
q.back(); //读取队尾元素
q.empty(); //判断队列是否为空，若空，返回true，否则返回false
q.size(); //队列的大小priority_queue优先级队列
优先级队列底层是使用堆实现的，优先级队列中，队首元素一定是当前队列中优先级最高最高的一个，其定义和使用如下；
//priority_queue的定义
priority_queue<typename> pq; //定义一个优先级队列，元素类型可以是结构体
//priority_queue的常用函数
pq.push(x); //将元素x入队，并自动实现优先级排序
pq.top(); //读取队首元素
pq.pop(); //队首元素出队
pq.empty(); //判断是否队空
pq.size(); //队列的大小
//为基本数据类型设定优先级，如int char double类型等
priority_queue<int,vector<int>,less<int> > pq; //int型队列，底层使用vector实现排序
//less<int>表示数字越大，优先级越大;如果使用greater<int> 表示数字越小，优先级越大
stack栈
栈是一种后进先出的数据结构，这里的stack便是这样一种容器，其定义与基本使用方法如下：
//stack的定义
stack<typename> st; //栈的定义
//stack的常用函数
st.push(x); //把x入栈
st.pop(); //栈顶元素出栈
st.top(); //读取栈顶元素
st.size(); //栈的大小
st.empty(); //栈判空栈以及队列的pop、top、front等操作要预先验证栈或者队列是否为空，否则会出错
string类
string类是C++中的一种特殊的字符串类型，对字符串进行了封装，将很多常用的操作放在类中，方便了字符串的操作和使用。
//string类型的定义与基本数据类型的定义相同
string str; //定义字符串类型变量
//string类的初始化为空的方法
//方法一 直接定义为空字符串
string str=""; //直接定义为空字符串
//方法二 定义为任意的字面量，然后使用clear函数清空
string str="hello"; str.clear(); //定义后清空
//string类的输入输出和访问，只能使用cin和cout，或者转为c风格字符串输出
cin>>str; //输入和输出
cout<<str;
getline(cin,str); //整行输入
str[0]='A'； //使用下边直接访问，并赋值为一个字符，也可以使用迭代器访问
//string类的常用操作
//重载的 + 操作，使用+ 可以将string类进行拼接,并用等号= 进行赋值
string str1,str2,str3;
str1=str2+str3;
//重载的比较操作 == != < <= > >=等比较操作都按照字典序进行比较
if(str1==str2){ } //可直接比较
if(str1!=str2){ }
if(str1>str2){ }
if(str1<str2){ }
str.size(); str.length(); //返回str字符串的长度
str.insert(pos,str2); //在str的下标pos处插入str2字符串
str.insert(it,it1,it2); //在str迭代器为it处插入某个字符串[it1,it2)区间内的字符串
str.push_back('A'); //在str字符串的尾部插入一个字符
str.erase(it); //删除迭代器it指向位置的字符
str.erase(first,last); //删除迭代器[first,last)左闭右开区间内的所有字符
str.erase(pos,length); //删除从下标pos开始（包含pos位置）往后的长度为length的字符
str.clear(); //清空字符串
str=str1.substr(pos,len); //把str1中从下标pos位置开始（包含pos位置）往后长度为len的字串赋值给str
string::npos //一个常数，组为find函数失配时的返回值，一般等于-1或者4294967295（unsigned int的最大值）
str.find(str1); //查找str2在str中第一次出现的位置，如果匹配不到返回string::npos
str.find(str1,pos); //查找str2在str中从pos位置开始第一次出现的位置，如果不匹配，返回string::npos
reverse(str.begin(),str.end()); //reverse函数将str进行逆转操作heap堆
STL中的heap（堆），使用完全二叉树实现。在STL中，heap有一些可用的函数供我们使用，可以很方便的解决设计堆的问题：
//建堆，make_heap函数可以把容器中的元素按照堆的规则排序
make_heap(first,last); //把容器中从迭代器[first,last)区间内的元素按照堆的规则排好，默认大根堆
make_heap(first,last,cmp); //指定比较函数的堆
//示例
make_heap(v.begin(),v.end(),less<int>()); //默认的大根堆
make_heap(v.begin(),v.end(),greater<int>());//小根堆
//push_heap函数可以实现把一个元素插入到堆中
//push_heap函数像make_heap一样也有两个版本，一个默认，另一个可以指定比较函数
make_heap(v.begin(),v.end()); //插入前保证已经是一个堆
v.push_back(5); //向容器中增加一个元素
push_heap(v.begin(),v.end()) //将新插入的元素插入到前部的堆中
//注： push_heap(first,last);的操作必须保证[first,last-1)已经是一个堆，push_heap只会把最后一个元素插入到之前的堆中
//pop_heap函数把first堆顶元素交换到尾部last-1，然后把[first,last-1)建成一个新堆
make_heap(v1.begin(), v1.end()); //先建堆
pop_heap(v1.begin(), v1.end()); //pop操作
//sort_heap即为经典的堆排序算法：每次弹出堆顶，直到堆空形成的排序序列
//sort_heap将根据已有的堆，形成推排序序列
make_heap(v1.begin(), v1.end());
sort_heap(v1.begin(), v1.end()); //sort_heap于make_heap要使用同样的排序规则
//sort排序后的结果实际上是逆序的，因为每次弹出的堆顶元素都放在了尾巴上
//is_heap函数用于判定容器的某个区间是不是堆，返回值为bool类型（C++11）
//is_heap也有默认和指定比较函数两个版本
//声明如下，参数为迭代器
bool is_heap( RandomIt first, RandomIt last );
bool is_heap( RandomIt first, RandomIt last, Compare comp );
//带有比较函数的堆判定写法,以int型的vector数组v为例
is_heap(v.begin(),v.end(),less<int>()); //判断v是不是大根堆
is_heap(v.begin(),v.end(),greater<int>()); //判断v是不是小根堆
//is_heap_until第一个不满足堆的位置的迭代器（C++11）
is_heap_until(v.begin(),v.end()); //判断容器中第一个不满足的位置，可用默认比较函数，或者自定义比较函数
is_heap_until(v.begin(),v.end(),cmp);函数类
C++的STL中的函数模板
包含在algorithm头文件中有很多可用的函数，可以直接用于代码中：
max(a,b); //返回a和b中的最大值，参数可以是浮点数
min(a,b); //返回a和b中的最小值，参数可以是浮点数
tolower(char ch); //将字符型变量ch的大写转换为小写，其他不变
toupper(char ch); //将字符型变量ch的小写转换为大写，其他不变
isdigit(char ch); //判定一个字符是不是0~9的数字，参数是int型，这里为了好理解写成char
isalpha(char ch); //判断一个字符是不是字母，参数是int型，这里为了好理解写成char
islower(char ch); //判断是不是小写，参数是int型，这里为了好理解写成char
isupper(char ch); //判断是不是大写，参数是int型，这里为了好理解写成char
abs(x); //返回x的绝对值，参数x必须是整数
swap(a,b); //交换a，b的值，不会损失精度
reverse(it1,it2); //对迭代器[it1,it2)范围内的所有元素进行反转
next_permutation(a,a+3); //将int型数组a~a+3之间的元素，排成当前序列的下一个全排列
//例如a的前三个元素是2，3，1 则下一个序列是3，1，2
fill(a,a+n,value); //将数组a的n个元素全部填充为值value
//说明，二维数组的写法可有以下两种，G[m][n]
fill(G[0],G[0]+m*n,value); //涉及到二维指针的解引用，不能像一维数组那样直接写G
fill(G[0][0],G[0][0]+m*n,value);
fill(v.begin(),v.end(),value); //对于容器，可以使用迭代器作为参数
//排序函数
sort(首地址，尾地址的下一个地址，比较函数); //不填写比较函数时，默认升序排列
sort(a,a+n,cmp); //对a的n个元素进行排序
sort(v.begin(),v.end(),cmp); //对vector容器进行排序
//比较函数的实现
//基本类型的排序
bool cmp(int a,int b){
return a<b; //按照从小到大，如果是大于号> 则从大到小排
}
//结构体的多级排序，假设结构体的定义如下
typedef struct node{
string id;
int high;
int weigh;
}Node;
bool cmp(Noe a,Node b){
if(a.id!=b.id) return a.id<b.id; //如果名字不同，按照名字的字典序从小到大排序
else if(a.high!=b.high) return a.high<b.high; //如果名字相同，但是高度不同，从低到高排序
else return a.weigh<b.weigh; //如果名字和高度都相同，重量不同，按照重量从小到大排序
}
//排序的技巧
//如果结构体的数据量比较大，则采用下标排序的方式，减少时间复杂度
int index[100]; //记录原始的下标，初始化为index[i]=i
vector<Node> v(100); //存放结构体的容器，为了让比较函数能够访问，直接定义为全局变量
bool cmp(int a,int b){ //对下标排序，比较函数的参数为下标的类型，即整型
if(v[a].id!=v[b].id) return v[a].id<v[b].id;//引用结构体数组确定排序规则
... //以下写法类推
...
}
lower_bound(first,last,val); //在数组或者容器的[first,last） 范围内找到第一个大于等于val的位置，然会下标或者迭代器
upper_bound(first,last,val); //在数组或者容器的[first,last） 范围内找到第一个大于val的位置，然会下标或者迭代器
//如果找不到这样的位置，返回可以插入该元素的位置的下标或者指针C标准库中的函数
- math.h中的函数
double hypot(double x,double y); //返回根号下x与y的平方和 double pow(double x,double y); //返回x的y次方 double sqrt(double x); //返回根号x double ceil(double x); //返回不小于x的最小整数，即向上取整 double floor(double x); //返回不大于x的最小整数，即向下取整 double fabs（double x); //返回x的绝对值 double round(double x); //四舍五入到最近的整数 //四舍五入到整数的实现，可以采用+0.5 然后强制类型转换为整数来实现
结构体的初始化
结构体在C++中的实现，已经接近于类的实现，因此对于需要在定义时就初始化的情况，或者为了方便快速的调用，在结构体的定义中加入构造函数，方便初始化，使用示例如下:
//简单的初始化和重载的初始化
typedef struct node{ //定义一个点的坐标结构体
int x,y;
node():x(0),y(0){} //默认的构造函数，初始化为x=0,y=0
node(int _x,int _y):x(_x),y(_y){} //重载的构造函数，使用两个参数初始化x，y
}Node;
//使用示例
Node a; //默认构造函数，自动初始为(0,0)
Node b=node(3,4); //使用重载的构造函数，初始化为(3,4)
//复杂类型的初始化，在默认构造函数中实现初始化
typedef struct st{ //学生结构体
string id; //学生id
int score[10]; //记录10门课程成绩的数组，-1表示缺考
bool pass; //是否合格的标记
st(){
pass=true; //默认合格，不合格时修改标记
fill(score,score+n;-1); //初始化为-1，表示缺考
}
} //默认构造函数，定义时便完成初始化
//结构体比较，对 < 的重载
struct node{
int x,y;
friend bool operator < (node a,node b){ //重载小于号，用于构建优先级关系，或者在set或者堆中的大小关系
if(a.x!=b.x) return a.x<b.x;
else return a.y<b.y;
}
};
typedef strcut node Node;解题技巧
在刷PAT甲级、乙级题库时，积累了很多有用的解题思路和技巧，包括一些常用的函数，比如求公约数，判断素数，判断闰年等，一些数据的处理方式，比如计算跨天时间差，排队问题的时间和队列处理等等，整理如下：
常用自定义函数
最大公约数和最小公倍数
最大公约数，根据辗转相除法可以得到一下递归的函数求解最大公约数：
int gcd(int a,int b){
return !b?a:gcd(b,a%b);
}最小公倍数可有最大公约数求得：
如果a和b的最大公约数为d，则两个数的最小公倍数为：a*b/d;素数
素数的求解可以直接对某个素数进行判定，或者使用打表的方式，采用筛选法提前得到素数表：
//素数判定方法
bool isprime(int n){ //判定n是不是素数
if(x<=1) return false; //特判
int sqr=(int)sqrt(1.0*n); //得到根号n，sqrt函数在c++中参数必须是浮点型
for(int i=2;i<=sqr;i++){ //如果n有除了自身和1以外的因子，则不是素数
if(n%i==0)
return false;
}
return true;
}
//筛选法获取素数表
bool p[MAXN];
fill(p,p+MAXN,true); //素数标记数组，可传引用或者直接定义为全局变量，初始化为真，然后筛掉不是素数的数
void getPrime(){
p[0]=p[1]=false;
for(int i=2;i<MAXN;i++){
if(p[i]){ //如果i是素数，将所有i的所有倍数全部标记为非素数
for(int j=i+i;j<MAXN;j+=i){
p[j]=false;
}
}
}
}闰年判定
能被400整除的或者能被4整除但是不能被100整除的年份就是闰年：
bool isLeap(int year){
return (year%400==0)||(year%4==0&&year%100!=0);
}进制转换
把十进制y转换为Q进制
vector<int> v; //用于保存获得的q进制数
int y,Q; //y为十进制，Q为进制数
do{
int temp=y%Q; //除留余数法
v.push_back(temp); //存放
y/=Q;
}while(y!=0);
//倒序输出v即使转换后的值
for(int i=v.size()-1;i>=0;i--){
cout<<v[i];
}P进制数x转换为十进制y
int P; //进制P
int y=0,pw=1; //y用于保存十进制数，P表示每一步进制的权值，最低为权值为1
while(x!=0){
y=y+(x%10)*pw; //去一位数，并乘上权值，计入y;
x/=10; //x除以十，用于下一轮循环提取下一位
pw*=P; //权值提高一个位
}操作技巧
复杂结构体只排下标（见排序中代码实现）
跨天时间计算
一个月内的跨天时间计算，由于不同天数内时间大小和先后判定需要考虑是否跨天，比较复杂，有两种情况可以进行解决：一、将每一分钟从开始hash映射到一个整数，然后进行加减计算；二、对不同情况进行判定，开始时间向后推算到整天，整时，整分，结束时间向前推算到整天，整时，整分；然后单独计算非整天，非整时，非整分（虽然非常麻烦，但是这种思路可能对某些问题具有启发性）。
第二种推算的方法实现如下：
//使用一下格式表示时间 mm:dd:hh:mimi 月 天 小时 分钟
//这里采用 "mm:dd:hh:mimi mm:dd:hh:mimi"的字符串格式表示一条输入记录，计算第一个时间到第二个时间之间的分钟数
double paycount(string s)
{
string out=s.substr(3,8)+" "+s.substr(16,8); //截取记录的时间用于输出
int cnt=0;
int pay=0;
double ret;
int mon1,d1,h1,min1,mon2,d2,h2,min2;
sscanf(s.c_str(),"%d:%d:%d:%d %d:%d:%d:%d",&mon1,&d1,&h1,&min1,&mon2,&d2,&h2,&min2);
if(d1==d2){ //如果是同一天内
if(h1==h2){ //如果是同一个小时内，直接相减计算
cnt=min2-min1;
}
else{ //否则开始时间向后推算到下一个整点，结束时间向前计算到当前整点，然后进行整点统计
cnt+=(60-min1+min2);
pay+=(rate[h1]*(60-min1)+rate[h2]*min2);
for(h1++;h1<h2;h1++){
cnt+=60;
}
}
}
else{ //如果不在同一天
cnt+=(60-min1+min2); //开始时间向后推算到下一个整点，结束时间向前计算到当前整点
for(h1++;h1<24;h1++){ //开始时间推算到下一个整天，且天数加一
cnt+=60;
}
d1++; //推算后天数加一
for(int i=0;i<h2;i++){ //结尾时间向前推算到当前的整天
cnt+=60;
}
cnt+=(d2-d1)*60*24; //计算整天时间
}
cout<<out<<' '<<cnt<<' '; //输出该条记录，并输出总的分钟数
return cnt; //返回分钟数
}排队服务的模拟
首先把所有的时间都映射为整形，使用数组记录所有服务队列的结束时间（初始化为服务开始的时间，比如银行窗口开放的时间），然后在时间计数的循环体内，遍历所有的服务队列，如果时间刚好到达该服务队列的结束时间，则从顾客等待队列中取出一位正在等待的顾客放入该服务队列进行服务，此时根据顾客的时间花费，更新该服务队列的结束时间，循环直至所有顾客被服务完或者时间结束。
中文读数
对于不超过九位的数字，按照中文读法读出，从低到高对每一位进行读取，（除了个位都需要加入单位），然后非0数字需要读；如果是0进行判定是否读零，对于万位的单位不论如何都要读“万”，对于需要读零的情况进行判定即可：
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<vector>
#include<queue>
#include<stack>
#include<string>
using namespace std;
int main(){
#ifdef ONLINE_JUDGE
#else
freopen("1.txt", "r", stdin);
#endif
//数字位读法
string shu[10]={"ling","yi","er","san","si","wu","liu","qi","ba","jiu"};
//位数的读法
string wei[10]={"0","0","Shi","Bai","Qian","Wan","Shi","Bai","Qian","Yi"};
int n; //读入要处理的数
int tag=0; //正负数标记，1表示负数，0表示正数
cin>>n;
vector<string> v; //用于存放最终结果，最后倒序输出
int now,numcnt=0,pre; //now记录当前位的数字，pre记录前一位的数字，numcnt记录当前数字的位数
if(n==0) { //特判0
puts("ling"); return 0;
}
if(n<0){
tag=1;n=-n; //修改正负号标记，改为正数统一处理
}
while(n){
now=n%10;
n/=10;
numcnt++;
if(now){ //如果当前为不是0
if(numcnt>1) //如果当前为不是个位，则需要单位
v.push_back(wei[numcnt]); //如果需要单位，放入对应的单位
v.push_back(shu[now]); //存入数字的读法
}
else{ //如果是0，考虑读不读0
if(numcnt==5) //如果是万位，则加入万的单位
v.push_back(wei[numcnt]);
else if(pre!=0&&numcnt!=9&&numcnt!=1) //如果前一位不是0，且不是亿位，万位和个位的时候读0
v.push_back(shu[now]);
}
pre=now; //更新pre
}
if(tag==1) v.push_back("Fu");
for(int i=v.size()-1;i>=0;i--){
if(i!=v.size()-1) putchar(' ');
cout<<v[i];
}
return 0;
}读入并处理未知数量连续多个关键词
//如下样例
//如果需要对一下多个使用空格分隔，使用换行结束的关键词进行分别读取和操作
song music word keyword bike book方法1
使用整行读取，然后分别取词；
string temp,str;
getline(cin,str); //整行读入
for(int i=0;i<str.size();i++){ //遍历取词
if(str[i]==' '||i==str.size()-1){ //如果遇到空格或者结束，获得一个单词
if(i==str.size()-1) //如果是结束，需要吧结尾的字符加入单词
temp+=str[i];
dealwith(temp); //处理获得单词，具体操作函数视情况而定
temp.clear(); //temp清空，准备接收下一个字符
}
else
temp+=str[i];
}方法2
使用string和char类型混合输入，char字符用于辨别最后换行结束：
while(1){
cin>>word; //读入一个单词
char ch=getchar(); //吸收空格字符
dealwith(word); //处理获得的单词
if(ch=='\n') break; //到换行处结束
}对不同变量使用相同或类似操作
如果对于不同的变量使用相同或者相似的操作，相同的使用函数调用并传引用的方式，如果只是相似操作，但是只有局部的不用，可以使用全局变量作为标记，在函数段内改变操作对象或者操作方式，比如，多规则排序函数的实现。
Comments | NOTHING