假装备战明年蓝桥杯怒做四道蓝桥真题

答疑

题目描述

有n位同学同时找老师答疑。每位同学都预先估计了自己答疑的时间。
老师可以安排答疑的顺序，同学们要依次进入老师办公室答疑。 一位同学答疑的过程如下：

1. 首先进入办公室，编号为 i的同学需要 si​ 毫秒的时间。
2. 然后同学问问题老师解答，编号为 i 的同学需要 ai​ 毫秒的时间。
3. 答疑完成后，同学很高兴，会在课程群里面发一条消息，需要的时间可 以忽略。
4. 最后同学收拾东西离开办公室，需要 ei​ 毫秒的时间。一般需要 10秒、20秒或 30秒，即 ei​ 取值为 10000，20000 或 30000
   一位同学离开办公室后，紧接着下一位同学就可以进入办公室了。
   答疑从 0 时刻开始。老师想合理的安排答疑的顺序，使得同学们在课程群 里面发消息的时刻之和最小。

输入描述

输入第一行包含一个整数 n，表示同学的数量。
接下来 n 行，描述每位同学的时间。其中第 i 行包含三个整数 si​,ai​,ei​，意义如上所述。
其中有 1≤n≤1000，1≤si​≤60000，1≤ai​≤10^6，ei​∈10000,20000,30000，即 ei​ 一定是 10000、20000、30000 之一。

输出描述

输出一个整数，表示同学们在课程群里面发消息的时刻之和最小是多少。

思路

这是一道贪心问题，假设第一个同学发消息的时间为s1+a1，第二个同学发消息的时间为s1+a1+e1+s2+a2，再假设第一个同学发消息的时间为s2+a2，第二个同学发消息的时间为s2+a2+e2+s1+a1，我们可以发现，如果我们按照s+a+e的和从小到大排序，如果相等的话，我们再按照s+a从小到大排序，这样就可以保证每个同学发消息的时间是最小的。

代码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class 答疑 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Stu> stuList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int s = sc.nextInt(), a = sc.nextInt(), e = sc.nextInt();
            Stu stu = new Stu(s, a, e);
            stuList.add(stu);
        }
        stuList.sort((s1, s2) -> {
            int sum1 = s1.a + s1.s + s1.e, sum2 = s2.a + s2.s + s1.e;
            if (sum1 == sum2) return (s1.s + s1.a) - (s2.s + s2.a);
            return sum1 - sum2;
        });
        long ans = 0L;
        long cur = 0L;
        for (Stu stu : stuList) {
            cur += stu.s + stu.a;
            ans += cur;
            cur += stu.e;
        }
        System.out.println(ans);
    }

    public static class Stu {
        int s, a, e;

        public Stu(int s, int a, int e) {
            this.s = s;
            this.a = a;
            this.e = e;
        }
    }

}

等差素数列

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

2,3,5,7,11,13,….是素数序列。类似：7,37,67,97,127,157这样完全由素数组成的等差数列，叫等差素数数列。

上边的数列公差为30长度为6。

2004年，格林与华人陶哲轩合作证明了：存在任意长度的素数等差数列。 这是数论领域一项惊人的成果！

有这一理论为基础，请你借助手中的计算机，满怀信心地搜索：

长度为10的等差素数列，其公差最小值是多少？

我的思路

我的做法比较暴力，但是毕竟是填空题，暴力就暴力吧，

我就先2-10000去枚举每次等差数列的首项，然后再去枚举公差，然后根据公差和首项进行暴力搜索，初始化变量int min=Integer.MAX_VALUE;，如果找到了长度为10的等差素数列并且公差比min还小，那么就更新min的值，最后搜索完了输出min的值。

代码

代码里的path记不记录都无所谓，我只是想看看这个搜出来的数列结果是什么。

import java.util.ArrayList;

public class 等差素数列 {
    public static void main(String[] args) {
        for (int i = 2; i <= 10000; i++) {
            for (int d = 1; d <= 500; d++) {
                path.add(i);
                dfs(0, i, -1, d);
                path.remove(path.size() - 1);
            }
        }
        System.out.println(min);
    }

    static int min = Integer.MAX_VALUE;

    static ArrayList<Integer> path = new ArrayList<>();

    public static void dfs(int i, int cur, int last, int d) {

        if (i == 10) {
            min = Math.min(min, d);
//            System.out.println(path);
            return;
        }
        if (!isPrime(cur)) {
            return;
        }
        if(i != 0 && cur - last != d) {
            return;
        }
        for (int j = cur + d; j <= 10000; j += d) {
            path.add(j);
            dfs(i + 1, j, cur, d);
            path.remove(path.size() - 1);
        }
    }

    public static boolean isPrime(int n) {
        if (n == 1) return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
}

老师的思路

代码

import java.util.*;

class T {
    int from, to;

    T(int f, int t) {
        from = f;
        to = t;
    }

    @Override
    public int hashCode() {
        return Objects.hash(to);
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        T other = (T) obj;
        return to == other.to;
    }

}

public class 等差素数列2 {
    public static void main(String[] args) {
        Deque<Integer> d = new ArrayDeque<>();
        Map<Integer, Set<T>> m = new HashMap<>();
        d.addLast(3);

        int i, j, from, to;
        for (i = 5; ; i += 2) {
            int sqrti = (int) Math.sqrt(i);
            for (j = 0; d.toArray(new Integer[0])[j] <= sqrti; j++) {
                if (i % d.toArray(new Integer[0])[j] == 0) break;
            }
            if (d.toArray(new Integer[0])[j] > sqrti) {
                to = i;
                for (j = 0; j < d.size(); ++j) {
                    from = d.toArray(new Integer[0])[j];
                    Set<T> set_t = m.computeIfAbsent(to - from, k -> new HashSet<>());
                    T temp = new T(0, from);
                    if (set_t.contains(temp)) {
                        for (T t : set_t) {
                            if (t.equals(temp)) {
                                temp = t;
                                break;
                            }
                        }
                        set_t.remove(temp);
                        set_t.add(new T(temp.from, to));
                        if ((to - temp.from) / (to - from) == 9) {
                            System.out.println(to - from);
                            return;
                        }
                    } else {
                        set_t.add(new T(from, to));
                    }
                }
                d.addLast(i);
            }
        }
    }
}

讲解

Deque<Integer> d用于存放奇素数，所以先放个3；然后从5开始，考察每个奇数i是否，能够被小于等于sqrt(i)的数整除，以判断i是否是素数。这里，for(i=5;;i+=2)是死循环，会无穷的计算下去。

在寻找到每一个新的素数的时候，都要看一下是否已经存在题解，即集合d中，是否存在长度为10的等差序列，所以我们创建一个类T，类型T表示，一个等差序列，其中from和to分别，表示序列的头项和尾项，但这里没有保存数列的公差是多少。

然后用一个哈希表key为Integer，value为Set，来保存所有的等差序列，key是等差序列的公差，value是所有的等差序列。

key	value
2	(3,7) (11,13) (17,19) (29,31) (41,43) (59,61) (71,73)……
4	(3,11) (13,17) (19,23) (37,41) (43,47) (67,71) (79,83)……
6	(7,19) (5,29) (31,43) (41,59) (61,79) (83,89) (97,109)……

上表中，2开头的行表示存在的“差值”2的等差序列，其中(3,7)就表示等差序列3,5,7；再如：4开头的行表示存在的“差值”4的等差序列，其中(3,11)就表示等差序列3,7,11；等等。

当第8点中的那个循环中如果找到，一个新的素数x （例如11）,我会将x（11）与d中已经存在的素数3、5、7的每一个相结合，组成数对（3,11）、（5,11）和（7,11），并将（3,11）放入m差值为8对应的set，（5,11）放入m差值为6对应的set，（7,11）放入m差值为4对应的set。特别的，（3,11）放入m[8]时，属于新的；而（7,11）放入m[4]时，由于m[4]对应的set中已经有（3,7）这一项，此时通过查找尾项7，我们将（3,7）改成（3,11），就是把（3,7）和（7,11）两项合并了。

测试次数

X 星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机。

各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试，并且评定出一个耐摔指数来，之后才允许上市流通。

X 星球有很多高耸入云的高塔，刚好可以用来做耐摔测试。塔的每一层高度都是一样的，与地球上稍有不同的是，他们的第一层不是地面，而是相当于我们的 2 楼。如果手机从第 7 层扔下去没摔坏，但第 8 层摔坏了，则手机耐摔指数=7。 特别地，如果手机从第 1 层扔下去就坏了，则耐摔指数 =0。 如果到了塔的最高层第 n 层扔没摔坏，则耐摔指数 =n。

为了减少测试次数，从每个厂家抽样 3 部手机参加测试。

某次测试的塔高为 1000 层，如果我们总是采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？

请填写这个最多测试次数。

思路

我们可以反向思考，我们不去求1000层3部手机需要测多少次，而是求三部手机测多少次能够1000层。那么我们可以先求一下1部手机能测多少层。

假设楼层数为10

• 1部手机：1 2 3 4 5 6 7 8 … n
• 2部手机：1 3 6 10 15 21 28 … n
• 3部手机：1 3 7 14 25 41 63 … n

2部手机摔i次最多能测到的楼层数相当于，找一个合适的楼层（就是第a[i-1]+1层,第i层）摔第一次，如果没碎，还剩2部手机，此时第i层相当于第0层，第i+1层以上含第i+1层能测的层数显然等于b[i-1]，如果第一次在第i层摔碎了，还剩1部手机，此时最多还能摔i-1次，最多测a[i-1]层。

3部手机同理，3部手机摔i次最多能测到的楼层数相当于，找一个合适的楼层（就是第b[i-1]+1层）摔第一次，如果没碎，还剩3部手机，此时第b[i-1]+1层相当于第0层，第b[i-1]+2层以上含第b[i-1]+2层能测的层数显然等于c[i-1]，如果第一次在第b[i-1]+1层摔碎了，还剩2部手机，此时最多还能摔i-1次，最多能测的楼层数就是b[i-1]，最后公式中的1，就代表的就是第b[i-1]+1层，就是中间测得这一层。

b[i]=b[i-1]+a[i-1]+1
c[i]=c[i-1]+b[i-1]+1

代码

public class 测试次数2 {
    public static void main(String[] args) {
        int[] a = new int[100];
        int[] b = new int[100];
        int[] c = new int[100];
        for (int i = 1; i < a.length; i++) {
            a[i] = i;
        }
        int i = 1;
        for (i = 1; ; i++) {
            b[i] = b[i - 1] + a[i - 1] + 1;
            c[i] = c[i - 1] + b[i - 1] + 1;
            if (c[i] >= 1000) break;
        }
        System.out.println(i);
    }
}

K倍区间

题目描述

给定一个长度为 N 的数列， A1​,A2​,⋯AN​，如果其中一段连续的子序列  Ai​,Ai​+1,⋯Aj​ ( i≤j ) 之和是 K 的倍数，我们就称这个区间  [i,j] 是 K 倍区间。
你能求出数列中总共有多少个 K 倍区间吗？

输入描述

第一行包含两个整数 N 和 K ( 1≤N,K≤10^5 )。
以下 N 行每行包含一个整数 Ai​ ( 1≤Ai​≤10^5 )

思路

可以先求出给定数组的前缀和，然后用一个mod数组来记录前缀和对K取模的结果，然后根据同余原理，我们可以发现，如果两个前缀和对K取模的结果相等，那么这两个前缀和之间的区间的差集的和一定是K的倍数，那么在这个余数相等的区间任取两个也就是一共C(X,2)个K倍区间，然后再加上mod[i]等于0的情况，也就是前缀和本身就是K的倍数的情况。

代码

import java.util.Arrays;
import java.util.Scanner;

public class K倍区间 {

    static long[] preSum;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(), K = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) arr[i] = sc.nextInt();
        preSum = new long[N + 1];
        preSum[0] = 0;
        for (int i = 1; i <= N; i++) {
            preSum[i] = preSum[i - 1] + arr[i - 1];
        }
        long ans = 0;
        int[] mod = new int[K];
        for (int i = 1; i < N + 1; i++) {
            mod[(int) (preSum[i] % K)]++;
        }
        ans += mod[0];
        for (int i = 0; i < K; i++) {
            ans += ((long) mod[i] * (mod[i] - 1) / 2);
        }
        System.out.println(ans);
    }
}

K倍区间Ⅱ

这道题与上一道的区别就是给定的数组内是存在负数的，而在计算机中对负数取模与我们平常的取模是不一样的。

例如：

数学中：
-12 ÷ 5 = -3 ... 3

计算机中:
-12 ÷ 5 = -2 ... -2

为什么会出现这样的情况呢，假设被除数为A(A<0)，除数为B(B>0)，得到数C余D，那么满足等式A = B * C + D，而且计算机整数除法是直接取整的，所以B*C是大于A的，那么D就是负数。

如何解决呢，我们可以直接让得数借上一位，C=C-1，D=D+B，这样就可以使mod的结果为正数。

我们创建一个哈希表，key是余数，value是余数为key的除数的列表，

HashMap<Integer, ArrayList<Long>> mod = new HashMap<>();

然后我们遍历前缀和，如果前缀和小于0，那么我们就让前缀和对K取模加上K，然后再对K取模，这样就可以保证余数为正数，然后我们将余数相同的前缀和除K的到的除数放到同一个列表中，然后我们再遍历这个列表，如果列表中有n个除数，那么我们就可以得到C(n,2)个K倍区间，然后再减去这个列表中的逆序对的个数，就是这个列表中的所有K倍区间的个数，然后再加上余数为0的情况，也就是前缀和本身就是K的倍数的情况就是最后的答案。

代码

package 实践学期.第七节课;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class K倍区间2 {

    static long[] preSum;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(), K = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) arr[i] = sc.nextInt();
        preSum = new long[N + 1];
        preSum[0] = 0;
        for (int i = 1; i <= N; i++) {
            preSum[i] = preSum[i - 1] + arr[i - 1];
        }
        long ans = 0;
        HashMap<Integer, ArrayList<Long>> mod = new HashMap<>();
        for (int i = 1; i < N + 1; i++) {
            if (preSum[i] % K == 0 && preSum[i] / K >= 0) {
                ans++;
            }
            if (preSum[i] < 0) {
                int cur = (int) ((preSum[i] % K + K) % K);
                mod.computeIfAbsent(cur, k -> new ArrayList<>());
                ArrayList<Long> curList = mod.get(cur);
                curList.add(preSum[i] / K - 1);
            } else {
                int cur = (int) (preSum[i] % K);
                mod.computeIfAbsent(cur, k -> new ArrayList<>());
                ArrayList<Long> curList = mod.get(cur);
                curList.add(preSum[i] / K);
            }
        }
        for (Map.Entry<Integer, ArrayList<Long>> entry : mod.entrySet()) {
            ArrayList<Long> list = entry.getValue();
            int size = list.size();
            long curNi = ni(list);
            ans += ((long) size * (size - 1)) / 2 - curNi;
        }
        System.out.println(ans);
    }

    public static long ni(ArrayList<Long> list) {
        int size = list.size();
        int sum = 0;
        for (int i = 0; i < size - 1; i++) {
            for (int j = i + 1; j < size; j++) {
                if (list.get(i) > list.get(j)) {
                    sum++;
                }
            }
        }
        return sum;
    }
}