PAT练习题

3.5 PAT甲级低分飘过😶‍🌫️ 笔记做都做了，发一下吧。

考试题型跟网上说的无太大差距，都在考纲范围内。

这次考的是——字符串+排序+二叉查找树+图&&最短路径。麻了，最后一题没时间做完，虽然没复习到那里，但是感觉也能做emm。

复习的时候看的是算法笔记和配套的上机指南，没空做真题。

春节后天天刷，把前面的字符串处理、排序、数学问题的各种题型刷完的话，大概花了两周，已经能做的很熟练了。在我考试的时候看来，这类题目属于“有手就行”，但是不把题目刷完吧，有些做题技巧还是没法积累到的（比如直接sort会超时的情况）。

之前很少用到STL库的vector、set、map，这里有的题目用这些数据结构会更好解。光看那几道例题（一天就能做完）不行，得通过后面树、图的题练熟。

树的前中后和层次序列，这四者的互相转换很重要，对应的也有好几道题。BST和AVL也很重要。由树衍生出来的并查集和堆，比较好掌握，但是好像还是树考的比较多。一棵树，来来去去无非就是判断类别和查找，所以遍历的算法（DFS和BFS）相当相当重要。只要搞懂了树的结构特点，很多题目都可以用一维/二维数组解决，无需真的struct node* 建树。

DFS和BFS的题目在树的前面，还有栈、队列那些，连在一起练习会好理解些。这些题我大概做了一周，题不多但是刚开始做会有点生疏，熟了之后后面的树、图会做得更快。

树的题目，套路为主吧。我是考前一周才复习到这里的，早晚总共花2~3小时左右，题目也没完全做完（实在是不够时间了55），练熟了就行。

图的话，压根没看完，凭着点理解和以前学过的记忆就上考场了🥲，但是我觉得树图和DFS、BFS是一体的，连着刷个一两周题目应该没问题。

考试时间是三个小时。最耗时间的应该是读题，前两道题目虽然简单，但是读不好题，肯定有很多测试点不过，又得慢慢改。最后一题有hint，但我光是看懂hint都不知道花了多少时间…… 我这次大概是第一题四五十分钟，第二题二三十分钟，第三题四五十分钟，第四题四五十分钟这样。如果下次还考的话，争取多做一下树图的题和真题，把熟练度刷上去。虽然感觉这次最后一题能做，但真的太不熟了，估计再给一小时也做不完emm。

笔记整理的是我刷过的题和书上的一些代码，复杂一点的题目或者当时没记牢的题目直接贴代码了。

一、c++标准模板库

【1】vector

变长数组，以邻接表的方式存储图。

适用于：

1. 元素个数不确定
2. 输出数据的个数不确定，结尾无多余空格。
3. 用邻接表存储图。

#include<vector>
vector<int> vi;//下标：vi[0]~vi[vi.size()-1]
vector<char> vi;//迭代器：vector<char>::iterator it;通过*it访问
vector<node> vi;//struct node

vi.push_back(i);//在结尾追加元素i，O(1)
vi.pop_back(i);//删除结尾元素i，O(1)   
vi.size();//返回的是unsigned类型
vi.clear();//O(N)
vi.insert(it,x);//向地址it插入元素x，O(N)
vi.erase(vi.begin()+1,vi.begin()+4);//删除单个/所有元素
vector<char>::iterator it=vi.begin();//取首元素的地址
//......
vector<vector<int>> vi;
vector<int> Array[ArraySize];//二维数组

题号	题目名称	描述	注意点
A1039	Course List for Student	给定每门课程的学生名单，输出每个（查询的）学生的课程列表	使用hashID存每个学生的课程；注意vector size是无符号数%lu
A1047	Student List for Course	给定每个学生的课程列表，输出每个课程有什么学生	学生名用name数组存，下标id作为标记学生的id即可，依旧用int的vector。

【2】set

内部自动有序，不含重复元素。

适用于：

1. 需要去除重复元素
2. 元素较大不能直接用hash table

#include<set>
set<int> a;
set<double> a;
//...
set<int> a[100];//二维数组
set<int>::iterator it;//迭代器，it++取下一元素的地址

a.insert(x);//自动递增排序和去重，O(log N)
a.find(s);//返回迭代器（x的地址）
a.erase(...);//it/x/it,a.end()
//需要处理不唯一的情况时，使用multiset

题号	题目名称	描述	注意点
A1063	Set Similarity	给定多行数字（含重复），求指定两行数字间的共同数字个数和总个数（不含重复）	使用vector<set> v(n) 二维数组，v[i]对应着每一行的set，find的时候只需要定义对应的it就可以了。

【3】string

题号	题目名称	描述	注意点
A1060	Are They Equal	用指定n位的科学计数法表示数字，判断是否相等	用erase删除前导0、小数点、非0位前面所有的0；用+=复制剩下的n位数字到新的字符串中，注意可能要补0。

【4】map

作用：建立映射。第一个是键的类型，第二个是值的类型。

如果是字符串到整型的映射，必须用string，因为char数组不能作为键值。

但是可以将一个set容器映射到一个字符串：map<set,string> mp;

key就是map的下标，可以通过下标访问map元素；也可以通过迭代器it->first或it->second访问key或value。

同时map会按键从小到大的顺序自动排序。

【5】queue

#include<queue>
using namespace std;

queue<typename> name;//定义

q.push(x);//压入队列
q.pop();//出队
q.front();
q.back();
q.empty();//队列非空
q.size();

【6】priority_queue

优先队列，底层使用堆来实现的。

队首元素是当前队列中优先级最高的。

无front和back函数，只能通过top函数来访问队首/堆顶元素。

#include<queue>
using namespace std;

priority_queue<typename> name;//定义

priority_queue<int, vector<int>, greater<int> q;//数字小的优先级越大
priority_queue<int, vector<int>, less<int> q;//数字大的优先级越大

q.push(x);
q.pop();
q.empty();
q.size();
q.top();

【7】pair

#include<utility>
using namespace std;

pair<typeName1, typeName2> name;//定义

p.first();
p.second();//比较时，先比较first大小，再比较second大小。

【8】algorithm

#include<algorithm>
min(x,y);// max
abs(x); //fabs用于求浮点数的绝对值，位于math头文件下
swap(x,y);
reverse(it,it2);// 反转[it,it2)的元素
next_permutation(it,it2);// 一个序列全排列的下一个序列
fill(it,it2,x);// 指定区间内赋值为x
sort(it,it2,cmp);
lower_bound(it,it2,x);// upper_bound; 寻找第一个≥/≤x的数

二、入门篇

【1】简单问题

简单模拟

题号	题目名称	描述	注意点
B1001	害死人不偿命的(3n+1)猜想	讨论自然数砍成1需要的步数	数组下标、max值初始化为-1
B1011	A+B和C	判断输入的a+b是否大于c	数字范围是long long，scanf的参数为%lld
B1016	部分A+B	指定数组成的新整数求和	范围是long long
B1026	程序运行时间	根据seconds输出时间	输出位数%02d、四舍五入（ifelse判断/先+0.5再类型转换/调用函数）
B1046	划拳	判断输赢	同时输赢情况的判断
B1008	数组元素循环右移	不新增数组，减少移动次数	移动位数m的大小可为0
B1012	数字分类	分类统计	输出格式
B1018	锤子剪刀布	分情况统计输赢	getchar吸收换行符，因为scanf的参数是%c
A1042	Shuffling Machine	按指定顺序洗多次牌
A1046	Shortest Distance	两点间最短距离	全遍历的话会超时，用累加的距离sum来计算最短距离
A1065	A+B and C(64 bit)	同B1011	long long也会溢出，分别判断正溢出和负溢出的情况
B1010	一元多项式求导	输出求导结果	若求导后无非零项，需要输出 0 0
A1002	A+B for Polynomials	多项式求和	count的计算
A1009	Product of Polynomials	多项式求积	加上结构体更容易算

查找元素

题号	题目名称	描述	注意点
B1041	考试座位号	随机访问数组，输出对应的座位号	以试机号为数组下标方便查找
B1004	成绩排名	输出最高/低成绩的学号、姓名	边读边更新max、min
B1028	人口普查	统计合法出生日期和最老/年轻年龄	使用结构体方便比较，转化为区间大小问题
B1032	挖掘机技术那家强	输出累积分数最高的编号	以编号为数组下标方便累计和查找
A1011	World Cup Betting	算出最佳赔率的方案	每次取最大值运算
A1006	Sign in and Sign Out	找出最早和最晚的时间	使用结构体方便比较
A1036	Boys VS Girls	找出最高/最低分	使用结构体方便存储数据，注意成绩只有一个的情况

图形输出

题号	题目名称	描述	注意点
B1036	跟奥巴马一起编程	输出正方形（行列数不等）	四舍五入取整
B1027	打印沙漏	打印沙漏图案，输出剩余字符个数	转化为数学算式，直接算出每行需要的字符个数
A1031	Hello World for U	输出规定的U字形图案	先算出符合题意的长度

日期处理

注意平年/闰年，大月/小月。

计算日期相差天数，可以用加1法统计。

进制转换

题号	题目名称	描述	注意点
B1022	D进制的A+B	十进制转其他进制	除基取余法，注意逆序输出、数组下标
B1037	在霍格沃兹找零钱	按题意，做减法	统一转为最小单位进行计算，再转换回去
A1019	General Palindromic Number	十进制转其他进制，再判断回文	除基取余法
A1027	Colors in Mars	十三进制	不足2bit时需补0，数组长度较小。可不用循环。
A1058	A+B in Hogwarts	按题意，做加法	从低位开始带上进位进行运算

字符串处理

题号	题目名称	描述	注意点
B1006	换个格式输出整数	对百十个位数转换格式	遍历
B1021	个数位统计	统计每个数字出现的次数	以数字作为数组下标，边读边统计
B1031	查验身份证	前十七位数字加权求和求模后，验证最后一位是否正确	遍历
B1002	写出这个数	求和后输出数字拼音	用二位字符数组存储拼音比较方便
B1009	说反话	反序输出英文句子	scanf和cin都是遇到空格截止，因此需要用gets输入一整行（选择gcc编译器）。
B1014/A1061	福尔摩斯的约会	找字符串中相同的字母	两个字符串长度可能不同，注意 i 的范围
B1024/A1073	科学计数法	输出补全0后的数字	小数点的位置与指数、原数字长度有关
B1048	数字加密	奇偶位不同的加密方式	注意奇偶位的处理
A1001	A+B Format	用逗号隔开三个数字	注意结果为0时要特殊处理
A1005	Spell it Right	输出数字求和结果的拼音	注意结果为0时要特殊处理
A1035	Password	特殊字符替换	注意输出格式
A1077	Kuchiguse	输出最长子串	求的是公共后缀，注意题意
A1082	Read Number in Chinese	中文读数字	零是否单独发音的问题

A1077 Kuchiguse

这道题比较多细节，对算法笔记上的代码补充了下。

首先PTA的编译器版本似乎都不支持gets(s[i])，但是gets(str)是可以的。这里用 fgets 替换。由于fgets是从stdin取指定长度的字符，数据长度最长为256，加上换行符有257个，因此每次至少取257个字符。同时注意将换行符转为空字符（以免后续找子串时加上了换行符）。

其次虽然这道题只能遍历，但也可以通过只找最短长度的子串的方法来减少运行时间。因为题目要求的是找到最长公共后缀，所以可以先反转字符串再查找，或者从后往前找，这样就能保证公共后缀带或不带空格的情况都考虑到了。查找的过程也可以用strstr函数代替。

还要注意题目给的字符串长度范围，是0~256闭区间。当长度为0时，可以直接输出，无需查找。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int n,minlen=256,ans=0;
char s[100][260];

int main()
{
    scanf("%d",&n);
    getchar();
    for(int i=0;i<n;i++){
        fgets(s[i],260,stdin);//注意字符串长度
        for(int j=0;j<strlen(s[i]);j++) if(s[i][j]=='\n') s[i][j]='\0';//注意换行符
        int len=strlen(s[i]);
        if(len==0){
        	printf("nai");
        	exit(0);
		}
        if(len<minlen) minlen=len;//
        for(int j=0;j<len/2;j++){//反转字符串，方便查找
            char tmp=s[i][j];
            s[i][j]=s[i][len-j-1];
            s[i][len-j-1]=tmp;
        }
    }
    
    for(int i=0;i<minlen;i++){
        char c=s[0][i];
        bool same=true;
        for(int j=1;j<n;j++){
            if(c!=s[j][i]){
                same=false;
                break;
            }
        }
        if(same)ans++;
        else break;
    }
    
    if(ans){
        for(int i=ans-1;i>=0;i--){
            printf("%c",s[0][i]);
        }
    }else{
        printf("nai");
    }
	
	return 0;
}

A1082 Read Number in Chinese

这道题的“0”尤其麻烦，发不发音有多种情况，如果一一分情况讨论程序会很复杂。除了0，还有“万”、“亿”这些单位在后续数字全0的情况下发不发音的问题。由此看来，关键在数字0的位置。

不难发现优先处理的是个十百千这四位，最后再根据它的位置决定输出的是“万”还是“亿”。但是这两个单位也不一定输出，当处理的四位数字全0时，这里是不需要发音的。当四位数字里有非0时，还需要看0的位置——0在非0前，需要单独发一次音；在非0后不需要发音。

综上，需要另设两个辅助变量判断”亿万“和0是否发音。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

char nums[10][6]={{"ling"},{"yi"},{"er"},{"san"},{"si"},{"wu"},{"liu"},{"qi"},{"ba"},{"jiu"}};
char wei[5][5]={{"Shi"},{"Bai"},{"Qian"},{"Wan"},{"Yi"}};
int main()
{
    char str[10];
    scanf("%s",str);
    int len=strlen(str);
    
    //初始化左边界和右边界
    int left=0,right=len-1;
    if(str[0]=='-'){
    	printf("Fu");
    	left++;
	}
	
    //找到从左往右的第一个区间
	while(left+4<=right){
		right-=4;
	}
	
	while(left<len){
		bool flag=false;//表示区间内是否有0
		bool isPrint=false;//表示该区间是否需要输出“亿”“万”单位
        
		while(left<=right){//先输出完区间内的四个数字
			if(left>0&&str[left]=='0') flag=true;
			else{//遇到非0数字
				if(flag==true){//说明区间内剩下的数字不是全0
					printf(" ling");//此处的0需要发一次音
					flag=false;
				}
			
				if(left>0) printf(" ");
				printf("%s",nums[str[left]-'0']);
				isPrint=true;
				if(left!=right) printf(" %s",wei[right-left-1]);
			}
			left++;
		}
		
		if(isPrint==true&&right!=len-1){//需要输出“亿”和“万”的情况
			printf(" %s",wei[(len-1-right)/4+2]);
		}
		
		
		right+=4;//下一个区间
	}
	

	return 0;
}

【2】简单算法

排序（选择/插入排序）

选择排序（n^2）：遍历未排序的子序列，选择最大/最小放入已排序列末尾（两次遍历）。

插入排序（最好n/最坏n^2）：根据未排序的子序列首元素的大小，放入已排序列（插入时需逐位移动）。

题目主要用sort函数可以解决。对于元素多的题目用结构体更方便。有的题目数据量很大，可以先做预处理筛选出有效数据再做排序/查找。

题号	题目名称	描述	注意点
B1015/A1062	徳才论	多种标准排序	使用结构体和sort函数（头文件：algorithm，std头）
A1012	The Best Rank	四类成绩排序，择优输出	成绩并列的情况，排名应该类似 1 1 1 4 5 6…
A1016	Phone Bills	找到同一用户配对的上/下线时间，按rate费用表算出费用，排序后输出	费用计算用加一法，简化计算过程。
A1025	PAT Ranking	merge all the ranklists and generate the final rank	注意成绩并列的情况
A1028	List Sorting	三种排序	sort排序
A1055	The World’s Richest	输出给定age区间内排序（wealth>age>name）的结果	数据总数和查询次数较大，但有效数据个数<=100，先筛选出有效数据能减少运行时间
A1075	PAT Judge	从提交记录中统计出所有考生的总分排名、各题得分	注意边界值0、-1和标志位的计算方式
A1083	List Grades	成绩从高到低排序，输出目的区间内的name、id	sort
A1080	Graduate Admission	择优录取，在指定quota范围内从排名高到低选择学生第一、二、…志愿的学校。	平均数可以用sum代替；学校也用一个数组存（加入lastid、stuNum变量方便存储超额的情况）
A1095	Cars on Campus	根据停车记录输出指定时间内车的数量和总停车时间最长的车牌号	数据量多，不用map会超时。

A1016 Phone Bills

这道题最重要的是审题：

• on/off line 记录配对的原则是按时间顺序排列的相邻的两条。所以没有必要分别用两个数组记录同一个用户的上下线时间，用一个数组记录更方便排序和查找过程，在成员元素中加上一个标志位即可分辨出来。
• 账单打印按照客户姓名的字母顺序 alphabetical order。（emm不知道我为啥反复看题都没看到这句，还得多看点英文题）
• 题目只是说保证输入中至少有一对匹配的记录，不是说每个用户都有成对的记录，所以需要考虑用户无消费账单不输出计算结果的情况。（是谁又不好好审题🙃）

做了挺久，主要卡在费用计算上。比起多个if-else分支，加一法挺好用，但是数据足够大的时候也许会超时。

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;

int rate[24];//24小时内的不同费用

struct times{
	int day;
	int hour;
	int minute;
	bool on;//为true表示这是online记录，false为offline记录
}tmp;


struct user{
	char name[25];
	times records[1000];//单个用户的所有电话记录
	int len;//存records的长度
}usrs[1000];

bool cmp(times a,times b){//电话记录排序规则
	if(a.day!=b.day) return a.day<b.day;
	if(a.hour!=b.hour) return a.hour<b.hour;
	return a.minute<b.minute;
}

bool cmp2(user a,user b){//用户名排序
	return strcmp(a.name,b.name)<0?1:0;
}


int minutes(times a,times b){//计算时间差距（单位：分钟）
	int sum=(b.day-a.day)*60*24+(b.hour-a.hour)*60+(b.minute-a.minute);
	return sum;
}

float cost(times a,times b){//计算费用
	float sum=0;
    
    //加一法：直到时间a等于时间b为止（单位：分钟）
	while(a.day!=b.day||a.hour!=b.hour||a.minute!=b.minute){
		if(a.day==b.day&&a.hour==b.hour){//只剩分钟不同的情况
			sum+=rate[a.hour]*(b.minute-a.minute)*0.01;//直接加
			a.minute=b.minute;
		}
		else{
			sum+=rate[a.hour]*(60-a.minute)*0.01;//加满一个小时
			a.minute=0;
			if(a.hour==23){//满一天时，day加一
				a.hour=0;
				a.day++;
			}else{
				a.hour++;
			}
		}
	}
	return sum;
}


int main(){
	for(int i=0;i<24;i++) scanf("%d",&rate[i]) ;
	int n,month,count=0;
	char str[10],name[20];
	scanf("%d",&n);
	
	//输入 
	for(int i=0;i<n;i++){
		tmp.on=true;
		scanf("%s %d:%d:%d:%d %s",name,&month,&tmp.day,&tmp.hour,&tmp.minute, str);
		int j=0;
		while(j<count){
			if(!strcmp(name,usrs[j].name)) break;	
			j++;
		}
		if(j>=count){
			j=count++;//找不到name，第一次存储，count++ 
			strcpy(usrs[j].name,name);
		}
		
		int l=usrs[j].len++;
		usrs[j].records[l]=tmp;
		if(!strcmp(str,"off-line")){
			usrs[j].records[l].on=false;
		}
	}
	
	sort(usrs,usrs+count,cmp2);
	
	for(int i=0;i<count;i++){//遍历每个用户 	
		sort(usrs[i].records,usrs[i].records+usrs[i].len,cmp);//对用户的所有数据排序 
		
		float bill=0;
		bool isPrint=false,firstPrint=true;
		
		
		for(int j=0;j<usrs[i].len-1;j++) {//遍历当前用户的每条数据
			if(usrs[i].records[j].on==true){
				if(usrs[i].records[j+1].on==false){//找到两条相邻的on-off记录
				
					int m=minutes(usrs[i].records[j],usrs[i].records[j+1]);//计算分钟差距
					float money=cost(usrs[i].records[j],usrs[i].records[j+1]);
					if(m>0){//用户有消费才需要输出 
						isPrint=true;
						if(firstPrint)printf("%s %02d\n",usrs[i].name,month);
						printf("%02d:%02d:%02d %02d:%02d:%02d ",usrs[i].records[j].day,usrs[i].records[j].hour,usrs[i].records[j].minute,usrs[i].records[j+1].day,usrs[i].records[j+1].hour,usrs[i].records[j+1].minute);
						printf("%d $%.2f\n",m,money);
						firstPrint=false;
						bill+=money;
					}
					j++;
				}
			}
		}
		
		if(isPrint) printf("Total amount: $%.2f\n",bill);
	}	
	return 0;
} 

散列

大数hash

当目标数作数组下标的方法不适用（目标会溢出）的时候，通过散列函数H将目标转为key：直接定址法H(key)=key、平方取中法H(key)=key^2[取i:i+j]、除留余数法H(key)=key%mod、线性变换H(key)=a*key+b等。

解决冲突：线性（H(key)+1）、平方（H(key)+k^2*(-1)^i ）、链地址（单链表存储）。

一般使用map来直接使用hash功能，不需要自己实现解决冲突的方法。（除非题目要求）

字符串hash

当key为字符串，用hash把字符串转为整数。（AZ → 025）

int hashFunc(char S[],int len){//相当于二十六进制转十进制
    int id=0;
    for(int i=0;i<len;i++){
        id=id*26+(S[i]-'A');
    }
    return id;
}
//如果加上小写字母(a~z → 26~51)，则五十二进制转十进制
//如果再出现数字（0~9 → 52~61），则六十二进制转十进制
//因题而异，如果数字有固定位置、数量，可以直接加上其十进制的值

这类题要注意hashTable的大小、下标、存的内容，以及id是否越界。对于数字、字母组成的字符串，用256个ascii码作为下标的数组更方便。

题号	题目名称	描述	注意点
B1029/A1084	旧键盘	输出第二行比第一行少的字符	字母统一为大写，以ascii值为hashtable下标更方便
B1033	旧键盘打字	比上一题多了shift键（大写字母是否能输出）	单独判断大写字母，存的时候还是统一以小写存；使用fgets读一整行（可能有空白符）
B1038	统计同成绩学生	输出指定成绩的人数（百分制）	分数作数组下标
B1039/A1092	到底买不买	输出两字符串相差字符个数	用fgets读，长度为字符串最长长度+2
B1042	字符统计	输出出现次数最多的字符	如果用ascii码做数组下标，排序时的数组长度是256而不是有效字符个数。
B1043	输出PATest	按PATest顺序输出字符串中的字符	0~5下标分别对应PATest六个字母
B1047	编程团体赛	统计出得分最高的队伍	排序时的数组长度是maxn
A1041	Be Unique	按输入顺序输出第一个只出现过一次的数据	可以按顺序将数据存在a[i]，hashtable以a[i]作为下标。
A1050	String Subtraction	指定的字符全部不输出	用ascii码做数组下标
B1005	继续(3n+1)猜想	输出求3n+1过程中没有被覆盖过的数	a[i]做hashtable数组下标；数字为奇数的时候记得除以2
A1048	Find Coins	输出和等于m的两个数（给定序列内最小的）	hashTab存m-a[i]方便查找过程；注意新算的id v2是否会越界。

递归（分治）

两个重要：递归边界、递归式。

//n的阶乘
int F(int n){
    if(n==0) return 1;
    else return F(n-1)*n;
}

//求Fibonacci数列的第n项
int F(int n){
    if(n==0||n==1) return 1;
	else return F(n-1)+F(n-2);
}
//全排列问题、n后问题...

如果递归到某一层，发现不符合条件立刻返回，属于回溯法。n后问题示例：

void generateP(int index){
    if(index==n+1){
        count++;//有效方案数+1
        return;
    }
    
    for(int x=1;x<=n;x++{//遍历index列的每一行
        
        if(hashTable[x]==false){//当前第x行还没有皇后
            bool flag=true;//标志是否有冲突（对角线）     
            for(int pre=1;pre<index;pre++){//第pre列
                if(abs(index-pre)==abs(x-P[pre])){
                    flag=false;//与之前的皇后在同一条对角线上
                    break;
                }
            }
            
            if(flag){//在第x行的位置放的话不会有冲突
                P[index]=x;
                hashTable[x]=true;
                generateP[index+1];
                hashTable[x]=false;
            }
        }
    }
    
}

贪心

从局部最优实现整体最优（可反证）。

题号	题目名称	描述	注意点
B1023	组个最小数	按0~9的顺序把有的数字输出完	首位不能是0
B1020/A1070	月饼	从零售价最高的月饼开始卖	输入的库存量不一定是整数
A1033	To Fill or Not to Fill	给定加油站位置和油费，求最省钱的加油方案	贪心策略的制定
A1037	Magic Coupon	给定数字相乘相加后最大结果（有正负，从大到小算同号数字）	注意数组大小
A1067	Sort with Swap(0,*)	输出排序需要的最少的交换次数	用一位数组存每个数字的当前位置即可
A1038	Recover the Smallest Number	输出数字组成的最小数	局部最优：数a和数b拼接在一起比b与a拼接要小

A1033 to Fill or Not to Fill

好好审题）题目说了 fill or not to fill，也就是说贪心策略需要充分考虑加不加满油的情况。

总的思路是用较便宜的油费跑较多的路程。但是如果按price对station数组排序，距离会乱（当前站点离起点的距离）。既然都是与起点的距离，那么按照距离非降序排，找策略的时候只要从左往右找最佳的就可以了。

需要考虑的问题是：怎么选择下一站，什么时候加满/不加满。

贪心算法考虑的是局部最优，在这个题目里可以理解为：在能跑的距离内（越长越好），选更便宜的那个油费；每次都选较便宜的，那么总的来说花费也会较少。

例如示例1的最长距离为600，可选的站点油费有7、7.2、6.85、7.5，可以选6.85。但是起点的油费是7.1，比6.85贵，所以不应该加满，到了6.85的那个站点的时候再加满。而6.85后只有7.5和7可选，都比6.85贵，应该只加到刚好到7那个站点的量，等到下次去到一个更便宜的站点再加满。

由此可以总结出贪心策略：在可选范围内寻找站点，若有油费低于当前站点油费的，加满；若没有，则选最便宜的那个站点，只加刚好能到那个站点的量。这里用float或double都能过测试点。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

struct station{
	double price;
	double dis;
}list[510];

bool cmp(station a , station b){
	return a.dis<b.dis;
}

int main(){
	int n;
	double cmax,distance,run;
	scanf("%lf %lf %lf %d",&cmax,&distance,&run,&n);
	
	for(int i=0;i<n;i++){
		scanf("%lf %lf",&list[i].price,&list[i].dis);
	}
	list[n].price=0;
	list[n].dis=distance;//终点
	
	sort(list,list+n,cmp);
	
	if(list[0].dis!=0){//起点不是0 
		printf("The maximum travel distance = 0.00");
		return 0;
	}
	
	double left=0;//剩余的路程 
	int now=0;//汽车的位置
	double longest = run*cmax;//单次可跑的最长距离 
	double cost=0; 
	
	while(now<n) {//到达终点前
		
		int next=now;//下一站 
		double tmp=list[now].dis+longest;
		double min=10000000;
		bool found1=false,found2=false;
		
		
		 for(int i=now+1;i<=n&&list[i].dis<=tmp;i++){//可到达的范围内 
		 	if(list[i].price<list[now].price){//找到第一个比当前站价格更低的站 
		 		found1=true;
		 		next=i;
		 		break; 
			}else if(list[i].price<min) {

				min=list[i].price;
				next=i;
				found2=true; 
			}
		 }

		 if(found1==false&&found2==false){//找不到下一站，无法到达 
		 	printf("The maximum travel distance = %.2lf",list[now].dis+longest);
		 	return 0;
		}else{
			if(found1==true){//加到下一站
				double need=list[next].dis-list[now].dis-left;
				need/=run;
				cost+=list[now].price*need;
				now=next;
				left=0;
			}
			else{//加满 
				double need=longest-left;
				need/=run;
				cost+=list[now].price*need;
				left=longest-(list[next].dis-list[now].dis);
				now=next;
			}
			
		}
		
	}
	printf("%.2lf",cost) ;
	
	
	return 0;
}

A1067 Sort with Swap(0,*)

贪心策略比较容易推出：一直将0与 0的id那个数字 交换；如果0回到原位，就找下一个不在本位的数字先跟0交换，然后重复前面的交换步骤。

写法有很多，感觉我用结构体的方法是最麻烦的，分别记录了输入序列的数字、id、是否放回原位的bool标志、以及正确序列的id。

看别人代码的时候发现这种思路的话，用map会更方便。按照原本的思路，交换输入序列的数字的话，每次找0的id对应的数字都需要遍历，容易超时，因此需要用结构体记录更多的信息；但是如果反过来，用数组存数字的位置，交换的是id，查找过程就变成随机查找了：https://blog.csdn.net/Huangpengyu123/article/details/105811103。

#include <iostream>
using namespace std;
int main() {
    int n, t, cnt = 0, a[100010];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> t;
        a[t] = i;//每个数字t对应的位置为i 
    }
    for (int i = 1; i < n; i++) {
        if (i != a[i]) {
            while (a[0] != 0) {
                swap(a[0], a[a[0]]);
                cnt++;
            }
            if (i != a[i]) {
                swap(a[0], a[i]);
                cnt++;
            }
        }
    }
    cout << cnt;
    return 0;
}

二分

查找的时间复杂度：O(logn)

int binarySearch(int A[],int left,int right,int x)
{
    int mid;
    while(left<=right){//注意有等号（数组的数字不重复时）
        mid=(left+right)/2;
        if(A[mid]==x) return mid;
        else if(A[mid]>x) right=mid-1;
        else left=mid+1;
    }
    return -1;
}

除了查询，二分还可以用于计算近似值（比如根号2）：

const double eps=1e-5; //精度

double callSqrt(){
    double left=1,right=2,mid;
    while(right-left>eps){
        mid=(left+right)/2;
        if(mid*mid>2) right=mid;
        else left=mid;
    }
    return mid;
}

快速幂O(log b)——求a^b%m：

typedef long long LL;
LL binaryPow(LL a, LL b, LL m){
    if(b==0) return m;
    if(b%2==1) return a*binaryPow(a,b-1,m)%m;
    else{//b为偶数的时候，转化为先求b/2，最后再平方乘起来
        LL mul=binaryPow(a,b/2,m);
        return mul*mul%m;
    }
}

题号	题目名称	描述	注意点
B1030/A1085	完美数列	输出给定序列中满足max<=min*p的子序列	min*p在long long范围；使用二分法找到合适的max值。
A1010	Radix	给定数n1，求使n2与其相等的进制。	虽然字符最高为’z’(35)，但是进制可以比36大，上限应该为目标数；用二分法找较快；数据转换可能会超过long long范围
A1044	Shopping in Mars	切割连续子序列，其和等于或小于指定数字	用数组存储前i个数的和，减少for循环的个数
A1048	Find Coins	输出和等于m的两个数字	用二分法查找m-a[i]；检查当前数是否为a[i]

A1010 Radix

一开始以为radix上限是36，所以没有用二分法。上限改为n1后，在不用二分法的前提下，还差2个测试点过不了，一个超时，一个wrong answer。看来确实是必须用二分法：

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;

char n1[20],n2[20];

bool cmp(char x,char y){
	return x>y;
}

int turnnum(char x){//字符转为数字 
	if(x<='9') return x-='0';
	else return x+=10-'a';
}

long long getnum(char a[],int b){//将数字a按进制b转换
	if(b==10) return atoi(a);
	int len=strlen(a);
	long long ans=0;
	long long p=1;
	for(int i=len-1;i>=0;i--){
		ans+=turnnum(a[i])*p;
		p*=b;
	}
	return ans;
}

long long getradix(char a[]){//求a的最小进制
	char tmp[20];
	strcpy(tmp,a);
	sort(tmp,tmp+strlen(tmp),cmp);
	return turnnum(tmp[0])+1;//最大字符的值+1
}

int main() {
	int tag,radix;
	scanf("%s %s %d %d",n1,n2,&tag,&radix);
	
	if(tag==2){//交换n1和n2
		char tmp[20];
		strcpy(tmp,n2);
		strcpy(n2,n1);
		strcpy(n1,tmp);
	}
	
	long long dst=getnum(n1,radix);
	long long ans=0;
	long long l=getradix(n2);
	long long r=max(l,dst);
	long long mid;
	
	while(l<=r){
		mid=(l+r)/2;
		ans=getnum(n2,mid);
		if(ans==dst) {
			printf("%d\n",mid);//二分法找到合适的进制mid
			return 0;
		}
		else if(ans<0||ans>dst) r=mid-1;//ans<0表示转换的结果超出long long范围，绝对大于dst了
		else l=mid+1;
	}
	printf("Impossible\n");
	
	return 0;
}

在网上看到一个比较简短方便的写法，才意识到自己一直用c的思路来写，学习一下auto、string、max_element的用法：

// 根据进制，把字符串转为实际数字
long long convert(string numStr, long long radix) {
    long long res = 0;
    int exp = 0; // 指数初始化为0（从最低位开始算）
    
    // auto自动判断类型，rbegin()是最后一个字符的地址，rend()是第一个字符的地址
    for (auto it = numStr.rbegin(); it != numStr.rend(); ++it) {
        if (isdigit(*it)) // 注意这里要加*才能得到值
            res += (*it - '0') * pow(radix, exp++);
        else
            res += (*it - 'a' + 10) * pow(radix, exp++);
    }
    return res;
}

//......

// 找到字符串形式的n2中最大的那个字符的地址
char maxChar = *max_element(numStr.begin(), numStr.end());

two pointers

使用两个下标i、j同时扫描：O(n)

题号	题目名称	描述	注意点
B1030/A1085	完美数列	输出给定序列中满足max<=min*p的子序列	min*p在long long范围；使用i（首位，第一层循环）、j（末位，第二层循环）同时扫描找到合适的max值。
B1035/A1089	Insert or Merge	根据输入的中间序列判断排序算法是插入还是归并	考虑两种算法的特点，用i、j分别记录首个已排好序列的末尾和未排序的首部从而判断；在归并中，首个a[i]>=a[i-1]的位置不一定是当前归并的size边缘，需要从头跑一遍归并才能找到下一趟的排序结果。
A1029	Median	找出两个序列的中位数	如果用i和j逐个判断，中位数的位置应该是 (m+n-1)/2，记得判断某个序列遍历完、另一个序列剩很多个数的情况
A1048	Find Coins	输出和等于m的两个数字	i和j分别从头尾开始遍历，根据a[i]+a[j]大于或小于m来判断i还是j自增/减。

归并排序O(nlogn)

递归实现：

const int maxn=100;
void merge(int A[],int L1,int R1,int L2,int R2);

void mergeSort(int A[],int left,int right){
    if(left<right){
        int mid=(left+right)/2;
        mergeSort(A,left,mid);
        mergeSort(A,mid+1,right);
        merge(A,left,mid,mid+1,right);//两个子区间合并
    }
}

void merge(int A[],int L1,int R1,int L2,int R2){
    int i=L1,j=L2;
    int temp[maxn],index=0;//temp为合并后的数组
    
    while(i<=R1&&j<=R2){
        if(A[i]<A[j]) temp[index++]=A[i++];
        else temp[index++]=A[j++];
    }
    
    //复制剩下的元素
    while(i<=R1) temp[index++]=A[i++];
    while(j<=R2) temp[index++]=A[j++];
    
    for(i=0;i<index;i++) A[L1+i]=temp[i];//将合并后的数组回填数组A
}

快速排序O(nlogn)

//根据A[left]进行快速排序
int Partition(int A[],int left,int right){
    int temp=A[left];
    while(left<right){
        while(left<right&&A[right]>temp) right--;
        A[left]=right;
        while(left<right&&A[left]<=temp) left++;
        A[right]=A[left];
    }
    A[left]=temp;
    return left;//返回相遇的下标
}

void quickSort(int A[], int left,int right){
    if(left<right){
        int pos=Partition(A,left,right);
        quickSort(A,left,pos-1);
        quickSort(A,pos+1,right);
    }
}

其他高效技巧

题号	题目名称	描述	注意点
B1040/A1093	有几个PAT	按PAT顺序组成的字符串有多少	从后往前遍历，分别计算T、AT、PAT的个数
B1045/A1101	快速排序	找出快速排序中主元有可能是哪几个	考虑快速排序的特点，只拿当前数与前面几个数字中的最大值比较，用排序的预处理解决当前数后面的大小问题。

【3】数学问题

简单数学

题号	题目名称	描述	注意点
B1003	我要通过！	PAT相关的正则表达式	从aPbTc到aPbATca的推理，类似PA*T
B1019/A1069	数字黑洞	演示四位数相减得到固定数字6147的过程	暂存数字a的字符数组s，每次写的时候最好从0~3写（固定四位数），不要把退出循环的条件设为x==0（局部变量用同一个栈的时候，数据被上一次的覆盖了）
B1049/A1104	数列的片段和	找规律计算和	double计算的时候会损失精度，由于题目只保留两位小数，可以用longlong存乘上了1000的数，输出的时候再除回去。
A1008	Elevator	电梯升降所需时间	只根据当前所在楼层和下一次目标楼层判断cost加多少
A1049	Counting Ones	指定数字内所有数字有1的个数	从低位开始算，只考虑本位出现1的情况有多少种

最大公约数与最小公倍数

题号	题目名称	描述	注意点
B1008	数组元素循环右移问题	循环右移m位	直接算出右移后的位置

int gcd(int a,int b){//求a和b的最大公约数
    if(b==0) return a;
    else return gcd(b,a%b);
}

分数四则运算

题号	题目名称	描述	注意点
A1081	Rational Sum	分数求和	注意可约时整数部分的输出
B1034/A1088	有理数四则运算	分数四则运算	注意负数时要输出括号

素数

判断是否为素数：

bool isPrime(int n){// #include<math.h >
    if(n<=1) return false;
    int sqr=(int)sqrt(1.0*n);
    for(int i=2;i<=sqr;i++){
        if(n%i==0) return false;
    }
    return true;
}

题号	题目名称	描述	注意点
B1007	素数对猜想	求相邻素数相差2的对数	列举的i<=n

三、提高篇

【1】基本数据结构

栈

题号	题目名称	描述	注意点
A1051	Pop Sequence	规定按自然数序列入栈，求pop序列是否正确	应该是每push一个数，就判断一次是否需要pop。

队列

题号	题目名称	描述	注意点
A1056	Mice ans Rice	给定老鼠重量和玩家序列，分小组竞赛，给出最终排名	每次将小组内重量第一的老鼠插入到队列结尾，只对当前小组选择max值。

链表

#include<stdlib.h>
typename *p = (typename*) malloc(sizeof(typename));
free(p);

typename* p = new typename;
delete(p);

这类题目的 addr 和 next 地址都不是内存分配的真正地址，而是像 00000-99999 这样的自然数地址，因此结构体里包含的是多个整型变量，没有指针。

数组的下标可以灵活应用，可以是 addr ，也可以是键值等。addr 和 next 也可以用两个数组存储，方便查找的过程（for i=head; i!=-1; i=next[i]）。同时也可以根据题目需求，加入一些标志位的数组，简化查找重复值的过程。

题号	题目名称	描述	注意点
B1025/A1074	反转链表	给定链表地址和next地址，对连续的k个结点反转	可以直接算出移动后的id，或者借助sort进行reverse
A1032	Sharing	求结点连起来的单词的公共部分的首地址	注意求的不一定是公共后缀，而是公共子串；先遍历a标记出现位，再遍历b即可找到。
A1052	Linked List Sorting	从给定结点中，输出从起始地址开始的、按key增序排列的链表	在结构体中加入bool变量标记是否在同一条link上，然后根据key排序，输出。
A1097	Deduplication on a Linked List	从链表中删除重复的值，输出删除后的链表和重复值组成的链表	输出个数不确定，使用vector存储每个元素的地址，用key数组标志当前key是否出现过。

【2】搜索

DFS

背包问题：递归寻求的是所有选择方案的最优解，因此在遍历完n个物品（终止条件）后更新 max 值。每一层解决的问题是，当前第index个物品放还是放，分别递归调用处理第index+1个物品的函数。

本质上就是所有可能的情况全列举，走到终止条件再判断是否需要更新 max（回溯是在过程中判断，不符合的直接剪枝）。这里选择的是深度优先，列举的时候是先递归完一种情况（n件物品），再递归下一种情况。

根据题目情况，DFS也可以进行剪枝。

const int maxn=30;
int n, V, maxValue=0;//物品件数n、背包容量V、最大价值maxValue
int w[maxn], c[maxn];//w[i]为每件物品的重量，c[i]为每件物品的价值

//index为当前处理的物品编号
//sumW 和 sumC 分别为当前总重量和当前总价值
void DFS(int index, int sumW, int sumC)
{
	if(index==n){//已经完成对n件物品的选择（死胡同）
        if(sumW<=V && sumC>maxValue) maxValue=sumC;
        return;
    }
    
    //岔道口
    DFS(index+1,sumW,sumC); //不选第index件物品
    DFS(index+1,sumW+w[index],sumC+c[index]);//选第index件物品
}

int main(){
    //......
    DFS(0,0,0);
    return 0;
}

这类题目似乎比较有特点。如果发现输入数据不大（如小于1000、500），但是解决方案除了枚举没有其他方法，过程中可能可以剪枝减少运行时间，那么DFS应该能解决。

题号	题目名称	描述	注意点
A1103	Integer Factorization	给定数n，求在k个数内，所有p次幂的数的和等于n的解决方案，数字按非增序输出。输出单个数字和最大的方案，若相等，则输出数字（从首位开始比较）最大的方案。	DFS的过程注意剪枝：当前sum≤n的才递归。

另外，在网上看到的快速幂解法：

int Pow(int a,int b)//快速幂 
{
	int ans=1,base=a;
	while(b)
	{
		if(b&1) ans*=base;
		base*=base;
		b>>=1;
	}
	return ans;
}

BFS

枚举的是每一个可能的位置的元素。

例：给定m x n矩阵（0/1），求相邻的1（上下左右）组成的块数。

这里的BFS主要用于找到属于同一个块的元素，并标记为已出现。要注意题目求的不是连续的1的个数，而是这些连续的1的成片的块的个数。

连续的数字有多少个是不确定的，但是固定是从上下左右四个方向去找，所以可以用BFS找到同一块的数字。在遍历每个数字的时候，如果可以用“是否已经在前一块统计过”这样的标志位辅助查找，可以节省很多运行时间。

#include<stdio.h>
#include<queue>
using namespace std;
const int maxn = 100;
struct node{
    int x,y;//横纵坐标
}Node;
int n,m;
int matrix[maxn][maxn];//01矩阵
bool inq[maxn][maxn] = {false};// 记录位置（x，y）是否已入过队
int X[4]={0,0,1,-1},Y[4]={1,-1,0,0}; //增量数组-》上下左右

bool judge(int x,int y){//判断坐标(x,y)是否需要访问
    if( x>=n || x<0 || y>=m || y<0 ) return false;
    if( matrix[x][y]==0 || inq[x][y]==true ) return false;
    return true;
}

bool BFS(int x,int y){//访问（x，y）所在的块，将块中所有1的inq设为true
    queue<node> Q;
    Node.x=x, Node.y=y;
    Q.push(Node);
    inq[x][y]=true;//初始化：push当前（x,y），标记已访问过
    
    while(!Q.empty()){
        node top=Q.front();
        Q.pop();
        
        for(int i=0;i<4;i++){//访问其上下左右连续相邻的位置（整个块）
            int newX=top.x+X[i];
            int newY=top.y+Y[i];
            if(judge(newX,newY)){//此位置是1，且之前没访问过
                Node.x=newX,Node.y=newY;
                Q.push(Node);
                inq[newX][newY]=true;
            }
        }
    }
    
}

int main(){
    //...读入01矩阵
    int ans=0;// 块数
    for(int x=0;x<n;x++){
        for(int y=0;y<m;y++){//此位置是1，且之前没访问过
            if( matrix[x][y]==1 && inq[x][y]==false ){
                ans++;
                BFS(x,y);//访问整个块，将所有1标记为访问过
            }
        }
    }
    printf("%d",ans);
}

题号	题目名称	描述	注意点
A1091	Acute Stroke	跟前面的例相似，这次给的是三维的矩阵，求连续的1（六个面）组成的块（1的个数至少≥t）中，1的总个数。	三位数组在输入和遍历时，注意坐标顺序

【3】数与二叉树

与普通链表的区别：二叉树每个结点有两个指针（左右孩子）

struct node{
    typename data;
    node* lchild;
    node* rchild;
};

//新建结点
node* newNode(int v){
    node* Node = new node;
    Node->data = v;
    Node->lchild = Node0>rchild = NULL;
    return Node;
}

//查找
void search(node* root, int x, int newdata){
    if(root == NULL) return; //空树
    if(root->data ==x) root->data=newdata; //修改
    search(root->lchild,x,newdata);
    search(root->rchild,x,newdata);
}

//插入
void insert(node* &root, int x){//加上引用符
    if(root == NULL){//空树
        root=newNode(x);//新建结点插入
        return;
    }
    
    if(...) insert(root->lchild,x);//根据具体情况决定插入的是左还是右
    else insert(root->rchild,x);
}

//创建
node* Create(int data[],int n){
    node* root = NULL;
    for(int i=0;i<n;i++) insert(root,data[i]);
    return root;
}

二叉树的遍历

先序遍历（DFS）——根》左子树》右子树：

void preorder(node* root){
    if(root==NULL) return;
    printf("%d\n",root->data);
    preorder(root->lchild);
    preorder(root->rchild);
}

中序遍历（DFS）——左子树》根》右子树：

void inorder(node* root){
    if(root==NULL) return;
    inorder(root->lchild);
    printf("%d\n",root->data);
    inorder(root->rchild);
}

后序遍历（DFS）——左子树》右子树》根：

void postorder(node* root){
    if(root==NULL) return;
    postorder(root->lchild);
    postorder(root->rchild);
    printf("%d\n",root->data);
}

层序遍历（BFS）——根入队》出队》左孩子入队》右孩子入队

struct node{
    int data;
    //int layer;//层次，因题目需要决定是否加入
    node* lchild;
    node* rchild;
}

void LayerOrder(node* root){
    queue<node*> q;// 注意队列里存放的是地址
//    root->layer=1;
    q.push(root);
    while(!q.empty()){
        node* now = q.front();
        q.pop();
        printf("%d\n",now->data);
        
        if(now->lchild != NULL){
            //now->lchild->layer = now->layer +1;
            q.push(now->lchild);
        }
        if(now->rchild != NULL){
            //now->rchild->layer = now->layer +1;
            q.push(now->rchild);
        }
    }
}

已知后序和中序序列，输出先序序列：

/*后序的最后一个总是根节点，在中序中找到根节点，将中序分为左右两个子树，分别输出打印*/
int post[] = {3, 4, 2, 6, 5, 1};
int in[] = {3, 2, 4, 1, 6, 5};
void pre(int root, int start, int end) {
    if(start > end) return ;
    int i = start;
    while(i < end && in[i] != post[root]) i++;
    printf("%d ", post[root]);
    pre(root - 1 - end + i, start, i - 1);
    pre(root - 1, i + 1, end);
}
 
int main() {
    pre(5, 0, 5);
    return 0;
}

题号	题目名称	描述	注意点
A1020	Tree Traversals	已知中序和后序序列，输出层次序列	可借助map的自动排序，对树进行层次排序
A1086	Tree Traversals Again	给定中序序列的出入栈步骤，求后序序列	压栈顺序是前序，出栈顺序的中序，可转为已知前序和中序，求后序
A1102	Invert a Binary Tree	给定0~n-1每个结点的左右孩子，左右反转二叉树，再给出层次序列和中序序列	未出现过的数字为整棵树的root，从root开始push左右孩子得到层次序列；再通过递归将层次序列转成中序序列

A1020 Tree Traversals

#include <cstdio>
#include <vector>
#include <map>
using namespace std;
vector<int> post, in;
map<int, int> level;
void pre(int root, int start, int end, int index) {
    if(start > end) return ;
    int i = start;
    while(i < end && in[i] != post[root]) i++;
    level[index] = post[root];//记录结点的下标，用于排序
    pre(root - 1 - end + i, start, i - 1, 2 * index + 1);
    pre(root - 1, i + 1, end, 2 * index + 2);
}
int main() {
    int n;
    scanf("%d", &n);
    post.resize(n);
    in.resize(n);
    for(int i = 0; i < n; i++) scanf("%d", &post[i]);
    for(int i = 0; i < n; i++) scanf("%d", &in[i]);
    pre(n-1, 0, n-1, 0);
    auto it = level.begin();
    printf("%d", it->second);
    while(++it != level.end()) printf(" %d", it->second);
    return 0;
}

A1086 Tree Traversals Again

void postorder(int rootidx,int startidx,int endidx){//根据前序和中序序列求后序序列
    if(startidx>endidx) return;
    int i=startidx;
    while(i<endidx&&in[i]!=pre[rootidx]) i++;
    postorder(rootidx+1,startidx,i-1);
    postorder(rootidx+i-startidx+1,i+1,endidx);
    post.push_back(pre[rootidx]);
}

A1102 Invert a Binary Tree

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
vector<int> book, in, level;
struct node {
	int l, r;
};
vector<node> t;
void getin(int u) {//层次序列转中序序列
	if(u == -1) return;
	getin(t[u].l);//左子树
	in.push_back(u);//root
	getin(t[u].r);//右子树
} 
int n;
char a, b;
int main() {
	scanf("%d", &n);
	t.resize(n); book.resize(n);
	for(int i = 0; i < n; ++i) {
		scanf("%*c%c %c", &a, &b);
		t[i].r = (a == '-' ? -1 : a - '0');
		t[i].l = (b == '-' ? -1 : b - '0');
		if(t[i].l != -1) book[t[i].l] = 1; // 特别注意负数下标是违反语法的！！！ 
		if(t[i].r != -1) book[t[i].r] = 1;
	}
	int root;
	for(int i = 0; i < n; ++i) if(!book[i]) {
		root = i;
		break;
	}
	queue<int> q;
	q.push(root);
	while(!q.empty()) {
		int u = q.front(); q.pop();
		level.push_back(u);
		if(t[u].l != -1) q.push(t[u].l);
		if(t[u].r != -1) q.push(t[u].r);
	}
	for(int i = 0; i < n; ++i) printf("%d%c", level[i], i == n - 1 ? '\n' : ' ');
	getin(root);
	for(int i = 0; i < n; ++i) printf("%d%c", in[i], i == n - 1 ? '\n' : ' ');
	return 0;
}

树的遍历

先根遍历：

void PreOrder(int root){
    printf("%d",Node[root].data);//当前结点
    for(int i=0;i<Node[root].child.size();i++)
        PreOrder(Node[root],child[i]);//递归访问结点root所有子结点
}

层序遍历：

void LayerOrder(int root){
    queue<int> Q;
    Q.push(root);
    while(!Q.empty()){
        int front = Q.front();
        printf("%d ",Node[front].data);
        Q.pop();//队首元素出队
        for(int i=0;i<Node[front].child.size();i++)
            Q.push(Node[front].child[i]);//当前结点所有子节点入队
    }
}

除此之外，DFS（相当于先根遍历）和BFS（相当于层次遍历）也可以。

这类题目一般是给出各个结点的信息，要求查找树的叶子结点或者每个结点的层次，算出结果。

• 建树：用 vector v [1000]数组，因为每个结点的孩子节点个数是不确定的。数组v的下标是每个节点的下标，如果题目给的是父节点，可以在父节点的元素位置pushback child（当前 i ）；如果给的是孩子结点，直接在当前节点（i）的元素位置 push back 孩子结点。

• 遍历：如果需要知道每一层结点的层数是什么，可以用DFS遍历孩子结点，每次递归调用时带上depth参数即可

  void DFS(int index,int depth) {
  	if(child[index].size()==0){//到达叶子结点
  		//... 此时的depth就是当前结点的层数
  	}
  	
  	for(int i=0;i<child[index].size();i++)//遍历每个孩子结点
  		DFS(child[index][i],depth+1);
  }

题号	题目名称	描述	注意点
A1079	Total Sales of Supply Chain	给出树的孩子结点，求叶子节点的总销售量（单价与层次有关）	可以用DFS遍历到叶子节点后，sum+=num*pow(1+r,depth)，最后再乘上单价p
A1090	Highest Price in Supply Chain	同上，这次给的是树的父结点，求深度最大的叶子结点的零售价和数量	用DFS遍历，每次递归（求下一层孩子结点）时 depth++。递归过程中只需记录最大的深度和统计个数，最后直接算出零售价即可
A1094	The Largest Generation	给出有孩子结点的结点信息，求最多结点的层数	用DFS遍历，同上，加上depth。在每次递归（当前结点）中加上 ans[depth]++
A1106	Lowest Price in Supply Chain	同A1079的供应链，求最低单价（叶子结点）	用DFS遍历，这次保留的是最小的深度并统计同层叶子结点个数
A1004	Counting Leaves	数叶子结点的个数	用DFS遍历，这次只在叶子结点处ans[depth]++
A1053	Path of Equal Weight	给出树的结构和权重，求总权重等于S的每条路径	在前面的基础上加入一个path数组，用于保存每次的路径方案，当找到w==S时，保存一份path数组。因此可以使用vector的二维数组，输出前直接用sort排序，注意写法。

A1079 Total Sales of Supply Chain

//dfs 剪枝
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> tree;
vector<vector<int>> res;
int n, m, s;
int weight[110];
vector<int> path;
int sum = 0;
void dfs(int u)
{
    if (sum > s)
    {
        return;
    }
    if (sum == s && tree[u].size() == 0)
    {
        res.push_back(path);
        return;
    }

    for (int i = 0; i < tree[u].size(); i++)
    {
        int j = tree[u][i];
        path.push_back(weight[j]);
        sum += weight[j];
        dfs(j);
        sum -= weight[j];
        path.pop_back();
    }
}

int main()
{
    cin >> n >> m >> s;
    tree.resize(n);

    for (int i = 0; i < n; i++)
    {
        int temp;
        cin >> temp;
        weight[i] = temp;
    }

    for (int i = 0; i < m; i++)
    {
        int id, k;
        cin >> id >> k;
        for (int j = 0; j < k; j++)
        {
            int temp;
            cin >> temp;
            tree[id].push_back(temp);
        }
    }
    path.push_back(weight[0]);
    sum += weight[0];
    dfs(0);
    
    //vector可直接比较大小
    sort(res.begin(), res.end(), greater<vector<int>>());

    for (int i = 0; i < res.size(); i++)
    {
        for (int j = 0; j < res[i].size(); j++)
        {
            if (!j)
                cout << res[i][j];
            else
                cout << " " << res[i][j];
        }
        cout << endl;
    }
    
    
    return 0;
}

A1053 Path of Equal Weight

//dfs 剪枝
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> tree;
vector<vector<int>> res;
int n, m, s;
int weight[110];
vector<int> path;
int sum = 0;
void dfs(int u)
{
    if (sum > s) return;
    if (sum == s && tree[u].size() == 0)
    {
        res.push_back(path);
        return;
    }

    for (int i = 0; i < tree[u].size(); i++)
    {
        int j = tree[u][i];
        path.push_back(weight[j]);
        sum += weight[j];
        dfs(j);
        sum -= weight[j];
        path.pop_back();
    }
}

int main()
{
    cin >> n >> m >> s;
    tree.resize(n);

    for (int i = 0; i < n; i++)
    {//存储weight数组 
        int temp;
        cin >> temp;
        weight[i] = temp;
    }

    for (int i = 0; i < m; i++)
    {
        int id, k;
        cin >> id >> k;
        for (int j = 0; j < k; j++)
        {
            int temp;
            cin >> temp;
            tree[id].push_back(temp);//存储每个child结点 
        }
    }
    path.push_back(weight[0]);//从根节点开始 
    sum += weight[0];
    dfs(0);
    
    //vector可直接比较大小
    sort(res.begin(), res.end(), greater<vector<int>>());//注意写法

    for (int i = 0; i < res.size(); i++)
    {
        for (int j = 0; j < res[i].size(); j++)
        {
            if (!j) cout << res[i][j];
            else cout << " " << res[i][j];
        }
        cout << endl;
    }
    
    return 0;
}

二叉查找树（BST）

左子树的结点data小于等于根结点的data，右子树的结点data大于根结点data。

查找，最坏的时间复杂度是 O(h)：

void search(node* root,int x){
    if(root == NULL){//查找到叶子结点的孩子结点（NULL），说明查找失败
        printf("search failed\n");
        return;
    }
    if(x == root->data) printf("%d\n",root->data);//查找成功
    else if(x < root->data) search(root->lchild,x);//左子树
    else search(root->rchild,x);//右子树
}

插入，时间复杂度是 O(h)：

void insert(node* &root, int x){
	if(root == NULL){//空树，说明查找失败，即插入位置
		root = newNode(x);//新建结点
		return;
	}
	if(x == root->data) return;//查找成功，说明结点已存在，直接返回
	else if(x < root->data) insert(root->lchild,x);//往左子树插入
    else insert(root->rchild,x);//往右子树插入
}

建立：

node* Create(int data[],int n){
    node* root = NULL;
    for(int i=0;i<n;i++) insert(root,data[i]);
    return root;
}

删除：

node* findMax(node* root){
    while(root->rchild != NULL) root = root->rchild;//一直往右，直到没有右孩子
    return root;
}
node* findMin(node* root){
    while(root->lchild != NULL) root = root->lchild;//一直往左，直到没有左孩子
    return root;
}
void deleteNode(node* &root,int x){
    if(root == NULL) return;
    if(root->data == x){//找到准备删除的结点
        if(root->lchild == NULL && root->rchild == NULL) root=NULL;
        else if(root->lchild != NULL){//左子树不为空
            node* pre = findMax(root->lchild);//找到root前驱:左子树中比左孩子大的max
            root->data = pre->data;
            deleteNode(root->lchild, pre->data);
        }else{//右子树不为空
            node* next = findMin(root->rchild);//找到root后继:右子树中比右孩子小的min
            root->data = next->data;
            deleteNode(root->rchild, next->data);
        }
    }else if(root->data > x) deleteNode(root->lchild,x);
    else deleteNode(root->rchild,x);
}

对二叉查找树进行中序遍历，输出结果是有序的。

题号	题目名称	描述	注意点
A1043	Is it a Binary Search Tree	给定一串先序输出的序列，判断它是否是BST或者镜像BST，如果是则输出后序序列	转换为先序转后序的问题，如果转换后的size不等于n，说明这棵树的先序错误，也就是不是我们假设的BST。
A1064	Complete Binary Search Tree	给定序列，构建完全二叉树，输出层次遍历的序列	因为对二叉树进行中序遍历是有序的，所以可以对输入序列进行排序、得到中序序列，问题变成了中序到层次遍历的转换（完全二叉排序树左孩子结点是2x，右孩子是2x+1，根节点为1）。对树进行中序遍历，找到根结点将对应的输入位置赋值给树就可以了。
A1099	Build a Binary Search Tree	给定二叉排序树的结构（结点下标），填data域，最后输出层次遍历的序列	同上，对输入的序列进行排序得到中序序列。因为这里已经有树的结构，中序遍历的过程中只需要填data就可以了。

A1043 Is it a Binary Search Tree

#include <cstdio>
#include <vector>
using namespace std;
bool isMirror;
vector<int> pre, post;//先序和后序的数组 
void getpost(int root, int tail) {
    if(root > tail) return ;
    int i = root + 1, j = tail;
    if(!isMirror) {
        while(i <= tail && pre[root] > pre[i]) i++;
        while(j > root && pre[root] <= pre[j]) j--;
    } else {
        while(i <= tail && pre[root] <= pre[i]) i++;//右孩子 
        while(j > root && pre[root] > pre[j]) j--;//左孩子 
    }
    if(i - j != 1) return ;

    getpost(root + 1, j);
    getpost(i, tail);
    
    post.push_back(pre[root]);
}
int main() {
    int n;
    scanf("%d", &n);
    pre.resize(n);
    for(int i = 0; i < n; i++)
        scanf("%d", &pre[i]);
    getpost(0, n - 1);//转换为后序序列 
    if(post.size() != n) {
        isMirror = true;
        post.clear();
        getpost(0, n - 1);
    }
    if(post.size() == n) {
        printf("YES\n%d", post[0]);
        for(int i = 1; i < n; i++)
            printf(" %d", post[i]);
    } else {
        printf("NO");
    }
    return 0;
}

A1064 Complete Binary Search Tree

#include <iostream>
#include <algorithm>
using namespace std;
int in[1010], level[1010], n, t = 0;
void inOrder(int root) {
    if (root >= n) return ;
    inOrder(root * 2 + 1);//左子树 
    level[root] = in[t++];//根结点 
    inOrder(root * 2 + 2);//右子树 
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &in[i]);
    sort(in, in + n);
    inOrder(0);
    printf("%d", level[0]);
    for (int i = 1; i < n; i++)
        printf(" %d", level[i]);
    return 0;
}

A1099 Build a Binary Search Tree

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, cnt, b[100], maxLevel;
struct node {
    int data, l, r;
}a[110];
vector<int> v[100];
void dfs(int root, int level) {
    maxLevel = max(level, maxLevel);
    if (a[root].l != -1) dfs(a[root].l, level + 1);//左子树 
    a[root].data = b[cnt++];
    if (a[root].r != -1) dfs(a[root].r, level + 1);//右子树 
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i].l >> a[i].r;
    for (int i = 0; i < n; i++) cin >> b[i];
    sort(b, b + n);
    dfs(0, 0);
    v[0].push_back(0);
    for (int i = 0; i <= maxLevel; i++) {
        for (int j = 0; j < v[i].size(); j++) {
            if (i != 0) cout << " ";
            cout << a[v[i][j]].data;
            if(a[v[i][j]].l != -1) v[i+1].push_back(a[v[i][j]].l);
            if(a[v[i][j]].r != -1) v[i+1].push_back(a[v[i][j]].r);
        }
    }
    return 0;
}

平衡二叉树(AVL)

二叉查找树查找的最坏情况是 O(n)，平衡二叉树是O(logn)。

平衡二叉树加入了结点的权值：

struct node{
    int v,height;
    node* lchild,*rchild;
}

node* newNode(int v){
    node* Node = new node;
    Node->v = v;
    Node->height = 1;
    Node->lchild = Node->rchild = NULL;
    return Node;
}

平衡因子的计算：

int getHeight(node* root){
    if(root == NULL) return 0;
    return root->height;
}
int getBalanceFactor(node* root){
    return getHeight(root->lchild) - getHeight(root->rchild);
}
void updateHeight(node* root){
    root->height = max(getHeight(root->lchild), getHeight(root->rchild))+1;
}

查找过程跟BST是一样的。

并查集

father数组，记录元素 i 的父亲/根结点。通过findFather函数记录，每个i结点记录的是同一棵树上的根结点（递归查找）。

一般还需要一个isRoot数据，统计所有的根结点。

题号	题目名称	描述	注意点
A1107	Social Clusters	给定1-n个人的hobby，根据共同hobby分群，输出群的个数和每个群的人数（非增序）	只要有一个hobby相同都需要合并，因此在每次输入hobby的时候进行一次合并；最终直接遍历每个人的findFather根结点，进行统计。

#include<iostream>
#include<stdio.h> 
#include<vector>
#include <algorithm>
using namespace std;

int hobby[1001]={0};
vector<int> father;
vector<int> isRoot;

int cmp1(int a, int b){
    return a > b;
}

int findFather(int v){
    if(father[v]==v)
        return v;
    else{
        int F = findFather(father[v]);//找到对应的根结点
        father[v] = F;
        return F;
    }
}

void Union(int a,int b)
{
	int fa=findFather(a);
	int fb=findFather(b);
	if(fa!=fb) father[fa]=fb;//合并，设置fa的父节点
}

int main()
{
	int n;
	cin>>n;
	father.resize(n+1);
	isRoot.resize(n+1);
	
	for (int i = 1; i <= n;i++){
        father[i] = i;//初始化 
    }
	
	int k,tmp;
	for(int i=1;i<=n;i++){
		scanf("%d:", &k);//注意冒号的输入
		for(int j=1;j<=k;j++){
			cin>>tmp;
			if(hobby[tmp]==0) hobby[tmp]=i;
			Union(i,hobby[tmp]);
		}
	}
	
	for (int i = 1; i <= n;i++){
        isRoot[findFather(i)]++;//统计树的个数 
    }
    
    int cnt = 0;
    for (int i = 1; i <= n;i++){
        if(isRoot[i]!=0)
            cnt++;
    }
    
    //将数组isRoot按人数逆序排序
    sort(isRoot.begin(), isRoot.end(),cmp1);
    //输出
    cout<<cnt<<endl;
    for(int i = 0; i < cnt; i++) {
        printf("%d", isRoot[i]);
        if(i != cnt - 1) printf(" ");
    }
    
	
	return 0;
}

堆

完全二叉树。

建堆向下调整的过程：

//对heap数组在[low,high]范围向下调整
//其中low为欲调整结点的数组下标，high一般为堆的最后一个元素的数组下标
void downAdjust(int low, int high){
    int i=low,j=i*2;// i为欲调整结点，j为其左孩子
    while(j<=high){//存在孩子结点
        //如果右孩子存在，且右孩子的值大于左孩子
        if(j+1<=high&&heap[j+1]>heap[j]) j=j+1;
        
        //如果孩子中最大的权值比欲调整结点i还大
        if(heap[j]>heap[i]){
            swap(heap[j],heap[i]);
            i=j;
            j=i*2;
        }else break;//孩子的权值都比i小，调整结束
    }
}

void createHeap(){
    for(int i=n/2;i>=1;i--) downAdjust(i,n);
}

void deleteTop(){
    heap[1]=heap[n--];
    downAdjust(1,n);
}

插入时，先将结点放在数组的最后，然后向上调整。

void upAdjust(int low, int high){//high为欲调整下标
    int i=high, j=i/2; //i为欲调整结点，j为i的父亲
    while(j>=low){
        if(heap[j]<heap[i]){
            swap(heap[j],heap[i]);
            i=j;
            j=i/2;
        }else break;//父亲权值都比i大，调整结束
    }
}

void insert(int x){
    heap[n++]=x;
    upAdjust(1,n);
}

堆排序：

void heapSort(){
    createHeap();
    for(int i=n;i>1;i--){
        swap(heap[i],heap[1]);
        downAdjust(1,i-1);
    }
}

题号	题目名称	描述	注意点
A1098	Insertion or Heap Sort	给定原始序列和中间序列，判断此次排序是插入排序还是堆排序	插入排序好判断，堆排序只需要从后往前找一个比a[1]小的数字，跟a[1] swap，然后downAdjust

【4】图算法

邻接矩阵：G二维数组，表示顶点 i 与顶点 j 是否有边。适用于顶点数目<1000的题目。

邻接表：Adj[N]存放同一个顶点的所有出边

vector<int> Adj[N];
Adj[i].push_back(j);//添加一条从顶点i到顶点j的边

struct Node{
    int v,w;
    Node(int _v,int _w) : v(_v), w(_w) {}//构造函数
}
Adj[1].push_back(Node(3,4));

图的遍历

DFS：

//邻接矩阵
int n,G[MAXV][MAXV];
bool vis[MAXV]={false};

void DFS(int u,int depth){//u为当前访问的顶点标号，depth为深度
    vis[u]=true;// 设置u已被访问
    //...    
    
    for(int v=0;v<n;v++)//从u出发能到达的顶点进行枚举
        if(vis[v]==false && G[u][v]!=INF) DFS(v,depth+1);
}
void DFSTrace(){
    for(int u=0;u<n;u++)
        if(vis[u]==false) DFS(u,1);
}


//邻接表
vector<int> Adj[MAXV];
int n;
bool vis[MAXV]={false};

void DFS(int u, int depth){
    vis[u]=true;
    //...
    
    for(int i=0;i<Adj[u].size();i++){
        int v=Adj[u][i];
        if(vis[v]==false) DFS(v,depth+1);
    }
}
void DFSTrace(){
    for(int u=0;u<n;u++)
        if(vis[u]==false) DFS(u,1);
}

题号	题目名称	描述	注意点
A1076	Forwards on Weibo	给定1-n每个用户关注的id，求待查询id发布微博后有多少个转发量	输入的时候创建floower列表，每次BFS时带上depth层数。