hdvsyu's blog

蓝桥杯 ALGO-83 算法训练阶乘 java版

Posted on 2018-05-25 Edited on 2025-12-14 In LanqiaoOJ

问题描述

一个整数n的阶乘可以写成n!，它表示从1到n这n个整数的乘积。阶乘的增长速度非常快，例如，13!就已经比较大了，已经无法存放在一个整型变量中；而35!就更大了，它已经无法存放在一个浮点型变量中。因此，当n比较大时，去计算n!是非常困难的。幸运的是，在本题中，我们的任务不是去计算n!，而是去计算n!最右边的那个非0的数字是多少。例如，5! = 12345 = 120，因此5!最右边的那个非0的数字是2。再如：7! = 5040，因此7!最右边的那个非0的数字是4。请编写一个程序，输入一个整数n(n<=100)，然后输出n! 最右边的那个非0的数字是多少。输入格式：输入只有一个整数n。输出格式：输出只有一个整数，即n! 最右边的那个非0的数字。

输入输出样例

样例输入

6

样例输出

2

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int t = n;
        for (int i = n - 1; i >= 1; i--) {
            int temp = i * t;
            while (temp % 10 == 0) {
                temp /= 10;
            }
            t = temp % 100;
        }
        in.close();

        System.out.println(t % 10);
    }

}

蓝桥杯 ALGO-21算法训练装箱问题 java版

Posted on 2018-05-25 Edited on 2025-12-14 In LanqiaoOJ

问题描述

有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入格式

　　第一行为一个整数，表示箱子容量；第二行为一个整数，表示有n个物品；接下来n行，每行一个整数表示这n个物品的各自体积。

输出格式

　　一个整数，表示箱子剩余空间。

样例输入

24 6 8 3 12 7 9 7

样例输出

0

这是一个背包问题，用动态规划来解

import java.util.Scanner;

public class Main {

    private static int[][] dpOne;
    private static int[] dpTwo;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int V = in.nextInt();
        int n = in.nextInt();
        dpOne = new int[n + 1][V + 1];
        int[] v = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            v[i] = in.nextInt();
        }
        in.close();
        MethodOne(n, v, V);
        System.out.println(V - dpOne[n][V]);
        dpTwo = new int[V + 1];
        MethodTwo(n, v, V);
        System.out.println(V - dpTwo[V]);
    }

    /*
     * 用二维数组来存储 前n个物品放入体积为V的背包中，对于每个物品，如果不取，dp[i][j] = dp[i -
     * 1][j]即前n-1个物品来装体积为V的这个背包 如果取，dp[i][j] = dp[i - 1][j - v[i]] + v[i]即前n
     * -1个物品来装体积为V - v[i]的这个背包
     */
    private static void MethodOne(int n, int[] v, int V) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                if (j >= v[i]) {
                    dpOne[i][j] = Integer.max(dpOne[i - 1][j], dpOne[i - 1][j - v[i]] + v[i]);
                } else {
                    dpOne[i][j] = dpOne[i - 1][j];
                }
            }
        }
    }

    /*
     * 用一维数组来存储 对于每个物品都有取和不取两个状态，如果不取，dp[j]不变，如果取dp[j] = dp[j - v[i]] + v[i]
     */
    private static void MethodTwo(int n, int[] v, int V) {
        for (int i = 1; i <= n; i++) {
            for (int j = V; j > 0; j--) {
                if (j >= v[i]) {
                    dpTwo[j] = Integer.max(dpTwo[j], dpTwo[j - v[i]] + v[i]);
                }
            }
        }
    }
}

蓝桥杯 ADV-194 算法提高盾神与积木游戏 java版

Posted on 2018-05-23 Edited on 2025-12-14 In LanqiaoOJ

问题描述

　　最近的m天盾神都去幼儿园陪小朋友们玩去了~ 每个小朋友都拿到了一些积木，他们各自需要不同数量的积木来拼一些他们想要的东西。但是有的小朋友拿得多，有的小朋友拿得少，有些小朋友需要拿到其他小朋友的积木才能完成他的大作。如果某个小朋友完成了他的作品，那么他就会把自己的作品推倒，而无私地把他的所有积木都奉献出来；但是，如果他还没有完成自己的作品，他是不会把积木让出去的哟~ 盾神看到这么和谐的小朋友们感到非常开心，于是想帮助他们所有人都完成他们各自的作品。盾神现在在想，这个理想有没有可能实现呢？于是把这个问题交给了他最信赖的你。

输入格式

　　第一行为一个数m。接下来有m组数据。每一组的第一行为n，表示这天有n个小朋友。接下来的n行每行两个数，分别表示他现在拥有的积木数和他一共需要的积木数。

输出格式

　　输出m行，如果第i天能顺利完成所有作品，输出YES，否则输出NO。

样例输入

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

样例输出

YES NO

数据规模和约定

　　1<=n<=10000，1<=m<=10。

算法类似于银行家算法，每次满足那个最容易满足的（即所需积木最少的），满足之后把它所占有的资源都回收了，这里直接用Scanner会超时

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(bufferedReader.readLine());
        for (int i = 0; i < m; i++) {
            int n = Integer.parseInt(bufferedReader.readLine());
            Child[] childs = new Child[n];
            for (int j = 0; j < n; j++) {
                String[] t = bufferedReader.readLine().split(" ");
                childs[j] = new Child(Integer.parseInt(t[0]), Integer.parseInt(t[1]));
            }

            System.out.println(bankAlgorithm(childs));
        }
        bufferedReader.close();
    }

    private static String bankAlgorithm(Child[] childs) {
        Arrays.sort(childs);
        int currentNeed = 0;
        for (int i = 0; i < childs.length; i++) {
            if (childs[i].need <= 0) {
                currentNeed += childs[i].have;
            } else { // childs[i].need > 0
                if (currentNeed >= childs[i].need) {
                    currentNeed += childs[i].have;
                } else {
                    return "NO";
                }
            }
        }
        return "YES";
    }
}

class Child implements Comparable<Child> {
    int have;
    int total;
    int need;

    public Child(int have, int total) {
        this.have = have;
        this.total = total;
        this.need = total - have;
    }

    @Override
    public int compareTo(Child child) {
        return need - child.need;
    }

}

PAT 乙级 1006. 换个格式输出整数 (15) C++版

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

让我们用字母B来表示“百”、字母S表示“十”，用“12…n”来表示个位数字n（<10），换个格式来输出任一个不超过3位的正整数。例如234应该被输出为BBSSS1234，因为它有2个“百”、3个“十”、以及个位的4。

输入格式：

每个测试输入包含1个测试用例，给出正整数n（<1000）。

输出格式：

每个测试用例的输出占一行，用规定的格式输出n。

输入样例1：

234

输出样例1：

BBSSS1234

输入样例2：

23

输出样例2：

SS123

#include <iostream>

using namespace std;

int main() {
    int number;
    cin >> number;
    int array[3] = {0};
    int i = 0;
    for (i = 0; number; i++) {
        array[i] = number % 10;
        number /= 10;
    }
    for (int j = array[2]; array[2]; j--) {
        cout << "B";
        array[2]--;
    }
    for (int j = array[1]; array[1]; j--) {
        cout << "S";
        array[1]--;
    }
    for (int j = 1; j <= array[0]; j++) {
        cout << j;
    }
    return 0;
}

PAT 乙级 1007. 素数对猜想 (20) Java版

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

让我们定义 dn 为：dn = pn+1 - pn，其中 pi 是第i个素数。显然有 d1=1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。现给定任意正整数N (< 105)，请计算不超过N的满足猜想的素数对的个数。

输入格式：

每个测试输入包含1个测试用例，给出正整数N。

输出格式：

每个测试用例的输出占一行，不超过N的满足猜想的素数对的个数。

输入样例：

20

输出样例：

4

import java.util.LinkedList;
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();

        LinkedList<Integer> prime = new LinkedList<Integer>();
        for (int i = 2; i <= number; i++) {
            if (isPrime(i)) {
                prime.add(i);
            }
        }


        int cnt = 0;

        for (int i = 0; i < prime.size() - 1; i++) {
            if (prime.get(i) - prime.get(i + 1) == -2) {
                cnt++;
            }
        }

        System.out.println(cnt);
    }

    private static boolean isPrime(int number) {
        for (int i = 2; i <= Math.sqrt(number); i++) {
            if (number % i == 0) {
                return false;
            }
        }
        return true;
    }
}

PAT 乙级 1008. 数组元素循环右移问题 (20) Java版

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

一个数组A中存有N（N>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向右移M（M>=0）个位置，即将A中的数据由（A0A1……AN-1）变换为（AN-M …… AN-1 A0 A1……AN-M-1）（最后M个数循环移至最前面的M个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？

输入格式：

每个输入包含一个测试用例，第1行输入N ( 1<=N<=100)、M（M>=0）；第2行输入N个整数，之间用空格分隔。

输出格式：

在一行中输出循环右移M位以后的整数序列，之间用空格分隔，序列结尾不能有多余空格。

输入样例：

6 2
1 2 3 4 5 6

输出样例：

5 6 1 2 3 4

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int size = in.nextInt();
        int cnt = in.nextInt();
        int[] array = new int[size];

        for (int i = 0; i < array.length; i++) {
            array[i] = in.nextInt();
        }

        in.close();

        for (int i = 0; i < cnt; i++) {
            int temp = array[array.length - 1];
            for (int j = array.length - 1; j > 0; j--) {
                array[j] = array[j - 1];
            }
            array[0] = temp;
        }

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

PAT 乙级 1009. 说反话 (20) Java版

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

给定一句英语，要求你编写程序，将句中所有单词的顺序颠倒输出。

输入格式：

测试输入包含一个测试用例，在一行内给出总长度不超过80的字符串。字符串由若干单词和若干空格组成，其中单词是由英文字母（大小写有区分）组成的字符串，单词之间用1个空格分开，输入保证句子末尾没有多余的空格。

输出格式：

每个测试用例的输出占一行，输出倒序后的句子。

输入样例：

Hello World Here I Come

输出样例：

Come I Here World Hello

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        String[] temp = in.nextLine().split(" ");

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

        in.close();
    }

}

PAT 乙级 1011. A+B和C (15) Java版

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

给定区间[-231, 231]内的3个整数A、B和C，请判断A+B是否大于C。

输入格式：

输入第1行给出正整数T(<=10)，是测试用例的个数。随后给出T组测试用例，每组占一行，顺序给出A、B和C。整数间以空格分隔。

输出格式：

对每组测试用例，在一行中输出“Case #X: true”如果A+B>C，否则输出“Case #X: false”，其中X是测试用例的编号（从1开始）。

输入样例：

4
1 2 3
2 3 4
2147483647 0 2147483646
0 -2147483648 -2147483647

输出样例：

Case #1: false
Case #2: true
Case #3: true
Case #4: false

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        BigInteger[][] number = new BigInteger[t][3];
        for (int i = 0; i < t; i++) {
            for (int j = 0; j < 3; j++) {
                number[i][j] = new BigInteger(in.next());
            }
        }
        in.close();

        for (int i = 0; i < t; i++) {
            System.out.println("Case #" + (i + 1) + ": " + (number[i][0].add(number[i][1]).compareTo(number[i][2]) == 1));
        }
    }
}

PAT 乙级 1017. A除以B (20) Java版

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

本题要求计算A/B，其中A是不超过1000位的正整数，B是1位正整数。你需要输出商数Q和余数R，使得A = B * Q + R成立。

输入格式：

输入在1行中依次给出A和B，中间以1空格分隔。

输出格式：

在1行中依次输出Q和R，中间以1空格分隔。

输入样例：

123456789050987654321 7

输出样例：

17636684150141093474 3

用模拟除的方法AC了

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] ab = bufferedReader.readLine().split(" ");
        bufferedReader.close();
        int b = Integer.parseInt(ab[1]), t = 0;
        StringBuilder stringBuffer = new StringBuilder();
        for (int i = 0; i < ab[0].length(); i++) {
            t = t * 10 + ab[0].charAt(i) - '0';
            stringBuffer.append((char) (t / b + '0'));
            t = t % b;
        }
        String result = stringBuffer.toString();
        if (result.charAt(0) == '0' && result.length() != 1) {
            System.out.print(result.substring(1) + " " + t);
        } else {
            System.out.print(result + " " + t);
        }
    }
}

PAT 乙级 1003. 我要通过！(20) Java版

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

“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于PAT的“答案正确”大派送 —— 只要读入的字符串满足下列条件，系统就输出“答案正确”，否则输出“答案错误”。得到“答案正确”的条件是： 1. 字符串中必须仅有P, A, T这三种字符，不可以包含其它字符； 2. 任意形如 xPATx 的字符串都可以获得“答案正确”，其中 x 或者是空字符串，或者是仅由字母 A 组成的字符串； 3. 如果 aPbTc 是正确的，那么 aPbATca 也是正确的，其中 a, b, c 均或者是空字符串，或者是仅由字母 A 组成的字符串。现在就请你为PAT写一个自动裁判程序，判定哪些字符串是可以获得“答案正确”的。

输入格式：

每个测试输入包含1个测试用例。第1行给出一个自然数n (<10)，是需要检测的字符串个数。接下来每个字符串占一行，字符串长度不超过100，且不包含空格。

输出格式：

每个字符串的检测结果占一行，如果该字符串可以获得“答案正确”，则输出YES，否则输出NO。

输入样例：

8
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA

输出样例：

YES
YES
YES
YES
NO
NO
NO
NO

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        String[] s = new String[n];

        for (int i = 0; i < n; i++) {
            boolean isOther = false;
            s[i] = in.nextLine();
            for (int j = 0; j < s[i].length(); j++) {
                if (s[i].charAt(j) != 'P' && s[i].charAt(j) != 'A' && s[i].charAt(j) != 'T') {
                    System.out.println("NO");
                    isOther = true;
                    break;
                }
            }

            if (!isOther) {
                //if all the character are only P A and T
                if (isTrue(s[i])) {
                    System.out.println("YES");
                } else {
                    System.out.println("NO");
                }

            }
        }
        in.close();
    }

    private static boolean isTrue(String s) {
        //refine the a b and c three substring.
        int p = s.indexOf('P');
        int t = s.indexOf('T');

        if (p > t) {
            return false;
        }

        String a, b, c;
        if (p != -1) {
            a = s.substring(0, p);
        } else {
            return false;
        }

        if (t != -1) {
            c = s.substring(t + 1);
        } else {
            return false;
        }

        b = s.substring(p + 1, t);

        if (a.contains("P") || a.contains("T") || b.contains("T") || b.contains("P") || c.contains("P") || c.contains("T")) {
            return false;
        }

        if (c.length() < a.length()) {
            return false;
        }

        //it assume that the substring not have other character.
        if (b.length() == 0) {
            // b must not be empty.
            return false;
        }


        if (a.equals(c) && a.equals("")) {
            return true;
        }

        int times = 0;
        for (int i = 0; i <= c.length() - a.length(); i += a.length()) {
            if (a.equals(c.substring(i, i + a.length()))) {
                times++;
            }
        }

        return times == b.length();
    }
}