PAT甲之初窥门径（上）_pat初窥门径答案

引子

此游戏副本名为PAT甲，相信有不少的玩家都知道此副本，并有部分玩家通关过此副本。此副本能让初级玩家获得丰厚的经验值，甚至可能获得进阶的关键钥匙。本玩家经历了15天终于刷完了此副本，留下副本攻略以供其余玩家参考。
此副本大体分为两个部分，其一是规律题，也即是只要掌握了题怪的运动规律，则可以不掉血也能获得分值，另一是技巧题，这个就得靠历史的打怪经验或是一定的天资了。
规律题分为7种：

1. STL（标准模板库）
2. 排序（插入排序，归并排序，堆排序，表排序）
3. 二叉树，图论，联通体，并查集
4. BFS（宽度优先搜索算法），DFS（深度优先搜素算法）
5. 验证问题
6. 数组映射问题
7. 字符串处理问题

技巧题分为3种：

1. 数学关联
2. 贪吃算法
3. 动态规划

规律题破解攻略

规律题是按照固有的框架搭建的，因此是有规律可循的，也是有固定的模板可供破解的，只要玩家记住固定的心法，便可破之。

攻略之STL

STL也称标准模板库，一般的小题，仅仅需要玩家在新手村点亮的技能即可，稍微有点难度的题，也仅需要玩家组合施放技能的能力。一般的小题类似如下：“1006 Sign In and Sign Out”，而有点难度的题也莫过于“1014 Waiting in Line”，攻破他们首要的是了解Vector，Map，Pair，Set，Queue，Stack这些基本容器的用法。

STL类型的题型分为这样几种：排队题，统计题，模拟题。
排队题和统计题，需要一定的面向对象的思维，即通过struct构造体构造出对象，如 1014 Waiting in Line

struct window 
{
    int endtime;  //结束时间
	int capacity; //容量
	queue<int> cust;  //客户队列
}; 
1
2
3
4
5
6

此结构体为构造出的银行柜台的对象，构造出对象更能方便玩家思考时按照立体思维模式，而不需要先将思维转换成程序语言再从程序语言整理出题意中种种复杂的关系。
模拟题需要的是对相关概念的理解，如 1051 Pop Sequence 是对栈的一种模拟，只要清楚栈的定义，知道栈是先入后出，能用程序模拟出入栈的操作即可。
STL主要的攻破点是在于如下几点：

• 建立结构体，能根据题意建立对象的结构模型
• 能选用合适的容纳对象的容器
• 能修改相应容器的排序模式

前两点只要能读懂题，知道各个容器的特点就可以了，第三点修改对应容器的排序模式，针对不同的容器，修改排序模式的方式有所不同。
数组，Vector，Dequeue：

#include <algorithm>
bool cmp(int a, int b){
	return a > b;
}
int main(){
	int arr[] = {3,1,2,5,4};
	sort(arr, arr+5, cmp);
}
1
2
3
4
5
6
7
8

Set（内有红黑树，会在插入时自动排序）：

struct Node {
	value;
	bool operator < const(Node& a) const{
		return value < a.value;
	}
}
int main(){
	set<Node> s;
	s.insert(Node{ 0 });
	s.insert(Node{ 1 });
}
1
2
3
4
5
6
7
8
9
10
11

Priority_queue：

• 定义法：

priority_queue<int> q;
priority_queue<int, vector<int>, less<int>> q;
//vector<int>承载底层数据结构堆的容器。
//less<int>表示数字大的优先级大。
//greater<int>表示数字小的优先级小。
1
2
3
4
5

• 重载法：

struct fruit{
	string name;
	int price;
	friend bool operator < (fruit f1, fruit f2){
		//价格高的优先级高
		return f1.price < f2.price;
		//价格低的优先级高
		//return f1.price > f2.price;
	}
}
int main(){
	priority_queue<fruit> q;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

• 外载法：

struct cmp{
	bool operator() (fruit f1, fruit f2){
		return f1.price > f2.price;
	}
}
int main(){
	priority_queue<fruit, vector<fruit>, cmp> q;
}
1
2
3
4
5
6
7
8

攻略之排序

排序这类题，分为4类，模板分别如下：

• 插入排序

 const int maxN = 1000010;
 int arr[maxN];
 void insertSort(){
 	for(int i=1; i<maxN; i++){
 		int j=i;
 		int tmp = arr[i];
 		while(j > 0 && tmp > arr[j]){
 			arr[j] = arr[j-1];
 			j--;
 		}
 		arr[j] = tmp;
 	}
 }
1
2
3
4
5
6
7
8
9
10
11
12
13

• 归并排序

const int maxN = 100010;
int arr[maxN];
void merge(int L1, int R1, int L2, int R2){
  int i = L1;
  int j = L2;
  int idx = 0;
  int tmp[maxN];
  while(i<=R1 && j<=R2){
  	if(arr[i]<arr[j]){
  		tmp[idx++] = arr[i]; 
  	}else{
  		tmp[idx++] = arr[j];
  	}
  }
  while(i<=R1){
  	tmp[idx++] = arr[i];
  }
  while(j<=R2){
  	tmp[idx++] = arr[j];
  }
  for(int k=0; k<idx; k++){
  	arr[L1+k] = tmp[k];
  }
}
void mergeSort(){
	for(int step=2; step/2<maxN; step*=2){
		for(int i=0; i<N; i+=step){
			int mid = i+step/2-1;
			if(mid+1<N){
				merge(i, mid, mid+1, min(i+step-1, maxN-1));
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

• 堆排序

const int maxN = 100010;
int arr[maxN+1];
void downAdjust(int low, int high){
	int i = low;
	int j = 2*i+1;
	while(j <= high){
		if(j+1 <= high && arr[j+1] > arr[j]){
			j+=1;
		}
		if(arr[i] < arr[j]){
			swap(arr[i], arr[j]);
			i = j;
			j = 2*i+1;
		}else{
			break;
		}
	}
}
void createHeap(){
	for(int i=maxN/2; i>=1; i--){
		downAdjust(i, maxN);
	}
}
void sortHeap(){
	createHeap();
	for(int i=N; i>=1; i--){
		swap(arr[i], arr[1]);
		downAdjust(1, i-1);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

• 表排序

表排序是一个方法，如，重量级数组A[] = {book1, book2, book3}，每一个book包含了10GB的内容，如果直接进行排序，内存中移动book会是相当慢的过程。此时表外排序将是好的选择，将book1的地址索引0存到B[0]中，book2的地址索引1存到B[1]中，book3的地址索引2存到B[2]中，排序B时需要读取数据才通过索引读取A的数据即可。
相关题目 1067 Sort with Swap(0, i)

攻略之二叉树

确定方式

二叉树是指树中节点的度不大于2的有序树。唯一 确定一个二叉树的方式有这样4种：

• 已知二叉树的中序序列，且序列的所有值都不同，并有前序序列或后序序列任知其一，即中序+前序，中序+后序可唯一确定二叉树结构。
• 已知每个节点及其孩子节点的关联关系。
• 已知此树为完全二叉树，且已知所有的节点值。
• 已知此树为AVL树，且已知其插入序列。

不能唯一 确定一个二叉树的方式：

• 已知前序序列和后序序列（1119 Pre- and Post-order Traversals）。

能否确定二叉树的关键在于

1. 能否确定根节点。
2. 能否确定左右子树分别由哪些节点构成。
3. 判定根节点和左右子树的方法能否递推到子树上。

这些建二叉树的关键因素怎么和题提供的线索绑定起来，可以看看是否有下表的关系。记：先序序列pre[]，中序序列in[]，后序序列post[]。先序序列的开始索引和结束索引为preLeft，preRight。中序序列的开始索引和结束索引为inLeft，inRight。后序序列的开始索引和结束索引为postLeft，postRight。完全二叉树的开始索引和结束索引为CBTLeft，CBTRight。

存储方式

二叉树的存储方式分为2种：

• 链表

链表式存储是构造一般二叉树的经典方式，只要是二叉树都可用链表的方式进行存储。

struct Node{
	int data;
	Node* lchild;//左子树
	Node* rchild;//右子树
}
Node* createNode(int d){ //创建节点
	Node nd = new Node;
	nd->lchild = NULL;
	nd->rchild = NULL;
	nd->data = data;
	return nd;
}
1
2
3
4
5
6
7
8
9
10
11
12

• 数组

数组式存储用于完全二叉树层次遍历的记录，root为根在数组中的索引，2*root为其左孩子在数组中的索引，2*root+1为其右孩子在数组中的索引。注：此数组的开始节点的索引为1。

细分类型

二叉树继续细分，则可分为完全二叉树，平衡二叉树，红黑树，其某些特性可作为其判断的依据。

攻略之DFS，BFS

DFS又可谓之不撞南墙不回头，这有标准模板，直接套模板就行。

void dfs(int 下一步){
	if(撞到了南墙)
		return;//回头
	dfs(下一步+1);
}
int main(){
	dfs(第一步);
}
1
2
3
4
5
6
7
8

BFS又谓之排队大法，这还是有标准模板，一起套模板吧。

void bfs(int s){
	queue<int> q;
	q.push(s);
	while(!q.empty()){
		取出队首节点top;
		访问队首节点top;
		将队首元素出队;
		将top的下一层节点中未曾入队的节点全部入队，并设置为已入队;
	}
}
1
2
3
4
5
6
7
8
9
10

DFS，BFS是作为探究关系的工具所存在，用这两个工具可以理清各个关系与结构。

DFS，BFS一般是可以互相转换使用的，但使用时仍需注意些许不同的地方。
DFS的函数参数能够传递层次，传递下一个状态，传递递推的信息。如若需要用DFS遍历二叉树，想要获得其高度。便可将高度信息作为函数的一个参数传递下去。

struct Node{
	int data;
	Node* lchild;
	Node* rchild;
}
void dfs(Node* root, int height){
	if(root==NULL){
		return;
	}
	dfs(root->lchild, height+1);
	dfs(root->rchild, height+1);
}
1
2
3
4
5
6
7
8
9
10
11
12

若需要用BFS，则不同于递归函数的参数，此时可以用节点，结构体传输信息。

struct Node{
	int data;
	Node* lchild;
	Node* rchild;
	int level;//层次
}
void bfs(Node* root){
	queue<Node*> q;
	root->level = 1;
	q.push(root);
	while(!q.empty()){
		Node* nd = q.front();
		q.pop();
		if(nd->lchild!=NULL){
			nd->lchild->level = nd->level+1;
			q.push(nd->lchild);
		}
		if(nd->rchild!=NULL){
			nd->rchild->level = nd->level+1;
			q.push(nd->rchild);
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

攻略之并查集，拓扑结构

并查集和拓扑结构也是描述多节点关联关系的结构，并查集的作用为归集，将有关系的节点归集到一起。拓扑结构的作用为发展，将各个节点的先后关系展现出来，用于判断一个给定的图是否是有向无环图。
并查集（1114 Family Property，1118 Birds in Forest）对应的模板代码：

const int maxN = 10010;
int father[maxN];
void initFather(){
	for(int i=0; i<maxN; i++){
		father[i] = i;
	}
}
int findFather(int x){
	if(father[x]==x){
		return father[x];
	}else{
		int F = findFather(father[x]);
		father[x] = F;
		return F;
	}
}
void unionGroup(int x, int y){
	if(findFather(x)!=findFather(y)){
		father[findFather(x)] = findFather(y);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

拓扑排序（1146 Topological Order）的代码模板

const int maxN = 10010;
vector<int> G[maxN];
int n, m, inDegree[maxN];
bool topologicalSort(){
	int num = 0;
	queue<int> q;
	for(int i=0; i<n; i++){
		if(inDegree[i]==0){
			q.push(i);
		}
	}
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(int i=0; i<G[u].size(); i++){
			int v = G[u][i];
			inDegree[v]--;
			if(inDegree[v] == 0){
				q.push(v);
			}
		}
		G[u].clear();
		num++;
	}
	if(num == n) return true;
	else return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

攻略之Dijkstra最短路径

Dijkstra是用来解决 单源最短路径问题，即给定图G和起点S，通过算法得到S到达其他每个顶点的最短距离。一般需要Dijkstra的场景都需要与DFS搭配使用才能解决问题。Dijkstra可求得最短路径，和对应的前置路径节点集，一般最短路径不只有一条，这时需要其他条件从这些相同最短路径中筛选出最合适的那一条，这时就需要DFS了。
图结构的构造有两种方式，一种为邻接矩阵，一种为邻接表。因为邻接矩阵需要直接定义二维数组，若节点个数不是很多的情况下可直接用邻接矩阵，若节点数目过多，则最好采用邻接表的方式定义图。

//邻接矩阵
G[N][N];
//邻接表
vector<int> Adj[N];
//存放终点编号和边权的邻接表
struct Node{
	int v; //边的终点编号
	int w; //边权
}
vector<Node> Adj[N];
1
2
3
4
5
6
7
8
9
10

Dijkstra最短路径+DFS（1018 Public Bike Management）模板代码

const int maxN = 100;
const int INF = 99999999;
int G[maxN][maxN];
bool visited[maxN];
int d[maxN];
int start; //开始
int dest; //终止
int N; //总点数
vector<int> pre[maxN];
vector<int> temppath;
vector<int> path;
void dfs(int start){
	temppath.push_back(start);
	if(start==dest){
		for(int i=temppath.size()-1; i>=0; i--){
			//根据每一条路径的处理内容
		}
		temppath.pop_back();
		return;
	}
	for(int i=0; i<pre[start].size(); i++){
		dfs(pre[start][i]);
	}
	temppath.pop_back();
}
int main(){
	fill(d, d+N, INF);//初始化
	d[start]=0;
	for(int i=0; i<N; i++){
		int mind=INF;
		int u=-1;
		for(int j=0; j<N; j++){
			if(!visited[j] && d[j]<mind){
				mind=d[j];
				u=j;
			}
		}
		if(u==-1){
			break;
		}
		visited[u]=true;
		for(int j=0; j<N; j++){
			if(!visited[j] && G[u][j]!=INF){
				if(d[u]+G[u][j]<d[j]){
					d[j]=d[u]+G[u][j];
					pre[j].clear();
					pre[j].push_back(u);
				}else if(d[u]+G[u][j]==d[j]){
					pre[j].push_back(u);
				}
			}
		}
	}
	dfs(start);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

攻略之大数运算

判断是否是大数运算的条件是看题目中提示的输入数字的范围是否大于10^18。大数运算分为两种，一种是整数型大数的运算，一种是分数型大数的运算。
整数型大数的处理方式是以字符数组的形式读取数据转换为整型数组，然后分别对数字的每一位进行运算。

struct bign{
	int d[1000];
	int len;
	bign(){
		memset(d, 0, sizeof(d));
		len=0;
	}
}
/**
	将读入的字符数组转换为大数结构体
**/
bign change(char str[]){
	bign a;
	a.len = strlen(str);
	for(int i=0; i<a.len; i++){
		a.d[i] = str[a.len-i-1] - '0';
	}
	return a;
}
/**
	大数加法
**/
bign add(bign a, bign b){
	bign c;
	int carry=0;//进位
	for(int i=0; i<a.len||i<b.len; i++){
		int temp = a.d[i]+b.d[i]+carry;
		c.d[c.len++] = temp%10;
		carry = temp/10;
	}
	if(carry!=0){
		c.d[c.len++] = carry;
	}
}
/**
	大数减法
**/
bign sub(bign a, bign b){
	bign c;
	for(int i=0; i<a.len || i<b.len; i++){
		if(a.d[i]<b.d[i]){
			a.d[i+1]--;
			a.d[i]+=10;
		}
		c.d[c.len++] = a.d[i]-b.d[i];
	}
	//去掉高位的0，至少保留一位最低位
	while(c.len-1>=1 && c.d[c.len-1] == 0){
		c.len--;
	}
	return c;
}
/**
	大数乘法
**/
bign multi(bign a, bign b){
	bign c;
	int carry = 0;
	for(int i=0; i<a.len; i++){
		int temp = a.d[i]*b+carry;
		c.d[c.len++]=temp%10;
		carry=temp/10;
	}
	while(carry!=0){//乘法的进位不止一位
		c.d[c.len++]=carry%10;
		carry/=10;
	}
	return c;
}
/**
	大数除法
**/
bign divide(bign a, bign b, int& r){
	bign c;
	c.len = a.len;
	for	(int i=a.len-1; i>=0; i--){
		r = r*10+a.d[i];
		if(r<b){
			c.d[i]=0;
		}else{
			c.d[i] = r/b;
			r = r%b;
		}
	}
	while(c.len-1>=1 && c.d[c.len-1]==0){
		c.len--;
	}
	return c;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

分数型大数（1088 Rational Arithmetic）的处理方式可看作分别对分子和分母进行处理。

struct Fraction{
	int up, down;
};
/**
	求最大公约数
**/
int gcd(int a, int b){
	if(b==0){
		return a;
	}
	return gcd(b, a%b);
}
/**
	分数化简
**/
Fraction reduction(Fraction result){
	if(result.down<0){
		result.up = -result.up;
		result.down = -result.down;
	}
	if(result.up==0){
		result.down = 1;
	}else{
		int d = gcd(abs(result.up), abs(result.down));
		result.up/=d;
		result.down/=d;
	}
	return result;
}
/**
	分数加法
**/
Fraction add(Fraction f1, Fraction f2){
	Fraction result;
	result.up = f1.up*f2.down+f2.up*f1.down;
	result.down = f1.down*f2.down;
	return reduction(result);
}
/**
	分数减法
**/
Fraction minu(Fraction f1, Fraction f2){
	Fraction result;
	result.up = f1.up*f2.down-f2.up*f1.down;
	result.down = f1.down*f2.down;
	return reduction(result);
}
/**
	分数乘法
**/
Fraction multi(Fraction f1, Fraction f2){
	Fraction result;
	result.up = f1.up*f2.up;
	result.down = f1.down*f2.down;
	return reduction(result);
}
/**
	分数除法
**/
Fraction divide(Fraction f1, Fraction f2){
	Fraction result;
	result.up = f1.up*f2.down;
	result.down = f1.down*f2.up;
	return reduction(result);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

攻略之字符串处理

构造方法

string的构造方法有多种，如下介绍常见2种。

• 通过cin读取string

string str;
cin >> str;
1
2

• 通过char[]读入，构造string

char c[100];
scanf("%s", c);
string str = string(c);
1
2
3

遍历方法

遍历方法介绍如下常见2种。

• 索引遍历

string str = "abc";
for(int i=0; i<str.size(); i++){
	printf("%c", str[i]);
}
1
2
3
4

• 迭代器遍历

string str = "abc";
for(string::iterator it=str.begin(); it!=str.end(); it++){
	printf("%c", *it);
}
1
2
3
4

删除元素

删除元素的方法可分为如下2种。

• 迭代器删除

string str = "abcdefg";
str.erase(str.begin()+2, str.end()-1);
cout << str << endl;
1
2
3

输出结果：

abg
1

• 索引删除

string str = "abcdefg";
str.erase(3, 2);
cout << str << endl;
1
2
3

输出结果：

abcfg
1

查找方法

查找分为查找字符串，或者查找某个字符。

• 找字符（找不到则返回string::npos）

string str = "abcdeft";
int cPosition = str.find_first_of('c');
1
2

• 找字符串（找不到则返回string::npos）

string str = "abcdefg";
int idx = str.find("cde");
int idx2 = str.find("cde", 2);//从2位置开始匹配cde子串
1
2
3

数字与string转换

通常此转换用于简单的大数字计算场景。

//string 转 int
string str = "111";
int a = stoi(str);
//int 转 string
str = to_string(a);
//char[] 转 int
string str = "111";
char c[5] = "111";
int b = atoi(c);
b = atoi(str.c_str());
1
2
3
4
5
6
7
8
9
10

大小写转换

若需要将string整体全转为大写或者小写则可按如下方法转换。

string str = "abcABC";
//转换大写
transform(str.begin(), str.end(), str.begin(), ::toupper);
//转换小写
transform(str.begin(), str.end(), str.begin(), ::tolower);
1
2
3
4
5

攻略之数组

数组是用于存放数据的基本容器，下面介绍3种此容器可承载的数据。

树状数组求和模板：

#define lowbit(i) ((i) & (-i))
const int maxN = 100010;
int c[maxN];
int getSum(int x){
	int sum = 0;
	for(int i=x; i>=1; i-=lowbit(i)){
		sum += c[i];
	}
	return sum;
}
void update(int x, int v){
	for(int i=x; i<maxN; i+=lowbit(i)){
		c[i]+=v;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

规律题破解攻略总结

规律题破解攻略解析到此就结束了，想必各位玩家已早已洞悉一切，规律题之所以含有规律二字，便是因为设计者设计题时也是有所设计的上界和下界的，也是有所参考框架的。只要掌握了框架，直接套用便可攻破了。
To be continue…