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

[Java] 蓝桥杯BASIC-27 基础练习 2n皇后问题

问题描述
给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。
输入格式
输入的第一行为一个整数n，表示棋盘的大小。
接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。
输出格式
输出一个整数，表示总共有多少种放法。
样例输入
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
2
样例输入
4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
0

package base27;

import java.util.Scanner;

public class Main {
    static int count = 0;
    static int n;
    static int[] w_place;
    static int[] b_place;
    static int[][] a;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        a = new int[n][n];
        w_place = new int[n];
        b_place = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                a[i][j] = in.nextInt();
            }
        }
        backTrace(0);
        //双回溯

        System.out.println(count);
    }

    private static void backTrace(int i) {//m为从上到下递增的行数 w为左到右的列
        if (i > n - 1) {
            count++;
            return;
        }
        for (int w = 0; w < n; w++) {
            if (check_w(i, w)) {
                w_place[i] = w;
                a[i][w] = 0;
                for (int b = 0; b < n; b++) {
                    if (check_b(i, b)) {
                        b_place[i] = b;
                        a[i][b] = 0;
                        backTrace(i + 1);
                        a[i][b] = 1;
                    }

                }
                a[i][w] = 1;
            }
        }

    }

    private static boolean check_w(int i, int j) {
        if (a[i][j] == 0)
            return false;
        for (int k = 0; k < i; k++) {
            if (w_place[k] == j || Math.abs(i - k) == Math.abs(w_place[k] - j))
                return false;
        }
        return true;
    }

    private static boolean check_b(int i, int j) {
        if (a[i][j] == 0)
            return false;
        for (int k = 0; k < i; k++) {
            if (b_place[k] == j || Math.abs(i - k) == Math.abs(b_place[k] - j))
                return false;
        }
        return true;
    }
}

package base27;

import java.util.Scanner;

public class Main {

static int count = 0;

static int n;

static int[] w_place;

static int[] b_place;

static int[][] a;

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

n = in.nextInt();

a = new int[n][n];

w_place = new int[n];

b_place = new int[n];

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

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

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

}

backTrace(0);

//双回溯

System.out.println(count);

}

private static void backTrace(int i) {//m为从上到下递增的行数 w为左到右的列

if (i > n - 1) {

count++;

return;

}

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

if (check_w(i, w)) {

w_place[i] = w;

a[i][w] = 0;

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

if (check_b(i, b)) {

b_place[i] = b;

a[i][b] = 0;

backTrace(i + 1);

a[i][b] = 1;

}

a[i][w] = 1;

}

private static boolean check_w(int i, int j) {

if (a[i][j] == 0)

return false;

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

if (w_place[k] == j || Math.abs(i - k) == Math.abs(w_place[k] - j))

return false;

}

return true;

}

private static boolean check_b(int i, int j) {

if (a[i][j] == 0)

return false;

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

if (b_place[k] == j || Math.abs(i - k) == Math.abs(b_place[k] - j))

return false;

}

return true;

}

[Java] 蓝桥杯BASIC-28 基础练习 Huffuman树

问题描述
Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。
给出一列数{pi}={p0, p1, …, pn-1}，用这列数构造Huffman树的过程如下：
1. 找到{pi}中最小的两个数，设为pa和pb，将pa和pb从{pi}中删除掉，然后将它们的和加入到{pi}中。这个过程的费用记为pa + pb。
2. 重复步骤1，直到{pi}中只剩下一个数。
在上面的操作过程中，把所有的费用相加，就得到了构造Huffman树的总费用。
本题任务：对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。

例如，对于数列{pi}={5, 3, 8, 2, 9}，Huffman树的构造过程如下：
1. 找到{5, 3, 8, 2, 9}中最小的两个数，分别是2和3，从{pi}中删除它们并将和5加入，得到{5, 8, 9, 5}，费用为5。
2. 找到{5, 8, 9, 5}中最小的两个数，分别是5和5，从{pi}中删除它们并将和10加入，得到{8, 9, 10}，费用为10。
3. 找到{8, 9, 10}中最小的两个数，分别是8和9，从{pi}中删除它们并将和17加入，得到{10, 17}，费用为17。
4. 找到{10, 17}中最小的两个数，分别是10和17，从{pi}中删除它们并将和27加入，得到{27}，费用为27。
5. 现在，数列中只剩下一个数27，构造过程结束，总费用为5+10+17+27=59。
输入格式
输入的第一行包含一个正整数n（n<=100）。
接下来是n个正整数，表示p0, p1, …, pn-1，每个数不超过1000。
输出格式
输出用这些数构造Huffman树的总费用。
样例输入
5
5 3 8 2 9
样例输出
59

package base28;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < n; i++) {
            list.add(in.nextInt());
        }
        int sum = 0;
        Collections.sort(list);
        int s = list.size();
        while (s >= 2) {
            int temp = list.get(0) + list.get(1);
            list.remove(0);
            list.remove(0);
            sum += temp;
            list.add(temp);
            Collections.sort(list);
            s = list.size();
        }
        System.out.println(sum);
    }
}

package base28;

import java.util.ArrayList;

import java.util.Collections;

import java.util.Comparator;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int n = in.nextInt();

ArrayList<Integer> list = new ArrayList<Integer>();

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

list.add(in.nextInt());

}

int sum = 0;

Collections.sort(list);

int s = list.size();

while (s >= 2) {

int temp = list.get(0) + list.get(1);

list.remove(0);

sum += temp;

list.add(temp);

Collections.sort(list);

s = list.size();

}

System.out.println(sum);

}

[Java] 蓝桥杯BASIC-29 基础练习高精度加法

问题描述
输入两个整数a和b，输出这两个整数的和。a和b都不超过100位。
算法描述
由于a和b都比较大，所以不能直接使用语言中的标准数据类型来存储。对于这种问题，一般使用数组来处理。
定义一个数组A，A[0]用于存储a的个位，A[1]用于存储a的十位，依此类推。同样可以用一个数组B来存储b。
计算c = a + b的时候，首先将A[0]与B[0]相加，如果有进位产生，则把进位（即和的十位数）存入r，把和的个位数存入C[0]，即C[0]等于(A[0]+B[0])%10。然后计算A[1]与B[1]相加，这时还应将低位进上来的值r也加起来，即C[1]应该是A[1]、B[1]和r三个数的和．如果又有进位产生，则仍可将新的进位存入到r中，和的个位存到C[1]中。依此类推，即可求出C的所有位。
最后将C输出即可。
输入格式
输入包括两行，第一行为一个非负整数a，第二行为一个非负整数b。两个整数都不超过100位，两数的最高位都不是0。
输出格式
输出一行，表示a + b的值。
样例输入
20100122201001221234567890
2010012220100122
样例输出
20100122203011233454668012

package base29;

import java.util.Scanner;

public class Main {
    static final int MAX = 101;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] a = in.nextLine().toCharArray();
        char[] b = in.nextLine().toCharArray();
        in.close();
        int count = a.length > b.length ? b.length : a.length;
        int[] x = new int[MAX];
        int[] y = new int[MAX];
        int[] z = new int[MAX];
        for (int i = a.length - 1, j = 0; i >= 0; i--, j++) {
            x[j] = (a[i] - '0') > 0 ? a[i] - '0' : 0;
        }
        for (int i = b.length - 1, j = 0; i >= 0; i--, j++) {
            y[j] = (b[i] - '0') > 0 ? b[i] - '0' : 0;//不知道为什么会出现负数。。。。。
        }

        int r = 0;
        for (int i = 0; i < MAX; i++) {
            z[i] = x[i] + y[i] + r;
            r = z[i] / 10;
            z[i] %= 10;
        }

        r = MAX - 1;
        while (z[r] == 0) --r;
        while (r >= 0) {
            System.out.print(z[r]);
            r--;
        }


    }
}

package base29;

import java.util.Scanner;

public class Main {

static final int MAX = 101;

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

char[] a = in.nextLine().toCharArray();

char[] b = in.nextLine().toCharArray();

in.close();

int count = a.length > b.length ? b.length : a.length;

int[] x = new int[MAX];

int[] y = new int[MAX];

int[] z = new int[MAX];

for (int i = a.length - 1, j = 0; i >= 0; i--, j++) {

x[j] = (a[i] - '0') > 0 ? a[i] - '0' : 0;

}

for (int i = b.length - 1, j = 0; i >= 0; i--, j++) {

y[j] = (b[i] - '0') > 0 ? b[i] - '0' : 0;//不知道为什么会出现负数。。。。。

}

int r = 0;

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

z[i] = x[i] + y[i] + r;

r = z[i] / 10;

z[i] %= 10;

}

r = MAX - 1;

while (z[r] == 0) --r;

while (r >= 0) {

System.out.print(z[r]);

r--;

}

[Java] 蓝桥杯BASIC-30 基础练习阶乘计算

问题描述
输入一个正整数n，输出n!的值。
其中n!=1*2*3*…*n。
算法描述
n!可能很大，而计算机能表示的整数范围有限，需要使用高精度计算的方法。使用一个数组A来表示一个大整数a，A[0]表示a的个位，A[1]表示a的十位，依次类推。
将a乘以一个整数k变为将数组A的每一个元素都乘以k，请注意处理相应的进位。
首先将a设为1，然后乘2，乘3，当乘到n时，即得到了n!的值。
输入格式
输入包含一个正整数n，n<=1000。
输出格式
输出n!的准确值。
样例输入
10
样例输出
3628800

package base30;

import java.util.Scanner;

public class Main {
    static final int MAX = 10000;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.close();
        int[] A = new int[MAX + 1];
        for (int i = 0; i < A.length; i++) {
            A[i] = 0;
        }
        A[0] = 1;
        int r = 0;
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < MAX; j++) {
                int temp = A[j] * i + r;
                r = temp / 10;
                A[j] = temp % 10;
            }
        }

        int m = MAX;
        while (A[m--] == 0 && m >= 0) ;
        for (int i = m + 1; i >= 0; i--) {
            System.out.print(A[i]);
        }
    }
}

package base30;

import java.util.Scanner;

public class Main {

static final int MAX = 10000;

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int n = in.nextInt();

in.close();

int[] A = new int[MAX + 1];

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

A[i] = 0;

}

A[0] = 1;

int r = 0;

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

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

int temp = A[j] * i + r;

r = temp / 10;

A[j] = temp % 10;

}

int m = MAX;

while (A[m--] == 0 && m >= 0) ;

for (int i = m + 1; i >= 0; i--) {

System.out.print(A[i]);

}

[Java] 蓝桥杯BASIC-11 基础练习十六进制转十进制

问题描述
从键盘输入一个不超过8位的正的十六进制数字符串，将它转换为正的十进制数后输出。
注：十六进制数中的10~15分别用大写的英文字母A、B、C、D、E、F表示。
样例输入
FFFF
样例输出
65535

package base11;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        char[] str;
        long sum = 0;
        Scanner in = new Scanner(System.in);
        str = in.next().toCharArray();
        in.close();
        for (int i = 0; i < str.length; i++) {
            if (str[i] >= 'A' && str[i] <= 'F') {
                sum = sum * 16 + str[i] - 'A' + 10;
            } else {
                sum = sum * 16 + str[i] - '0';
            }
        }
        System.out.println(sum);
    }
}

package base11;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

char[] str;

long sum = 0;

Scanner in = new Scanner(System.in);

str = in.next().toCharArray();

in.close();

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

if (str[i] >= 'A' && str[i] <= 'F') {

sum = sum * 16 + str[i] - 'A' + 10;

} else {

sum = sum * 16 + str[i] - '0';

}

System.out.println(sum);

}

[Java] 蓝桥杯BASIC-13 基础练习数列排序

问题描述
给定一个长度为n的数列，将这个数列按从小到大的顺序排列。1<=n<=200
输入格式
第一行为一个整数n。
第二行包含n个整数，为待排序的数，每个整数的绝对值小于10000。
输出格式
输出一行，按从小到大的顺序输出排序后的数列。
样例输入
5
8 3 6 4 9
样例输出
3 4 6 8 9

package base13;

import java.util.Scanner;

//快速排序
public class Main {
    public static void main(String[] args) {
        int[] nums = new int[200];
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        in.close();
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
        }
        qickSort(nums, 0, n - 1);
        for (int i = 0; i < n; i++) {
            System.out.println(nums[i]);
        }
    }

    //快速排序
    private static void qickSort(int[] a, int l, int h) {
        if (h > l) {
            int p = sort(a, l, h);
            qickSort(a, l, p - 1);
            qickSort(a, p + 1, h);
        }
    }

    private static int sort(int[] a, int l, int h) {
        int x = a[l], i = l, j = h + 1;
        while (true) {
            while (x > a[++i]) ;
            while (x < a[--j]) ;
            if (i > j) {
                break;
            }
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
        a[l] = a[j];
        a[j] = x;
        return j;
    }

}

package base13;

import java.util.Scanner;

//快速排序

public class Main {

public static void main(String[] args) {

int[] nums = new int[200];

Scanner in = new Scanner(System.in);

int n = in.nextInt();

in.nextLine();

in.close();

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

nums[i] = in.nextInt();

}

qickSort(nums, 0, n - 1);

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

System.out.println(nums[i]);

}

//快速排序

private static void qickSort(int[] a, int l, int h) {

if (h > l) {

int p = sort(a, l, h);

qickSort(a, l, p - 1);

qickSort(a, p + 1, h);

}

private static int sort(int[] a, int l, int h) {

int x = a[l], i = l, j = h + 1;

while (true) {

while (x > a[++i]) ;

while (x < a[--j]) ;

if (i > j) {

break;

}

int temp = a[i];

a[i] = a[j];

a[j] = temp;

}

a[l] = a[j];

a[j] = x;

return j;

}