PAT – 第8页 – liuchuo

PAT 1128. N Queens Puzzle (20)-甲级

The “eight queens puzzle” is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general N queens problem of placing N non-attacking queens on an N×N chessboard. (From Wikipedia – “Eight queens puzzle”.)

Here you are NOT asked to solve the puzzles. Instead, you are supposed to judge whether or not a given configuration of the chessboard is a solution. To simplify the representation of a chessboard, let us assume that no two queens will be placed in the same column. Then a configuration can be represented by a simple integer sequence (Q1, Q2, …, QN), where Qi is the row number of the queen in the i-th column. For example, Figure 1 can be represented by (4, 6, 8, 2, 7, 1, 3, 5) and it is indeed a solution to the 8 queens puzzle; while Figure 2 can be represented by (4, 6, 7, 2, 8, 1, 9, 5, 3) and is NOT a 9 queens’ solution.

Input Specification:

Each input file contains several test cases. The first line gives an integer K (1 < K <= 200). Then K lines follow, each gives a configuration in the format “N Q1 Q2 … QN”, where 4 <= N <= 1000 and it is guaranteed that 1 <= Qi <= N for all i=1, …, N. The numbers are separated by spaces.

Output Specification:

For each configuration, if it is a solution to the N queens problem, print “YES” in a line; or “NO” if not.

Sample Input:
4
8 4 6 8 2 7 1 3 5
9 4 6 7 2 8 1 9 5 3
6 1 5 2 6 4 3
5 1 3 5 2 4
Sample Output:
YES
NO
NO
YES

题目大意：给出一个皇后图，以这样的方式给出：一个数组包含n个数字，每个数字表示该列的皇后所在的行数～判断给出的皇后图是否满足不会互相攻击（任意两个皇后都要不在同一行或者同一列，且不在斜对角线上～）
分析：用v[n]存储一张图给出的数字～对于第j个数字，判断前0～j-1个数字中是否有在同一行的（v[j] == v[t]）和在斜对角线上的（abs(v[j]-v[t]) == abs(j-t)）【因为已经告诉肯定不在同一列了，所以不需要判断是否在同一列啦～】如果发现了不满足的情况，就将result由true标记为false～最后根据result是true还是false输出对应的YES还是NO即可～

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main() {
    int k, n;
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> n;
        vector<int> v(n);
        bool result = true;
        for (int j = 0; j < n; j++) {
            cin >> v[j];
            for (int t = 0; t < j; t++) {
                if (v[j] == v[t] || abs(v[j]-v[t]) == abs(j-t)) {
                    result = false;
                    break;
                }
            }
        }
        cout << (result == true ? "YES\n" : "NO\n");
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <cmath>

using namespace std;

int main() {

int k, n;

cin >> k;

for (int i = 0; i < k; i++) {

cin >> n;

vector<int> v(n);

bool result = true;

for (int j = 0; j < n; j++) {

cin >> v[j];

for (int t = 0; t < j; t++) {

if (v[j] == v[t] || abs(v[j]-v[t]) == abs(j-t)) {

result = false;

break;

}

cout << (result == true ? "YES\n" : "NO\n");

}

return 0;

}

PAT 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. And it is a simple standard routine to print the numbers in level-order. However, if you think the problem is too simple, then you are too naive. This time you are supposed to print the numbers in “zigzagging order” — that is, starting from the root, print the numbers level-by-level, alternating between left to right and right to left. For example, for the following tree you must output: 1 11 5 8 17 12 20 15.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<= 30), the total number of nodes in the binary tree. The second line gives the inorder sequence and the third line gives the postorder sequence. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the zigzagging sequence of the tree in a line. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:
8
12 11 20 17 1 15 8 5
12 20 17 11 15 8 5 1
Sample Output:
1 11 5 8 17 12 20 15

题目大意：给出一个树的中序和后序遍历结果，求它的Z字型层序遍历，也就是偶数层从右往左，奇数层从左往右遍历～
分析：分为3步：1.根据中序和后序建树保存在tree二维数组中，比如：tree[i][0] = val表示post[i]的左孩子是post[val]，tree[i][1] = val表示post[i]的右孩子是post[val]～
2.进行广度优先搜索，将树从根结点开始所有结点层序遍历，保存在result二维数组中，比如：result[i]保存第i层所有结点的序列～
3.进行z字型输出，根据当前层号的奇偶性分别从左往右、从右往左遍历输出～

1. dfs：因为post(后序)是按照左、右、根的顺序遍历的，所以从右往左，最右边的肯定是根结点～所以postRight是当前子树的根结点的下标，将它的赋值给index，并继续dfs tree[index][0]和tree[index][1]～
根据post[postRight]的结点在in里面的下标位置i，可以得到i的左边是左子树，即inLeft 到 i – 1，右边是右子树：i + 1 到 inRight。而对于post来说，根据左子树的结点个数i – inLeft可以得到[postLeft, postLeft + (i – inLeft) – 1]是post中左子树的范围，[postLeft + (i – inLeft), postRight – 1]是post中右子树的范围～
2.广度优先搜索，采用队列q，q中保存的是node结点，node.index表示当前节点在post中的下标，node.depth表示当前结点在树中的层数～
3.当 i % 2 == 0的时候倒序输出，否则正序输出～

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> in, post, result[35];
int n, tree[35][2], root;
struct node {
    int index, depth;
};
void dfs(int &index, int inLeft, int inRight, int postLeft, int postRight) {
    if (inLeft > inRight) return;
    index = postRight;
    int i = 0;
    while (in[i] != post[postRight]) i++;
    dfs(tree[index][0], inLeft, i - 1, postLeft, postLeft + (i - inLeft) - 1);
    dfs(tree[index][1], i + 1, inRight, postLeft + (i - inLeft), postRight - 1);
}
void bfs() {
    queue<node> q;
    q.push(node{root, 0});
    while (!q.empty()) {
        node temp = q.front();
        q.pop();
        result[temp.depth].push_back(post[temp.index]);
        if (tree[temp.index][0] != 0)
            q.push(node{tree[temp.index][0], temp.depth + 1});
        if (tree[temp.index][1] != 0)
            q.push(node{tree[temp.index][1], temp.depth + 1});
    }
}
int main() {
    cin >> n;
    in.resize(n + 1), post.resize(n + 1);
    for (int i = 1; i <= n; i++) cin >> in[i];
    for (int i = 1; i <= n; i++) cin >> post[i];
    dfs(root, 1, n, 1, n);
    bfs();
    printf("%d", result[0][0]);
    for (int i = 1; i < 35; i++) {
        if (i % 2 == 1) {
            for (int j = 0; j < result[i].size(); j++)
                printf(" %d", result[i][j]);
        } else {
            for (int j = result[i].size() - 1; j >= 0; j--)
                printf(" %d", result[i][j]);
        }
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

vector<int> in, post, result[35];

int n, tree[35][2], root;

struct node {

int index, depth;

};

void dfs(int &index, int inLeft, int inRight, int postLeft, int postRight) {

if (inLeft > inRight) return;

index = postRight;

int i = 0;

while (in[i] != post[postRight]) i++;

dfs(tree[index][0], inLeft, i - 1, postLeft, postLeft + (i - inLeft) - 1);

dfs(tree[index][1], i + 1, inRight, postLeft + (i - inLeft), postRight - 1);

}

void bfs() {

queue<node> q;

q.push(node{root, 0});

while (!q.empty()) {

node temp = q.front();

q.pop();

result[temp.depth].push_back(post[temp.index]);

if (tree[temp.index][0] != 0)

q.push(node{tree[temp.index][0], temp.depth + 1});

if (tree[temp.index][1] != 0)

q.push(node{tree[temp.index][1], temp.depth + 1});

}

int main() {

cin >> n;

in.resize(n + 1), post.resize(n + 1);

for (int i = 1; i <= n; i++) cin >> in[i];

for (int i = 1; i <= n; i++) cin >> post[i];

dfs(root, 1, n, 1, n);

bfs();

printf("%d", result[0][0]);

for (int i = 1; i < 35; i++) {

if (i % 2 == 1) {

for (int j = 0; j < result[i].size(); j++)

printf(" %d", result[i][j]);

} else {

for (int j = result[i].size() - 1; j >= 0; j--)

printf(" %d", result[i][j]);

}

return 0;

}

1068. 万绿丛中一点红(20)-PAT乙级真题

对于计算机而言，颜色不过是像素点对应的一个24位的数值。现给定一幅分辨率为MxN的画，要求你找出万绿丛中的一点红，即有独一无二颜色的那个像素点，并且该点的颜色与其周围8个相邻像素的颜色差充分大。

输入格式：

输入第一行给出三个正整数，分别是M和N（<= 1000），即图像的分辨率；以及TOL，是所求像素点与相邻点的颜色差阈值，色差超过TOL的点才被考虑。随后N行，每行给出M个像素的颜色值，范围在[0, 224)内。所有同行数字间用空格或TAB分开。

输出格式：

在一行中按照“(x, y): color”的格式输出所求像素点的位置以及颜色值，其中位置x和y分别是该像素在图像矩阵中的列、行编号（从1开始编号）。如果这样的点不唯一，则输出“Not Unique”；如果这样的点不存在，则输出“Not Exist”。

输入样例1：

8 6 200
0 0 0 0 0 0 0 0
65280 65280 65280 16711479 65280 65280 65280 65280
16711479 65280 65280 65280 16711680 65280 65280 65280
65280 65280 65280 65280 65280 65280 165280 165280
65280 65280 16777015 65280 65280 165280 65480 165280
16777215 16777215 16777215 16777215 16777215 16777215 16777215 16777215

输出样例1：
(5, 3): 16711680

输入样例2：
4 5 2
0 0 0 0
0 0 3 0
0 0 0 0
0 5 0 0
0 0 0 0

输出样例2：
Not Unique

输入样例3：
3 3 5
1 2 3
3 4 5
5 6 7

输出样例3：
Not Exist

分析：首先这个点必须是唯一的，所以用map标记如果不是唯一的点就不用考虑了～接着对于每个点，判断它的周围八个点与它的差值是否大于阈值，如果有一个点没有满足大于阈值就return false～最后记得输入的时候是列、行——m、n，输出的时候也是列、行坐标～

#include <iostream>
#include <vector>
#include <map>
using namespace std;
int m, n, tol;
vector<vector<int>> v;
int dir[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};
bool judge(int i, int j) {
    for (int k = 0; k < 8; k++) {
        int tx = i + dir[k][0];
        int ty = j + dir[k][1];
        if (tx >= 0 && tx < n && ty >= 0 && ty < m && v[i][j] - v[tx][ty] >= 0 - tol && v[i][j] - v[tx][ty] <= tol) return false;
    }
    return true;
}
int main() {
    int cnt = 0, x = 0, y = 0;
    scanf("%d%d%d", &m, &n, &tol);
    v.resize(n, vector<int>(m));
    map<int, int> mapp;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &v[i][j]);
            mapp[v[i][j]]++;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (mapp[v[i][j]] == 1 && judge(i, j) == true) {
                cnt++;
                x = i + 1;
                y = j + 1;
            }
        }
    }
    if (cnt == 1)
        printf("(%d, %d): %d", y, x, v[x-1][y-1]);
    else if (cnt == 0)
        printf("Not Exist");
    else
        printf("Not Unique");
    return 0;
}

#include <iostream>

#include <vector>

#include <map>

using namespace std;

int m, n, tol;

vector<vector<int>> v;

int dir[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};

bool judge(int i, int j) {

for (int k = 0; k < 8; k++) {

int tx = i + dir[k][0];

int ty = j + dir[k][1];

if (tx >= 0 && tx < n && ty >= 0 && ty < m && v[i][j] - v[tx][ty] >= 0 - tol && v[i][j] - v[tx][ty] <= tol) return false;

}

return true;

}

int main() {

int cnt = 0, x = 0, y = 0;

scanf("%d%d%d", &m, &n, &tol);

v.resize(n, vector<int>(m));

map<int, int> mapp;

for (int i = 0; i < n; i++) {

for (int j = 0; j < m; j++) {

scanf("%d", &v[i][j]);

mapp[v[i][j]]++;

}

for (int i = 0; i < n; i++) {

for (int j = 0; j < m; j++) {

if (mapp[v[i][j]] == 1 && judge(i, j) == true) {

cnt++;

x = i + 1;

y = j + 1;

}

if (cnt == 1)

printf("(%d, %d): %d", y, x, v[x-1][y-1]);

else if (cnt == 0)

printf("Not Exist");

else

printf("Not Unique");

return 0;

}

PAT 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. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Konigsberg problem in 1736. It has been proven that connected graphs with all vertices of even degree have an Eulerian circuit, and such graphs are called Eulerian. If there are exactly two vertices of odd degree, all Eulerian paths start at one of them and end at the other. A graph that has an Eulerian path but not an Eulerian circuit is called semi-Eulerian. (Cited from https://en.wikipedia.org/wiki/Eulerian_path)

Given an undirected graph, you are supposed to tell if it is Eulerian, semi-Eulerian, or non-Eulerian.

Input Specification:

Each input file contains one test case. Each case starts with a line containing 2 numbers N (<= 500), and M, which are the total number of vertices, and the number of edges, respectively. Then M lines follow, each describes an edge by giving the two ends of the edge (the vertices are numbered from 1 to N).

Output Specification:

For each test case, first print in a line the degrees of the vertices in ascending order of their indices. Then in the next line print your conclusion about the graph — either “Eulerian”, “Semi-Eulerian”, or “Non-Eulerian”. Note that all the numbers in the first line must be separated by exactly 1 space, and there must be no extra space at the beginning or the end of the line.

Sample Input 1:
7 12
5 7
1 2
1 3
2 3
2 4
3 4
5 2
7 6
6 3
4 5
6 4
5 6
Sample Output 1:
2 4 4 4 4 4 2
Eulerian
Sample Input 2:
6 10
1 2
1 3
2 3
2 4
3 4
5 2
6 3
4 5
6 4
5 6
Sample Output 2:
2 4 4 4 3 3
Semi-Eulerian
Sample Input 3:
5 8
1 2
2 5
5 4
4 1
1 3
3 2
3 4
5 3
Sample Output 3:
3 3 4 3 3
Non-Eulerian

题目大意：如果一个连通图的所有结点的度都是偶数，那么它就是Eulerian，如果除了两个结点的度是奇数其他都是偶数，那么它就是Semi-Eulerian，否则就是Non-Eulerian～
分析：用邻接表存储图，判断每个结点的度【也就是每个结点i的v[i].size()】是多少即可得到最终结果～注意：图必须是连通图，所以要用一个深搜判断一下连通性，从结点1开始深搜，如果最后发现统计的连通结点个数cnt != n说明是不是连通图，要输出Non-Eulerian～

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int> > v;
vector<bool> visit;
int cnt = 0;
void dfs(int index) {
    visit[index] = true;
    cnt++;
    for (int i = 0; i < v[index].size(); i++)
        if (visit[v[index][i]] == false)
            dfs(v[index][i]);
}
int main() {
    int n, m, a, b, even = 0;
    scanf("%d%d", &n, &m);
    v.resize(n + 1);
    visit.resize(n + 1);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) {
        if (i != 1) printf(" ");
        printf("%d", v[i].size());
        if (v[i].size() % 2 == 0) even++;
    }
    printf("\n");
    dfs(1);
    if (even == n && cnt == n)
        printf("Eulerian");
    else if(even == n - 2 && cnt == n)
        printf("Semi-Eulerian");
    else
        printf("Non-Eulerian");
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

vector<vector<int> > v;

vector<bool> visit;

int cnt = 0;

void dfs(int index) {

visit[index] = true;

cnt++;

for (int i = 0; i < v[index].size(); i++)

if (visit[v[index][i]] == false)

dfs(v[index][i]);

}

int main() {

int n, m, a, b, even = 0;

scanf("%d%d", &n, &m);

v.resize(n + 1);

visit.resize(n + 1);

for (int i = 0; i < m; i++) {

scanf("%d%d", &a, &b);

v[a].push_back(b);

v[b].push_back(a);

}

for (int i = 1; i <= n; i++) {

if (i != 1) printf(" ");

printf("%d", v[i].size());

if (v[i].size() % 2 == 0) even++;

}

printf("\n");

dfs(1);

if (even == n && cnt == n)

printf("Eulerian");

else if(even == n - 2 && cnt == n)

printf("Semi-Eulerian");

else

printf("Non-Eulerian");

return 0;

}

1067. 试密码(20)-PAT乙级真题

当你试图登录某个系统却忘了密码时，系统一般只会允许你尝试有限多次，当超出允许次数时，账号就会被锁死。本题就请你实现这个小功能。

输入格式：

输入在第一行给出一个密码（长度不超过20的、不包含空格、Tab、回车的非空字符串）和一个正整数N（<= 10），分别是正确的密码和系统允许尝试的次数。随后每行给出一个以回车结束的非空字符串，是用户尝试输入的密码。输入保证至少有一次尝试。当读到一行只有单个#字符时，输入结束，并且这一行不是用户的输入。

输出格式：

对用户的每个输入，如果是正确的密码且尝试次数不超过N，则在一行中输出“Welcome in”，并结束程序；如果是错误的，则在一行中按格式输出“Wrong password: 用户输入的错误密码”；当错误尝试达到N次时，再输出一行“Account locked”，并结束程序。

输入样例1：
Correct%pw 3
correct%pw
Correct@PW
whatisthepassword!
Correct%pw
#
输出样例1：
Wrong password: correct%pw
Wrong password: Correct@PW
Wrong password: whatisthepassword!
Account locked
输入样例2：
cool@gplt 3
coolman@gplt
coollady@gplt
cool@gplt
try again
#
输出样例2：
Wrong password: coolman@gplt
Wrong password: coollady@gplt
Welcome in

分析：注意3个点：1、如果已经是”#”了就不要继续下面的判断了，不然可能输出Wrong password: “#”
2、如果密码错误并且达到了尝试的次数，是先输出Wrong password那句紧接着输出Account locked那句
3、Wrong password: 后面有个空格～

#include <iostream>
using namespace std;
int main() {
    string password, temp;
    int n, cnt = 0;
    cin >> password >> n;
    getchar();
    while(1) {
        getline(cin, temp);
        if (temp == "#") break;
        cnt++;
        if (cnt <= n && temp == password) {
            cout << "Welcome in";
            break;
        } else if (cnt <= n && temp != password) {
            cout << "Wrong password: " << temp << endl;
            if (cnt == n) {
                cout << "Account locked";
                break;
            }
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

string password, temp;

int n, cnt = 0;

cin >> password >> n;

getchar();

while(1) {

getline(cin, temp);

if (temp == "#") break;

cnt++;

if (cnt <= n && temp == password) {

cout << "Welcome in";

break;

} else if (cnt <= n && temp != password) {

cout << "Wrong password: " << temp << endl;

if (cnt == n) {

cout << "Account locked";

break;

}

return 0;

}

1066. 图像过滤(15)-PAT乙级真题

图像过滤是把图像中不重要的像素都染成背景色，使得重要部分被凸显出来。现给定一幅黑白图像，要求你将灰度值位于某指定区间内的所有像素颜色都用一种指定的颜色替换。

输入格式：

输入在第一行给出一幅图像的分辨率，即两个正整数M和N（0 < M, N <= 500），另外是待过滤的灰度值区间端点A和B（0 <= A < B <= 255）、以及指定的替换灰度值。随后M行，每行给出N个像素点的灰度值，其间以空格分隔。所有灰度值都在[0, 255]区间内。

输出格式：

输出按要求过滤后的图像。即输出M行，每行N个像素灰度值，每个灰度值占3位（例如黑色要显示为000），其间以一个空格分隔。行首尾不得有多余空格。

输入样例：
3 5 100 150 0
3 189 254 101 119
150 233 151 99 100
88 123 149 0 255
输出样例：
003 189 254 000 000
000 233 151 099 000
088 000 000 000 255

分析：不用存储到数组中，可以边输入边处理输出～假设当前输入的temp值在a～b区间就将temp替换为num～以%03d的方式输出temp～

#include <iostream>
using namespace std;
int main() {
    int m, n, a, b, num, temp;
    scanf("%d%d%d%d%d", &m, &n, &a, &b, &num);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &temp);
            if (temp >= a && temp <= b)
                temp = num;
            if (j != 0) printf(" ");
            printf("%03d", temp);
        }
        printf("\n");
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int m, n, a, b, num, temp;

scanf("%d%d%d%d%d", &m, &n, &a, &b, &num);

for (int i = 0; i < m; i++) {

for (int j = 0; j < n; j++) {

scanf("%d", &temp);

if (temp >= a && temp <= b)

temp = num;

if (j != 0) printf(" ");

printf("%03d", temp);

}

printf("\n");

}

return 0;

}