关于算法:PAT甲级2019年冬季考试题解

7-1 Good in C (20 分)
When your interviewer asks you to write “Hello World” using C, can you do as the following figure shows?

Each input file contains one test case. For each case, the first part gives the 26 capital English letters A-Z, each in a 7×5 matrix of C‘s and .‘s. Then a sentence is given in a line, ended by a return. The sentence is formed by several words (no more than 10 continuous capital English letters each), and the words are separated by any characters other than capital English letters.

It is guaranteed that there is at least one word given.

For each word, print the matrix form of each of its letters in a line, and the letters must be separated by exactly one column of space. There must be no extra space at the beginning or the end of the word.

Between two adjacent words, there must be a single empty line to separate them. There must be no extra line at the beginning or the end of the output.

..C..
.C.C.
C...C
CCCCC
C...C
C...C
C...C
CCCC.
C...C
C...C
CCCC.
C...C
C...C
CCCC.
.CCC.
C...C
C....
C....
C....
C...C
.CCC.
CCCC.
C...C
C...C
C...C
C...C
C...C
CCCC.
CCCCC
C....
C....
CCCC.
C....
C....
CCCCC
CCCCC
C....
C....
CCCC.
C....
C....
C....
CCCC.
C...C
C....
C.CCC
C...C
C...C
CCCC.
C...C
C...C
C...C
CCCCC
C...C
C...C
C...C
CCCCC
..C..
..C..
..C..
..C..
..C..
CCCCC
CCCCC
....C
....C
....C
....C
C...C
.CCC.
C...C
C..C.
C.C..
CC...
C.C..
C..C.
C...C
C....
C....
C....
C....
C....
C....
CCCCC
C...C
C...C
CC.CC
C.C.C
C...C
C...C
C...C
C...C
C...C
CC..C
C.C.C
C..CC
C...C
C...C
.CCC.
C...C
C...C
C...C
C...C
C...C
.CCC.
CCCC.
C...C
C...C
CCCC.
C....
C....
C....
.CCC.
C...C
C...C
C...C
C.C.C
C..CC
.CCC.
CCCC.
C...C
CCCC.
CC...
C.C..
C..C.
C...C
.CCC.
C...C
C....
.CCC.
....C
C...C
.CCC.
CCCCC
..C..
..C..
..C..
..C..
..C..
..C..
C...C
C...C
C...C
C...C
C...C
C...C
.CCC.
C...C
C...C
C...C
C...C
C...C
.C.C.
..C..
C...C
C...C
C...C
C.C.C
CC.CC
C...C
C...C
C...C
C...C
.C.C.
..C..
.C.C.
C...C
C...C
C...C
C...C
.C.C.
..C..
..C..
..C..
..C..
CCCCC
....C
...C.
..C..
.C...
C....
CCCCC
HELLO~WORLD!

C...C CCCCC C.... C.... .CCC.
C...C C.... C.... C.... C...C
C...C C.... C.... C.... C...C
CCCCC CCCC. C.... C.... C...C
C...C C.... C.... C.... C...C
C...C C.... C.... C.... C...C
C...C CCCCC CCCCC CCCCC .CCC.

C...C .CCC. CCCC. C.... CCCC.
C...C C...C C...C C.... C...C
C...C C...C CCCC. C.... C...C
C.C.C C...C CC... C.... C...C
CC.CC C...C C.C.. C.... C...C
C...C C...C C..C. C.... C...C
C...C .CCC. C...C CCCCC CCCC.

思路剖析：本题有很多细节须要解决。首先第一个字符不肯定是大写字母，故要先找到第一个大写字母。其次，两头的距离字符可能是空格，故要整行读取（一旦应用了整行读取函数，后面的输出前面记得增加 getchar() 来排汇换行符）。最初，开端不肯定有其余字符，故能够思考人为加上一个非大写字母的字符，从而便于解决，这种操作之前也是见过的。
再来看图形如何输入。因为输入只能一行一行输入，故不能每个单词一个字母一个字母输入，而要每个单词的每个字母的雷同行先输入，而后再输入下一行。这其中要想分明，能够增加中文正文避免搞混。

参考代码：

#include <bits/stdc++.h>
using namespace std;

int main(){string letter[30][10];
    for(int i = 0; i < 26; i ++){for(int j = 0; j < 7; j++){cin >> letter[i][j];
            getchar();}
    }
    string seq;
    int pos, flag;
    getline(cin, seq);
    seq += "^";
    int i = 0;
    while(seq[i] > 'Z' || seq[i] < 'A') i++;
    pos = flag = i;
    for(; i < seq.length()+1; i++){if(seq[i] > 'Z' || seq[i] < 'A'){if(pos != flag)    printf("\n");
            for(int j = 0; j < 7; j++){// 每个字母的每一行
                for(int k = pos; k < i; k++){cout << letter[seq[k]-'A'][j]; // 不同字母
                    printf("%s", k == i-1 ? "\n" : " ");
                }
            }
            while(i+1 < seq.length() && seq[i+1] > 'Z' || seq[i+1] < 'A')   i++;
            pos = i+1;
        }
    }
    return 0;
}

7-2 Block Reversing (25 分)
Given a singly linked list L. Let us consider every K nodes as a block (if there are less than K nodes at the end of the list, the rest of the nodes are still considered as a block). Your job is to reverse all the blocks in L. For example, given L as 1→2→3→4→5→6→7→8 and K as 3, your output must be 7→8→4→5→6→1→2→3.

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤10^5) which is the total number of nodes, and a positive K (≤N) which is the size of a block. The address of a node is a 5-digit nonnegative integer, and NULL is represented by −1.

Then N lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is an integer, and Next is the position of the next node.

For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

00100 8 3
71120 7 88666
00000 4 99999
00100 1 12309
68237 6 71120
33218 3 00000
99999 5 68237
88666 8 -1
12309 2 33218

71120 7 88666
88666 8 00000
00000 4 99999
99999 5 68237
68237 6 00100
00100 1 12309
12309 2 33218
33218 3 -1

思路剖析：本题属于链表的惯例题，动态链表解决即可，次要留神每一块须要应用一个向量数组来存储，是二维的。
可能存在有效结点，故从头结点开始向后拜访直到尾结点，并存入一个向量中。而后每 k 个结点退出一个向量中，并存入开拓的数组中。因为最初可能不满 k 个，链表就完结了，故最初若长期向量非空，则退出后果数组中即可。而后依次输入，留神分三种状况。

参考代码：

#include <bits/stdc++.h>
using namespace std;

struct node{int Address, Data, Next;}link[100010];

vector<node> block[100010];
vector<node> temp;

int main(){
    int head, node_num, block_size;
    int add, dat, nex;
    scanf("%d %d %d", &head, &node_num, &block_size);
    for(int i = 0; i < node_num; i++){scanf("%d %d %d", &add, &dat, &nex);
        link[add].Address = add;
        link[add].Data = dat;
        link[add].Next = nex;
    }
    int cot = 0;
    int block_num = 0;
    while(head != -1){temp.push_back(link[head]);
        cot++;
        if(cot % block_size == 0){block[block_num++] = temp;
            temp.clear();}
        head = link[head].Next;
    }
    if(!temp.empty())   block[block_num++] = temp;
    reverse(block, block+block_num);
    for(int i = 0; i < block_num; i++){for(int j = 0; j < block[i].size(); j++){if(j == block[i].size()-1){if(i == block_num-1)    printf("%05d %d -1\n", block[i][j].Address, block[i][j].Data);
                else   printf("%05d %d %05d\n", block[i][j].Address, block[i][j].Data, block[i+1][0].Address);
            }
            else    printf("%05d %d %05d\n", block[i][j].Address, block[i][j].Data, block[i][j+1].Address);
        }
    }
    return 0;
}

7-3 Summit (25 分)
A summit (峰会) is a meeting of heads of state or government. Arranging the rest areas for the summit is not a simple job. The ideal arrangement of one area is to invite those heads so that everyone is a direct friend of everyone.

Now given a set of tentative arrangements, your job is to tell the organizers whether or not each area is all set.

Each input file contains one test case. For each case, the first line gives two positive integers N (≤ 200), the number of heads in the summit, and M, the number of friendship relations. Then M lines follow, each gives a pair of indices of the heads who are friends to each other. The heads are indexed from 1 to N.

Then there is another positive integer K (≤ 100), and K lines of tentative arrangement of rest areas follow, each first gives a positive number L (≤N), then followed by a sequence of L distinct indices of the heads. All the numbers in a line are separated by a space.

For each of the K areas, print in a line your advice in the following format:

if in this area everyone is a direct friend of everyone, and no friend is missing (that is, no one else is a direct friend of everyone in this area), print Area X is OK..
if in this area everyone is a direct friend of everyone, yet there are some other heads who may also be invited without breaking the ideal arrangement, print Area X may invite more people, such as H. where H is the smallest index of the head who may be invited.
if in this area the arrangement is not an ideal one, then print Area X needs help. so the host can provide some special service to help the heads get to know each other.

Here X is the index of an area, starting from 1 to K.

Area 1 is OK.
Area 2 is OK.
Area 3 is OK.
Area 4 is OK.
Area 5 may invite more people, such as 3.
Area 6 needs help.

思路剖析：这种题最近很常见，但牢记不要用图的遍历或并查集啥的，一一测验即可。本题即是先判一房间人是否相互都意识，再看是否存在一个人与该房间每个人都意识即可。

参考代码：

#include <bits/stdc++.h>
using namespace std;

int rela[210][210];

int main(){
    int h1, h2;
    int head_num, rela_num;
    scanf("%d %d", &head_num, &rela_num);
    for(int i = 0; i < rela_num; i++){scanf("%d %d", &h1, &h2);
        rela[h1][h2] = rela[h2][h1] = 1;
    }
    int rest_num, in_num;
    scanf("%d", &rest_num);
    for(int i = 1; i <= rest_num; i++){int exist[210] = {0};
        int flag = 1;
        int in[210];
        scanf("%d", &in_num);
        for(int j = 0; j < in_num; j++){scanf("%d", &in[j]);
            exist[in[j]] = 1;
            if(flag){for(int k = j-1; k >= 0; k--){if(!rela[in[j]][in[k]]) flag = 0;
                }
            }
        }
        if(!flag)   printf("Area %d needs help.\n", i);
        else{
            int more = 0;
            int j = 1;
            for(; j <= head_num; j++){if(!exist[j]){// 不在该房间的人
                    int k;
                    for(k = 0; k < in_num; k++){// 与该房间每个人是否意识
                        if(!rela[j][in[k]]) break;
                    }
                    if(k == in_num){
                        more = 1;
                        break;
                    }
                }
            }
            if(more)    printf("Area %d may invite more people, such as %d.\n", i, j);
            else    printf("Area %d is OK.\n", i);
        }
    }
    return 0;
}

7-4 Cartesian Tree (30 分)
A Cartesian tree is a binary tree constructed from a sequence of distinct numbers. The tree is heap-ordered, and an inorder traversal returns the original sequence. For example, given the sequence {8, 15, 3, 4, 1, 5, 12, 10, 18, 6}, the min-heap Cartesian tree is shown by the figure.

Your job is to output the level-order traversal sequence of the min-heap Cartesian tree.

Each input file contains one test case. Each case starts from giving a positive integer N (≤30), and then N distinct numbers in the next line, separated by a space. All the numbers are in the range of int.

For each test case, print in a line the level-order traversal sequence of the min-heap Cartesian tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the beginning or the end of the line.

10
8 15 3 4 1 5 12 10 18 6

1 3 5 8 4 6 15 10 12 18

思路剖析：最小数是根，因为中序序列和原始序列一样，故左子树的全副结点在序列中根的右边，右子树同理，而后递归建树即可。

参考代码：

#include <bits/stdc++.h>
using namespace std;

struct node{
    int data;
    node *left, *right;
};

vector<int> seq;

node* build(int l, int r){if(l > r)   return NULL;
    node* root = new node;
    int min_num = seq[l], min_pos = l;
    for(int i = l+1; i <= r; i++){if(seq[i] < min_num){min_num = seq[i];
            min_pos = i;
        }
    }
    root->data = min_num;
    root->left = build(l, min_pos-1);
    root->right = build(min_pos+1, r);
    return root;
}

void BFS(node* root){
    queue<node*> q;
    q.push(root);
    while(!q.empty()){node* top = q.front();
        q.pop();
        if(top->left != NULL)   q.push(top->left);
        if(top->right != NULL)  q.push(top->right);
        printf("%d%s", top->data, q.empty() ? "\n" : " ");
    }
}

int main(){
    int n;
    scanf("%d", &n);
    seq.resize(n);
    for(int i = 0; i < n; i++)  scanf("%d", &seq[i]);
    node* root = new node;
    root = build(0, n-1);
    BFS(root);
    return 0;
}

第一次模拟考试取得了满分，还是挺开心的，不过题目也不算太难。

关于算法:PAT甲级2019年冬季考试题解

Input Specification:

Output Specification:

Sample Input:

Sample Output:

Input Specification:

Output Specification:

Sample Input:

Sample Output:

Input Specification:

Output Specification:

Sample Input:

Sample Output:

Input Specification:

Output Specification:

Sample Input:

Sample Output: