考试结果:满分。 任何成功都绝非纯碎的偶然,是包含必然的偶然。(9月8日)
准备2019.9.8pat甲级
1.pat甲级的题目重新刷一遍,记录一下经验教训。 2.对题目做个分类,方便进行针对性练习。
- 1122 Hamiltonian Cycle (25) 哈密顿图
- 1126 Eulerian Path (25) 欧拉图
- 1134 Vertex Cover (25) 点覆盖
- 1142 Maximal Clique (25)
- 1150 Travelling Salesman Problem (25)
- 1154 Vertex Coloring (25)
- 1146 Topological Order (25)
- 7-34 任务调度的合理性 (25)
- 7-11 关键活动 (30)
- 1013 Battle Over Cities (25)
- 1021 Deepest Root (25)
能用Dijkstra的就用,因为dfs可能会超时,Dijkstra的时间复杂度中的常数因子比较小。
- 1003 Emergency (25)
- 1072 Gas Station (30)
- 1111 Online Map (30)
- 7-8 哈利·波特的考试 (25) //数组初始化用 memset、fill,
int G[MAXN][MAXN] = {INF}
这种初始化方法是错误的,只有一个元素赋值为INF
- 1076 Forwards on Weibo (30)
- 1091 Acute Stroke (30) //dfs会爆栈
对于在图的问题上应用dfs已经比较熟练,对于其他一些非图类问题做起来还是有点困难,特别是剪枝。
- 1018 Public Bike Management (30)
- 1030 Travel Plan (30)
- 1034 Head of a Gang (30)
- 1045 Favorite Color Stripe (30)
- 1068 Find More Coins (30) //理解状态
- 1087 All Roads Lead to Rome (30)
- 1103 Integer Factorization (30) //1.将一些在搜索中被重复计算的值,提前算好存在数组中;2.剪枝最关键。
- 1131 Subway Map (30) //将 v1 * 10000 + v2 存入unorder_map 用于查询一段区间属于哪条线路
- 1139 First Contact (30) // 对于四个数字的id要注意 0000 ,特别是还要带正负号时 正数读入-0和+0时结果都是+0,要用字符串读入
- 1004 Counting Leaves (30)
- 1020 Tree Traversals (25)
- 1053 Path of Equal Weight (30)
- 1079 Total Sales of Supply Chain (25)
- 1086 Tree Traversals Again (25)
- 1090 Highest Price in Supply Chain (25)
- 1094 The Largest Generation (25)
- 1102 Invert a Binary Tree (25)
- 1106 Lowest Price in Supply Chain (25)
- 1119 Pre- and Post-order Traversals (30)
- 1127 ZigZagging on a Tree (30)
- 1130 Infix Expression (25)
- 1135 Is It A Red-Black Tree (30)
- 1138 Postorder Traversal (25)
- 1159 Structure of a Binary Tree (30) //对于 &&、|| 的使用注意优先级,该加括号的加括号,不要吝啬。熟悉string,sscanf的使用
- 1147 Heaps (30)
- 1155 Heap Paths (30)
- 1110 Complete Binary Tree (25) //完全二叉树的判断,层次遍历将空指针也放入,如果是完全二叉树,那么空指针后面不会有非空指针。
- 1043 Is It a Binary Search Tree (25)
- 1064 Complete Binary Search Tree (30)
- 1099 Build A Binary Search Tree (30)
- 1115 Counting Nodes in a BST (30)
- 1066 Root of AVL Tree (25) * 插入与左右旋
- 1123 Is It a Complete AVL Tree (30) 插入、完全二叉树的判断
- 平衡二叉树的删除
- 1107 Social Clusters (30)
- 1118 Birds in Forest (25)
- 1114 Family Property (25)
- 1158 Telefraud Detection (25)
- 1143 Lowest Common Ancestor (30)
- 1151 LCA in a Binary Tree (30)
- 1125 Chain the Ropes (25)
- 1033 To Fill or Not to Fill (25) *
- 1070 Mooncake (25)
- 1014 Waiting in Line (30)
- 1016 Phone Bills (25)
- 1017 Queueing at Bank (25)
- 1026 Table Tennis (30)
- 1080 Graduate Admission (30)
- 1095 Cars on Campus (30)
- 1007 Maximum Subsequence Sum (25)
- 1049 Counting Ones (30)
- 1078 Hashing (25)
- 1145 Hashing - Average Search Time (25) 平方探测,只有正数项,1^2,2^2,...(m-1)^2,最后一项是m-1,不是包含正负项时的m/2
如果不要求有序,可以采用unordered_map,它是用哈希表来实现的,用法和map相同,但时间复杂度几乎为O(1)
- 1022 Digital Library (30) * //auto it 可以代替 map <string, int>::iterator it
- 1039 Course List for Student (25)
- 1047 Student List for Course (25)
- 1149 Dangerous Goods Packaging (25)
- 1055 The World's Richest (25)
- 1057 Stack (30)
- 1063 Set Similarity (25)
- 1129 Recommendation System (25)
- 1089 Insert or Merge (25)
- 1098 Insertion or Heap Sort (25)
- 1012 The Best Rank (25)
- 1025 PAT Ranking (25)
- 1028 List Sorting (25)
- 1036 Boys vs Girls (25)
- 1038 Recover the Smallest Number (30)
- 1062 Talent and Virtue (25)
- 1075 PAT Judge (25)
- 1083 List Grades (25)
- 1137 Final Grading (25)
- 1141 PAT Ranking of Institutions (25)
- 1153 Decode Registration Card of PAT (25)
- 1157 Anniversary (25)
- 1032 Sharing (25)
- 1052 Linked List Sorting (25)
- 1074 Reversing Linked List (25)
- 1097 Deduplication on a Linked List (25)
- 1133 Splitting A Linked List (25)
- 1051 Pop Sequence (25)
- 1044 Shopping in Mars (25)
- 1085 Perfect Sequence (25)
- 1056 Mice and Rice (25)
- 1105 Spiral Matrix (25)
- 1048 Find Coins (25)
- 1050 String Subtraction (20)
- 1065 A+B and C (64bit) (20)
这一类题,题目读清楚,不要慌。
- 1001 A+B Format (20)
- 1002 A+B for Polynomials (25)
- 1005 Spell It Right (20)
- 1006 Sign In and Sign Out (25)
- 1008 Elevator (20)
- 1009 Product of Polynomials (25)
- 1010 Radix (25) *
- 1011 World Cup Betting (20)
- 1015 Reversible Primes (20)
- 1019 General Palindromic Number (20)
- 1023 Have Fun with Numbers (20)
- 1024 Palindromic Number (25)
- 1027 Colors in Mars (20)
- 1029 Median (25)
- 1031 Hello World for U (20)
- 1035 Password (20)
- 1037 Magic Coupon (25)
- 1040 Longest Symmetric String (25)
- 1041 Be Unique (20)
- 1042 Shuffling Machine (20)
- 1046 Shortest Distance (20)
- 1048 Find Coins (25)
- 1054 The Dominant Color (20)
- 1058 A+B in Hogwarts (20)
- 1059 Prime Factors (25)
- 1060 Are They Equal (25)
- 1061 Dating (20)
- 1067 Sort with Swap(0, i) (25)
- 1069 The Black Hole of Numbers (20)
- 1071 Speech Patterns (25)
- 1073 Scientific Notation (20)
- 1077 Kuchiguse (20)
- 1081 Rational Sum (20)
- 1082 Read Number in Chinese (25)
- 1084 Broken Keyboard (20)
- 1088 Rational Arithmetic (20)
- 1092 To Buy or Not to Buy (20)
- 1093 Count PAT's (25)
- 1096 Consecutive Factors (20) *
- 1100 Mars Numbers (20)
- 1101 Quick Sort (25)
- 1104 Sum of Number Segments (20)
- 1108 Finding Average (20)
- 1109 Group Photo (25)
- 1112 Stucked Keyboard (20)
- 1113 Integer Set Partition (25) //408真题
- 1116 Come on! Let's C (20)
- 1117 Eddington Number (25)
- 1120 Friend Numbers (20)
- 1121 Damn Single (25)
- 1124 Raffle for Weibo Followers (20)
- 1128 N Queens Puzzle (20)
- 1132 Cut Integer (20)
- 1136 A Delayed Palindrome (20) 字符串加法(高精度整数)
- 1140 Look-and-say Sequence (20)
- 1144 The Missing Number (20)
- 1148 Werewolf - Simple Version (20)
- 1152 Google Recruitment (20)
- 1156 Sexy Primes (20)