更新日志

5.22

试题E：路径，添加了Dijkstra算法，秒出答案

2.21

抱着开摆的心态先来试试题目难度

试题 A: ASC（5分）

已知大写字母 A 的 ASCII 码为 65，请问大写字母 L 的 ASCII 码是多少？

答案： 76

1
2
3
4
5
6
public class Main {
    public static void main(String[] args) {
        System.out.println((int)'L');
    }
}

试题 B: 卡片（5分）

小蓝有很多数字卡片，每张卡片上都是数字 0 到 9。

小蓝准备用这些卡片来拼一些数，他想从 1 开始拼出正整数，每拼一个， 就保存起来，卡片就不能用来拼其它数了。

小蓝想知道自己能从 1 拼到多少。

例如，当小蓝有 30 张卡片，其中 0 到 9 各 3 张，则小蓝可以拼出 1 到 10， 但是拼 11 时卡片 1 已经只有一张了，不够拼出 11。

现在小蓝手里有 0 到 9 的卡片各 2021 张，共 20210 张，请问小蓝可以从 1 拼到多少？

答案： 3181

思路

思路是哈希
模拟一遍这个流程就好了
创建一个长度为10的数组 将数组中的每个元素初始化为2021 代表0~9 总共十种卡片 每种有2021张
然后将数字转化成字符串 字符串再转化成字符数组 遍历字符数组 将每个字符对应的卡片张数-1
当遍历完某个数字之后 卡片张数变为负数 则当前数字无法拼出来 输出当前数字的上一个数字即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] cards = new int[10];
        Arrays.fill(cards, 2021);
        int num = 1;
        boolean flag = true;
        while (flag) {
            String str = num + "";
            char[] c = str.toCharArray();
            for (char ch : c) {
                cards[ch - '0'] -= 1;
                if (cards[ch - '0'] < 0) {
                    System.out.println(num - 1);
                    flag = false;
                    break;
                }
            }
            num++;
        }
    }
}

试题 C: 直线（10分）

在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上， 那么这些点中任意两点确定的直线是同一条。

给定平面上 2 × 3 个整点 {(x, y)|0 ≤ x < 2, 0 ≤ y < 3, x ∈ Z, y ∈ Z}，即横坐标 是 0 到 1 (包含 0 和 1) 之间的整数、纵坐标是 0 到 2 (包含 0 和 2) 之间的整数 的点。这些点一共确定了 11 条不同的直线。

给定平面上 20 × 21 个整点 {(x, y)|0 ≤ x < 20, 0 ≤ y < 21, x ∈ Z, y ∈ Z}，即横 坐标是 0 到 19 (包含 0 和 19) 之间的整数、纵坐标是 0 到 20 (包含 0 和 20) 之 间的整数的点。请问这些点一共确定了多少条不同的直线。

答案： 40257

思路

直线的斜截式 y=kx+b 只要每条直线的k和b不同 那就不是同一条直线
由于涉及到小数问题 直接比较大小会出错 这里我才用保留八位有效数字
浮点数比较大小 只要差值小于1e-8 即可认为相等
新建一个Fx类和Point类
Point类用来存放每一个点，遍历Point集合，将任意两点组成直线的k和b计算出来，并存入res集合
Fx类用来记录每两个点产生直线的k和b 并将它存入sdt集合中去重 平行于X轴和Y轴的单独处理 最后加上就行

HashSet去重：先判断hashCode（）是否相同，相同才会判断equals()
如果是需要对我们自定义的对象去重，就需要我们重写 hashCode 和 equals 方法
注意：HashSet要求放入的对象必须重写hashCode(),不然HashSet调用默认的hashCode方法判断对象的地址，不等就达不到想根据对象的值去重的目的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import java.text.DecimalFormat;
import java.util.*;

class Solution {
    public static void main(String[] args) {
        ArrayList<Point> points = new ArrayList<>();
        for (int i = 0; i < 20; i++) {
            for (int j = 0; j < 21; j++) {
                points.add(new Point(i, j));
            }
        }
        HashSet<Fx> set = new HashSet<>();
        for (Point p1 : points) {
            for (Point p2 : points) {
                if (p1.x != p2.x && p1.y != p2.y){
                    double k = (p1.y - p2.y) / (p1.x - p2.x);
                    double b = p1.y - k * p1.x;
                    set.add(new Fx(k, b));
                }
            }
        }
        System.out.println(set.size() + 20 + 21);
    }
}

class Point {
    double x;
    double y;

    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }
}

class Fx {
    double k;
    double b;

    public Fx(double k, double b) {
        DecimalFormat df = new DecimalFormat("0.00000000");
        this.k = Double.parseDouble(df.format(k));
        this.b = Double.parseDouble(df.format(b));
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Fx)) return false;
        Fx fx = (Fx) o;
        return Double.compare(fx.k, k) == 0 && Double.compare(fx.b, b) == 0;
    }

    @Override
    public int hashCode() {
        return Objects.hash(k, b);
    }
}

试题 D: 货物摆放（10分）

小蓝有一个超大的仓库，可以摆放很多货物。

现在，小蓝有 n 箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝 规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、 宽、高。 小蓝希望所有的货物最终摆成一个大的立方体。即在长、宽、高的方向上 分别堆 L、W、H 的货物，满足 n = L × W × H。

给定 n，请问有多少种堆放货物的方案满足要求。 例如，当 n = 4 时，有以下 6 种方案：1×1×4、1×2×2、1×4×1、2×1×2、 2 × 2 × 1、4 × 1 × 1。

请问，当 n = 2021041820210418 （注意有 16 位数字）时，总共有多少种方案？

答案： 2430

思路

计算出因数然后无脑暴力三重循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.HashSet;

public class Main {
    public static void main(String[] args) {
        long num = 2021041820210418L;
        HashSet<Long> set = new HashSet<>();
        for (long i = 1; i < Math.sqrt(num); i++) {
            if (num % i == 0) {
                set.add(i);
                set.add(num / i);
            }
        }
        int res = 0;
        for (long a : set)
            for (long b : set)
                for (long c : set)
                    if (a * b * c == num)
                        res++;
        System.out.println(res);
    }
}

试题 E: 路径（15分）

小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图 中的最短路径。

小蓝的图由 2021 个结点组成，依次编号 1 至 2021。

对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点 之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。

例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无 向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。

请计算，结点 1 和结点 2021 之间的最短路径长度是多少。

**答案：**10266387

思路

先按题目要求建图，将所有节点初始化为0x3f3f3f3f
(0x3f3f3f3f的十进制是1061109567,是10^9级别的,而一般场合下的数据都是小于10^9的,所以它可以作为无穷大使用)
两个节点的绝对值小于等于21 则求最小公倍数
最小公倍数公式 lcm = a * b / (gcd(a, b))
lcm是最小公倍数 gcd是最大公约数
欧几里得法求最大公约数 gcd(a, b) = gcd(b, a % b)
然后用弗洛伊德算法 求最短路径即可
(时间复杂度n^3 仅限填空题可以用用 编程题还是要用迪杰斯特拉算法)

心里默念了一下，大概算了10秒…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Main {
    static int[][] arr = new int[2030][2030];

    static void Floyd() {
        for (int k = 1; k <= 2021; k++)
            for (int i = 1; i <= 2021; i++)
                for (int j = 1; j <= 2021; j++)
                    if (arr[i][j] > arr[i][k] + arr[k][j])
                        arr[i][j] = arr[i][k] + arr[k][j];
    }

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public static void main(String[] args) {
        for (int i = 1; i <= 2021; i++) {
            for (int j = 1; j <= 2021; j++) {
                if (Math.abs(i - j) <= 21)
                    arr[i][j] = i * j / gcd(i, j);
                else arr[i][j] = 0x3f3f3f3f;
            }
        }
        Floyd();
        System.out.println(arr[1][2021]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.Arrays;

public class Main {
    static int[] dist = new int[2030];
    static int[][] graph = new int[2030][2030];
    static boolean[] used = new boolean[2030];

    static int Dijkstra() {
        for (int i = 1; i <= 2021; i++) {
            int minIndex = -1;
            for (int j = 1; j <= 2021; j++)
                if (!used[j] && (minIndex == -1 ||dist[j] < dist[minIndex]))
                    minIndex = j;
            used[minIndex] = true;
            for (int j = 1; j <= 2021; j++) {
                dist[j] = Math.min(dist[j], dist[minIndex] + graph[minIndex][j]);
            }
        }
        return dist[2021];
    }

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public static void main(String[] args) {
        Arrays.fill(dist, 0x3f3f3f3f);
        dist[1] = 0;
        for (int i = 1; i <= 2021; i++) {
            for (int j = 1; j <= 2021; j++) {
                if (Math.abs(i - j) <= 21)
                    graph[i][j] = i * j / gcd(i, j);
                else graph[i][j] = 0x3f3f3f3f;
            }
        }
        System.out.println(Dijkstra());
    }
}

试题 F: 时间限制（15分）

小蓝要和朋友合作开发一个时间显示的网站。在服务器上，朋友已经获取 了当前的时间，用一个整数表示，值为从 1970 年 1 月 1 日 00:00:00 到当前时 刻经过的毫秒数。

现在，小蓝要在客户端显示出这个时间。小蓝不用显示出年月日，只需要 显示出时分秒即可，毫秒也不用显示，直接舍去即可。

给定一个用整数表示的时间，请将这个时间对应的时分秒输出。

输入格式

输入一行包含一个整数，表示时间。

输出格式

输出时分秒表示的当前时间，格式形如 HH:MM:SS，其中 HH 表示时，值 为 0 到 23，MM 表示分，值为 0 到 59，SS 表示秒，值为 0 到 59。时、分、秒 不足两位时补前导 0。

样例输入 1

46800999

样例输出 1

13:00:00

样例输入 2

1618708103123

样例输出 2

01:08:23

评测用例规模与约定

对于所有评测用例，给定的时间为不超过10^18的正整数。

代码

1
2
3
4
5
6
7
8
9
10
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        long time = scan.nextLong();
        time = time / 1000 % (24 * 60 * 60);
        System.out.printf("%02d:%02d:%02d", time / 3600, time / 60 % 60, time % 60);
    }
}

试题 G: 砝码称重（20分）

你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1,W2,⋅⋅⋅,WN。

请你计算一共可以称出多少种不同的正整数重量？

注意砝码可以放在天平两边。

输入格式

输入的第一行包含一个整数 N。

第二行包含 N 个整数：W1,W2,W3,⋅⋅⋅,WN。

输出格式

输出一个整数代表答案。

输入样例：

3

1 4 6

输出样例：

10

样例解释

能称出的 10 种重量是：1、2、3、4、5、6、7、9、10、11。
1 = 1；

2 = 6 − 4 (天平一边放 6，另一边放 4)；

3 = 4 − 1；

4 = 4；

5 = 6 − 1；

6 = 6；

7 = 1 + 6；

9 = 4 + 6 − 1；

10 = 4 + 6；

11 = 1 + 4 + 6。

数据范围

对于 50% 的评测用例，1≤N≤15。

对于所有评测用例，1≤N≤100，N 个砝码总重不超过 100000。

思路

网上看别的题解都用的是dp，我这里有个不用dp的方法
建立一个set集合 用来去重
我们先将第一个砝码a存入set集合
每个砝码只有三种情况 放左边 放右边 不放
那对于第二个砝码b 我们有 a+b a-b b 三种情况
我们把这三种情况的结果放入set
然后再用一个list集合遍历即可
每次放一个砝码之前 都将set集合中的结果 初始化到list集合中
用list集合中的每个元素，对砝码的三种情况进行计算，并放入set集合中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            int a = scan.nextInt();
            ArrayList<Integer> tmp = new ArrayList<>(set);
            for (int b : tmp) {
                set.add(b + a);
                if (b != a) set.add(Math.abs(b - a));
            }
            set.add(a);
        }
        System.out.println(set.size());
    }
}

试题 H: 杨辉三角形（20分）

杨辉三角
HE

思路

杨辉三角的第i行第j个的数都是组合数C(i, j) （i，j从0开始）
C(n, 1) = n 对应斜着的第二行 也就是一定有解
由于杨辉三角左右对称C(a, b) == C(a, a-b)，又由于找第一次出现，因此一定在左边，右边不用看

        1  ---> C(0, 0)
      1 
    1   2  ---> C(2, 1)
  1   3                             ---> C(2n, n)
1   4   6  ---> C(4, 2)

1 5 10
1 6 15 20 —> C(6, 3)

题目范围上限1E9，C(34, 17) > 1E9, C(32, 16) < 1E9，因此只要枚举前16个斜行即可

  1. 每个斜行是依次递增的C(n,m) m相同n越大 C(n,m)越大
  2. 每个横行从中间到两边是递减的
    因此我们直接从中间对称轴倒序二分找起即可
    C(r, k)对应的位置为：(r + 1) * r / 2 + k + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.*;

public class Main {
    static int target;

    static long C(int a, int b) {
        long res = 1;
        for (int i = a, j = 1; j <= b; i--, j++) {
            res = res * i / j;
            //组合数是一步一步算的 如果当前数值已经超过我们要寻找的值了 就没必要继续算下去了 再继续算下去可能会超过long能存储的数据范围
            if (res > target) return res;
        }
        return res;
    }
    //对每一斜行进行二分查找 找到了就直接输出所在位置
    static boolean check(int line) {
        if (target == 1) {
            System.out.println(1);
            return true;
        }
        int left = 2 * line;//左端点就是上面字符画的规律值
        int right = target;//右端点取最坏情况 例如要查找1E9 那只能在C(1000000000,1)找到
        while (left < right) {
            int mid = left + right >> 1;
            if (C(mid, line) >= target) right = mid;
            else left = mid + 1;
        }
        if (C(left, line) != target) return false;
        System.out.println((long) right * (right + 1) / 2 + line + 1);
        return true;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        target = scan.nextInt();
        int line = 16;
        while (line-- > 0) {
            if (check(line))
                break;
        }
    }
}

试题 I: 双向排序（25分）

双向排序

思路

暴力解法会超时 所以这个题还是要找规律的(比赛肯定想不出来)
如果有两个连续的指令都是让我们降序排序，比如0 3和0 5，那么0 3这条指令就不需要进行操作，我们只需要执行操作区间更大的0 5
{ 1 2 3 4 5 6 7 }
0 3
{ 3 2 1 4 5 6 7 }
0 5
{ 5 4 3 2 1 6 7 }

再观察一下下面的两个操作
{ 1 2 3 4 5 6 7 }
0 5
{ 5 4 3 2 1 6 7 }
1 4
{ 5 4 3 1 2 6 7 }
0 5的意义就是将[1, 5]这个区间进行降序操作，而一开始整个区间[1, 7]都是升序的,我们要让[1,5]降序，那就只需要取[1,7]和[1,5]的交集，然后翻转这个交集，显然这个交集就是[1, 5]，翻转[1, 5]，于是我们得到了一个降序的[1, 5]区间，1 4的意义就是将[4, 7]这个区间进行升序操作，而最右边的区间[6, 7]已经是升序的了，并且里面所有的数字都比它们左边所有的数字都要大，**所以[6, 7]区间的数字并不会变化，**我们只需要接着取交集，取[1, 5]和[4, 7]的交集，得到一个[4, 5]的区间，翻转[4, 5]就是我们最终的答案。
要是上面两个操作之后，突然出现一个0 7的指令怎么办 显然执行0 7会覆盖之前两步的操作
所以不是连续的0操作最大就行了 而是要让后面比较大的0操作 覆盖掉之前操作区间所有比它小的操作 其间的1和0操作都会因为这个比较大的0操作而变得无效
经过上述这两步 我们就可以去掉很多无效操作 只保留有效操作 将这些有效操作入栈
栈维护出来之后，区间外部的东西就永远都不会动了，所以只需要一边缩区间一边填数字就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
import java.util.Scanner;

public class Main {

    static int N = 100010;
    static int n, m;
    static PII[] stk = new PII[N];
    static int[] ans = new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        int top = 0;//栈顶

        while (m -- > 0) {

            int p = sc.nextInt();
            int q = sc.nextInt();

            if (p == 0) {
                //求出连续操作的最长前缀
                while (top != 0 && stk[top].x == 0) q = Math.max(q, stk[top -- ].y);
                while (top >= 2 && stk[top - 1].y <= q) top -= 2;
                stk[ ++ top] = new PII(0, q);
            } else if (top != 0) {
                //求出连续操作的最长后缀
                while (top != 0 && stk[top].x == 1) q = Math.min(q, stk[top --].y);
                while (top >= 2 && stk[top - 1].y >= q) top -= 2;
                stk[ ++ top] = new PII(1, q);
            }
        }

        //k是递减变量，l为左边界，r为右边界
        int k = n, l = 1, r = n;
        for (int i = 1; i <= top; i ++ ) {
            if (stk[i].x == 0) {
                //若为前缀操作，则(stk[i].y, r]不用操作，直接填数
                while (r > stk[i].y && l <= r) ans[r -- ] = k --;
            } else {
                //若为后缀操作，则[l, stk[i].y)不用操作，直接填数
                while (l < stk[i].y && l <= r) ans[l ++ ] = k --;
            }
            if (l > r) break;
        }

        //若l < r, 表示中间还有些数没有填上，操作次数为奇数，则下一次操作为前缀操作
        if (top % 2 == 1) {
            while (l <= r) ans[l ++ ] = k --;
        } else {
            while (l <= r) ans[r -- ] = k --;
        }

        for (int i = 1; i <= n; i ++ ) System.out.print(ans[i] + " ");
    }

    static class PII {
        int x, y;

        public PII(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

}

//暴力骗分能通过60%的案例
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        Integer[] arr = new Integer[n];
        for (int i = 0; i < n; i++) {
            arr[i] = i + 1;
        }

        int m = scan.nextInt();
        for (int i = 0; i < m; i++) {
            int p = scan.nextInt();
            int split = scan.nextInt();
            if (p == 0) {
                Arrays.sort(arr, 0, split, (o1, o2) -> o2 - o1);
            } else {
                Arrays.sort(arr, split - 1, n);
            }
        }
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}

试题 J: 括号序列（25分）

括号序列

摆烂了 有空再说