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

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. You are supposed to help the scientists to count the maximum number of trees in the forest, and for any pair of birds, tell if they are on the same tree.

In[……]

Read more

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

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, or preorder and inorder traversal sequences. However, if only the postorder and preorder traversal sequences are given, the[……]

Read more

1122. Hamiltonian Cycle (25)-PAT甲级真题

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 a Hamiltonian cycle.

Input Specification:

Each input file contains one test case. For each case[……]

Read more

1124. Raffle for Weibo Followers (20)-PAT甲级真题

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 would select winners from every N followers who forwarded his post, and give away gifts. Now you are supposed to help him generate the list of winners.

Input Specification:

Ea[……]

Read more

PAT 1129. Recommendation System (25) 甲级

Recommendation system predicts the preference that a user would give to an item. Now you are asked to program a very simple recommendation system that rates the user’s preference by the number of times that an item has been accessed by this user.

Input Specification:

Each input file contains one t[……]

Read more

1120. Friend Numbers (20)-PAT甲级真题

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 friend numbers since 1+2+3 = 5+1 = 6, and 6 is their friend ID. Given some numbers, you are supposed to count the number of different friend ID’s among t[……]

Read more

1108. Finding Average (20)-PAT甲级真题

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 t[……]

Read more