【转载】【PAT】PAT甲级题型分类整理

【转载】【PAT】PAT甲级题型分类整理

最短路径

1003. Emergency (25)-PAT甲级真题（Dijkstra算法）

1018. Public Bike Management (30)-PAT甲级真题（Dijkstra + DFS）

1030. Travel Plan (30)-PAT甲级真题（Dijkstra + DFS，输出路径，边权）

1087. All Roads Lead to Rome (30)-PAT甲级真题-Dijkstra + DFS

1111. Online Map (30)-PAT甲级真题（Dijkstra + DFS）

最短路径扩展问题

• 要求数最短路径有多少条

  • count[s] = 1;
  • 如果找到更短路：count[W]=count[V];
  • 如果找到等长路：count[W]+=count[V];

• 要求边数最少的最短路

  • count[s] = 0;
  • 如果找到更短路：count[W]=count[V]+1;
  • 如果找到等长路：count[W]=count[V]+1;

• 存在点权

  比如救火问题，多条最短路径，选择点权最大的那条

  for(int i = 0; i < n; i++) {
  
  	int u = -1, minn = inf;
  
  	for(int j = 0; j < n; j++) {
  
  		if(visit[j] == false && dis[j] < minn) {
  
  			u = j;
  
  			minn = dis[j];
  
  		}
  
  	}
  
  	if(u == -1) break;
  
  	visit[u] = true;
  
  	for(int v = 0; v < n; v++) {
  
  		if(visit[v] == false && e[u][v] != inf) {
  
  			if(dis[u] + e[u][v] < dis[v]) {
  
  				dis[v] = dis[u] + e[u][v];
  
  				num[v] = num[u];
  
  				w[v] = w[u] + weight[v];
  
  			} else if(dis[u] + e[u][v] == dis[v]) {
  
  				num[v] = num[v] + num[u];
  
  				if(w[u] + weight[v] > w[v])
  
  					w[v] = w[u] + weight[v];
  
  			}
  
  		}
  
  	}
  
  }
  
  

• 边权不唯一

  比如旅游规划问题，存在多条最短路径时，选择花费最少的

  void Dijkstra( Vertex s ) {
  
  	while (1) {
  
  		V = 未收录顶点中dist最小者;
  
  		if ( 这样的V不存在)
  
  			break;
  
  		collected[V] = true;
  
  		for ( V 的每个邻接点W )
  
  			if ( collected[W] == false )
  
  				if ( dist[V]+E<V,W> < dist[W] ) {
  
  					dist[W] = dist[V] + E<V,W> ;
  
  					path[W] = V;
  
  					cost[W] = cost[V] + C<V,W> ;
  
  				} else if ( (dist[V]+E<V,W> == dist[W])
  
  				            && (cost[V]+C<V,W> < cost[W]) ) {
  
  					cost[W] = cost[V] + C<V,W> ;
  
  					path[W] = V;
  
  				}
  
  	}
  
  }
  
  

树的遍历

1004. Counting Leaves (30)-PAT甲级真题(bfs,dfs,树的遍历，层序遍历)

1020. Tree Traversals (25)-PAT甲级真题

1053. Path of Equal Weight (30)-PAT甲级真题(树的遍历)

1079. Total Sales of Supply Chain (25)-PAT甲级真题（dfs,bfs,树的遍历）

1086. Tree Traversals Again (25)-PAT甲级真题

1090. Highest Price in Supply Chain (25)-PAT甲级真题

1094. The Largest Generation (25)-PAT甲级真题（bfs,dfs,树的遍历）

1102. Invert a Binary Tree (25)-PAT甲级真题

1106. Lowest Price in Supply Chain (25)-PAT甲级真题(dfs,bfs,树的遍历)

1115. Counting Nodes in a BST (30)-PAT甲级真题（二叉树的遍历，dfs）

1119. Pre- and Post-order Traversals (30)-PAT甲级真题（前序后序转中序）

图的遍历

1013. Battle Over Cities (25)-PAT甲级真题（图的遍历，统计强连通分量的个数，dfs）

1021. Deepest Root (25)-PAT甲级真题（图的遍历，dfs，连通分量的个数）

1034. Head of a Gang (30)-PAT甲级真题（图的遍历dfs）

1072. Gas Station (30)-PAT甲级真题（Dijkstra）

1076. Forwards on Weibo (30)-PAT甲级真题（图的遍历bfs）

深度优先搜索

1103. Integer Factorization (30)-PAT甲级真题（dfs深度优先）

广度优先搜索

1091. Acute Stroke (30)-PAT甲级真题（广度优先搜索）

哈希、散列

1048. Find Coins (25)-PAT甲级真题(Hash散列)

1050. String Subtraction (20)-PAT甲级真题（哈希）

1092. To Buy or Not to Buy (20)-PAT甲级真题

1084. Broken Keyboard (20)-PAT甲级试题

动态规划

1007. Maximum Subsequence Sum (25)-PAT甲级真题（动态规划dp）

1040. Longest Symmetric String (25)-PAT甲级真题（动态规划）

1045. Favorite Color Stripe (30)-PAT甲级真题

1068. Find More Coins (30)-PAT甲级真题（01背包）

排序

1012. The Best Rank (25)-PAT甲级真题

1016. Phone Bills (25)-PAT甲级真题

1025. PAT Ranking (25)-PAT甲级真题

1028. List Sorting (25)-PAT甲级真题

1055. The World’s Richest (25)-PAT甲级真题

1062. Talent and Virtue (25)-PAT甲级真题

1075. PAT Judge (25)-PAT甲级真题

1080. Graduate Admission (30)-PAT甲级真题

1083. List Grades (25)-PAT甲级真题

STL的使用

1022. Digital Library (30)-PAT甲级真题（map映射）

1039. Course List for Student (25)-PAT甲级真题

1047. Student List for Course (25)-PAT甲级真题

1054. The Dominant Color (20)-PAT甲级真题

1063. Set Similarity (25)-PAT甲级真题

1071. Speech Patterns (25)-PAT甲级真题（map应用）

1100. Mars Numbers (20)-PAT甲级真题

链表处理

1032. Sharing (25)-PAT甲级真题

1052. Linked List Sorting (25)-PAT甲级真题

1074. Reversing Linked List (25)-PAT甲级真题

1097. Deduplication on a Linked List (25)-PAT甲级真题

大整数

1023. Have Fun with Numbers (20)-PAT甲级真题（大整数运算）

1024. Palindromic Number (25)-PAT甲级真题（大整数相加）

二叉搜索树

1043. Is It a Binary Search Tree (25)-PAT甲级真题

Complete Binary Search Tree (30)-PAT甲级真题

1099. Build A Binary Search Tree (30)-PAT甲级真题

平衡二叉树

1066. Root of AVL Tree (25)-PAT甲级真题

堆排序

1098. Insertion or Heap Sort (25)-PAT甲级真题（堆排序）

贪心算法

1033. To Fill or Not to Fill (25)-PAT甲级真题（贪心算法）

1037. Magic Coupon (25)-PAT甲级真题（贪心算法）

1038. Recover the Smallest Number (30)-PAT甲级真题（贪心算法）

1067. Sort with Swap(0,*) (25)-PAT甲级真题（贪心算法）

1070. Mooncake (25)-PAT甲级真题

并查集

1107. Social Clusters (30)-PAT甲级真题（并查集）

1114. Family Property (25)-PAT甲级真题（并查集）

1118. Birds in Forest (25)-PAT甲级真题（并查集）

树状数组

1057. Stack (30)-PAT甲级真题（树状数组）

原文出处：

作者：柳婼

链接：https://www.liuchuo.net/archives/2502

以下内容作为补充

线性结构：数组，栈，队列看一下就过了；

链表自己实现了一遍；

常见排序理解并会写。

树：二叉搜索树熟练（尤其是各种遍历）；AVL树和红黑树尽力理解了一下，我是真的记不住……

图：BFS, DFS, 最短路（dijkstra, spfa, floyd）。

这里的题目最常见，要能写得很灵活。

其它：堆，背包问题（良心教程 https://github.com/tianyicui/pack/blob/master/V2.pdf），贪心问题， KMP（还没遇到过题目）。