【PAT刷题甲级】部分笔记1001-1064~（上）

【PAT刷题甲级】部分笔记1001-1064~（上） 写在前面

这里C++菜鸟一枚~
暑假将近两个月刷PAT甲级的笔记在此，虽然最终也没有取得满意的结果，但是不可否认，还是从中学到了很多，是我准备的还不够充分，希望能给刷题的同学们一些帮助。
PS：不是每道题都有，仅仅记录了本人刷过的题中记下的一点心得，分为上下两篇笔记。
下篇：【PAT刷题甲级】部分笔记1065-1155~（下）

常用知识点：

1. 数据类型转换
(1) string 类型转 int 、 long 、 long long 、 float 、 double 、 long double
// 头文件 #include < string > ：
stoi 、 stol 、 stoll 、 stof 、 stod 、 stold

(2) char c[10] 类型转 int 、 long 、 long long
// 头文件 #include < cstdlib > ：
atoi 、 atol 、 atoll

(3) int 、 long 、 long long 、 float 、 double 、 long double 转 string
// 头文件 #include < string > ：
to_string

2.随机数

#include < cstdlib >
#include < ctime >
srand((unsigned)time(NULL)); //生成随机种子
再使用rand()函数即可
输出给定范围内的随机数需要使用rand（）%（b-a+1）+a //[a,b]范围内的随机数
输出一个大范围内的随机数

（int）（（double）rand（）/32767*（b-a+1）+a）
（int）（round（1.0*rand（）/32767*50000+10000））
//[10000,60000]内的随机数

1001：将数字显示成英语中常用格式，每三位用逗号分离（简单模拟）

commas 逗号
关于字符串中insert函数：

string str="hello";
string s1="Hahah";
str.insert(1,s1);
//在字符串s下标为1的字符前插入字符串s1(字符串下标从0开始)
str.insert(4,5,c);
//在字符串s下标为4的字符o前插入5个字符c
str.insert(0,s1,1,3);
//将字符串s1从下标为1的e开始数3个字符插入字符串s的下标为0的字符前

1002：多项式相加（简单模拟）

polynomial 多项式
exponents 指数 coefficients 系数
nonzero terms 非零项
使用标记数组，用数组自然的序号来表示指数，对应值表示系数
c[i]=j表示指数i的系数为j

1003：最短路径问题（Dijkstra算法）

fill函数可以为数组或者vector中的每个元素赋以相同的值，通常用于初始化！
数组的效率往往比vector高,使用assign函数只能对vector赋初值~所以当要对数组赋初值时可以使用fill函数。
输入：

//fill函数包含在中
eg:	int v[10];
	fill(v,v+10,-1);

输出：

-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

输入：

int v[10][10];
fill(v[0],v[0]+10*10,-1);

输出：

-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

1004：数叶子（DFS）

pedigree 家谱；起源；纯种的
a two-digit number 两位数
The input ends with N being 0. That case must NOT be processed.
输入以n为零。不得处理该情况。
输出每一层的孩子数

vector< int > v[100] 和 vector< int > v(100)
vector初始化后所有元素都是0/false/空。v[100]是二维数组，v(100)是一维
vector< int > v[100]是创建一个有100个vector的vector数组（每个vector的size为0），vector< int > v(100)是创建一个vector，其容量为100

1005：输入一串数字求和，并用英文表示（字符串处理）

法一：

#include 
using namespace std;
    char n[101];
    cin >> n;
    int sum=0,i=0;
    while(n[i]!=''){
        sum+=n[i]-'0';   //字符转为数字求和
        i++;
    }

法二：

char c;
int sum=0;
while((c=getchar())!='n')  //getchar()函数是从I/O字符流中读取一个字符，必须输入换行才能读入字符。
    sum += c-'0';  //字符转为数字求和

1006：记录最早签入、最晚签出（简单模拟）

比较时间：start = 3600 * h1 + 60 * m1 + s1;
end = 3600 * h2 + 60 * m2 + s2;

1008：电梯（简单模拟）

注意审题！第一个数是总共要输的序列数，后面依次输入序列元素
positive numbers 正整数
事先不知道要输多少，夹杂空格输入数字，遇换行停止输入

vector v(0); //动态数组
int n;
while (cin >> n) {
	v.push_back(n);
	if(cin.get() == 'n')	break;
}
int len = v.size();

1009：多项式乘法（简单模拟） 1011：世界杯投注（简单模拟） 1012：最佳排名（排序）

输入每位学生的ID号及各科成绩，平均成绩需要自己算
输出每位学生的最佳排名（单科或平均），若两位同学排名一样，按A>C>M>E的优先级排序

//sort函数头文件：#include 
struct node { 				//定义结构体stu
	int id,best;			//学号
	int score[4],rank[4];	//三科成绩+平均成绩以及相应排名(平均分需要四舍五入)
} stu[2001];

bool cmp(node a, node b) {
	return a.score[flag] > b.score[flag];	//用于计算各科成绩的排名
}

sort(stu,stu+n,cmp);

1013：保卫城市（图的遍历，DFS，统计强连通分量的个数）

用DFS遍历图，可以统计强联通分量个数n，若想要分立的连通分量变为连通图最少需要n-1条线！

1015：可逆素数

一个数本身是素数，且在转换成D进制数后反转后再转换为十进制后也是素数
即：1.先判断该数是否为素数
2.将该数转换为D进制
3.将转换后的数逆转，再转换为十进制，判断是否为素数
4.两次判断均为素数才可输出Yes,否则输出No
a negative N 负数N
radix 基数
radix D D进制

（1）sqrt：

#include  
//sqrt只支持double和float类型，使用时需要强制类型转化
//可以这样
c=(int) sqrt((double)a*a+b*b);
//或者
c=(int) sqrt((float)a*a+b*b);

（2）判断素数

bool isprime(int num) {	//判断素数
	if(num<=1) return false;
	int sqr=(int) sqrt(1.0*num);
	for(int i=2; i<=sqr; i++) {
		if(num % i ==0)	return false;
	}
	return true;
}

（3）将十进制 a 转换为 b 进制数，当 a 不等于 0 时，将 a%b 从后往前倒序保存下来，每次保存后将 a/b 。这样倒序保存的数就是十进制 a 在 b 进制下的结果。

int DtoN(int num,int d) {	//十进制数转换为N进制
	int dnum=0,i=0,count=0;
	while(num!=0) {
		n0[i] = num % d;
		num = num/d;
		i++,count++;
		dnum += n0[i] * pow(10,count-1);
	}
}

（4）关于while(scanf("%d",&n) != EOF)

while(scanf("%d",&n) != EOF){ 
	
}
	return 0;
}

当上面的程序运行时，如果不加" != EOF"，那么这个程序就是个死循环，会一直运行下去；加上" != EOF"后该程序就不是死循环了，如果在终端不进行输入该程序会自动结束(while的意思就是说当当前输入缓存还有东西时就一直读取，直到输入缓存中的内容为空时停止)。
在这"scanf("%d",&n) != EOF"相当于"scanf("%d",&n) != EOF"，或"~scanf("%d",&n)"，或"scanf("%d",&n) == 1 " 。scanf的返回值由后面的参数决定。

但是在C++中不存在这种用法，但相同作用的有while((cin >> a) != 0)

1018：共享单车管理（最短路径+DFS）

vertice 点
edge 边
边权代表时间，点权表示存储的单车数。假设每点单车最大储量为10
vector中的函数clear()删除储存在vector中的所有元素.

Dijkstra求最短路径，dfs求minNeed和minBack和path，dfs的时候模拟一遍需要调整的过程，求出最后得到的need和back，与minNeed和minBack比较然后根据情况更新path，最后输出minNeed path 和 minBack，记得path是从最后一个结点一直到第一个结点的，所以要倒着输出～
vector删除元素pop_back()，默认删除最后一个元素

1019：回文数字

Palindromic Number 回文数字
decimal number 十进制数

1020：树的遍历

postorder traversal 后序遍历
inorder traversal 中序遍历
给出后序遍历和中序遍历，输出层次遍历
可以使用map，key标记改点的下标，最后按照key依次输出

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];	//用index保存每次的根结点 
	pre(root-(end-i)-1,start, i-1,2*index+1);
	pre(root-1,i+1,end,2*index+2);
}

// ⽤迭代器遍历，输出map中所有的元素，键⽤it->first获取，值⽤it->second获取
for (auto it = m.begin(); it != m.end(); it++) {
cout << it->first << " " << it->second << endl;
}
// 访问map的第⼀个元素，输出它的键和值
cout << m.begin()->first << " " << m.begin()->second << endl;
// 访问map的最后⼀个元素，输出它的键和值
cout << m.rbegin()->first << " " << m.rbegin()->second << endl;
// 输出map的元素个数
cout << m.size() << endl;
return 0;

1021：最深根（DFS）

图是联通的且无环可视为树。
输出能使树的高度最大的根，有多个按升序输出，若不能生成树，输出该图的连通分量个数。
acyclic 无环的
adjacent 毗邻的

首先进行DFS计算连通分量个数，>=2不能形成树，=1可以形成树。然后进行两次DFS，第一次先从一个结点遍历保存最高高度层的叶子节点，然后在这些叶子节点中随机选一个进行第二次DFS，同样得到最高高度层的叶子节点，两次叶子节点集合的并集即为所有的最深根。

1022：数字图书馆（map的使用）

（1）getline函数可以输入带空格的字符串getline(cin, inputLine);，读到换行符就结束
如果cin和getline同时使用需要在cin>>后加上 cin.ignore();或者直接用scanf

cin.get (char *str, int maxnum)
cin.get()函数可以接收空格，遇回车结束输入。

cin.getline (char *str, int maxnum)（包含头文件#include ）
cin.getline()函数可以同cin.get()函数类似，也可接收空格，遇回车结束输入。
在cin与cin.getline()之间加上cin.get();语句
fflush(stdin); //刷新缓冲区

（2）map中的find函数和count函数：
①find()
在map中查找关键字（key） 为 k 的元素，返回指向它的迭代器。若k不存在，返回 map::end.
返回值是一个迭代器，成功返回迭代器指向要查找的元素，失败返回的迭代器指向end

②count()
统计map中关键字（key）为 k 的元素的个数，对于 map，返回值不是 1 (存在)，就是 0 (不存在)
返回值是一个整数，1 表示有这个元素，0 表示没有这个元素。只会返回这两个数中的 1 个。可以用于判断某值是否存在

1023：趣味数字（大整数的乘法）

duplication 重复
permutation 排列
一个9位数，每个数字不重复，两倍后仍然满足此要求。
输入一个k位数，双倍后仍然不重复，只是重新排列。

1024：回文数Palindromic Number

所有的一位数都是回文数
字符串赋值用#include < cstring > 下 strcpy(a,b); //把字符串b复制给字符串a

1025：PAT排序（排序） 1027：火星上的颜色（进制转换） 1028：列表排序（结构体排序） 1029：中位数（数字处理） 1030：旅游计划（Dijkstra+DFS）

记住模板！

1031：U字形输出字符串（图形输出） 1032：共享（链表）

可用flag标记在第一个链表中出现的字母，后面遍历只需要flag==true就可输出两个链表公共部分的起始位置。

1034：犯罪团伙的头（图的遍历DFS）

threshold 阈值，下限，临界值

1035：密码（字符串）

两字符串比较用strcmp，两单字符比较直接用==

1036：男孩女孩（简单模拟） 1037：获得钱的最大值（贪心）

排序，之后负的与负的相乘，正的与正的相乘即可，用两个while循环。

1038：恢复最小数（贪心）

对于不同长度字符串的拼接，组装成一个一个最小数。
用cmp函数！

bool cmp(string a,string b){
	return a+b < b+a;
}

1039：学生的课程表（map、set的使用）

根据输入信息输出每个学生的选课情况

1041：最独特（散列）

对10000以内的数字列表，统计每个数字出现次数。

1042：洗牌器（简单模拟）

Spade 黑桃
Heart 红心
Club 梅花
Diamond 方块
Joker 鬼牌
permutation 交换，排列

char c[6]={"SHCDJ"};
for(int i=1;i<55;i++){
	trans[i]=trans[i]-1;
	printf("%c%d",c[trans[i]/13],(trans[i]+1)%13);
	if(i!=54) printf(" ");
} 

1043：它是二叉排序树吗？（BST）

根据先序和中序输出后序遍历

1044：火星购物（二分查找）

int binfind(int i,int &j,int &tmp) {	//二分查找，每次固定i-1点，遍历之后的点来查找>=m的值 
	int left = i,right = n;
	while(left < right) {
		int mid = (left + right) / 2;
		if(sum[mid]-sum[i-1]>=m) {
			right = mid;
		} else {
			left = mid + 1;
		}
	}
	j = right;
	tmp = sum[j] - sum[i-1];
}

1046：最短距离（简单模拟）

环形路，输出两点之间最短距离，每次计算距离和，最终只要计算两点之间的距离差即可，无需再次相加，否则会超时。
两点之间每次都有两条路径，顺时针或者逆时针，取两者间较小者输出即可。

1047：课程的学生名单（vector的使用）

for(auto it=v[i].begin(); it!=v[i].end(); it++) {
	printf("%sn", it->c_str());
}

1048：找硬币（标记数组）

因为总额不会超过1000，故可定义数组标记1000以内的数出现的次数。只要遍历该数组即可。

1050：字符串分割（散列）

使用bool marked[256]标记需要删除的字符即可。
输入带空格的字符串，遇空格停止输入
string s;
getline(cin,s);

1051：d出序列（栈模拟）

原思路（18/25）：

#include 
#include 
#include 
#include 
using namespace std;
int main() {
	int m,n,k;
	scanf("%d%d%d",&m,&n,&k);
	for(int i=0; i v(n);
		for(int j=0; jm) {
			printf("NOn");
			continue;
		} else {
			int flag=1;
			for(int j=1; j1) {
					sort(v.begin(),v.begin()+j);
					int a=v[0]-v[j];
					int b=v[j]-v[j-1];
					if(det<0) {
						if(a>1) {
							flag=0;
							printf("NOn");
							break;
						}
					} else {
						if(b>1) {
							flag=0;
							printf("NOn");
							break;
						}
					}
				} else if(det==0) {
					flag=0;
					printf("NOn");
				}
			}
			if(flag==1)	printf("YESn");
		}
	}
	return 0;
}

1052：链表排序 1053：相等权值的路径（用DFS进行树的遍历）

给出一个值，找出总权值等于该值的所有路径

1054：主色（map的使用）

pixel 像素

1055：世界上最富有的人（结构体排序） 1056：老鼠和米饭（队列）

permutation 排列
注意思路！

1057：栈（分块）

模拟，但要使用分块思想找第k小的数，用sort会超时。

1058：哈利波特里的A+B

long int输入输出为 %ld

1059：素数因子（素数）

给出一串long int型数字，将其拆成素数指数幂之积的形式，若指数为1不用输出。

for(auto it=p.begin(); it!=p.end();) {
	printf("%ld",it->first);
	if(it->second!=1)	printf("^%ld",it->second);
	if(++it!=p.end())	printf("*");
}

最后一个数与之前的不同，采用++it!=p.end()表示。

1060：他们相等吗（数字处理）

Note: Simple chopping is assumed without rounding.
注意：假设没有四舍五入的简单截取。
significant digits

1061：约会（字符串处理，直接用普通for循环，无需用迭代器）

capital English letter 大写英文字母
case sensitive 区分大小写
两个字符串，第一个共同的大写字母是D，代表周四；
第二个共同的大写字母是E，代表14:00（09和AN代表0~23点）
最后两个字符串共同的字母是s且都在第4个位置，代表第4分钟
给出两对字符串，计算约会时间。（DAY HH:MM 周几用三个字母简写表示）

1062：天赋和美德（结构体排序）

记住cmp每个都要return返回结果！

1063：集合的相似度（map、set的使用） 1064：完全二叉排序树（中序遍历）

由于BST的中序遍历恰好为升序排列，用level记住他们的位置即可得到层序遍历。
根的左节点为2root+1，右节点为2root+2

inorder(2*root+1);
level[root]=in[t++];
inorder(2*root+2);