Code – 第60页

[Java] 蓝桥杯ALGO-2 算法训练最大最小公倍数

问题描述
已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。
输入格式
输入一个正整数N。
输出格式
输出一个整数，表示你找到的最小公倍数。
样例输入
9
样例输出
504
数据规模与约定
1 <= N <= 106。

package algo2;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        
        Scanner in = new Scanner(System.in);

        long n = in.nextLong();
        in.close();

        if (n <= 2) {
            System.out.print(n);
            return;
        } 
        
        if (0 == n % 2) {
            // Even.
            if (0 != n % 3) {
                System.out.print((n * (n - 1) * (n - 3)));
            } else {
                System.out.print((n - 1) * (n - 2) * (n - 3));
            }
        } else {
            // Odd.
            System.out.print(n * (n - 1) * (n - 2));
        }
    }
}

package algo2;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

long n = in.nextLong();

in.close();

if (n <= 2) {

System.out.print(n);

return;

}

if (0 == n % 2) {

// Even.

if (0 != n % 3) {

System.out.print((n * (n - 1) * (n - 3)));

} else {

System.out.print((n - 1) * (n - 2) * (n - 3));

}

} else {

// Odd.

System.out.print(n * (n - 1) * (n - 2));

}

问题描述
有一棵 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的正整数。

package algo4;

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        dp = new int[n][2];
        final String[] valueString = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            dp[i][1] = Integer.parseInt(valueString[i]);
            v.add(new ArrayList<Integer>());
        }
        
        for (int i = 0; i < n - 1; i++) {
            final String[] ab = br.readLine().split(" ");
            int a = Integer.parseInt(ab[0]) - 1, b = Integer.parseInt(ab[1]) - 1;
            v.get(a).add(b);
            v.get(b).add(a);
        }
        br.close();
        dfs(0, -1);
        System.out.println(Math.max(dp[0][0], dp[0][1]));
    }
    
    private static void dfs(int root, int pre) {
        List<Integer> temp = v.get(root);
        for (int i = 0; i < temp.size(); i++) {
            if (temp.get(i) != pre) {
                dfs(temp.get(i), root);
                dp[root][1] += dp[temp.get(i)][0];
                dp[root][0] += Math.max(dp[temp.get(i)][0], dp[temp.get(i)][1]);
            }
        }
    }

    private static int[][] dp;
    private static List<List<Integer>> v = new ArrayList<>();
}

package algo4;

import java.io.*;

import java.util.*;

public class Main {

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

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

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

dp = new int[n][2];

final String[] valueString = br.readLine().split(" ");

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

dp[i][1] = Integer.parseInt(valueString[i]);

v.add(new ArrayList<Integer>());

}

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

final String[] ab = br.readLine().split(" ");

int a = Integer.parseInt(ab[0]) - 1, b = Integer.parseInt(ab[1]) - 1;

v.get(a).add(b);

v.get(b).add(a);

}

br.close();

dfs(0, -1);

System.out.println(Math.max(dp[0][0], dp[0][1]));

}

private static void dfs(int root, int pre) {

List<Integer> temp = v.get(root);

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

if (temp.get(i) != pre) {

dfs(temp.get(i), root);

dp[root][1] += dp[temp.get(i)][0];

dp[root][0] += Math.max(dp[temp.get(i)][0], dp[temp.get(i)][1]);

}

private static int[][] dp;

private static List<List<Integer>> v = new ArrayList<>();

}

[Java] 蓝桥杯ALGO-42 算法训练送分啦

问题描述
这题想得分吗？想，请输出“yes”；不想，请输出“no”。
输出格式
输出包括一行，为“yes”或“no”。

package algo42;

public class Main{
    public static void main(String[] args){
        System.out.println("yes");
    }
}

package algo42;

public class Main{

public static void main(String[] args){

System.out.println("yes");

}

[Java] 蓝桥杯ALGO-48 算法训练关联矩阵

问题描述
有一个n个结点m条边的有向图，请输出他的关联矩阵。
输入格式
第一行两个整数n、m，表示图中结点和边的数目。n<=100,m<=1000。
接下来m行，每行两个整数a、b，表示图中有(a,b)边。
注意图中可能含有重边，但不会有自环。
输出格式
输出该图的关联矩阵，注意请勿改变边和结点的顺序。
样例输入
5 9
1 2
3 1
1 5
2 5
2 3
2 3
3 2
4 3
5 4
样例输出
1 -1 1 0 0 0 0 0 0
-1 0 0 1 1 1 -1 0 0
0 1 0 0 -1 -1 1 -1 0
0 0 0 0 0 0 0 1 -1
0 0 -1 -1 0 0 0 0 1

package algo48;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int m = in.nextInt();

        int[][] matrix = new int[n + 1][m + 1];
        for (int i = 1; i <= m; i++) {
            int a = in.nextInt();
            int b = in.nextInt();

            matrix[a][i] = 1;
            matrix[b][i] = -1;
        }
        in.close();

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                System.out.print(matrix[i][j] + " ");
            }

            System.out.println();
        }
    }

}

package algo48;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int m = in.nextInt();

int[][] matrix = new int[n + 1][m + 1];

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

int a = in.nextInt();

int b = in.nextInt();

matrix[a][i] = 1;

matrix[b][i] = -1;

}

in.close();

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

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

System.out.print(matrix[i][j] + " ");

}

System.out.println();

}

[Java] 蓝桥杯ALGO-122 算法训练未名湖边的烦恼

问题描述
每年冬天，北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋，可是人太多了，每天下午收工后，常常一双冰鞋都不剩。
每天早上，租鞋窗口都会排起长龙，假设有还鞋的m个，有需要租鞋的n个。现在的问题是，这些人有多少种排法，可以避免出现体育组没有冰鞋可租的尴尬场面。（两个同样需求的人（比如都是租鞋或都是还鞋）交换位置是同一种排法）
输入格式
两个整数，表示m和n
输出格式
一个整数，表示队伍的排法的方案数。
样例输入
3 2
样例输出
5
数据规模和约定
m,n∈［0,18］

package algo122;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        in.close();
        System.out.println(f(m, n));
    }
    public static int f(int m, int n) {
        if (n > m) return 0; //借鞋的人比还鞋的人多，则无法组成组合
        if (n == 0) return 1; //没人借鞋，则就是一种排列   
        return f(m-1, n) + f(m, n-1); //第一个是借鞋的人 + 第一个是还鞋的人
    }
}

package algo122;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int m = in.nextInt();

int n = in.nextInt();

in.close();

System.out.println(f(m, n));

}

public static int f(int m, int n) {

if (n > m) return 0; //借鞋的人比还鞋的人多，则无法组成组合

if (n == 0) return 1; //没人借鞋，则就是一种排列

return f(m-1, n) + f(m, n-1); //第一个是借鞋的人 + 第一个是还鞋的人

}

[Java] 蓝桥杯ALGO-124 算法训练数字三角形

问题描述
（图３.１－１）示出了一个数字三角形。请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。
●每一步可沿左斜线向下或右斜线向下走；
●1＜三角形行数≤100；
●三角形中的数字为整数0，1，…99；

（图３.１－１）
输入格式
文件中首先读到的是三角形的行数。
接下来描述整个三角形
输出格式
最大总和（整数）
样例输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出
30

package algo124;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        
        int[][] triple = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i;j++) {
                triple[i][j] = in.nextInt();
            }
        }
        in.close();
        
        int[][] result = new int[n][n];
        int max = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) { if (i == 0) { result[i][j] = triple[i][j]; } else if (j == 0) { result[i][j] = result[i-1][j] + triple[i][j]; } else if (i == j){ result[i][j] = result[i-1][j-1] + triple[i][j]; } else { result[i][j] = Integer.max(result[i-1][j], result[i-1][j-1]) + triple[i][j]; } if (result[i][j] > max) {
                    max = result[i][j];
                }
            }
        }
        
        System.out.println(max);
    }
}

package algo124;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int[][] triple = new int[n][n];

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

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

triple[i][j] = in.nextInt();

}

in.close();

int[][] result = new int[n][n];

int max = 0;

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

for (int j = 0; j <= i; j++) { if (i == 0) { result[i][j] = triple[i][j]; } else if (j == 0) { result[i][j] = result[i-1][j] + triple[i][j]; } else if (i == j){ result[i][j] = result[i-1][j-1] + triple[i][j]; } else { result[i][j] = Integer.max(result[i-1][j], result[i-1][j-1]) + triple[i][j]; } if (result[i][j] > max) {

max = result[i][j];

}

System.out.println(max);

}

分类： Code

[Java] 蓝桥杯ALGO-2 算法训练最大最小公倍数

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

[Java] 蓝桥杯ALGO-42 算法训练送分啦

[Java] 蓝桥杯ALGO-48 算法训练关联矩阵

[Java] 蓝桥杯ALGO-122 算法训练未名湖边的烦恼

[Java] 蓝桥杯ALGO-124 算法训练数字三角形