柳婼の blog – 第176页 – 我不管，反正我最萌～

1123. Is It a Complete AVL Tree (30)-PAT甲级真题

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.

Now given a sequence of insertions, you are supposed to output the level-order traversal sequence of the resulting AVL tree, and to tell if it is a complete binary tree.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<= 20). Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.

Output Specification:

For each test case, insert the keys one by one into an initially empty AVL tree. Then first print in a line the level-order traversal sequence of the resulting AVL tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line. Then in the next line, print “YES” if the tree is complete, or “NO” if not.

Sample Input 1:

5
88 70 61 63 65

Sample Output 1:

70 63 88 61 65
YES

Sample Input 2:

8
88 70 61 96 120 90 65 68

Sample Output 2:

88 65 96 61 70 90 120 68
NO

分析：这道题实际上考察AVL树和层序遍历两个知识点～～
判断是不是完全二叉树，就看在出现了一个孩子为空的结点之后是否还会出现孩子结点不为空的结点，如果出现了就不是完全二叉树。
AVL树一共有四种情况，这里我把发现树不平衡的那个结点叫做A结点，A发现树不平衡的情况有四种：
新来的结点插入到A的左子树的左子树
新来的结点插入到A的左子树的右子树
新来的结点插入到A的右子树的左子树
新来的结点插入到A的右子树的右子树
发现不平衡时就需要处理，第1种情况只要简单的右旋，第4种情况只需左旋一下，第2种情况需要先对A的左子树左旋一下，然后对A右旋，同理第3种情况需要对A的右子树右旋一下，然后对A左旋就可以啦～～～

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct node {
    int val;
    struct node *left, *right;
};
node* leftRotate(node *tree) {
    node *temp = tree->right;
    tree->right = temp->left;
    temp->left = tree;
    return temp;
}
node* rightRotate(node *tree) {
    node *temp = tree->left;
    tree->left = temp->right;
    temp->right = tree;
    return temp;
}
node* leftRightRotate(node *tree) {
    tree->left = leftRotate(tree->left);
    return rightRotate(tree);
}
node* rightLeftRotate(node *tree) {
    tree->right = rightRotate(tree->right);
    return leftRotate(tree);
}
int getHeight(node *tree) {
    if (tree == NULL) return 0;
    int l = getHeight(tree->left);
    int r = getHeight(tree->right);
    return max(l, r) + 1;
}
node* insert(node *tree, int val) {
    if (tree == NULL) {
        tree = new node();
        tree->val = val;
    }else if (tree->val > val) {
        tree->left = insert(tree->left, val);
        int l = getHeight(tree->left), r = getHeight(tree->right);
        if (l - r >= 2) {
            if (val < tree->left->val)
                tree = rightRotate(tree);
            else
                tree = leftRightRotate(tree);
        }
    } else {
        tree->right = insert(tree->right, val);
        int l = getHeight(tree->left), r = getHeight(tree->right);
        if (r - l >= 2) {
            if (val > tree->right->val)
                tree = leftRotate(tree);
            else
                tree = rightLeftRotate(tree);
        }
    }
    return tree;
}
int isComplete = 1, after = 0;
vector<int> levelOrder(node *tree) {
    vector<int> v;
    queue<node *> queue;
    queue.push(tree);
    while (!queue.empty()) {
        node *temp = queue.front();
        queue.pop();
        v.push_back(temp->val);
        if (temp->left != NULL) {
            if (after) isComplete = 0;
            queue.push(temp->left);
        } else {
            after = 1;
        }
        if (temp->right != NULL) {
            if (after) isComplete = 0;
            queue.push(temp->right);
        } else {
            after = 1;
        }
    }
    return v;
}
int main() {
    int n, temp;
    scanf("%d", &n);
    node *tree = NULL;
    for (int i = 0; i < n; i++) {
        scanf("%d", &temp);
        tree = insert(tree, temp);
    }
    vector<int> v = levelOrder(tree);
    for (int i = 0; i < v.size(); i++) {
        if (i != 0) printf(" ");
        printf("%d", v[i]);
    }
    printf("\n%s", isComplete ? "YES" : "NO");
    return 0;
}

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

struct node {

int val;

struct node *left, *right;

};

node* leftRotate(node *tree) {

node *temp = tree->right;

tree->right = temp->left;

temp->left = tree;

return temp;

}

node* rightRotate(node *tree) {

node *temp = tree->left;

tree->left = temp->right;

temp->right = tree;

return temp;

}

node* leftRightRotate(node *tree) {

tree->left = leftRotate(tree->left);

return rightRotate(tree);

}

node* rightLeftRotate(node *tree) {

tree->right = rightRotate(tree->right);

return leftRotate(tree);

}

int getHeight(node *tree) {

if (tree == NULL) return 0;

int l = getHeight(tree->left);

int r = getHeight(tree->right);

return max(l, r) + 1;

}

node* insert(node *tree, int val) {

if (tree == NULL) {

tree = new node();

tree->val = val;

}else if (tree->val > val) {

tree->left = insert(tree->left, val);

int l = getHeight(tree->left), r = getHeight(tree->right);

if (l - r >= 2) {

if (val < tree->left->val)

tree = rightRotate(tree);

else

tree = leftRightRotate(tree);

}

} else {

tree->right = insert(tree->right, val);

int l = getHeight(tree->left), r = getHeight(tree->right);

if (r - l >= 2) {

if (val > tree->right->val)

tree = leftRotate(tree);

else

tree = rightLeftRotate(tree);

}

return tree;

}

int isComplete = 1, after = 0;

vector<int> levelOrder(node *tree) {

vector<int> v;

queue<node *> queue;

queue.push(tree);

while (!queue.empty()) {

node *temp = queue.front();

queue.pop();

v.push_back(temp->val);

if (temp->left != NULL) {

if (after) isComplete = 0;

queue.push(temp->left);

} else {

after = 1;

}

if (temp->right != NULL) {

if (after) isComplete = 0;

queue.push(temp->right);

} else {

after = 1;

}

return v;

}

int main() {

int n, temp;

scanf("%d", &n);

node *tree = NULL;

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

scanf("%d", &temp);

tree = insert(tree, temp);

}

vector<int> v = levelOrder(tree);

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

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

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

}

printf("\n%s", isComplete ? "YES" : "NO");

return 0;

}

1063. 计算谱半径(20)-PAT乙级真题

在数学中，矩阵的“谱半径”是指其特征值的模集合的上确界。换言之，对于给定的n个复数空间的特征值{a1+b1i, …, an+bni}，它们的模为实部与虚部的平方和的开方，而“谱半径”就是最大模。

现在给定一些复数空间的特征值，请你计算并输出这些特征值的谱半径。

输入格式：

输入第一行给出正整数N（<= 10000）是输入的特征值的个数。随后N行，每行给出1个特征值的实部和虚部，其间以空格分隔。注意：题目保证实部和虚部均为绝对值不超过1000的整数。

输出格式：

在一行中输出谱半径，四舍五入保留小数点后2位。

输入样例：
5
0 1
2 0
-1 0
3 3
0 -3
输出样例：
4.24

分析：用max保存谱半径，对于n个特征值的实部a和虚部b，模ans = (a的平方+b的平方)的开方，所以ans = sqrt(a * a + b * b)；将ans的最大值保存在max中，最后用%.2f输出max的值～

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int n;
    scanf("%d", &n);
    float max = 0;
    for(int i = 0; i < n; i++) {
        float a, b, ans;
        scanf("%f%f", &a, &b);
        ans = sqrt(a * a + b * b);
        max = ans > max ? ans : max;
    }
    printf("%.2f", max);
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n;

scanf("%d", &n);

float max = 0;

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

float a, b, ans;

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

ans = sqrt(a * a + b * b);

max = ans > max ? ans : max;

}

printf("%.2f", max);

return 0;

}

1062. 最简分数(20)-PAT乙级真题

一个分数一般写成两个整数相除的形式：N/M，其中M不为0。最简分数是指分子和分母没有公约数的分数表示形式。

现给定两个不相等的正分数 N1/M1 和 N2/M2，要求你按从小到大的顺序列出它们之间分母为K的最简分数。

输入格式：

输入在一行中按N/M的格式给出两个正分数，随后是一个正整数分母K，其间以空格分隔。题目保证给出的所有整数都不超过1000。

输出格式：

在一行中按N/M的格式列出两个给定分数之间分母为K的所有最简分数，按从小到大的顺序，其间以1个空格分隔。行首尾不得有多余空格。题目保证至少有1个输出。

输入样例：
7/18 13/20 12
输出样例：
5/12 7/12

分析：使用辗转相除法gcd计算a和b的最大公约数，因为要列出n1/m1和n2/m2之间的最简分数，但是n1/m1不一定小于n2/m2，所以如果n1 * m2 > n2 * m1，说明n1/m1比n2/m2大，则调换n1和n2、m1和m2的位置～假设所求的分数分母为k、分子num，先令num=1，当n1 * k >= m1 * num时，num不断++，直到num符合n1/m1 < num/k为止～然后在n1/m1和n2/m2之间找符合条件的num的值，用gcd(num, k)是否等于1判断num和k是否有最大公约数，如果等于1表示没有最大公约数，就输出num/k，然后num不断++直到退出循环～

#include <iostream>
using namespace std;
int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a % b);
}
int main() {
    int n1, m1, n2, m2, k;
    scanf("%d/%d %d/%d %d", &n1, &m1, &n2, &m2, &k);
    if(n1 * m2 > n2 * m1) {
        swap(n1, n2);
        swap(m1, m2);
    }
    int num = 1;
    bool flag = false;
    while(n1 * k >= m1 * num) num++;
    while(n1 * k < m1 * num && m2 * num < n2 * k) {
        if(gcd(num, k) == 1) {
            printf("%s%d/%d", flag == true ? " " : "", num, k);
            flag = true;
        }
        num++;
    }
    return 0;
}

#include <iostream>

using namespace std;

int gcd(int a, int b){

return b == 0 ? a : gcd(b, a % b);

}

int main() {

int n1, m1, n2, m2, k;

scanf("%d/%d %d/%d %d", &n1, &m1, &n2, &m2, &k);

if(n1 * m2 > n2 * m1) {

swap(n1, n2);

swap(m1, m2);

}

int num = 1;

bool flag = false;

while(n1 * k >= m1 * num) num++;

while(n1 * k < m1 * num && m2 * num < n2 * k) {

if(gcd(num, k) == 1) {

printf("%s%d/%d", flag == true ? " " : "", num, k);

flag = true;

}

num++;

}

return 0;

}

1061. 判断题(15)-PAT乙级真题

判断题的评判很简单，本题就要求你写个简单的程序帮助老师判题并统计学生们判断题的得分。

输入格式：

输入在第一行给出两个不超过100的正整数N和M，分别是学生人数和判断题数量。第二行给出M个不超过5的正整数，是每道题的满分值。第三行给出每道题对应的正确答案，0代表“非”，1代表“是”。随后N行，每行给出一个学生的解答。数字间均以空格分隔。

输出格式：

按照输入的顺序输出每个学生的得分，每个分数占一行。

输入样例：
3 6
2 1 3 3 4 5
0 0 1 0 1 1
0 1 1 0 0 1
1 0 1 0 1 0
1 1 0 0 1 1
输出样例：
13
11
12

分析：score数组表示每道题的分值，ans数组表示每道题的答案，对于每一个学生，如果他给出的答案temp等于正确答案ans[j]，则将这道题的分数score[j]累加到total中，最后输出total的值～

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, m, temp;
    scanf("%d%d", &n, &m);
    vector<int> score(m), ans(m);
    for(int i = 0; i < m; i++)
        scanf("%d", &score[i]);
    for(int i = 0; i < m; i++)
        scanf("%d", &ans[i]);
    for(int i = 0; i < n; i++) {
        int total = 0;
        for(int j = 0; j < m; j++) {
            scanf("%d", &temp);
            if(temp == ans[j])
                total += score[j];
        }
        printf("%d\n", total);
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

int n, m, temp;

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

vector<int> score(m), ans(m);

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

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

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

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

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

int total = 0;

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

scanf("%d", &temp);

if(temp == ans[j])

total += score[j];

}

printf("%d\n", total);

}

return 0;

}

1065. 单身狗(25)-PAT乙级真题

“单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人，以便给予特殊关爱。

输入格式：

输入第一行给出一个正整数N（<=50000），是已知夫妻/伴侣的对数；随后N行，每行给出一对夫妻/伴侣——为方便起见，每人对应一个ID号，为5位数字（从00000到99999），ID间以空格分隔；之后给出一个正整数M（<=10000），为参加派对的总人数；随后一行给出这M位客人的ID，以空格分隔。题目保证无人重婚或脚踩两条船。

输出格式：

首先第一行输出落单客人的总人数；随后第二行按ID递增顺序列出落单的客人。ID间用1个空格分隔，行的首尾不得有多余空格。

输入样例：

3
11111 22222
33333 44444
55555 66666
7
55555 44444 10000 88888 22222 11111 23333

输出样例：

5
10000 23333 44444 55555 88888

分析：设立数组couple[i] = j表示i的对象是j～一开始先设置为都是-1，设立数组isExist表示某人的对象是否来到了派对上～接收数据的时候，对于每一对a和b，将couple的a设置为b，b设置为a，表示他俩是一对～对于每一个需要判断的人，将其存储在guest数组里面，如果它不是单身的（也就是如果它的couple[guest[i]] != -1）那么就将它对象的isExist设置为1，表示他对象的对象（也就是他自己）来到了派对～这样所有isExist不为1的人，对象是没有来到派对的～把所有的人遍历后插入一个集合set里面，set的size就是所求的人数，set里面的所有数就是所求的人的递增排列～

#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main() {
    int n, a, b, m;
    scanf("%d", &n);
    vector<int> couple(100000, -1);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &a, &b);
        couple[a] = b;
        couple[b] = a;
    }
    scanf("%d", &m);
    vector<int> guest(m), isExist(100000);
    for (int i = 0; i < m; i++) {
        scanf("%d", &guest[i]);
        if (couple[guest[i]] != -1)
            isExist[couple[guest[i]]] = 1;
    }
    set<int> s;
    for (int i = 0; i < m; i++) {
        if (!isExist[guest[i]])
            s.insert(guest[i]);
    }
    printf("%d\n", s.size());
    for (auto it = s.begin(); it != s.end(); it++) {
        if (it != s.begin()) printf(" ");
        printf("%05d", *it);
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <set>

using namespace std;

int main() {

int n, a, b, m;

scanf("%d", &n);

vector<int> couple(100000, -1);

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

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

couple[a] = b;

couple[b] = a;

}

scanf("%d", &m);

vector<int> guest(m), isExist(100000);

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

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

if (couple[guest[i]] != -1)

isExist[couple[guest[i]]] = 1;

}

set<int> s;

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

if (!isExist[guest[i]])

s.insert(guest[i]);

}

printf("%d\n", s.size());

for (auto it = s.begin(); it != s.end(); it++) {

if (it != s.begin()) printf(" ");

printf("%05d", *it);

}

return 0;

}

1064. 朋友数(20)

如果两个整数各位数字的和是一样的，则被称为是“朋友数”，而那个公共的和就是它们的“朋友证号”。例如123和51就是朋友数，因为1+2+3 = 5+1 = 6，而6就是它们的朋友证号。给定一些整数，要求你统计一下它们中有多少个不同的朋友证号。注意：我们默认一个整数自己是自己的朋友。

输入格式：

输入第一行给出正整数N。随后一行给出N个正整数，数字间以空格分隔。题目保证所有数字小于10⁴。

输出格式：

首先第一行输出给定数字中不同的朋友证号的个数；随后一行按递增顺序输出这些朋友证号，数字间隔一个空格，且行末不得有多余空格。

输入样例：

8
123 899 51 998 27 33 36 12

1 2	8 123 899 51 998 27 33 36 12

输出样例：

4
3 6 9 26

1 2	4 3 6 9 26

分析：在接收输入数据的时候就把该数字的每一位相加，并把结果插入一个set集合中。因为set是有序的、不重复的，所以set的size值就是输出的个数，set中的每一个数字即所有答案的数字序列

此为Java版，C/C++版本请戳：http://www.liuchuo.net/archives/2889

import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int numOfInteger = scanner.nextInt();
		Set<Integer> set = new TreeSet<Integer>();
		for (int i = 0; i < numOfInteger; i++) {
			int temp = scanner.nextInt();
			set.add(getFriendId(temp));
		}
		scanner.close();
		System.out.println(set.size());
		boolean isFirst = true;
		for (int id : set) {
			if (!isFirst) {
				System.out.print(" ");
			}
			System.out.print(id);
			isFirst = false;
		}
	}
	
	private static int getFriendId(int num) {
		int sum = 0;
		while(num != 0) {
			sum += num % 10;
			num /= 10;
		}
		return sum;
	}
}

import java.util.Scanner;

import java.util.Set;

import java.util.TreeSet;

public class Main {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int numOfInteger = scanner.nextInt();

Set<Integer> set = new TreeSet<Integer>();

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

int temp = scanner.nextInt();

set.add(getFriendId(temp));

}

scanner.close();

System.out.println(set.size());

boolean isFirst = true;

for (int id : set) {

if (!isFirst) {

System.out.print(" ");

}

System.out.print(id);

isFirst = false;

}

private static int getFriendId(int num) {

int sum = 0;

while(num != 0) {

sum += num % 10;

num /= 10;

}

return sum;

}