Code – 第108页

[note] 初等函数、代数函数、超越函数、有理函数、无理函数、有理整式、有理分式的概念解释

对应的包含关系如下图：

初等函数：包括代数函数和超越函数。
初等函数是由冥函数、指数函数、对数函数、三角函数、反三角函数与常数经过有限次的有力运算及有限次函数复合所产生，并且能用一个解析式表示。

代数函数：包括有理函数和无理函数。
代数函数是指只包含常数与自变量相互之间有限次的加、减、乘、除、有理指数幂和开方六种运算的函数。

超越函数：与代数函数相反，是指那些不满足任何以多项式方程的函数，即函数不满足以变量自身的多项式为系数的多项式方程。如三角函数、对数函数，反三角函数，指数函数等就属于超越函数。

有理函数：包括有理整式和有理分式。
有理函数是通过多项式的加减乘除得到的函数。

无理函数：对应规律含对自变量的开方运算的代数函数称为无理函数，无理函数通常是自变量包含在根式（通常是最简根式）中的函数。

有理整式：可以认为有理整式即是多项式，对变数字母与数仅限于有限次加、减、乘、乘方运算的代数式，即除式不含变数字母的有理式称为有理整式。

有理分式：有理分式指的是两个多项式的商，具体来说是指分子及分母都是多项式的分式。

1135. Is It A Red-Black Tree (30)-PAT甲级真题

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

(1) Every node is either red or black.
(2) The root is black.
(3) Every leaf (NULL) is black.
(4) If a node is red, then both its children are black.
(5) For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

For example, the tree in Figure 1 is a red-black tree, while the ones in Figure 2 and 3 are not.

For each given binary search tree, you are supposed to tell if it is a legal red-black tree.

Input Specification:

Each input file contains several test cases. The first line gives a positive integer K (<=30) which is the total number of cases. 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 preorder traversal sequence of the tree. While all the keys in a tree are positive integers, we use negative signs to represent red nodes. All the numbers in a line are separated by a space. The sample input cases correspond to the trees shown in Figure 1, 2 and 3.

Output Specification:

For each test case, print in a line “Yes” if the given tree is a red-black tree, or “No” if not.

Sample Input:
3
9
7 -2 1 5 -4 -11 8 14 -15
9
11 -2 1 -7 5 -4 8 14 -15
8
10 -7 5 -6 8 15 -11 17
Sample Output:
Yes
No
No

题目大意：给一棵二叉搜索树的前序遍历，判断它是否为红黑树，是输出Yes，否则输出No。

分析：判断以下几点：
1.根结点是否为黑色
2.如果一个结点是红色，它的孩子节点是否都为黑色
3.从任意结点到叶子结点的路径中，黑色结点的个数是否相同
所以分为以下几步：
0. 根据先序建立一棵树，用链表表示
1. 判断根结点（题目所给先序的第一个点即根结点）是否是黑色【arr[0] < 0】
2. 根据建立的树，从根结点开始遍历，如果当前结点是红色，判断它的孩子节点是否为黑色，递归返回结果【judge1函数】
3. 从根节点开始，递归遍历，检查每个结点的左子树的高度和右子树的高度（这里的高度指黑色结点的个数），比较左右孩子高度是否相等，递归返回结果【judge2函数】

注意：终于知道自己PAT考试的时候错在哪了。。。维基百科定义：红黑树（英语：Red–black tree）是一种自平衡二叉查找树。AVL树：在计算机科学中，AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。所以说红黑树不是一种AVL树，红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。而我根据先序遍历直接建树后判断了是否AVL平衡，把判断是否平衡的那段代码注释掉就AC了～

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<int> arr;
struct node {
    int val;
    struct node *left, *right;
};
node* build(node *root, int v) {
    if(root == NULL) {
        root = new node();
        root->val = v;
        root->left = root->right = NULL;
    } else if(abs(v) <= abs(root->val))
        root->left = build(root->left, v);
    else
        root->right = build(root->right, v);
    return root;
}
bool judge1(node *root) {
    if (root == NULL) return true;
    if (root->val < 0) {
        if (root->left != NULL && root->left->val < 0) return false;
        if (root->right != NULL && root->right->val < 0) return false;
    }
    return judge1(root->left) && judge1(root->right);
}
int getNum(node *root) {
    if (root == NULL) return 0;
    int l = getNum(root->left);
    int r = getNum(root->right);
    return root->val > 0 ? max(l, r) + 1 : max(l, r);
}
bool judge2(node *root) {
    if (root == NULL) return true;
    int l = getNum(root->left);
    int r = getNum(root->right);
    if(l != r) return false;
    return judge2(root->left) && judge2(root->right);
}
int main() {
    int k, n;
    scanf("%d", &k);
    for (int i = 0; i < k; i++) {
        scanf("%d", &n);
        arr.resize(n);
        node *root = NULL;
        for (int j = 0; j < n; j++) {
            scanf("%d", &arr[j]);
            root = build(root, arr[j]);
        }
        if (arr[0] < 0 || judge1(root) == false || judge2(root) == false)
            printf("No\n");
        else
            printf("Yes\n");
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <cmath>

using namespace std;

vector<int> arr;

struct node {

int val;

struct node *left, *right;

};

node* build(node *root, int v) {

if(root == NULL) {

root = new node();

root->val = v;

root->left = root->right = NULL;

} else if(abs(v) <= abs(root->val))

root->left = build(root->left, v);

else

root->right = build(root->right, v);

return root;

}

bool judge1(node *root) {

if (root == NULL) return true;

if (root->val < 0) {

if (root->left != NULL && root->left->val < 0) return false;

if (root->right != NULL && root->right->val < 0) return false;

}

return judge1(root->left) && judge1(root->right);

}

int getNum(node *root) {

if (root == NULL) return 0;

int l = getNum(root->left);

int r = getNum(root->right);

return root->val > 0 ? max(l, r) + 1 : max(l, r);

}

bool judge2(node *root) {

if (root == NULL) return true;

int l = getNum(root->left);

int r = getNum(root->right);

if(l != r) return false;

return judge2(root->left) && judge2(root->right);

}

int main() {

int k, n;

scanf("%d", &k);

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

scanf("%d", &n);

arr.resize(n);

node *root = NULL;

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

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

root = build(root, arr[j]);

}

if (arr[0] < 0 || judge1(root) == false || judge2(root) == false)

printf("No\n");

else

printf("Yes\n");

}

return 0;

}

1134. Vertex Cover (25)-PAT甲级真题

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 graph with several vertex sets, you are supposed to tell if each of them is a vertex cover or not.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N and M (both no more than 104), being the total numbers of vertices and the edges, respectively. Then M lines follow, each describes an edge by giving the indices (from 0 to N-1) of the two ends of the edge.

After the graph, a positive integer K (<= 100) is given, which is the number of queries. Then K lines of queries follow, each in the format:

Nv v[1] v[2] … v[Nv]

where Nv is the number of vertices in the set, and v[i]’s are the indices of the vertices.

Output Specification:

For each query, print in a line “Yes” if the set is a vertex cover, or “No” if not.

Sample Input:
10 11
8 7
6 8
4 5
8 4
8 1
1 2
1 4
9 8
9 1
1 0
2 4
5
4 0 3 8 4
6 6 1 7 5 4 9
3 1 8 4
2 2 8
7 9 8 7 6 5 4 2
Sample Output:
No
Yes
Yes
No
No

题目大意：给n个结点m条边，再给k个集合。对这k个集合逐个进行判断。每个集合S里面的数字都是结点编号，求问整个图所有的m条边两端的结点，是否至少一个结点出自集合S中。如果是，输出Yes否则输出No

分析：用vector v[n]保存某结点属于的某条边的编号，比如a b两个结点构成的这条边的编号为0，则v[a].push_back(0)，v[b].push_back(0)——表示a属于0号边，b也属于0号边。对于每一个集合做判断，遍历集合中的每一个元素，将当前元素能够属于的边的编号i对应的hash[i]标记为1，表示这条边是满足有一个结点出自集合S中的。最后判断hash数组中的每一个值是否都是1，如果有不是1的，说明这条边的两端结点没有一个出自集合S中，则输出No。否则输出Yes～

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, m, k, nv, a, b, num;
    scanf("%d%d", &n, &m);
    vector<int> v[n];
    for (int i = 0;i < m; i++) {
        scanf("%d%d", &a, &b);
        v[a].push_back(i);
        v[b].push_back(i);
    }
    scanf("%d", &k);
    for (int i = 0; i < k; i++) {
        scanf("%d", &nv);
        int flag = 0;
        vector<int> hash(m, 0);
        for (int j = 0; j < nv; j++) {
            scanf("%d", &num);
            for (int t = 0; t < v[num].size(); t++)
                hash[v[num][t]] = 1;
        }
        for (int j = 0; j < m; j++) {
            if (hash[j] == 0) {
                printf("No\n");
                flag = 1;
                break;
            }
        }
        if (flag == 0) printf("Yes\n");
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

int n, m, k, nv, a, b, num;

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

vector<int> v[n];

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

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

v[a].push_back(i);

v[b].push_back(i);

}

scanf("%d", &k);

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

scanf("%d", &nv);

int flag = 0;

vector<int> hash(m, 0);

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

scanf("%d", &num);

for (int t = 0; t < v[num].size(); t++)

hash[v[num][t]] = 1;

}

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

if (hash[j] == 0) {

printf("No\n");

flag = 1;

break;

}

if (flag == 0) printf("Yes\n");

}

return 0;

}

1075. 链表元素分类(25)-PAT乙级真题

给定一个单链表，请编写程序将链表元素进行分类排列，使得所有负值元素都排在非负值元素的前面，而[0, K]区间内的元素都排在大于K的元素前面。但每一类内部元素的顺序是不能改变的。例如：给定链表为 18→7→-4→0→5→-6→10→11→-2，K为10，则输出应该为 -4→-6→-2→7→0→5→10→18→11。

输入格式：

每个输入包含1个测试用例。每个测试用例第1行给出：第1个结点的地址；结点总个数，即正整数N (<= 105)；以及正整数K (<=1000)。结点的地址是5位非负整数，NULL地址用-1表示。

接下来有N行，每行格式为：

Address Data Next

其中Address是结点地址；Data是该结点保存的数据，为[-105, 105]区间内的整数；Next是下一结点的地址。题目保证给出的链表不为空。

输出格式：

对每个测试用例，按链表从头到尾的顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。

输入样例：
00100 9 10
23333 10 27777
00000 0 99999
00100 18 12309
68237 -6 23333
33218 -4 00000
48652 -2 -1
99999 5 68237
27777 11 48652
12309 7 33218
输出样例：
33218 -4 68237
68237 -6 48652
48652 -2 12309
12309 7 00000
00000 0 99999
99999 5 23333
23333 10 00100
00100 18 27777
27777 11 -1

分析：将结点用list[10000]保存，list为node类型，node中保存结点的值value和它的next地址。list的下标就是结点的地址。将<0、0～k、>k三部分的结点地址分别保存在v[0]、v[1]、v[2]中，最后将vector中的值依次输出即可～

#include <iostream>
#include <vector>
using namespace std;
struct node {
    int data, next;
}list[100000];
vector<int> v[3];
int main() {
    int start, n, k, a;
    scanf("%d%d%d", &start, &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a);
        scanf("%d%d", &list[a].data, &list[a].next);
    }
    int p = start;
    while(p != -1) {
        int data = list[p].data;
        if (data < 0)
            v[0].push_back(p);
        else if (data >= 0 && data <= k)
            v[1].push_back(p);
        else
            v[2].push_back(p);
        p = list[p].next;
    }
    int flag = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < v[i].size(); j++) {
            if (flag == 0) {
                printf("%05d %d ", v[i][j], list[v[i][j]].data);
                flag = 1;
            } else {
                printf("%05d\n%05d %d ", v[i][j], v[i][j], list[v[i][j]].data);
            }
        }
    }
    printf("-1");
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

struct node {

int data, next;

}list[100000];

vector<int> v[3];

int main() {

int start, n, k, a;

scanf("%d%d%d", &start, &n, &k);

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

scanf("%d", &a);

scanf("%d%d", &list[a].data, &list[a].next);

}

int p = start;

while(p != -1) {

int data = list[p].data;

if (data < 0)

v[0].push_back(p);

else if (data >= 0 && data <= k)

v[1].push_back(p);

else

v[2].push_back(p);

p = list[p].next;

}

int flag = 0;

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

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

if (flag == 0) {

printf("%05d %d ", v[i][j], list[v[i][j]].data);

flag = 1;

} else {

printf("%05d\n%05d %d ", v[i][j], v[i][j], list[v[i][j]].data);

}

printf("-1");

return 0;

}

1133. Splitting A Linked List (25)-PAT甲级真题

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] appear before all those greater than K. The order of the elements inside each class must not be changed. For example, given the list being 18→7→-4→0→5→-6→10→11→-2 and K being 10, you must output -4→-6→-2→7→0→5→10→18→11.

Input Specification:
Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (<= 105) which is the total number of nodes, and a positive K (<=1000). 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 in [-105, 105], and Next is the position of the next node. It is guaranteed that the list is not empty.

Output Specification:
For each case, output in order (from beginning to the end of the list) the resulting linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:
00100 9 10
23333 10 27777
00000 0 99999
00100 18 12309
68237 -6 23333
33218 -4 00000
48652 -2 -1
99999 5 68237
27777 11 48652
12309 7 33218
Sample Output:
33218 -4 68237
68237 -6 48652
48652 -2 12309
12309 7 00000
00000 0 99999
99999 5 23333
23333 10 00100
00100 18 27777
27777 11 -1

题目大意：给一个链表和K，遍历链表后将<0的结点先输出，再将0～k区间的结点输出，最后输出>k的结点

分析：1.所有节点用结构体｛id, data, next｝存储
2.遍历链表，找出在此链表中的节点，放入容器v中
3.把节点分三类｛（-无穷，0）, [0,k], (k,+无穷) ｝,把他们按段，按先后顺序依次放进容器ans中，最后输出即可～

#include <iostream>
#include <vector>
using namespace std;
struct node {
    int id, data, next;
};
int main() {
    int begin, n, k, s, d, e;
    scanf("%d%d%d", &begin, &n, &k);
    node a[100010];
    vector<node> v, ans;
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d", &s, &d, &e);
        a[s] = {s, d, e};
    }
    for (; begin != -1; begin = a[begin].next)
        v.push_back(a[begin]);
    for (int i = 0; i < v.size(); i++)
        if (v[i].data < 0) ans.push_back(v[i]);
    for (int i = 0; i < v.size(); i++)
        if (v[i].data >= 0 && v[i].data <= k) ans.push_back(v[i]);
    for (int i = 0; i < v.size(); i++)
        if (v[i].data > k) ans.push_back(v[i]);
    for (int i = 0; i < ans.size() - 1; i++)
        printf("%05d %d %05d\n", ans[i].id, ans[i].data, ans[i + 1].id);
    printf("%05d %d -1\n", ans[ans.size() - 1].id, ans[ans.size() - 1].data);
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

struct node {

int id, data, next;

};

int main() {

int begin, n, k, s, d, e;

scanf("%d%d%d", &begin, &n, &k);

node a[100010];

vector<node> v, ans;

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

scanf("%d%d%d", &s, &d, &e);

a[s] = {s, d, e};

}

for (; begin != -1; begin = a[begin].next)

v.push_back(a[begin]);

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

if (v[i].data < 0) ans.push_back(v[i]);

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

if (v[i].data >= 0 && v[i].data <= k) ans.push_back(v[i]);

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

if (v[i].data > k) ans.push_back(v[i]);

for (int i = 0; i < ans.size() - 1; i++)

printf("%05d %d %05d\n", ans[i].id, ans[i].data, ans[i + 1].id);

printf("%05d %d -1\n", ans[ans.size() - 1].id, ans[ans.size() - 1].data);

return 0;

}

1132. Cut Integer (20)-PAT甲级真题

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, we have A = 167 and B = 334. It is interesting to see that Z can be devided by the product of A and B, as 167334 / (167 x 334) = 3. Given an integer Z, you are supposed to test if it is such an integer.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<= 20). Then N lines follow, each gives an integer Z (10<=Z<=231). It is guaranteed that the number of digits of Z is an even number.

Output Specification:

For each case, print a single line “Yes” if it is such a number, or “No” if not.

Sample Input:
3
167334
2333
12345678
Sample Output:
Yes
No
No

题目大意：给一个偶数个位的正整数num，把它从中间分成左右两个整数a、b，问num能不能被a和b的乘积整除，能的话输出yes，不能的话输出no

分析：要注意a*b如果为0的时候不能取余，否则会浮点错误～
直接用int保存num的值，计算出num的长度len，则令d = pow(10, len / 2)时，num取余d能得到后半部分的整数，num除以d能得到前半部分的整数，计算num % (a*b)是否等于0就可以得知是否可以被整除～

#include <iostream>
using namespace std;
int main() {
    int n, num;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &num);
        string s = to_string(num);
        int len = s.length();
        int a = stoi(s.substr(0, len/2));
        int b = stoi(s.substr(len/2));
        if (a * b != 0 && num % (a * b) == 0)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, num;

scanf("%d", &n);

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

scanf("%d", &num);

string s = to_string(num);

int len = s.length();

int a = stoi(s.substr(0, len/2));

int b = stoi(s.substr(len/2));

if (a * b != 0 && num % (a * b) == 0)

printf("Yes\n");

else

printf("No\n");

}

return 0;

}