PAT（甲级）2022年春季考试

7-1 Simple Lie Detection(20分)

Lie detection usually uses a set of prepared questions to ask the testee, and the result is obtained by analyzing the testee's reactions. The more advanced technology uses a polygraph (测谎仪) to monitor the physical activities of the testee. Our simple polygraph here is to make a judgment by analyzing the characteristics of the answers to the questions.

First, we ask the testee to complete N multiple choice questions, each with a single answer. Each question has 8 options, which are represented by the lowercase English letters a-h. Then we can obtain a string of length N, consisting of only the lowercase English letters a-h. Score each string, and those whose score exceeds a certain threshold (阈值) T are judged as "suspected liars". The scoring rules are as follows:

• the string starts with an f has its score −2;

• the string ends with an a has its score −1;

• for every longest segment of answeres where the same letter is chosen for consecutive questions, if the segment length is larger than 5, the score is to +3;

• if an a is immediately followed by e or h, the score is to −4;

• for every longest segment of answeres where consecutively increasing letters are chosen to answer consecutive questions (such as abcd or defgh), if the segment length is larger than 3, the score is to +5.

Your job is to score the answers and make a judgement.

Input Specification:

Each input file contains one test case. For each case, the first line gives 3 positive integers N (6≤N≤100), the number of questions; T (≤100), the threshold for judging a liar; and K (≤100), the number of testees.

Then K lines follow, each gives the string of answers of a testee.

Output Specification:

For each testee, print in a line the total score of his/her answers. If the score exceeds the threshold, print !!! after the score.

Sample Input:

12 1 6
fghaebcdeddd
ahhhhhhgbaaa
cdefffffffff
fffffghecaaa
feeeeeeeegcb
aaaaaabbbbbb

Sample Output:

-1
-2
8!!!
-3
1
6!!!

 代码（Python3）：

def pd(str1):
    max1 = 1
    count = 1
    score = 0
    if str1[0] == 'f':
        score -= 2
    if str1[-2] == 'a':
        score -= 1
    for i in range(1, len(str1)):
        if (str1[i] == 'e' or str1[i] == 'h') and str1[i - 1] == 'a':
            score -= 4
        if str1[i] == str1[i - 1]:
            max1 += 1
        else:
            if max1 > 5:
                score += 3
            max1 = 1
        if ord(str1[i]) == ord(str1[i - 1]) + 1:
            count += 1
        else:
            if count > 3:
                score += 5
            count = 1
    return score
 
 
data = list(map(int, input().split()))
for i in range(data[-1]):
    str1 = input()
    score = pd(str1 + " ")
    if score > data[1]:
        print("{}!!!".format(score))
    else:
        print(score)

7-2 The First K Largest Numbers(25分)

The task is simple: find the first K largest numbers from a given sequence of N integers, and output them in descending order.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive integers N (≤106) and K (≤5). Then N integer keys (in the range [−230,230]) are given in the next line. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in descending order the Kth largest numbers.

All the numbers in a line must be separated by a space, and there must be no extra space at the beginning or the end of the line.

Sample Input 1:

10 4
40 25 60 -15 30 -21 80 -1 -5 27

Sample Output 1:

80 60 40 30

Sample Input 2:

4 5
23 -17 99 1

Sample Output 2:

99 23 1 -17

提交结果：

 

 代码（Python3）：

data1 = list(map(int, input().split()))
mi = min(data1)
data2 = list(map(int, input().split()))
data2.sort(reverse=True)
for i in data2[:mi - 1]:
    print(i, end=" ")
print(data2[mi - 1])

7-3 Is It A Binary Search Tree - Again(25分)

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 node's key.
• The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
• Both the left and right subtrees must also be binary search trees.

A binary tree with positive keys can be represented by an array, which stores the keys in level-order as in a complete tree, with all the NULL nodes represented by −1. For example, the following tree is stored in an array as { 40, 25, 60, -1, 30, -1, 80, -1, -1, 27 }.

Now given a sequence of integers in an array, you are supposed to tell if it corresponds to a BST, and output its inorder traversal sequence.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤1000). Then N integer keys (in the range (0, 100000)) are given in the next line. All the numbers in a line are separated by a space.

Output Specification:

For each test case, first print in a line YES if the sequence does correspond to a BST, or NO if not. Then print in the next line the inorder traversal sequence of that tree. It is guaranteed that the tree is non-empty.

All the numbers in a line must be separated by a space, and there must be no extra space at the beginning or the end of the line.

Sample Input 1:

10
40 25 60 -1 30 -1 80 -1 -1 27

Sample Output 1:

YES
25 27 30 40 60 80

Sample Input 2:

11
40 50 60 -1 30 -1 -1 -1 -1 -1 35

Sample Output 2:

NO
50 30 35 40 60

  代码（Python3）：

def inOrder(x):
    if (x * 2 + 1 < num and a[x * 2 + 1] != -1):
        inOrder(x * 2 + 1)
    ins.append(a[x])
    if (x * 2 + 2 < num and a[x * 2 + 2] != -1):
        inOrder(x * 2 + 2)
 
 
num = int(input())
a = list(map(int, input().split()))
f = 1
ins = []
inOrder(0)
for i in range(1, len(ins)):
    if ins[i] < ins[i - 1]:
        f = 0
if f == 0:
    print("NO")
else:
    print("YES")
for i in range(len(ins)):
    if i == 0:
        print(ins[i], end="")
    else:
        print(" " + str(ins[i]), end="")

7-4 The Rescue(30分)

When a group of hikers get lost in a forest and call the rescue team, the team leader would send the hikers a sequence of instructions. By following these instructions, the hikers can always move to a spot that the rescue team can reach, no matter where their original location was. Your job is to generate such a sequence for each given map.

A map is a rectangular（矩形） area consists of n×m unit square areas. There is alway one square X that is marked to be the rescue spot. Some of the areas are blocked and marked to be #, meaning that the hikers cannot enter this block. We assume that the boundaries of the map are all blocked.

An instruction is an integer that represents a direction: 0 for North, 1 for East, 2 for South, and 3 for West. For example, the sequence of instructions 3001 tells the hikers to move toward West and enter the neighboring area first, then head toward North and cross two units, and finally move toward East into the neighboring area. If the destination area is blocked, the hikers must stay in the current area and wait for the next instruction. The sequence you generate must be able to direct the hikers to move into X no matter where they were in that map. Once they arrive at X, they will ignore the rest of the instructions.

There are many different ways of generating the sequence. Here we design a greedy algorithm, hoping to generate a not-too-long sequence. The algorithm works as the following:

• Step 1: find the shortest paths from X to every other areas which the hikers might be in, and pick the furthest area A.
• Step 2: generate sequence s for directing from A to X along the shortest path.
• Step 3: update the map according to s -- that is, mark all the possible areas that the hikers might be in after following s.
• Step 4: if X is the only possible area that contains the hikers, stop; else goto Step 1.

The final sequence can be obtained by concatenating all the s' generated in order.

Notice that while the shortest path might not be unique, you are supposed to output the smallest sequence. Sequence a1​,a2​,⋯,an​ is smaller than sequence b1​,b2​,⋯,bn​ if ther exists 1≤k≤n so that ai​=bi​ for all i

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive numbers 3≤n,m≤100. Then n lines follow, each contains m characters to represent the map. The rescue spot is X, a block is #, and O represents an open area.

Output Specification:

Output in a line the sequence of instructions. There must be no space between the numbers, nor at the beginning or the end of the line.

It is guaranteed that the solution exists.

Sample Input:

4 5
O#OOO
OOXOO
OO##O
OOO#O

Sample Output:

0011300121133

Hint:

During the 1st round, there are 3 candidates for A, as shown below:

O#OOO
OOXOO
OO##O
AOA#A

To direct them to X with the smallest sequence, we must choose the one at the lower-left corner, with the sequence 0011. Since at the very beginning, the hikers might be in any of the open areas, we apply 0011 to every open area, and obtain a map as shown below:

?#OO?
OOXO?
OO##O
OO?#O

where ? means that currently it is a possible position of the hikers. Now clearly we must pick the ? in the last row to be the next A, and direct it to X with 3001. After applying this sequence to other areas marked by ?, we update the map as the following:

?#OO?
OOXOO
OO##O
OOO#O

Now both ?'s have the same path length to X. We pick the upper-left corner to be A since it has the smaller sequence 211. The map is updated as the following:

O#OOO
OOXO?
OO##O
OOO#O

Finally apply 33, we can direct the last ? to X.

Hence the output sequence is 0011 3001 211 33.

提交结果：

代码（Python3）：

# 0 表示北，1 表示东，2 表示南，3 表示西
def bfs(x, y):
    vis = [[0 for i in range(m + 2)] for j in range(n + 2)]
    q = []
    q.append([x, y])
    vis[x][y] = 1
    while q != []:
        cur = q[0]
        q.pop(0)
        for i in range(4):
            tx = cur[0]
            ty = cur[1]
            if i == 0:
                tx -= 1
            if i == 1:
                ty += 1
            if i == 2:
                tx += 1
            if i == 3:
                ty -= 1
            if (tx, ty) not in is_hiker.keys():
                is_hiker[(tx, ty)] = 0
            if (not vis[tx][ty]) and is_hiker[(tx, ty)]:
                vis[tx][ty] = 1
                len1[tx][ty] = len1[cur[0]][cur[1]] + 1
                q.append([tx, ty])
 
 
def cal_path(x, y):
    vis = [[0 for i in range(m + 2)] for j in range(n + 2)]
    q = []
    start = [x, y, ""]
    q.append(start)
    vis[x][y] = 1
    while True:
        cur = q[0]
        q.pop(0)
        for i in range(4):
            tx = cur[0]
            ty = cur[1]
            if i == 0:
                tx -= 1
            if i == 1:
                ty += 1
            if i == 2:
                tx += 1
            if i == 3:
                ty -= 1
            if (not vis[tx][ty]) and p[tx][ty] != '#':
                vis[tx][ty] = 1
                ch = str(i)
                if p[tx][ty] == 'X':
                    return cur[2] + ch
                nex = [tx, ty, cur[2] + ch]
                q.append(nex)
 
 
def walk(tx, ty, s):
    for i in range(len(s)):
        if s[i] == '0' and p[tx - 1][ty] != '#':
            tx -= 1
        if s[i] == '1' and p[tx][ty + 1] != '#':
            ty += 1
        if s[i] == '2' and p[tx + 1][ty] != '#':
            tx += 1
        if s[i] == '3' and p[tx][ty - 1] != '#':
            ty -= 1
        if p[tx][ty] == 'X':
            return (tx, ty)
    return (tx, ty)
 
 
hiker_place = []
is_hiker = {}
n, m = list(map(int, input().split()))
p = [[-1 for i in range(m + 2)] for j in range(n + 2)]
len1 = [[-1 for i in range(m + 2)] for j in range(n + 2)]
x = 0
y = 0
nex = []
for i in range(m + 2):
    p[0][i] = '#'
    p[n + 1][i] = '#'
    len1[0][i] = '#'
    len1[n + 1][i] = '#'
for i in range(n + 2):
    p[i][0] = '#'
    p[i][m + 1] = '#'
    len1[i][0] = '#'
    len1[i][m + 1] = '#'
for i in range(1, n + 1):
    data2 = input()
    for j in range(1, m + 1):
        p[i][j] = data2[j - 1]
        if p[i][j] == 'X':
            x = i
            y = j
        if p[i][j] == '#':
            len1[i][j] = '#'
            len1[j][i] = '#'
        if p[i][j] == 'O':
            hiker_place.append([i, j])
            is_hiker[(i, j)] = 1
bfs(x, y)
ans = ""
while hiker_place != []:
    max_len1 = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if (i, j) not in is_hiker.keys():
                is_hiker[(i, j)] = 0
            if len1[i][j] == '#':
                continue
            elif is_hiker[(i, j)] and len1[i][j] > max_len1:
                max_len1 = len1[i][j]
    tmp = ""
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if is_hiker[(i, j)] and len1[i][j] == max_len1:
                path = cal_path(i, j)
                if tmp == "" or path < tmp:
                    tmp = path
    ans += tmp
    is_hiker.clear()
    tmp_place = []
    while hiker_place != []:
        cur = [hiker_place[0], nex]
        hiker_place.pop(0)
        nex = walk(cur[0][0], cur[0][1], tmp)
        if nex not in is_hiker.keys():
            is_hiker[nex] = 0
        if (not is_hiker[nex]) and p[nex[0]][nex[1]] != 'X':
            is_hiker[nex] = 1
            tmp_place.append([nex[0], nex[1]])
    hiker_place = tmp_place
print(ans)