hdvsyu's blog

PAT 乙级 1048. 数字加密(20) Java版

Posted on 2018-04-19 Edited on 2025-12-14 In PAT

本题要求实现一种数字加密方法。首先固定一个加密用正整数A，对任一正整数B，将其每1位数字与A的对应位置上的数字进行以下运算：对奇数位，对应位的数字相加后对13取余——这里用J代表10、Q代表11、K代表12；对偶数位，用B的数字减去A的数字，若结果为负数，则再加10。这里令个位为第1位。

输入格式：

输入在一行中依次给出A和B，均为不超过100位的正整数，其间以空格分隔。

输出格式：

在一行中输出加密后的结果。

输入样例：

1234567 368782971

输出样例：

3695Q8118

import java.util.Scanner;
import java.util.Stack;

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        String a = in.next();
        String b = in.next();
        in.close();

        int i = a.length() - 1;
        int j = b.length() - 1;

        if (i > j) {
            int c = i - j;
            while (c != 0) {
                b = "0" + b;
                c--;
            }
        } else if (i < j) {
            int c = j - i;
            while (c != 0) {
                a = "0" + a;
                c--;
            }
        }

        int index = b.length() - 1; // index = a.length() - 1
        boolean isOdd = true;
        Stack<String> stack = new Stack<>();
        while (index >= 0) {
            if (isOdd) {
                isOdd = false;
                int cNumber = a.charAt(index) - '0' + b.charAt(index) - '0';
                String r = null;
                switch (cNumber) {
                    case 10:
                        r = "J";
                        break;
                    case 11:
                        r = "Q";
                        break;
                    case 12:
                        r = "K";
                        break;
                    default:
                        r = "" + cNumber % 13;
                        break;
                }

                stack.push(r);
            } else {
                isOdd = true;
                int cNumber = (b.charAt(index) - a.charAt(index) + 10) % 10;
                String r = "" + cNumber;

                stack.push(r);
            }

            index--;
        }

        while (!stack.isEmpty()) {
            System.out.print(stack.pop());
        }
    }

}

PAT 乙级 1049. 数列的片段和(20) C++版

Posted on 2018-04-19 Edited on 2025-12-14 In PAT

给定一个正数数列，我们可以从中截取任意的连续的几个数，称为片段。例如，给定数列{0.1, 0.2, 0.3, 0.4}，我们有(0.1) (0.1, 0.2) (0.1, 0.2, 0.3) (0.1, 0.2, 0.3, 0.4) (0.2) (0.2, 0.3) (0.2, 0.3, 0.4) (0.3) (0.3, 0.4) (0.4) 这10个片段。给定正整数数列，求出全部片段包含的所有的数之和。如本例中10个片段总和是0.1 + 0.3 + 0.6 + 1.0 + 0.2 + 0.5 + 0.9 + 0.3 + 0.7 + 0.4 = 5.0。

输入格式：

输入第一行给出一个不超过105的正整数N，表示数列中数的个数，第二行给出N个不超过1.0的正数，是数列中的数，其间以空格分隔。

输出格式：

在一行中输出该序列所有片段包含的数之和，精确到小数点后2位。

输入样例：

4
0.1 0.2 0.3 0.4

输出样例：

5.00

#include <iostream>
#include <stdio.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    double num;
    double sum = 0.0;
    for (int i = 0; i < n; i++) {
        scanf("%lf", &num);
        sum += num * (i + 1) * (n - i);

    }

    printf("%.2f", sum);
    return 0;
}

PAT 乙级 1005. 继续(3n+1)猜想 (25) Java版

Posted on 2018-04-19 Edited on 2025-12-14 In PAT

卡拉兹(Callatz)猜想已经在1001中给出了描述。在这个题目里，情况稍微有些复杂。当我们验证卡拉兹猜想的时候，为了避免重复计算，可以记录下递推过程中遇到的每一个数。例如对n=3进行验证的时候，我们需要计算3、5、8、4、2、1，则当我们对n=5、8、4、2进行验证的时候，就可以直接判定卡拉兹猜想的真伪，而不需要重复计算，因为这4个数已经在验证3的时候遇到过了，我们称5、8、4、2是被3“覆盖”的数。我们称一个数列中的某个数n为“关键数”，如果n不能被数列中的其他数字所覆盖。现在给定一系列待验证的数字，我们只需要验证其中的几个关键数，就可以不必再重复验证余下的数字。你的任务就是找出这些关键数字，并按从大到小的顺序输出它们。

输入格式：

每个测试输入包含1个测试用例，第1行给出一个正整数K(<100)，第2行给出K个互不相同的待验证的正整数n(1<n<=100)的值，数字间用空格隔开。

输出格式：

每个测试用例的输出占一行，按从大到小的顺序输出关键数字。数字间用1个空格隔开，但一行中最后一个数字后没有空格。

输入样例：

6
3 5 6 7 8 11

输出样例：

7 6

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int k = in.nextInt();
        int[] n = new int[k];
        TreeSet[] treeSets = new TreeSet[k];
        for (int i = 0; i < k; i++) {
            n[i] = in.nextInt();
            treeSets[i] = new TreeSet<>(getNumber(n[i]));
        }
        in.close();

        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            if (isMajor(n[i], treeSets, i)) {
                list.add(n[i]);
            }
        }

        int[] array = new int[list.size()];
        for (int i = 0; i < array.length; i++) {
            array[i] = list.get(i);
        }

        Arrays.sort(array);

        for (int i = array.length - 1; i > 0; i--) {
            System.out.print(array[i] + " ");
        }
        System.out.print(array[0]);
    }

    private static boolean isMajor(int n, TreeSet[] treeSets, int index) {
        for (int i = 0; i < treeSets.length; i++) {
            if (i != index && treeSets[i].contains(n)) {
                return false;
            }
        }
        return true;
    }

    private static TreeSet<Integer> getNumber(int n) {
        TreeSet<Integer> treeSet = new TreeSet<>();
        treeSet.add(n);
        while (n != 1) {
            if (n % 2 == 0) {
                n = n / 2;
            } else {

                n = (3 * n + 1) / 2;
            }

            treeSet.add(n);
        }
        return treeSet;
    }
}

PAT 乙级 1004. 成绩排名 (20) C++版

Posted on 2018-04-19 Edited on 2025-12-14 In PAT

读入n名学生的姓名、学号、成绩，分别输出成绩最高和成绩最低学生的姓名和学号。

输入格式：

每个测试输入包含1个测试用例，格式为

第1行：正整数n
第2行：第1个学生的姓名学号成绩
第3行：第2个学生的姓名学号成绩
… … …
第n+1行：第n个学生的姓名学号成绩

其中姓名和学号均为不超过10个字符的字符串，成绩为0到100之间的一个整数，这里保证在一组测试用例中没有两个学生的成绩是相同的。

输出格式：

对每个测试用例输出2行，第1行是成绩最高学生的姓名和学号，第2行是成绩最低学生的姓名和学号，字符串间有1空格。

输入样例：

3
Joe Math990112 89
Mike CS991301 100
Mary EE990830 95

输出样例：

Mike CS991301
Joe Math990112

#include <iostream>
#include <string>

using namespace std;

typedef struct student {
    char name[11];
    char id[11];
    int score;
} student;

int maxScore(student *number, int n) {
    int max = 0;
    for (int i = 0; i < n; i++) {
        if (number[i].score >= number[max].score) {
            max = i;
        }
    }
    return max;

}

int minScore(student *number, int n) {
    int min = 0;
    for (int i = 0; i < n; i++) {
        if (number[i].score <= number[min].score) {
            min = i;
        }
    }
    return min;
}

int main() {
    int n;
    cin >> n;
    student *men = new student[n];
    for (int i = 0; i < n; i++) {
        scanf("%s", men[i].name);
        getchar();
        scanf("%s", men[i].id);
        getchar();
        cin >> men[i].score;
        getchar();
    }
    cout << men[maxScore(men, n)].name << " " << men[maxScore(men, n)].id << endl;
    cout << men[minScore(men, n)].name << " " << men[minScore(men, n)].id << endl;
    return 0;
}

PAT 乙级 1002. 写出这个数 (20) Java版

Posted on 2018-04-18 Edited on 2025-12-14 In PAT

读入一个自然数n，计算其各位数字之和，用汉语拼音写出和的每一位数字。

输入格式：

每个测试输入包含1个测试用例，即给出自然数n的值。这里保证n小于10100。

输出格式：

在一行内输出n的各位数字之和的每一位，拼音数字间有1 空格，但一行中最后一个拼音数字后没有空格。

输入样例：

1234567890987654321123456789

输出样例：

yi san wu

import java.util.Scanner;
import java.util.Stack;

public class Main {

    public static void main(String[]args) {

        Scanner in = new Scanner(System.in);
        String n = in.nextLine();
        in.close();

        int sum = 0;
        for (int i = 0; i < n.length(); i++) {
            sum += n.charAt(i) - '0';
        }

        Stack<String> stack = new Stack<>();
        do {
            int unit = sum % 10;
            switch (unit) {
                case 0:
                    stack.push("ling");
                    break;
                case 1:
                    stack.push("yi");
                    break;
                case 2:
                    stack.push("er");
                    break;
                case 3:
                    stack.push("san");
                    break;
                case 4:
                    stack.push("si");
                    break;
                case 5:
                    stack.push("wu");
                    break;
                case 6:
                    stack.push("liu");
                    break;
                case 7:
                    stack.push("qi");
                    break;
                case 8:
                    stack.push("ba");
                    break;
                case 9:
                    stack.push("jiu");
                    break;
            }
            sum /= 10;
        } while (sum != 0);

        System.out.print(stack.pop());
        while (!stack.isEmpty()) {
            System.out.print(" " + stack.pop());
        }
    }

}

PAT 乙级 1001. 害死人不偿命的(3n+1)猜想 (15) Java版

Posted on 2018-04-18 Edited on 2025-12-14 In PAT

卡拉兹(Callatz)猜想：对任何一个自然数n，如果它是偶数，那么把它砍掉一半；如果它是奇数，那么把(3n+1)砍掉一半。这样一直反复砍下去，最后一定在某一步得到n=1。卡拉兹在1950年的世界数学家大会上公布了这个猜想，传说当时耶鲁大学师生齐动员，拼命想证明这个貌似很傻很天真的命题，结果闹得学生们无心学业，一心只证(3n+1)，以至于有人说这是一个阴谋，卡拉兹是在蓄意延缓美国数学界教学与科研的进展…… 我们今天的题目不是证明卡拉兹猜想，而是对给定的任一不超过1000的正整数n，简单地数一下，需要多少步（砍几下）才能得到n=1？

输入格式：

每个测试输入包含1个测试用例，即给出自然数n的值。 #### 输出格式：输出从n计算到1需要的步数。

输入样例：

3

输出样例：

5

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int number = in.nextInt();
        in.close();
        int cnt = 0;
        while (number != 1) {
            if (number % 2 != 0) {
                number = 3 * number + 1;
            }

            number /= 2;
            cnt++;
        }
        System.out.println(cnt);
    }

}

PAT 乙级 1051. 复数乘法 (15) Java版

Posted on 2018-04-18 Edited on 2025-12-14 In PAT

复数可以写成(A + Bi)的常规形式，其中A是实部，B是虚部，i是虚数单位，满足i2 = -1；也可以写成极坐标下的指数形式(Re(P*i))，其中R是复数模，P是辐角，i是虚数单位，其等价于三角形式(R(cos(P) + isin(P))。现给定两个复数的R和P，要求输出两数乘积的常规形式。

输入格式：

输入在一行中依次给出两个复数的R1, P1, R2, P2，数字间以空格分隔。

输出格式：

在一行中按照“A+Bi”的格式输出两数乘积的常规形式，实部和虚部均保留2位小数。注意：如果B是负数，则应该写成“A-|B|i”的形式。

输入样例：

2.3 3.5 5.2 0.4

输出样例：

-8.68-8.23i

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        double r1 = in.nextDouble();
        double p1 = in.nextDouble();
        double r2 = in.nextDouble();
        double p2 = in.nextDouble();

        in.close();
        double a = r1 * Math.cos(p1) * r2 * Math.cos(p2) - r1 * Math.sin(p1) * r2 * Math.sin(p2);
        double b = r1 * Math.sin(p1) * r2 * Math.cos(p2) + r2 * Math.sin(p2) * r1 * Math.cos(p1);

        if (Math.abs(a) <= 0.001) {
            System.out.print("0.00");
        } else {
            System.out.printf("%.2f", a);
        }

        if (b > 0) {
            System.out.printf("+%.2fi", b);
        } else if (Math.abs(b) <= 0.001) {
            System.out.print("+0.00i");
        } else {
            System.out.printf("%.2fi", b);
        }
    }

}

PAT 乙级 1055. 集体照 (25) C++版

Posted on 2018-04-18 Edited on 2025-12-14 In PAT

拍集体照时队形很重要，这里对给定的N个人K排的队形设计排队规则如下：

每排人数为N/K（向下取整），多出来的人全部站在最后一排；
后排所有人的个子都不比前排任何人矮；
每排中最高者站中间（中间位置为m/2+1，其中m为该排人数，除法向下取整）；
每排其他人以中间人为轴，按身高非增序，先右后左交替入队站在中间人的两侧（例如5人身高为190、188、186、175、170，则队形为175、188、190、186、170。这里假设你面对拍照者，所以你的左边是中间人的右边）；
若多人身高相同，则按名字的字典序升序排列。这里保证无重名。

现给定一组拍照人，请编写程序输出他们的队形。

输入格式：

每个输入包含1个测试用例。每个测试用例第1行给出两个正整数N（<=10000，总人数）和K（<=10，总排数）。随后N行，每行给出一个人的名字（不包含空格、长度不超过8个英文字母）和身高（[30, 300]区间内的整数）。

输出格式：

输出拍照的队形。即K排人名，其间以空格分隔，行末不得有多余空格。注意：假设你面对拍照者，后排的人输出在上方，前排输出在下方。

输入样例：

10 3
Tom 188
Mike 170
Eva 168
Tim 160
Joe 190
Ann 168
Bob 175
Nick 186
Amy 160
John 159

输出样例：

Bob Tom Joe Nick
Ann Mike Eva
Tim Amy John

#include <iostream>
#include <algorithm>

using namespace std;
struct People {
    string name;
    int high;
};

bool cmp(People p1, People p2) {
    if (p1.high < p2.high) {
        return true;
    } else if (p1.high > p2.high) {
        return false;
    } else {
        return p1.name > p2.name;
    }
}

int main() {
    int n = 0, k = 0;
    cin >> n >> k;
    struct People *peoples = new struct People[n];
    for (int i = 0; i < n; i++) {
        cin >> peoples[i].name >> peoples[i].high;
    }

    sort(peoples, peoples + n, cmp);

    int per = n / k;
    for (int i = k; i >= 1; i--) {
        int len = 0;
        int index = 0;
        if (i == k) {
            len = n - k * per + per;
            index = n - 1;
        } else {
            len = per;
            index = i * per - 1;
        }

        People *temp = new People[len];
        int left = len / 2;
        int right = len / 2;
        temp[left] = peoples[index--];
        left--;
        right++;
        while (left >= 0 && right < len) {
            temp[left--] = peoples[index--];
            temp[right++] = peoples[index--];
        }

        if (left >= 0) {
            temp[left] = peoples[index];
        } else if (right < len) {
            temp[right] = peoples[index];
        }

        for (int j = 0; j < len - 1; j++) {
            cout << temp[j].name << " ";
        }
        cout << temp[len - 1].name << endl;;
    }

    delete[] peoples;
    return 0;
}

PAT 乙级 1054. 求平均值 (20) Java版

Posted on 2018-04-16 Edited on 2025-12-14 In PAT

本题的基本要求非常简单：给定N个实数，计算它们的平均值。但复杂的是有些输入数据可能是非法的。一个“合法”的输入是[-1000，1000]区间内的实数，并且最多精确到小数点后2位。当你计算平均值的时候，不能把那些非法的数据算在内。

输入格式：

输入第一行给出正整数N（<=100）。随后一行给出N个正整数，数字间以一个空格分隔。

输出格式：

对每个非法输入，在一行中输出“ERROR: X is not a legal number”，其中X是输入。最后在一行中输出结果：“The average of K numbers is Y”，其中K是合法输入的个数，Y是它们的平均值，精确到小数点后2位。如果平均值无法计算，则用“Undefined”替换Y。如果K为1，则输出“The average of 1 number is Y”。

输入样例1：

7
5 -3.2 aaa 9999 2.3.4 7.123 2.35

输出样例1：

ERROR: aaa is not a legal number
ERROR: 9999 is not a legal number
ERROR: 2.3.4 is not a legal number
ERROR: 7.123 is not a legal number
The average of 3 numbers is 1.38

输入样例2：

2
aaa -9999

输出样例2：

ERROR: aaa is not a legal number
ERROR: -9999 is not a legal number
The average of 0 numbers is Undefined

这里用了抛异常的方式来判断输入的值是否符合规则

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int cnt = 0;
        double y = 0;
        for (int i = 0; i < n; i++) {
            double x = 0;
            String s = null;
            try {
                s = in.next();
                x = Double.parseDouble(s);
                double temp = Double.parseDouble(String.format("%.2f", x));
                if (x > 1000 || x < -1000 || Math.abs(temp - x) >= 0.001) {
                    throw new NumberFormatException();
                }

                cnt++;
                y += x;
            } catch (NumberFormatException e) {
                System.out.println("ERROR: " + s + " is not a legal number");
            }
        }
        in.close();

        if (cnt == 0) {
            System.out.println("The average of 0 numbers is Undefined");
        } else if (cnt == 1) {
            System.out.printf("The average of 1 number is %.2f", y);
        } else {
            System.out.printf("The average of %d numbers is %.2f", cnt, y / cnt);
        }
    }

}

蓝桥杯 ALGO-4 算法训练结点选择

Posted on 2018-04-07 Edited on 2025-12-14 In LanqiaoOJ

问题描述

有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？

输入格式

第一行包含一个整数 n 。接下来的一行包含 n 个正整数，第 i 个正整数代表点 i 的权值。接下来一共 n-1 行，每行描述树上的一条边。

输出格式

输出一个整数，代表选出的点的权值和的最大值。

样例输入

5 1 2 3 4 5 1 2 1 3 2 4 2 5

样例输出

12

样例说明

选择3、4、5号点，权值和为 3+4+5 = 12 。

数据规模与约定

对于20%的数据， n <= 20。对于50%的数据， n <= 1000。对于100%的数据， n <= 100000。权值均为不超过1000的正整数。

题目给出的数据不一定是二叉树，用图来处理。每个点的最大权值有取当前这个点和不取当前这个点两种情况。取当前点，则不能取与它相邻的任何点；不取当前点，则取与它相邻点的最大值，然后对所有相邻点求和就是当前点所能得到的最大值。

#include <cstdio>
#include <vector>

using namespace std;

vector<vector<int> > v;
int dp[100000][2];

void dfs(int root, int pre) {
    for (int i = 0; i < v[root].size(); i++) {
        if (v[root][i] != pre) {
            dfs(v[root][i], root);
            dp[root][0] += max(dp[v[root][i]][0], dp[v[root][i]][1]);
            dp[root][1] += dp[v[root][i]][0];
        }
    }
}

int main() {
    int n = 0, a = 0, b = 0;
    scanf("%d", &n);
    v.resize(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &dp[i][1]);
    }
    for (int i = 0; i < n - 1; i++) {
        scanf("%d %d", &a, &b);
        v[a - 1].push_back(b - 1);
        v[b - 1].push_back(a - 1);
    }
    dfs(0, -1);
    printf("%d", max(dp[0][0], dp[0][1]));
    return 0;
}