分类: PAT甲级 |
作者: chengbei |
发表于: 2018-03-13 23:17 |
316 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1135

**1135. Is It A Red-Black Tree (30)**

There is a kind of balanced binary search tree named red-black tree in the data structure. It has the following 5 properties:

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2018-03-13 23:16 |
267 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1134

**1134. Vertex Cover (25)**

A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. Now given a

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2018-03-13 23:14 |
177 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1133

**1133. Splitting A Linked List (25)**

Given a singly linked list, you are supposed to rearrange its elements so that all the negative values appear before all of the non-negatives, and all the values in [0, K]

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2018-03-13 23:13 |
18309 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1132

**1132. Cut Integer (20)**

Cutting an integer means to cut a K digits long integer Z into two integers of (K/2) digits long integers A and B. For example, after cutting Z = 167334,

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2018-03-13 23:10 |
183 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1127

**1127. ZigZagging on a Tree (30)**

Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences.

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2018-03-12 23:08 |
172 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1126

**1126. Eulerian Path (25)**

In graph theory, an Eulerian path is a path in a graph which visits every edge exactly once. Similarly, an Eulerian circuit is an Eulerian path which starts and ends on the same vertex.

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2018-03-12 23:05 |
185 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1125

**1125. Chain the Ropes (25)**

Given some segments of rope, you are supposed to chain them into one rope. Each time you may only fold two segments into loops and chain them into one

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2018-03-12 23:04 |
57 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1124

**1124. Raffle for Weibo Followers (20)**

John got a full mark on PAT. He was so happy that he decided to hold a raffle（抽奖） for his followers on Weibo -- that is, he

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2018-03-12 22:56 |
73 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1123

**1123. Is It a Complete AVL Tree (30)**

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2018-03-12 22:55 |
59 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1122

**1122. Hamiltonian Cycle (25)**

The "Hamilton cycle problem" is to find a simple cycle that contains every vertex in a graph. Such a cycle is called a "Hamiltonian cycle".

In this problem, you are supposed to tell if a given cycle is

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2018-03-11 22:53 |
59 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1121

**1121. Damn Single (25)**

"Damn Single (单身狗)" is the Chinese nickname for someone who is being single. You are supposed to find those who are alone in a big party, so they can be taken care of.
**Input Specification:**

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2018-03-11 22:52 |
68 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1120

**1120. Friend Numbers (20)**

Two integers are called "friend numbers" if they share the same sum of their digits, and the sum is their "friend ID". For example, 123 and 51 are

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2018-03-11 22:50 |
75 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1119

**1119. Pre- and Post-order Traversals (30)**

Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2018-03-11 22:45 |
64 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1118

**1118. Birds in Forest (25)**

Some scientists took pictures of thousands of birds in a forest. Assume that all the birds appear in the same picture belong to the same tree.

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2018-03-11 22:44 |
72 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1117

**1117. Eddington Number(25)**

"British astronomer Eddington liked to ride a bike. It is said that in order to show off his skill, he has even defined an "Eddington number",

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2018-03-10 22:43 |
70 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1116

**1116. Come on! Let's C (20)**

"Let's C" is a popular and fun programming contest hosted by the College of Computer Science and Technology, Zhejiang University. Since the idea of the contest is for fun, the award rules are funny as the following:

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2018-03-10 22:41 |
118 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1111

**1111. Online Map (30)**

Input our current position and a destination, an online map can recommend several paths. Now your job is to recommend two paths to your user: one is the shortest, and the other is the fastest. It is guaranteed that a path exists for

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2018-03-10 22:38 |
65 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1110

**1110. Complete Binary Tree (25)**

Given a tree, you are supposed to tell if it is a complete binary tree.

**Input Specification:**

Each input file contains one test case. For each case,

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2018-03-08 22:37 |
62 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1109

**1109. Group Photo (25)**

Formation is very important when taking a group photo. Given the rules of forming K rows with N people as the following:

The number of people in each row must be N/K (round down to the nearest integer),

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2018-03-07 22:34 |
65 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1064

**1064. Complete Binary Search Tree (30)**

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

The left subtree of a node contains only nodes with keys less than the

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2018-03-07 22:33 |
72 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1063

**1063. Set Similarity (25)**

Given two sets of integers, the similarity of the sets is defined to be Nc/Nt*100%, where Nc is the number of distinct common numbers shared by the two sets,

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2018-03-07 22:30 |
73 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1062

**1062. Talent and Virtue (25)**

About 900 years ago, a Chinese philosopher Sima Guang wrote a history book in which he talked about people's talent and virtue. According to his theory, a man

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2018-03-07 18:00 |
60 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1061

**1061. Dating (20)**

Sherlock Holmes received a note with some strange strings: "Let's date! 3485djDkxh4hhGE 2984akDfkkkkggEdsb s&hgsfdk d&Hyscvnm". It took him only a minute to figure out that

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-09-14 17:58 |
66 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1108

**1108. Finding Average (20)**

The basic task is simple: given N real numbers, you are supposed to calculate their average. But what makes it complicated is that some of the input numbers might not be legal. A "legal" input is a real number in [-1000, 1000] and is accurate up to no more than 2 decimal places. When you calculate the average, those illegal numbers must not be counted in.

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-09-13 17:56 |
63 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1107

**1107. Social Clusters (30)**

When register on a social network, you are always asked to specify your hobbies in order to find some potential friends with the same hobbies. A "social cluster" is a set of people who have some of their hobbies in common. You are supposed to find all the clusters.

**Input Specification:**

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-09-12 17:55 |
75 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1106

**1106. Lowest Price in Supply Chain (25)**

A supply chain is a network of retailers（零售商）, distributors（经销商）, and suppliers（供应商）-- everyone involved in moving a product from supplier to customer.

Starting from one root supplier, everyone on the chain buys products from one's supplier in a price P and sell or distribute them in a price that is r%

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-09-12 17:49 |
63 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1105

**1105. Spiral Matrix (25)**

This time your job is to fill a sequence of N positive integers into a spiral matrix in non-increasing order. A spiral matrix is filled in from the first element at the upper-left corner, then move in a clockwise spiral. The matrix has m rows and n columns, where m and n satisfy the following: m*n must be equal to N; m>=n; and m-n is the minimum of all the possible values.

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-09-11 17:32 |
74 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1104

**1104. Sum of Number Segments (20)**

Given a sequence of positive numbers, a segment is defined to be a consecutive subsequence. For example, given the sequence {0.1, 0.2, 0.3, 0.4}, we have 10 segments: (0.1) (0.1, 0.2) (0.1, 0.2, 0.3) (0.1, 0.2, 0.3, 0.4) (0.2) (0.2, 0.3) (0.2, 0.3, 0.4) (0.3) (0.3, 0.4) (0.4).

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-09-11 17:29 |
81 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1103

**1103. Integer Factorization (30)**

The K-P factorization of a positive integer N is to write N as the sum of the P-th power of K positive integers. You are supposed to write a program to find the K-P factorization of N for any positive integers N, K and P.

**Input Specification:**

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-09-09 17:24 |
68 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1102

**1102. Invert a Binary Tree (25)**

The following is from Max Howell @twitter:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can't invert a binary tree on a whiteboard so fuck off.

Now it's your turn to prove that YOU CAN invert a binary tree!

**Input Specification:**

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-09-09 17:21 |
66 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1100

**1100. Mars Numbers (20)**

People on Mars count their numbers with base 13:

Zero on Earth is called "tret" on Mars.
The numbers 1 to 12 on Earch is called "jan, feb, mar, apr, may, jun, jly, aug, sep, oct, nov, dec" on Mars, respectively.
For the next higher digit, Mars people name the 12 numbers as "tam, hel, maa, huh, tou, kes, hei, elo, syy, lok, mer, jou", respectively.

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-09-08 17:23 |
68 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1101

**1101. Quick Sort (25)**

There is a classical process named partition in the famous quick sort algorithm. In this process we typically choose one element as the pivot. Then the elements less than the pivot are moved to its left and those larger than the pivot to its right. Given N distinct positive integers after a

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-09-07 17:19 |
68 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1095

**1095. Cars on Campus (30)**

Zhejiang University has 6 campuses and a lot of gates. From each gate we can collect the in/out times and the plate numbers of the cars crossing the gate. Now with all the information available, you are supposed to tell, at any specific time point, the number of cars parking on campus, and at the end of the day find the cars that have parked for the longest time period.

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-09-05 17:12 |
86 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1094

**1094. The Largest Generation (25)**

A family hierarchy is usually presented by a pedigree tree where all the nodes on the same level belong to the same generation. Your task is to find the generation with the largest population.

**Input Specification:**

Each input file contains one test case. Each case starts

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-09-04 23:40 |
72 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1093

**1093. Count PAT's (25)**

The string APPAPT contains two PAT's as substrings. The first one is formed by the 2nd, the 4th, and the 6th characters, and the second one is formed by the 3rd, the 4th, and the 6th characters.

Now given any string, you are supposed to tell the number of PAT's contained in the string.

**Input Specification:**

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-09-04 23:20 |
74 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1092

**1092. To Buy or Not to Buy (20)**

Eva would like to make a string of beads with her favorite colors so she went to a small shop to buy some beads. There were many colorful strings of beads. However the owner of the shop would only sell the strings in whole pieces. Hence Eva must check whether a string in

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-09-04 23:14 |
70 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1091

**1091. Acute Stroke (30)**

One important factor to identify acute stroke (急性脑卒中) is the volume of the stroke core. Given the results of image analysis in which the core regions are identified in each MRI slice, your job is to calculate the volume of the stroke core.

**Input Specification:**

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-09-03 22:47 |
75 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1090

**1090. Highest Price in Supply Chain (25)**

A supply chain is a network of retailers（零售商）, distributors（经销商）, and suppliers（供应商）-- everyone involved in moving a product from supplier to customer.

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-09-02 22:38 |
69 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1089

**1089. Insert or Merge (25)**

According to Wikipedia:

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-09-02 22:36 |
80 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1088

**1088. Rational Arithmetic (20)**

For two rational numbers, your task is to implement the basic arithmetics, that is, to calculate their sum, difference, product and quotient.

**Input Specification:**

Each input file contains one test case, which gives in one line the two rational numbers in the format "a1/b1 a2/b2".

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-09-01 22:34 |
78 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1087

**1087. All Roads Lead to Rome (30)**

Indeed there are many different tourist routes from our city to Rome. You are supposed to find your clients the route with the least cost while gaining the most happiness.

Each input file contains one test case. For each case, the first line contains 2 positive integers N (2<=N<=200), the number of cities, and K, the total number of routes betwee

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-08-31 22:25 |
72 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1086

**1086. Tree Traversals Again (25)**

An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-08-30 22:24 |
72 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1085

**1085. Perfect Sequence (25)**

Given a sequence of positive integers and another positive integer p. The sequence is said to be a "perfect sequence" if M <= m * p where M and m are the maximum and minimum numbers in the sequence, respectively.

Now given a sequence and a parameter p, you are supposed to find from the sequence as many numbers as possible to form a perfect subsequence.

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-08-30 22:08 |
70 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1084

**Broken Keyboard (20)**

Weibo is known as the Chinese version of Twitter. One user on Weibo may have many followers, and may follow many other users as well. Hence a social network is formed with followers relations. When a user makes a post on Weibo, all his/her followers can view and forward his/her post, which

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-08-30 22:05 |
70 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1076

**1076. Forwards on Weibo (30)**

Weibo is known as the Chinese version of Twitter. One user on Weibo may have many followers, and may follow many other users as well. Hence a social network is formed with followers relations. When a user makes a post on Weibo, all his/her followers can view and forward his/her post, which can then be

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-08-28 22:04 |
83 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1075

**1075. PAT Judge (25)**

The ranklist of PAT is generated from the status list, which shows the scores of the submittions. This time you are supposed to generate the ranklist for PAT.

Input Specification:

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-08-26 22:02 |
69 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1074

**1074. Reversing Linked List (25)**

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K = 3, then you must output 3→2→1→6→5→4; if K = 4, you must output 4→3→2→1→5→6.

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-08-25 15:16 |
57 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1073

**1073. Scientific Notation (20)**

Scientific notation is the way that scientists easily handle very large numbers or very small numbers. The notation matches the regular expression [+-][1-9]"."[0-9]+E[+-][0-9]+ which means that the integer portion has exactly one digit, there is at least one digit in the fractional portion

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-08-24 15:14 |
75 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1072

**1072. Gas Station (30)**

A gas station has to be built at such a location that the minimum distance between the station and any of the residential housing is as far away as possible. However it must guarantee that all the houses are in its service range.

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-08-23 15:10 |
65 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1071

**1071. Speech Patterns (25)**

People often have a preference among synonyms of the same word. For example, some may prefer "the police", while others may prefer "the cops". Analyzing such patterns can help to narrow down a speaker's identity, which is useful when validating, for example, whether it's still the same person behind an online avatar.

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-08-22 15:08 |
63 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1070

**1070. Mooncake (25)**

Mooncake is a Chinese bakery product traditionally eaten during the Mid-Autumn Festival. Many types of fillings and crusts can be found in traditional mooncakes according to the region's culture. Now given the inventory amounts and the prices of all kinds of the mooncakes, together with the maximum total demand of the market, you are supposed to

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-08-18 15:03 |
109 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1069

**1069. The Black Hole of Numbers (20)**

For any 4-digit integer except the ones with all the digits being the same, if we sort the digits in non-increasing order first, and then in non-decreasing order, a new number can be obtained by taking the second number from the first one. Repeat in this manner we will soon end u

继续阅读

分类: PAT甲级 |
作者: chengbei |
发表于: 2017-08-16 14:24 |
61 阅读

### 原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1001

Calculate a + b and 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**
**Output**
For each test case, you should output the s

继续阅读