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

[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;

}

问题描述
100 可以表示为带分数的形式：100 = 3 + 69258 / 714。
还可以表示为：100 = 82 + 3546 / 197。
注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。
类似这样的带分数，100 有 11 种表示法。
输入格式
从标准输入读入一个正整数N (N<1000*1000)
输出格式
程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。
注意：不要求输出每个表示，只统计有多少表示法！
样例输入1
100
样例输出1
11
样例输入2
105
样例输出2
6

分析: 用深度优先搜索，将1～9形成一个全排列，根据整数部分、分子和分母的长度来分割整个排列。设整数部分为a，分子为b，分母为c，这个数字的带分数形式就是a + (b / c)。a和b的长度是1～7，c的长度是由a和b来确定的，三个数字的总长度是9。最后验证a + (b / c)是否等于输入的数字。

package prev3;

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

public class Main {

    public static int cnt = 0, num = 0;
    public static boolean isVisit[] = new boolean[10];

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        num = Integer.parseInt(reader.readLine());
        reader.close();
        for (int i = 1; i <= 7; i++) {
            for (int j = 1; j <= 7; j++) { if (9 - i - j >= 1) {
                    dfs(0, 0, 0, i, j, 9 -i - j);
                }
            }
        }
        System.out.println(cnt);
    }

    public static void dfs(int a, int b, int c, int alen, int blen, int clen) {
        if (alen == 0 && 0 == blen && 0 == clen) {
            if (b % c == 0 && b / c == num - a) {
                cnt++;
            }
            return;
        }

        for (int i = 1; i < 10; i++) {
            if (!isVisit[i]) {
                isVisit[i] = true;
                if (0 < alen) {
                    dfs(a * 10 + i, b, c, alen - 1, blen, clen);
                } else if (0 < blen) {
                    dfs(a, b * 10 + i, c, alen, blen - 1, clen);
                } else if (0 < clen) {
                    dfs(a, b, c * 10 + i, alen, blen, clen - 1);
                }
                isVisit[i] = false;
            }
        }
    }
}

package prev3;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

public class Main {

public static int cnt = 0, num = 0;

public static boolean isVisit[] = new boolean[10];

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

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

num = Integer.parseInt(reader.readLine());

reader.close();

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

for (int j = 1; j <= 7; j++) { if (9 - i - j >= 1) {

dfs(0, 0, 0, i, j, 9 -i - j);

}

System.out.println(cnt);

}

public static void dfs(int a, int b, int c, int alen, int blen, int clen) {

if (alen == 0 && 0 == blen && 0 == clen) {

if (b % c == 0 && b / c == num - a) {

cnt++;

}

return;

}

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

if (!isVisit[i]) {

isVisit[i] = true;

if (0 < alen) {

dfs(a * 10 + i, b, c, alen - 1, blen, clen);

} else if (0 < blen) {

dfs(a, b * 10 + i, c, alen, blen - 1, clen);

} else if (0 < clen) {

dfs(a, b, c * 10 + i, alen, blen, clen - 1);

}

isVisit[i] = false;

}

[Java] 蓝桥杯PREV-5 历届试题错误票据

问题描述
某涉密单位下发了某种票据，并要在年终全部收回。
每张票据有唯一的ID号。全年所有票据的ID号是连续的，但ID的开始数码是随机选定的。
因为工作人员疏忽，在录入ID号的时候发生了一处错误，造成了某个ID断号，另外一个ID重号。
你的任务是通过编程，找出断号的ID和重号的ID。
假设断号不可能发生在最大和最小号。
输入格式
要求程序首先输入一个整数N(N<100)表示后面数据行数。
接着读入N行数据。
每行数据长度不等，是用空格分开的若干个（不大于100个）正整数（不大于100000），请注意行内和行末可能有多余的空格，你的程序需要能处理这些空格。
每个整数代表一个ID号。
输出格式
要求程序输出1行，含两个整数m n，用空格分隔。
其中，m表示断号ID，n表示重号ID
样例输入1
2
5 6 8 11 9
10 12 9
样例输出1
7 9
样例输入2
6
164 178 108 109 180 155 141 159 104 182 179 118 137 184 115 124 125 129 168 196
172 189 127 107 112 192 103 131 133 169 158
128 102 110 148 139 157 140 195 197
185 152 135 106 123 173 122 136 174 191 145 116 151 143 175 120 161 134 162 190
149 138 142 146 199 126 165 156 153 193 144 166 170 121 171 132 101 194 187 188
113 130 176 154 177 120 117 150 114 183 186 181 100 163 160 167 147 198 111 119
样例输出2
105 120

package prev5;

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();

        int min = 100000;
        int max = 0;
        int[] corrent = new int[100000];
        for (int i = 0; i < n; i++) {
            String[] id = in.nextLine().split(" ");

            for (int j = 0; j < id.length; j++) {
                if (!id[j].equals("")) {
                    int num = Integer.parseInt(id[j]);
                    corrent[num]++;

                    if (num < min) {
                        min = num;
                    }

                    if (max < num) {
                        max = num;
                    }
                }
            }
        }

        int dupilcate = 0, emp = 0;
        for (int i = min; i <= max; i++) {
            if (corrent[i] == 0) {
                emp = i;
            } else if (corrent[i] == 2) {
                dupilcate = i;
            }
        }

        System.out.println(emp + " " + dupilcate);
        in.close();
    }

}

package prev5;

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();

int min = 100000;

int max = 0;

int[] corrent = new int[100000];

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

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

for (int j = 0; j < id.length; j++) {

if (!id[j].equals("")) {

int num = Integer.parseInt(id[j]);

corrent[num]++;

if (num < min) {

min = num;

}

if (max < num) {

max = num;

}

int dupilcate = 0, emp = 0;

for (int i = min; i <= max; i++) {

if (corrent[i] == 0) {

emp = i;

} else if (corrent[i] == 2) {

dupilcate = i;

}

System.out.println(emp + " " + dupilcate);

in.close();

}

[Java] 蓝桥杯PREV-8 历届试题买不到的数目

问题描述
小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。
小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。
你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。
本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。
输入格式
两个正整数，表示每种包装中糖的颗数(都不多于1000)
输出格式
一个正整数，表示最大不能买到的糖数
样例输入1
4 7
样例输出1
17
样例输入2
3 5
样例输出2
7

package prev8;

import java.util.Scanner;

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

        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        in.close();
        boolean[] p = new boolean[a * a + b * b + 1];
        for (int i = 0; i <= b; i++) {
            for (int j = 0; j <= a; j++) {
                p[i * a + b * j] = true;
            }
        }

        for (int i = p.length - 1; i >= 0; i--) {
            if (p[i] == false && i <= a * b) {
                System.out.println(i);
                return;
            }
        }
    }
}

package prev8;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int a = in.nextInt();

int b = in.nextInt();

in.close();

boolean[] p = new boolean[a * a + b * b + 1];

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

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

p[i * a + b * j] = true;

}

for (int i = p.length - 1; i >= 0; i--) {

if (p[i] == false && i <= a * b) {

System.out.println(i);

return;

}

[Java] 蓝桥杯PREV-33 历届试题兰顿蚂蚁

问题描述

兰顿蚂蚁，是于1986年，由克里斯·兰顿提出来的，属于细胞自动机的一种。

平面上的正方形格子被填上黑色或白色。在其中一格正方形内有一只“蚂蚁”。
蚂蚁的头部朝向为：上下左右其中一方。

蚂蚁的移动规则十分简单：
若蚂蚁在黑格，右转90度，将该格改为白格，并向前移一格；
若蚂蚁在白格，左转90度，将该格改为黑格，并向前移一格。

规则虽然简单，蚂蚁的行为却十分复杂。刚刚开始时留下的路线都会有接近对称，像是会重复，但不论起始状态如何，蚂蚁经过漫长的混乱活动后，会开辟出一条规则的“高速公路”。

蚂蚁的路线是很难事先预测的。

你的任务是根据初始状态，用计算机模拟兰顿蚂蚁在第n步行走后所处的位置。
输入格式
输入数据的第一行是 m n 两个整数（3 < m, n < 100），表示正方形格子的行数和列数。
接下来是 m 行数据。
每行数据为 n 个被空格分开的数字。0 表示白格，1 表示黑格。

接下来是一行数据：x y s k, 其中x y为整数，表示蚂蚁所在行号和列号（行号从上到下增长，列号从左到右增长，都是从0开始编号）。s 是一个大写字母，表示蚂蚁头的朝向，我们约定：上下左右分别用：UDLR表示。k 表示蚂蚁走的步数。
输出格式
输出数据为两个空格分开的整数 p q, 分别表示蚂蚁在k步后，所处格子的行号和列号。
样例输入
5 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
2 3 L 5
样例输出
1 3
样例输入
3 3
0 0 0
1 1 1
1 1 1
1 1 U 6
样例输出
0 0

package prev33;

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();
        
        final int BLACK = 1;
        final int WHITE = 0;
        
        int[][] maxtrix = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                maxtrix[i][j] = in.nextInt();
            }
        }
        
        int x = in.nextInt();
        int y = in.nextInt();
        String s = in.next();
        int k = in.nextInt();
        in.close();
        
        for (int i = 0; i < k; i++) {
            if (s.equals("U")) {
                if (maxtrix[x][y] == BLACK) {
                    s = "R";
                    maxtrix[x][y] = WHITE;
                    y++;
                } else if (maxtrix[x][y] == WHITE) {
                    s = "L";
                    maxtrix[x][y] = BLACK;
                    y--;
                } else {
                    System.out.println("Are your square crack?");
                }
            } else if (s.equals("D")) {
                if (maxtrix[x][y] == BLACK) {
                    s = "L";
                    maxtrix[x][y] = WHITE;
                    y--;
                } else if (maxtrix[x][y] == WHITE) {
                    s = "R";
                    maxtrix[x][y] = BLACK;
                    y++;
                } else {
                    System.out.println("Are your square crack?");
                }
            } else if (s.equals("L")) {
                if (maxtrix[x][y] == BLACK) {
                    s = "U";
                    maxtrix[x][y] = WHITE;
                    x--;
                } else if (maxtrix[x][y] == WHITE) {
                    s = "D";
                    maxtrix[x][y] = BLACK;
                    x++;
                } else {
                    System.out.println("Are your square crack?");
                }
            } else if (s.equals("R")) {
                if (maxtrix[x][y] == BLACK) {
                    s = "D";
                    maxtrix[x][y] = WHITE;
                    x++;
                } else if (maxtrix[x][y] == WHITE) {
                    s = "U";
                    maxtrix[x][y] = BLACK;
                    x--;
                } else {
                    System.out.println("Are your square crack?");
                }
            } else {
                System.out.println("Your direction have some errors.");
            }
            
//            print(maxtrix, m, n);
        }
        
        System.out.println(x + " " + y);
    }
    
    public static void print(int[][] maxtrix, int m, int n) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(maxtrix[i][j] + " ");
            }
            
            System.out.println();
        }
    }
}

package prev33;

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();

final int BLACK = 1;

final int WHITE = 0;

int[][] maxtrix = new int[m][n];

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

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

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

}

int x = in.nextInt();

int y = in.nextInt();

String s = in.next();

int k = in.nextInt();

in.close();

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

if (s.equals("U")) {

if (maxtrix[x][y] == BLACK) {

s = "R";

maxtrix[x][y] = WHITE;

y++;

} else if (maxtrix[x][y] == WHITE) {

s = "L";

maxtrix[x][y] = BLACK;

y--;

} else {

System.out.println("Are your square crack?");

}

} else if (s.equals("D")) {

if (maxtrix[x][y] == BLACK) {

s = "L";

maxtrix[x][y] = WHITE;

y--;

} else if (maxtrix[x][y] == WHITE) {

s = "R";

maxtrix[x][y] = BLACK;

y++;

} else {

System.out.println("Are your square crack?");

}

} else if (s.equals("L")) {

if (maxtrix[x][y] == BLACK) {

s = "U";

maxtrix[x][y] = WHITE;

x--;

} else if (maxtrix[x][y] == WHITE) {

s = "D";

maxtrix[x][y] = BLACK;

x++;

} else {

System.out.println("Are your square crack?");

}

} else if (s.equals("R")) {

if (maxtrix[x][y] == BLACK) {

s = "D";

maxtrix[x][y] = WHITE;

x++;

} else if (maxtrix[x][y] == WHITE) {

s = "U";

maxtrix[x][y] = BLACK;

x--;

} else {

System.out.println("Are your square crack?");

}

} else {

System.out.println("Your direction have some errors.");

}

// print(maxtrix, m, n);

}

System.out.println(x + " " + y);

}

public static void print(int[][] maxtrix, int m, int n) {

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

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

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

}

System.out.println();

}

[Java] 蓝桥杯ADV-65 算法提高格子位置

问题描述
输入三个自然数N，i，j （1<=i<=N，1<=j<=N），输出在一个N*N格的棋盘中，与格子（i，j）同行、同列、同一对角线的所有格子的位置。
输入格式
输入共三行，分别输入自然数N，i，j。其中保证N<=24且1<=i<=N，1<=j<=N。
输出格式
输出共四行。第一行为与格子（i，j）同行的所有格子的位置，第二行为与格子（i，j）同列的所有格子的位置，第三行为从左上到右下对角线上的格子的位置，第四行为从左下到右上对角线上的格子的位置。
样例输入
4
2
3
样例输出
(2,1) (2,2) (2,3) (2,4)
(1,3) (2,3) (3,3) (4,3)
(1,2) (2,3) (3,4)
(4,1) (3,2) (2,3) (1,4)
输入输出样例解释
n=4，i=2，j=3表示了棋盘中的第二行第三列的格子，如下图：

第1列第2列第3列第4列
第1行
(2,3) 第2行
第3行
第4行
(2,1) (2,2) (2,3) (2,4) {同一行上格子的位置}
(1,3) (2,3) (3,3) (4,3) {同列列上格子的位置}
(1,2) (2,3) (3,4) {左上到右下对角线上的格子的位置}
(4,1) (3,2) (2,3) (1,4) {左下到右上对角线上的格子的位置}

package adv65;

import java.util.Scanner;

public class Main {

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

        for (int p = 1; p <= n; p++) {
            System.out.print("(" + i + "," + p + ")");
        }
        System.out.println();

        for (int p = 1; p <= n; p++) {
            System.out.print("(" + p + "," + j + ")");
        }
        System.out.println();
        
        for (int p = 1; p <= n; p++) {
            for (int q = 1; q <= n; q++) {
                if (q - p == j - i) {
                    System.out.print("(" + p + "," + q + ")");
                }
            }
        }
        System.out.println();
        
        for (int p = 1; p <= n; p++) {
            for (int q = 1; q <= n; q++) {
                if (q + p == j + i) {
                    System.out.print("(" + q + "," + p + ")");
                }
            }
        }
    }

}

package adv65;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int i = in.nextInt();

int j = in.nextInt();

in.close();

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

System.out.print("(" + i + "," + p + ")");

}

System.out.println();

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

System.out.print("(" + p + "," + j + ")");

}

System.out.println();

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

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

if (q - p == j - i) {

System.out.print("(" + p + "," + q + ")");

}

System.out.println();

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

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

if (q + p == j + i) {

System.out.print("(" + q + "," + p + ")");

}