注意这里只是把根A的father变成了B，A的孩子们的father还是A。
所以fa[i]不一定是i的真实父亲，find(i)才是。
对以i为根，到下标为n为止的数组建立大根堆：
void sift(vector<int> &b, int i, int n){ int l = 2 * i + 1; int r = 2 * i + 2; if (l >= n) return; //到达叶子 int maxI = i; //记录i、l、r中最大值位置 if (l<n && b[l]>b[maxI]) maxI = l; if (r<n && b[r]>b[maxI]) maxI = r; if (maxI != i) { swap(b[i], b[maxI]); sift(b, maxI, n); } }打印结果为：3, 4, 2, 6, 5, 1（左右根）
打印结果为：1, 2, 3, 4, 5, 6（根左右）
Tips：中序+先序/后序/层序中任意一个，都能确定唯一的二叉树。后三者两两搭配或者三个一起都无法确定唯一的二叉树，因为它们都只是提供了根节点信息，只有中序序列才能区分左右子树。
同样, 可以使用 stol(long), stof(float), stod(double) 等.
C++标准命名空间中有交换函数：
std::swap(T a, T b);可以直接用于各种类型。
sort(v.begin(), v.end(), cmp);
set常见用法有：
#include <set> using namespace std; //定义 set<int> myset; //插入元素 myset.insert(20); //查找元素 set<int>::iterator it=myset.find(20); //检查不存在某值 if (myset.find(value)==myset.end()){...} //删除元素 myset.erase (it); //删除所有元素 myset.clear(); //判断set是否为空 if (myset.empty()){...}set是红黑树结构，近似平衡，插入、删除、查找操作的时间复杂度都是 O(logn)，并且能自动排序。
适合判断相容性问题：PAT乙级真题 1064 朋友数
可使用map<int, int>对出现的数字计数，读到某个值时直接： mapp[v[i][j]]++;
对map使用[]索引值，若key不存在则会将该key添加，并调用value的默认值作为其值。int的默认值即0。所以可以使用map直接计数。
遍历map语法如下：
// show content: for (std::map<char,int>::iterator it=mymap.begin(); it!=mymap.end(); ++it) std::cout << it->first << " => " << it->second << '\n';以map为例，反向遍历STL库容器：
for (map<int, int>::reverse_iterator rit = countMap.rbegin(); rit!=countMap.rend(); ++rit){ cout << rit->first << " " << rit->second << endl; }类型map<int, int>::reverse_iterator可以换成auto（C++11特性）。
读取一行带空格的字符串，需要用getline(cin, s);
cin >> s只能读到空格前一个单词。
用scanf替代cin时，无法直接读入string类型，可以先读进一个临时字符数组里，再把字符串数组赋值给字符串即可，如：
char temp[10]; scanf("%s", temp); string str = temp;1、cout：
#include <iomanip> cout << setw(5) << setfill('0') << i;2、printf：
printf("%05d", i);1、cout：
#include <iomanip> cout << fixed << setprecision(2) << i;2、printf：
printf("%05d", i);用printf输出’%’，加转义字符’'是不对的，正确做法是：
printf("%%");
使用c++中”cctype”（c中的“ctype.h”）能极大提高效率，包括对单个字符判断类型及大小写转换的函数：
isalnum() 如果参数是字母数字，即字母或数字，该函数返回true isalpha() 如果参数是字母，该函数返回真 isblank() 如果参数是空格或水平制表符，该函数返回true iscntrl() 如果参数是控制字符，该函数返回true isdigit() 如果参数是数字（0～9），该函数返回true isgraph() 如果参数是除空格之外的打印字符，该函数返回true islower() 如果参数是小写字母，该函数返回true isprint() 如果参数是打印字符（包括空格），该函数返回true ispunct() 如果参数是标点符号，该函数返回true isspace() 如果参数是标准空白字符，如空格、进纸、换行符、回车、水平制表符或者垂直制表符，该函数返回true isupper() 如果参数是大写字母，该函数返回true isxdigit() 如果参数是十六进制的数字，即0～9、a~f、A~F，该函数返回true tolower() 如果参数是大写字符，则返回其小写，否则返回该参数 toupper() 如果参数是小写字母，则返回其大写，否则返回该参数倒置字符串，用法为：
#include <algorithm> std::reverse(myvector.begin(),myvector.end());用两组临时变量，记录最大、最小两组值，如果有新的最大/小产生，相应更新改组数据。
如： PAT乙级真题 1004 成绩排名 C++实现
cin、cout比scanf、printf慢很多，但只需在main函数第一行加上：
std::ios::sync_with_stdio(false);
就能快很多。因为C++为了兼容C，保证程序在使用了std::printf和std::cout的时候不发生混乱，将输出流绑到了一起。这行代码的作用便是取消iostream与stdio的默认关联同步，取消同步后的iostream的性能倍增，能与stdio相差无几。只要注意不要再混用iosteam和stdio即可，否则可能会出现预料之外的错误。
还能进一步提升效率，还可以再加上：
std::cin.tie(0);
但PAT乙级真题 1095中添加ios::sync_with_stdio(false); 和cin.tie(0);依然超时，改成scanf、printf后就AC了。
前者产生了新的对象，再把结果返回；后者只涉及到对象的引用，不产生新对象。
拼接字符串最好使用str += "a" ，效率较高。
开方用pow(n, 0.5)有时会超时，sqrt效率大增。
柳神说：“排序传参建议用引用传参，这样更快，虽然有时候不用引用传参也能通过，但还是尽量用，养成好习惯”。 代码如下：
bool cmp(const Info &i1, const Info &i2){ return i1.score==i2.score ? i1.s<i2.s : i1.score>i2.score; }索引是数字的时候，可以用vector代替map，用空间换时间。毕竟限定时间宝贵，空间几乎无限。
map是用红黑树实现的，默认按key排序，使用unordered_map即不排序的map，能提高不少效率。
如果有oj系统（在线判定），则忽略文件读入，否则使用文件作为标准输入。
int main() { #ifdef ONLINE_JUDGE #else freopen("in.txt", "r", stdin); //从1.txt输入数据 #endif }运算符有4种： &(按位与)、|(按位或)、^(按位异或)、~ (按位取反)。
可以用异或判断异号
//a,b异号或者有一个0直接算。 if ((int)(a^b)<0) { …… }异或运算符是“相异”为1，“相同”为0：
若x^y>0 则二者同号（符号位为0）若x^y<0 则二者异号（符号位为1）如： 1 ^ 1 = 0 ^ 0 = 0 1 ^ 0 = 0 ^ 1 = 1 (这里的1和0是位，不是数值)
再例如，1 ^ -1 = -2。因为数据在内存中以补码表示(以8位为例)： 1 = 00000001 --> 00000001（补码） -1 = 10000001 --> 111111111（补码） 异或是在补码的基础上运算的，二者异或结果为11111110（补码）–>10000010 = -2。
只刷到了1114题，明天考试，分类回顾一下常见题型。
PAT甲级真题 1023 Have Fun with Numbers (20分) C++实现（字符串模拟大数乘法）
PAT甲级真题 1024 Palindromic Number (25分) C++实现（判断回文数，字符串模拟大数加法）
PAT甲级真题 1065 A+B and C (64bit) (20分) C++实现（大数加法，预处理防溢出）
PAT甲级真题 1081 Rational Sum (20分) C++实现（模拟分数加法）
PAT甲级真题 1032 Sharing (25分) C++实现（模拟链表找公共元素，计数法两次遍历）
PAT甲级真题 1052 Linked List Sorting (25分) C++实现（模拟链表）
PAT甲级真题 1074 Reversing Linked List (25分) C++实现（模拟反转链表）
反转链表也可参考柳神的方法，直接用reverse()库函数：
1025. 反转链表 (25)-PAT乙级真题
PAT甲级真题 1097 Deduplication on a Linked List (25分) C++实现（模拟链表判断重复值，两个map）
PAT甲级真题 1057 Stack (30分) C++实现（单个multiset，维护中位数指针）
也可参考柳神树状数组的方法：
1057. Stack (30)-PAT甲级真题（树状数组）
堆排序heapSort C++实现
归并排序MergeSort递归版本+非递归版本（C语言实现）
PAT甲级真题 1089 Insert or Merge (25分) C++实现 (同乙级1035 插入与归并，注意测试点2、4)
PAT甲级真题 1098 Insertion or Heap Sort (25分) C++实现(插入排序、堆排序)
PAT甲级真题 1087 All Roads Lead to Rome (30分)
注意最好自定义无穷大，防止在松弛操作时，加法越界变成负数：
const int INF = 0x3f3f3f3f;更新dist的循环变成了：
for (int j=0; j<n; j++){ //此处g[minI][j]可以直接做加法，不用考虑是否等于INT_MAX了 //if (!visited[j] && g[minI][j]!=INT_MAX) { if (!visited[j]) { if (g[minI][j]+dist[minI] < dist[j]){ dist[j] = g[minI][j]+dist[minI]; pre[j].clear(); pre[j].push_back(minI); } else if (g[minI][j]+dist[minI] == dist[j]){ pre[j].push_back(minI); } } }参考：为何程序员喜欢将INF设置为0x3f3f3f3f
PAT甲级真题 1111 Online Map (30分) C++实现(两次dijkstra+dfs，复用封装函数)
PAT甲级真题 1072 Gas Station (30分) C++实现（Dijkstra算法，测试点4四舍五入的坑）
PAT甲级真题 1030 Travel Plan (30分) C++实现（求最短路径+最小权重，Dijkstra算法邻接表版，类似甲级1003题）
PAT甲级真题 1018 Public Bike Management (30分) C++实现（基于Dijkstra算法暴力存储所有最短路径；测试点5、7大坑）
PAT甲级真题 1003 Emergency (25分) C++实现（基于Dijkstra算法）
PAT甲级真题 1004 Counting Leaves (30分) C++实现（广度遍历）
PAT甲级真题 1020 Tree Traversals (25分) C++实现（由后序、中序求层次遍历，队列模拟递归）
PAT甲级真题 1043 Is It a Binary Search Tree (25分) C++实现（二叉搜索树，递归前序转后序）
PAT甲级真题 1053 Path of Equal Weight (30分) C++实现（DFS遍历树）
PAT甲级真题 1064 Complete Binary Search Tree (30分) C++实现（二叉搜索树中序转层次，队列递归法）
PAT甲级真题 1066 Root of AVL Tree (25分) C++实现（建立AVL树）
PAT甲级真题 1079 Total Sales of Supply Chain (25分) C++实现（带深度的DFS）
PAT甲级真题 1086 Tree Traversals Again (25分) C++实现（由先序、中序求后序）
PAT甲级真题 1099 Build A Binary Search Tree (30分) C++实现 (二叉搜索树BST inorder中序遍历得到有序数列)
PAT甲级真题 1102 Invert a Binary Tree (25分) C++实现（找树根，层序、中序遍历翻转二叉树）
PAT甲级真题 1103 Integer Factorization (30分) C++实现（dfs+剪枝+备忘录，经典题目）
PAT甲级真题 1110 Complete Binary Tree (25分) C++实现(判断完全二叉树)
PAT甲级真题 1111 Online Map (30分) C++实现(两次dijkstra+dfs，复用封装函数)
图的广度优先遍历（BFS)和深度优先遍历（DFS）C++实现
PAT甲级真题 1013 Battle Over Cities (25分) C++实现（基于Kruskal算法思想，分支标记法）
PAT甲级真题 1076 Forwards on Weibo (30分) C++实现（图的广度优先遍历，BFS）
PAT甲级真题 1091 Acute Stroke (30分) C++实现（bfs累计节点数，dfs会栈溢出）
PAT甲级真题 1010 Radix (25分) C++实现（二分法，细数多处神坑）
PAT甲级真题 1007 Maximum Subsequence Sum (25分) C++实现(3种方法对比：遍历法， 动态规划法，直接求解法)
PAT甲级真题 1045 Favorite Color Stripe (30分) C++实现 （动态规划，最长不下降子序列(LIS)）
PAT甲级真题 1107 Social Clusters (30分) C++实现(并查集：路径压缩+优先级）
PAT甲级真题 1114 Family Property (25分) C++实现 (并查集）
PAT甲级真题 1067 Sort with Swap(0, i) (25分) C++实现（注意测试点1、2超时问题）
