liuchuo – 第54页 – 我不管，反正我最萌～

[Java] 蓝桥杯ALGO-12 算法训练幂方分解

问题描述
任何一个正整数都可以用2的幂次方表示。例如：
137=27+23+20
同时约定方次用括号来表示，即ab 可表示为a（b）。
由此可知，137可表示为：
2（7）+2（3）+2（0）
进一步：7= 22+2+20 （21用2表示）
3=2+20
所以最后137可表示为：
2（2（2）+2+2（0））+2（2+2（0））+2（0）
又如：
1315=210 +28 +25 +2+1
所以1315最后可表示为：
2（2（2+2（0））+2）+2（2（2+2（0）））+2（2（2）+2（0））+2+2（0）
输入格式
输入包含一个正整数N（N<=20000），为要求分解的整数。
输出格式
程序输出包含一行字符串，为符合约定的n的0，2表示（在表示中不能有空格）

package algo12;

import java.util.Scanner;

public class Main {

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

    private static void div(int n) {
        if (n == 0) {
            System.out.print(0);
            return;
        }
        
        char[] cs = Integer.toBinaryString(n).toCharArray();
        boolean isOutputFirst = false;
        for (int i = 0; i < cs.length; i++) {
            if (cs[i] == '1') {
                if (isOutputFirst) {
                    if (cs.length - i - 1 == 1) {
                        System.out.print("+2");
                    } else {
                        System.out.print("+2(");
                        div(cs.length - 1 - i);
                        System.out.print(")");
                    }
                } else {
                    if (cs.length - i - 1 == 1) {
                        System.out.print(2);
                    } else {
                        System.out.print("2(");
                        div(cs.length - 1 - i);
                        System.out.print(")");
                    }
                    isOutputFirst = true;
                }
            }
        }
    }
}

package algo12;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int n = in.nextInt();

in.close();

div(n);

}

private static void div(int n) {

if (n == 0) {

System.out.print(0);

return;

}

char[] cs = Integer.toBinaryString(n).toCharArray();

boolean isOutputFirst = false;

for (int i = 0; i < cs.length; i++) {

if (cs[i] == '1') {

if (isOutputFirst) {

if (cs.length - i - 1 == 1) {

System.out.print("+2");

} else {

System.out.print("+2(");

div(cs.length - 1 - i);

System.out.print(")");

}

} else {

if (cs.length - i - 1 == 1) {

System.out.print(2);

} else {

System.out.print("2(");

div(cs.length - 1 - i);

System.out.print(")");

}

isOutputFirst = true;

}

[Java] 蓝桥杯ALGO-13 算法训练拦截导弹

问题描述
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
一行，为导弹依次飞来的高度
输出格式
两行，分别是最多能拦截的导弹数与要拦截所有导弹最少要配备的系统数
样例输入
389 207 155 300 299 170 158 65
样例输出
6
2

package algo13;

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] missile = reader.readLine().split(" ");
        reader.close();
        int[] high = new int[missile.length];
        for (int i = 0; i < high.length; i++) {
            high[i] = Integer.parseInt(missile[i]);
        }
        System.out.println(getMaxIntercept(high));
        System.out.println(getNumberOfIntercepter(high));
    }
    
    private static int getMaxIntercept(int[] high) {
        int[] dp = new int[high.length];
        int max = 0;
        for (int i = 0; i < high.length; i++) {
            for (int j = i + 1; j < high.length; j++) {
                if (high[j] <= high[i]) {
                    dp[j] = Integer.max(dp[j], dp[i] + 1);
                    max = Integer.max(max, dp[j]);
                }
            }
        }
        return max + 1;
    }
    
    private static int getNumberOfIntercepter(int[] high) {
        int numberOfIntercepter = 0;
        boolean[] isIntercept = new boolean[high.length];
        for (int i = 0; i < high.length; i++) {
            int midHighDifference = getMinHighDifference(high, i, isIntercept);
            if (midHighDifference == -1) {
                numberOfIntercepter++;
            } else {
                isIntercept[midHighDifference] = true;
            }
        }
        return numberOfIntercepter;
    }
    
    private static int getMinHighDifference(int[] high, int pos, boolean[] isIntercept) {
        int minHighDifferenceIndex = -1;
        for (int i = 0; i < pos; i++) { if (isIntercept[i] == false && high[i] >= high[pos]) {
                if (minHighDifferenceIndex == -1 || high[i] < high[minHighDifferenceIndex]) {
                    minHighDifferenceIndex = i;
                }
            }
        }
        return minHighDifferenceIndex;
    }
}

package algo13;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

public class Main {

public static void main(String[] args) throws IOException {

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

String[] missile = reader.readLine().split(" ");

reader.close();

int[] high = new int[missile.length];

for (int i = 0; i < high.length; i++) {

high[i] = Integer.parseInt(missile[i]);

}

System.out.println(getMaxIntercept(high));

System.out.println(getNumberOfIntercepter(high));

}

private static int getMaxIntercept(int[] high) {

int[] dp = new int[high.length];

int max = 0;

for (int i = 0; i < high.length; i++) {

for (int j = i + 1; j < high.length; j++) {

if (high[j] <= high[i]) {

dp[j] = Integer.max(dp[j], dp[i] + 1);

max = Integer.max(max, dp[j]);

}

return max + 1;

}

private static int getNumberOfIntercepter(int[] high) {

int numberOfIntercepter = 0;

boolean[] isIntercept = new boolean[high.length];

for (int i = 0; i < high.length; i++) {

int midHighDifference = getMinHighDifference(high, i, isIntercept);

if (midHighDifference == -1) {

numberOfIntercepter++;

} else {

isIntercept[midHighDifference] = true;

}

return numberOfIntercepter;

}

private static int getMinHighDifference(int[] high, int pos, boolean[] isIntercept) {

int minHighDifferenceIndex = -1;

for (int i = 0; i < pos; i++) { if (isIntercept[i] == false && high[i] >= high[pos]) {

if (minHighDifferenceIndex == -1 || high[i] < high[minHighDifferenceIndex]) {

minHighDifferenceIndex = i;

}

return minHighDifferenceIndex;

}

[Java] 蓝桥杯ALGO-27 算法训练 FBI树

问题描述
我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。
FBI树是一种二叉树，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：
1)T的根结点为R，其类型与串S的类型相同；
2)若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。
现在给定一个长度为2N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。
输入格式
第一行是一个整数N（0 <= N <= 10），第二行是一个长度为2N的“01”串。
输出格式
包括一行，这一行只包含一个字符串，即FBI树的后序遍历序列。
样例输入
3
10001011
样例输出
IBFBBBFIBFIIIFF
数据规模和约定
对于40%的数据，N <= 2；对于全部的数据，N <= 10。注： [1] 二叉树：二叉树是结点的有限集合，这个集合或为空集，或由一个根结点和两棵不相交的二叉树组成。这两棵不相交的二叉树分别称为这个根结点的左子树和右子树。 [2] 后序遍历：后序遍历是深度优先遍历二叉树的一种方法，它的递归定义是：先后序遍历左子树，再后序遍历右子树，最后访问根。

package algo27;

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 reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        char[] s = reader.readLine().toCharArray();
        reader.close();
        fbi(s, n);
    }
    
    private static String fbi(char[] s,int n) {
        if (s.length == 1) {
            switch (s[0]) {
            case '1':
                System.out.print("I");
                return "I";
            case '0':
                System.out.print("B");
                return "B";
            default:
                break;
            }
        }
    
        char[] s1 = Arrays.copyOfRange(s, 0, s.length / 2);
        String left = fbi(s1,n);
        char[] s2 = Arrays.copyOfRange(s, s.length / 2, s.length);
        String right = fbi(s2, n);
        if (left.equals(right)) {
            System.out.print(left);
            return left;
        } else {
            System.out.print("F");
            return "F";
        }
    }
}

package algo27;

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 reader = new BufferedReader(new InputStreamReader(System.in));

int n = Integer.parseInt(reader.readLine());

char[] s = reader.readLine().toCharArray();

reader.close();

fbi(s, n);

}

private static String fbi(char[] s,int n) {

if (s.length == 1) {

switch (s[0]) {

case '1':

System.out.print("I");

return "I";

case '0':

System.out.print("B");

return "B";

default:

break;

}

char[] s1 = Arrays.copyOfRange(s, 0, s.length / 2);

String left = fbi(s1,n);

char[] s2 = Arrays.copyOfRange(s, s.length / 2, s.length);

String right = fbi(s2, n);

if (left.equals(right)) {

System.out.print(left);

return left;

} else {

System.out.print("F");

return "F";

}

[Java] 蓝桥杯ALGO-30 算法训练入学考试

问题描述
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入格式
第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出格式
包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
样例输入
70 3
71 100
69 1
1 2
样例输出
3
数据规模和约定
对于30%的数据，M <= 10；对于全部的数据，M <= 100。

package algo30;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        int m = in.nextInt();
        int[] dp = new int[t + 1];

        for (int i = 1; i <= m; i++) {
            int time = in.nextInt();
            int value = in.nextInt();
            for (int j = t; j >= time; j--) {
                dp[j] = Integer.max(dp[j], dp[j - time] + value);
            }
        }
        in.close();
        System.out.println(dp[t]);
    }

}

package algo30;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int t = in.nextInt();

int m = in.nextInt();

int[] dp = new int[t + 1];

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

int time = in.nextInt();

int value = in.nextInt();

for (int j = t; j >= time; j--) {

dp[j] = Integer.max(dp[j], dp[j - time] + value);

}

in.close();

System.out.println(dp[t]);

}

[Java] 蓝桥杯ALGO-39 算法训练数组排序去重

问题描述
输入10个整数组成的序列，要求对其进行升序排序，并去掉重复元素。
输入格式
10个整数。
输出格式
多行输出，每行一个元素。
样例输入
2 2 3 3 1 1 5 5 5 5
样例输出
1
2
3
5

package algo39;

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

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Set<Integer> set = new TreeSet<>();
        for (int i = 0; i < 10; i++) {
            set.add(in.nextInt());
        }
        in.close();
        for (int i : set) {
            System.out.println(i);
        }
    }
}

package algo39;

import java.util.Scanner;

import java.util.Set;

import java.util.TreeSet;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

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

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

set.add(in.nextInt());

}

in.close();

for (int i : set) {

System.out.println(i);

}

[Java] 蓝桥杯ALGO-43 算法训练 A+B Problem

问题描述
输入A,B。
输出A+B。
输入格式
输入包含两个整数A,B，用一个空格分隔。
输出格式
输出一个整数，表示A+B的值。
样例输入
5 8
样例输出
13
数据规模和约定
-1,000,000,000<=A,B<=1,000,000,000。

package algo43;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println(in.nextInt() + in.nextInt());
        in.close();
    }

}

package algo43;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

System.out.println(in.nextInt() + in.nextInt());

in.close();

}