- 博客(95)
- 收藏
- 关注
RSS订阅
原创 【PAT B1089】 狼人杀-简单版 （20 分)
1089狼人杀-简单版（20分)以下文字摘自《灵机一动·好玩的数学》：“狼人杀”游戏分为狼人、好人两大阵营。在一局“狼人杀”游戏中，1 号玩家说：“2 号是狼人”，2 号玩家说：“3 号是好人”，3 号玩家说：“4 号是狼人”，4 号玩家说：“5 号是好人”，5 号玩家说：“4 号是好人”。已知这 5 名玩家中有 2 人扮演狼人角色，有 2 人说的不是实话，有狼人撒谎但并不是所有狼人都...
2019-04-01 20:01:34
2199
2
原创 1138 Postorder Traversal (25 分)
1138Postorder Traversal(25分)Suppose that all the keys in a binary tree are distinct positive integers. Given the preorder and inorder traversal sequences, you are supposed to output the first nu...
2019-07-04 16:35:19
224
原创 憨憨题1142 Maximal Clique (25 分)
1142Maximal Clique(25分)Acliqueis a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. Amaximal cliqueis a clique that cannot be exten...
2019-07-04 14:55:32
230
原创 1146 Topological Order (25 分)
1146Topological Order(25分)This is a problem given in the Graduate Entrance Exam in 2018: Which of the following is NOT a topological order obtained from the given directed graph? Now you are sup...
2019-07-03 16:36:40
180
原创 1150 Travelling Salesman Problem (25 分)
1150Travelling Salesman Problem(25分)The "travelling salesman problem" asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest pos...
2019-07-03 15:09:22
134
原创 1098 Insertion or Heap Sort (25 分)
1098Insertion or Heap Sort(25分)According to Wikipedia:Insertion sortiterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort rem...
2019-07-02 17:29:04
89
原创 1147 Heaps (30 分)
1147Heaps(30分)In computer science, aheapis a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either greater...
2019-07-02 15:35:19
105
原创 【PAT A1154】Vertex Coloring (25 分)
1154Vertex Coloring(25分)Aproper vertex coloringis a labeling of the graph's vertices with colors such that no two vertices sharing the same edge have the same color. A coloring using at mostk...
2019-07-02 14:24:07
116
原创 【PAT A1155】Heap Paths (30 分)
1155Heap Paths(30分)In computer science, aheapis a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either gr...
2019-07-01 22:44:25
179
原创 【PAT刷题】一个小妙招，缩短近一半运行时间
cmp函数上改动一点点。原理很简单，传引用比传值快很多。两者区别只在于形参的写法不用~1.传引用，只需要64ms。bool cmp(const node &a, const node &b){ return a.sco == b.sco ? a.id < b.id : a.sco > b.sco;}2.传值，需要103ms。bo...
2019-05-21 23:23:27
375
原创 1019 General Palindromic Number (20 分)
1019General Palindromic Number(20分)A number that will be the same when it is written forwards or backwards is known as aPalindromic Number. For example, 1234321 is a palindromic number. All sin...
2019-05-18 08:58:43
315
原创 1015 Reversible Primes (20 分)
1015Reversible Primes(20分)Areversible primein any number system is a prime whose "reverse" in that number system is also a prime. For example in the decimal system 73 is a reversible prime bec...
2019-05-16 22:51:12
418
原创 1012 The Best Rank (25 分)
1012The Best Rank(25分)To evaluate the performance of our first year CS majored students, we consider their grades of three courses only:C- C Programming Language,M- Mathematics (Calculus or ...
2019-05-16 16:37:34
404
原创 刷完PAT乙级的个人经验总结
刷乙级时无论是水题还是难题博主都写了博客，在这个过程中学到了一些知识，也分出了很多时间来写博客。所以为了平衡时间和写题效率，以后只有博主觉得能get到新技能时才会写新博客。1.写博客的确是一种很好的学习方法，道理大家都懂，尝试向他人讲授知识时理解会加深。对于一道题，如果觉得说不清楚 or 觉得只可意会不可言传 or 写不出解题步骤，其实还是自己没有真正地捋清思路，没有真正的会做这题...
2019-05-16 10:54:35
3553
1
原创 1010 Radix (25 分)
1010Radix(25分)Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer isyes, if 6 is a decimal number and 110 is a binary number.Now for any p...
2019-05-16 09:58:19
394
原创 1006 Sign In and Sign Out (25 分)
1006Sign In and Sign Out(25分)At the beginning of every day, the first person who signs in the computer room will unlock the door, and the last one who signs out will lock the door. Given the rec...
2019-05-14 12:58:58
406
原创 1001 A+B Format (20 分)
1001A+B Format(20分)Calculatea+band output the sum in standard format -- that is, the digits must be separated into groups of three by commas (unless there are less than four digits).Input Sp...
2019-05-14 11:40:23
388
原创 【PAT B1029】旧键盘 (20 分)
1029旧键盘(20分)旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字，请你列出肯定坏掉的那些键。输入格式：输入在 2 行中分别给出应该输入的文字、以及实际被输入的文字。每段文字是不超过 80 个字符的串，由字母 A-Z（包括大、小写）、数字 0-9、以及下划线_（代表空格）组成。题目保证 2 个字符串均非空...
2019-05-07 23:15:51
122
原创 【PATB 1028】人口普查 (20 分)
1028人口普查(20分)某城镇进行人口普查，得到了全体居民的生日。现请你写个程序，找出镇上最年长和最年轻的人。这里确保每个输入的日期都是合法的，但不一定是合理的——假设已知镇上没有超过 200 岁的老人，而今天是 2014 年 9 月 6 日，所以超过 200 岁的生日和未出生的生日都是不合理的，应该被过滤掉。输入格式：输入在第一行给出正整数N，取值在(0,105...
2019-05-07 22:39:57
168
原创 【PAT B1020】月饼 (25 分)
1020月饼(25分)月饼是中国人在中秋佳节时吃的一种传统食品，不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量，请你计算可以获得的最大收益是多少。注意：销售时允许取出一部分库存。样例给出的情形是这样的：假如我们有 3 种月饼，其库存量分别为 18、15、10 万吨，总售价分别为 75、72、45 亿元。如果市场的最大需求量只有 20 万吨，那...
2019-05-06 13:10:07
158
原创 模拟题【PAT B1018】锤子剪刀布 (20 分)
1018锤子剪刀布(20分)大家应该都会玩“锤子剪刀布”的游戏：两人同时给出手势，胜负规则如图所示：现给出两人的交锋记录，请统计双方的胜、平、负次数，并且给出双方分别出什么手势的胜算最大。输入格式：输入第 1 行给出正整数N（≤105），即双方交锋的次数。随后N行，每行给出一次交锋的信息，即甲、乙双方同时给出的的手势。C代表“锤子”、J代表“剪刀”、B...
2019-05-06 12:15:36
449
原创 模拟除法【PAT B1017】A除以B (20 分)
1017A除以B(20分)本题要求计算A/B，其中A是不超过 1000 位的正整数，B是 1 位正整数。你需要输出商数Q和余数R，使得A=B×Q+R成立。输入格式：输入在一行中依次给出A和B，中间以 1 空格分隔。输出格式：在一行中依次输出Q和R，中间以 1 空格分隔。输入样例：123456789050987654321 7...
2019-05-05 20:41:32
115
原创 模拟【PAT B1015】德才论 (25 分)
1015德才论(25分)宋代史学家司马光在《资治通鉴》中有一段著名的“德才论”：“是故才德全尽谓之圣人，才德兼亡谓之愚人，德胜才谓之君子，才胜德谓之小人。凡取人之术，苟不得圣人，君子而与之，与其得小人，不若得愚人。”现给出一批考生的德才分数，请根据司马光的理论给出录取排名。输入格式：输入第一行给出 3 个正整数，分别为：N（≤105），即考生总数；L（≥60），为录取...
2019-05-05 19:52:49
244
原创 【PAT B1010】一元多项式求导 (25 分)
1010一元多项式求导(25分)设计函数求一元多项式的导数。（注：xn（n为整数）的一阶导数为nxn−1。）输入格式:以指数递降方式输入多项式非零项系数和指数（绝对值均为不超过 1000 的整数）。数字间以空格分隔。输出格式:以与输入相同的格式输出导数多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。注意“零多项式”的指数和系数都是 0，但是...
2019-05-05 09:53:50
92
原创 【PAT B1009】说反话 (20 分)
1009说反话(20分)给定一句英语，要求你编写程序，将句中所有单词的顺序颠倒输出。输入格式：测试输入包含一个测试用例，在一行内给出总长度不超过 80 的字符串。字符串由若干单词和若干空格组成，其中单词是由英文字母（大小写有区分）组成的字符串，单词之间用 1 个空格分开，输入保证句子末尾没有多余的空格。输出格式：每个测试用例的输出占一行，输出倒序后的句子。输入样例：...
2019-05-05 09:14:10
168
原创 【PAT B1068】万绿丛中一点红 (20 分)
1068万绿丛中一点红(20分)对于计算机而言，颜色不过是像素点对应的一个 24 位的数值。现给定一幅分辨率为M×N的画，要求你找出万绿丛中的一点红，即有独一无二颜色的那个像素点，并且该点的颜色与其周围 8 个相邻像素的颜色差充分大。输入格式：输入第一行给出三个正整数，分别是M和N（≤1000），即图像的分辨率；以及 TOL，是所求像素点与相邻点的颜色差阈值，色差超...
2019-04-27 23:03:25
169
原创 纸老虎【PAT B1035】插入与归并 (25 分)
1035插入与归并(25分)根据维基百科的定义：插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。归并排序进行如下迭代操作：首先将原始序列看成 N 个只包含 1 个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下 1 个有序的序列。现给定原始序列...
2019-04-27 19:37:00
320
原创 【PAT B1034】有理数四则运算 (20 分)
1034有理数四则运算(20分)本题要求编写程序，计算 2 个有理数的和、差、积、商。输入格式：输入在一行中按照a1/b1 a2/b2的格式给出两个分数形式的有理数，其中分子和分母全是整型范围内的整数，负号只可能出现在分子前，分母不为 0。输出格式：分别在 4 行中按照有理数1 运算符 有理数2 = 结果的格式顺序输出 2 个有理数的和、差、积、商。注意输出的每...
2019-04-26 20:37:02
144
原创 【PAT B1055】集体照 (25 分)
1055集体照(25分)拍集体照时队形很重要，这里对给定的N个人K排的队形设计排队规则如下： 每排人数为N/K（向下取整），多出来的人全部站在最后一排； 后排所有人的个子都不比前排任何人矮； 每排中最高者站中间（中间位置为m/2+1，其中m为该排人数，除法向下取整）； 每排其他人以中间人为轴，按身高非增序，先右后左交替入队站在中间人的...
2019-04-26 13:35:20
173
原创 【非排序版】1045快速排序 （25 分)
1045快速排序（25分)著名的快速排序算法里有一个经典的划分过程：我们通常采用某种方法取一个元素作为主元，通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。 给定划分后的N个互不相同的正整数的排列，请问有多少个元素可能是划分前选取的主元？例如给定 $N = 5$, 排列是1、3、2、4、5。则：1 的左边没有元素，右边的元素都比它大，所以它可能是主元；...
2019-04-25 15:35:30
113
原创 【PAT B1074】宇宙无敌加法器 （20 分)
1074宇宙无敌加法器（20分)地球人习惯使用十进制数，并且默认一个数字的每一位都是十进制的。而在 PAT 星人开挂的世界里，每个数字的每一位都是不同进制的，这种神奇的数字称为“PAT数”。每个 PAT 星人都必须熟记各位数字的进制表，例如“……0527”就表示最低位是 7 进制数、第 2 位是 2 进制数、第 3 位是 5 进制数、第 4 位是 10 进制数，等等。每一位的进制 d ...
2019-04-25 08:53:49
123
原创 【PAT B1051】复数乘法 （15 分)
1051复数乘法（15分)复数可以写成(A+Bi)的常规形式，其中A是实部，B是虚部，i是虚数单位，满足i2=−1；也可以写成极坐标下的指数形式(R×e(Pi))，其中R是复数模，P是辐角，i是虚数单位，其等价于三角形式(R(cos(P)+isin(P))。现给定两个复数的R和P，要求输出两数乘积的常规形式。输入格式：输入在一行中...
2019-04-24 23:23:16
1025
原创 纸老虎【PATB1070】结绳 （25 分)
1070结绳（25分)给定一段一段的绳子，你需要把它们串成一条绳。每次串连的时候，是把两段绳子对折，再如下图所示套接在一起。这样得到的绳子又被当成是另一段绳子，可以再次对折去跟另一段绳子串连。每次串连后，原来两段绳子的长度就会减半。给定N段绳子的长度，你需要找出它们能串成的绳子的最大长度。输入格式：每个输入包含 1 个测试用例。每个测试用例第 1 行给出正整数N...
2019-04-23 13:41:07
160
原创 【PAT B1088】三人行 （20 分)
1088三人行（20分)子曰：“三人行，必有我师焉。择其善者而从之，其不善者而改之。”本题给定甲、乙、丙三个人的能力值关系为：甲的能力值确定是 2 位正整数；把甲的能力值的 2 个数字调换位置就是乙的能力值；甲乙两人能力差是丙的能力值的 X 倍；乙的能力值是丙的 Y 倍。请你指出谁比你强应“从之”，谁比你弱应“改之”。输入格式：输入在一行中给出三个数，依次为：M（你自己的能...
2019-04-23 01:21:48
130
原创 【PAT B1075】链表元素分类 （25 分)
1075链表元素分类（25分)给定一个单链表，请编写程序将链表元素进行分类排列，使得所有负值元素都排在非负值元素的前面，而 [0, K] 区间内的元素都排在大于 K 的元素前面。但每一类内部元素的顺序是不能改变的。例如：给定链表为 18→7→-4→0→5→-6→10→11→-2，K 为 10，则输出应该为 -4→-6→-2→7→0→5→10→18→11。输入格式：每个输入包含一...
2019-04-22 22:09:47
117
原创 【PAT B1025】反转链表 （25 分)
1025反转链表（25分)给定一个常数K以及一个单链表L，请编写程序将L中每K个结点反转。例如：给定L为 1→2→3→4→5→6，K为 3，则输出应该为 3→2→1→6→5→4；如果K为 4，则输出应该为 4→3→2→1→5→6，即最后不到K个元素不反转。输入格式：每个输入包含 1 个测试用例。每个测试用例第 1 行给出第 1 个结点的地址、结点总个...
2019-04-22 00:09:41
150
原创 【PAT B1050】螺旋矩阵 （25 分)
1050螺旋矩阵（25分)本题要求将给定的N个正整数按非递增的顺序，填入“螺旋矩阵”。所谓“螺旋矩阵”，是指从左上角第 1 个格子开始，按顺时针螺旋方向填充。要求矩阵的规模为m行n列，满足条件：m×n等于N；m≥n；且m−n取所有可能值中的最小值。输入格式：输入在第 1 行中给出一个正整数N，第 2 行给出N个待填充的正整数。所有数字不超过104...
2019-04-21 19:50:54
147
原创 【PAT B1003】我要通过！ （20 分)
1003我要通过！（20分)“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于 PAT 的“答案正确”大派送 —— 只要读入的字符串满足下列条件，系统就输出“答案正确”，否则输出“答案错误”。得到“答案正确”的条件是：字符串中必须仅有P、A、T这三种字符，不可以包含其它字符； 任意形如xPATx的字符串都可以获得“答案正确”，其中x或者是空字符串，或者是...
2019-04-20 22:50:30
246
原创 【PAT B1040】有几个PAT （25 分)
1040有几个PAT（25分)字符串APPAPT中包含了两个单词PAT，其中第一个PAT是第 2 位(P)，第 4 位(A)，第 6 位(T)；第二个PAT是第 3 位(P)，第 4 位(A)，第 6 位(T)。现给定字符串，问一共可以形成多少个PAT？输入格式：输入只有一行，包含一个字符串，长度不超过105，只包含P、A、T三种字母。输出格式...
2019-04-19 19:36:52
250
原创 【PAT B1037】在霍格沃茨找零钱 （20 分)
1037在霍格沃茨找零钱（20分)如果你是哈利·波特迷，你会知道魔法世界有它自己的货币系统 —— 就如海格告诉哈利的：“十七个银西可(Sickle)兑一个加隆(Galleon)，二十九个纳特(Knut)兑一个西可，很容易。”现在，给定哈利应付的价钱P和他实付的钱A，你的任务是写一个程序来计算他应该被找的零钱。输入格式：输入在 1 行中分别给出P和A，格式为Gall...
2019-04-19 18:44:36
104
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人