第十三届蓝桥杯大赛省赛Java研究生组（题目＋代码详解）

暴力思路即求出所有位置的查询次数，然后次数最多的填充最大值。优化一下即：这里的查询次数数组即可用一维差分数组来表示出来。

头发快不保

1909人浏览 · 2023-04-06 21:11:39

头发快不保 · 2023-04-06 21:11:39 发布

第十三届蓝桥杯大赛软件赛省赛 Java 研究生组

创作不易，如有帮助，多多点赞加关注🎉🎉

试题A：排列字母

本题总分：5 分

【问题描述】

小蓝要把一个字符串中的字母按其在字母表中的顺序排列。

例如，LANQIAO 排列后为 AAILNOQ。又如，GOODGOODSTUDYDAYDAYUP 排列后为 AADDDDDGGOOOOPSTUUYYY 。

请问对于以下字符串，排列之后字符串是什么？ WHERETHEREISAWILLTHEREISAWAY

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个由大写字母组成的字符串，在提交答案时只填写这个字符串，填写多余的内容将无法得分

思路及代码

直接搞一个字符数组排序即可，签到题五分

import java.util.Arrays;
public class Main
{
    public static void main(String[] args)
    {
        String Str = "WHERETHEREISAWILLTHEREISAWAY";
        char[] Arr=Str.toCharArray();
        Arrays.sort(Arr);
        System.out.println(Arr);
    }
}

试题B：灭鼠先锋

本题总分：5 分

【问题描述】

灭鼠先锋是一个老少皆宜的棋盘小游戏，由两人参与，轮流操作。灭鼠先锋的棋盘有各种规格，本题中游戏在两行四列的棋盘上进行。游戏的规则为：两人轮流操作，每次可选择在棋盘的一个空位上放置一个棋子，或在同一行的连续两个空位上各放置一个棋子，放下棋子后使棋盘放满的一方输掉游戏。小蓝和小乔一起玩游戏，小蓝先手，小乔后手。小蓝可以放置棋子的方法很多，通过旋转和翻转可以对应如下四种情况： XOOO XXOO OXOO OXXO OOOO OOOO OOOO OOOO 其中 O 表示棋盘上的一个方格为空，X 表示该方格已经放置了棋子。请问，对于以上四种情况，如果小蓝和小乔都是按照对自己最优的策略来玩游戏，小蓝是否能获胜。如果获胜，请用 V 表示，否则用 L 表示。请将四种情况的胜负结果按顺序连接在一起提交。

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个长度为 4 的由大写字母 V 和 L 组成的字符串，如 VVLL，在提交答案时只填写这个字符串，填写多余的内容将无法得分。

思路及代码

明天更新🤭

试题C：质因数个数

时间限制: 5.0s 内存限制: 512.0MB 本题总分：10 分

【问题描述】

给定正整数 n，请问有多少个质数是 n 的约数。

【输入格式】

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

【输出格式】

输出一个整数，表示 n 的质数约数个数。

【样例输入】

396

【样例输出】 3

【样例说明】

396 有 2, 3, 11 三个质数约数。

【评测用例规模与约定】

对于 30% 的评测用例，1 ≤ n ≤ 10000。对于 60% 的评测用例，1 ≤ n ≤ 109。对于所有评测用例，1 ≤ n ≤ 1016。

思路及ac代码

这题要会质因数分解

其数学定理为：任何一个大于1的自然数，如果它是质数，那它最大的质因数就是它自己，如果它是合数，那么它一定可以拆成质数 × 质数，并且它最小的第一个因子一定是质数。
详细解析可看主页博客链接: https://blog.csdn.net/zutdragon/article/details/129950659?spm=1001.2014.3001.5501

import java.util.Scanner;

public class Main {
    static int num;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        long n = scan.nextLong();
        long l= (long) Math.sqrt(n);
        for (int i = 2; i <= l ; i++) {
            if (n%i==0){
                num++;
                while (n%i==0){//直到不能除以当前质数因此为止，除完的这个质数，一定不会出现在后面的质数因子中
                    n=n/i;
                }
                if (n==1){
                    break;
                }
            }
        }
        num=n==1?num:num+1;//n=1说明该数已经完全拆成了几个质因子的乘积，（可能被其他质因子除过的自己也是质数，此时自己的值小于最初的根号n）
        //如果不为1说明该数被拆成了比自己的根号要大的质数，因此要加上它自己的这个质数因子
        System.out.println(num);
    }
}

试题D：数位排序

时间限制: 1.0s 内存限制: 512.0MB 本题总分：10 分

【问题描述】

小蓝对一个数的数位之和很感兴趣，今天他要按照数位之和给数排序。当两个数各个数位之和不同时，将数位和较小的排在前面，当数位之和相等时，将数值小的排在前面。例如，2022 排在 409 前面，因为 2022 的数位之和是 6，小于 409 的数位之和 13。又如，6 排在 2022 前面，因为它们的数位之和相同，而 6 小于 2022。给定正整数 n，m，请问对 1 到 n 采用这种方法排序时，排在第 m 个的元素是多少？

【输入格式】输入第一行包含一个正整数 n。第二行包含一个正整数 m。

【输出格式】输出一行包含一个整数，表示答案。

【样例输入】

【样例输出】

【样例说明】

1 到 13 的排序为：1, 10, 2, 11, 3, 12, 4, 13, 5, 6, 7, 8, 9。第 5 个数为 3。

【评测用例规模与约定】

对于 30% 的评测用例，1 ≤ m ≤ n ≤ 300。对于 50% 的评测用例，1 ≤ m ≤ n ≤ 1000。

对于所有评测用例，1 ≤ m ≤ n ≤ 10^6。

思路及代码

这里本来想用map的，但是我熟练度不够，后续可能会更新，暂时先用对象来实现了。

ac代码，暴力解决

import java.util.*;

class  Shu{
    int key;//数据的各位之和
    int value;//数据的十进制值
}

public class Main {


    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        ArrayList<Shu> list = new ArrayList<>();
        int n= scan.nextInt();
        int m= scan.nextInt();
        for (int i = 1; i <= n; i++) {
            Shu shu = new Shu();
            shu.value=i;//当前数据的十进制值
            String s= String.valueOf(i);
            for (int j = 0; j < s.length(); j++) {//统计当前数字的各位之和并记录到当前对象的key中
                shu.key=shu.key+s.charAt(j)-48;//按字符统计大小时，'0'在ASCII中是48
            }
            list.add(shu);
        }

        list.sort(new Comparator<Shu>() {
            @Override
            public int compare(Shu o1, Shu o2) {
                return o1.key-o2.key;
            }
        });
        System.out.println(list.get(m-1).value);
    }
}

试题E：蜂巢

时间限制: 1.0s 内存限制: 512.0MB 本题总分：15 分

【问题描述】

蜂巢由大量的六边形拼接而成，定义蜂巢中的方向为：0 表示正西方向，1 表示西偏北 60◦，2 表示东偏北 60◦，3 表示正东，4 表示东偏南 60◦，5 表示西偏南 60◦。

对于给定的一点 O，我们以 O 为原点定义坐标系，如果一个点 A 由 O 点先向 d 方向走 p 步再向 (d + 2) mod 6 方向（d 的顺时针 120◦ 方向）走 q 步到达，则这个点的坐标定义为 (d, p, q)。在蜂窝中，一个点的坐标可能有多种。

下图给出了点 B(0, 5, 3) 和点 C(2, 3, 2) 的示意。
在这里插入图片描述

给定点 (d1, p1, q1) 和点 (d2, p2, q2)，请问他们之间最少走多少步可以到达？

【输入格式】输入一行包含 6 个整数 d1, p1, q1, d2, p2, q2 表示两个点的坐标，相邻两个整数之间使用一个空格分隔。

【输出格式】输出一行包含一个整数表示两点之间最少走多少步可以到达。

【样例输入】0 5 3 2 3 2

【样例输出】7

思路及代码

明天更新🤭

试题F：爬树的甲壳虫

时间限制: 1.0s 内存限制: 512.0MB 本题总分：15 分

【问题描述】

有一只甲壳虫想要爬上一颗高度为 n 的树，它一开始位于树根，高度为 0，当它尝试从高度 i − 1 爬到高度为 i 的位置时有 Pi 的概率会掉回树根，求它从树根爬到树顶时，经过的时间的期望值是多少。

【输入格式】

输入第一行包含一个整数 n 表示树的高度。接下来 n 行每行包含两个整数 xi , yi，用一个空格分隔，表示 Pi = xi yi。

【输出格式】

输出一行包含一个整数表示答案，答案是一个有理数，请输出答案对质数 998244353 取模的结果。其中有理数 a b 对质数 P 取模的结果是整数 c 满足 0 ≤ c < P 且 c · b ≡ a (mod P)。

【样例输入 1】

1 2

【样例输出 1】

【样例输入 2】

1 2

3 5

7 11

【样例输出 2】

623902744

思路及代码

明天更新🤭

试题G：重新排序

时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分

【问题描述】

给定一个数组 A 和一些查询 Li , Ri，求数组中第 Li 至第 Ri 个元素之和。小蓝觉得这个问题很无聊，于是他想重新排列一下数组，使得最终每个查询结果的和尽可能地大。小蓝想知道相比原数组，所有查询结果的总和最多可以增加多少?

【输入格式】

输入第一行包含一个整数 n。第二行包含 n 个整数 A1, A2, · · · , An，相邻两个整数之间用一个空格分隔。第三行包含一个整数 m 表示查询的数目。接下来 m 行，每行包含两个整数 Li、Ri ，相邻两个整数之间用一个空格分隔。【输出格式】

输出一行包含一个整数表示答案。

【样例输入】

1 2 3 4 5

1 3

2 5

【样例输出】

【样例说明】原来的和为6+ 14 = 20，重新排列为 (1, 4, 5, 2, 3) 后和为 10 + 14 = 24，增加了 4

思路及代码

这里用贪心+差分的思路

这里所查询的范围出现的次数越多，里面所填充的数越大，最后的增加值就会越大

要求的数值总和公式即：【数字 * 出现次数】

暴力思路即求出所有位置的查询次数，然后次数最多的填充最大值。

优化一下即：
这里的查询次数数组即可用一维差分数组来表示出来。

一维差分数组d[]来表示查询的范围即若查询区间为（l，r），不需要进行遍历，只需要对差分数组进行操作即可：

d[l]+=1;
d[r+1]-=1;

按此思路统计完所有的查询范围后对差分数组d求和恢复成统计次数的数组。

然后在统计范围内求原来所查询的数值之和：

for (int i = 1; i <= n ; i++) {
		//【数字 * 出现次数】
            sum1+=A[i]*d[i];//按查询次数《-》原数据位置的规则求和
 }

再对原数据和统计次数数组排序后即可找到一一对应关系：

A[]: 1 2 3 4 5
d[]: 1 1 1 2 2

再次求和做差即可：

for (int i = A.length-1; i >=0 ; i--) {
            sum2+=A[i]*d[i];//按最大查询次数《-》最大值的规则求和

            if (d[i]==0){//当前的数据并没有查询
                break;
            }
        }

ac完整代码

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


public class Main {
    static int n;
    static long[] A;//long防止值数据求和后爆int
    static long[] d;


    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        n= scan.nextInt();
        A=new long[n+5];//数据数组
        d=new long[n+5];//查询次数的差分数组

        for (int i = 1; i <= n; i++) {
            A[i]= scan.nextInt();
        }
        int m= scan.nextInt();
        for (int i = 0; i < m; i++) {
            int l= scan.nextInt();
            int r=scan.nextInt();
            d[l]++;//构造差分数组
            d[r+1]--;
        }
        for (int i = 1; i <= n; i++) {
            d[i]+=d[i-1];
        }
        long sum1=0;
        for (int i = 1; i <= n ; i++) {
        //【数字 * 出现次数】
            sum1+=A[i]*d[i];//按查询次数《-》原数据位置的规则求和
        }
        Arrays.sort(A);
        Arrays.sort(d);
        long sum2=0;
        for (int i = A.length-1; i >=0 ; i--) {
            sum2+=A[i]*d[i];//按最大查询次数《-》最大值的规则求和
            if (d[i]==0){//当前的数据并没有查询
                break;
            }
        }
        System.out.println(sum2-sum1);

    }
}

试题H：技能升级

时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分

【问题描述】

小蓝最近正在玩一款 RPG 游戏。他的角色一共有 N 个可以加攻击力的技能。其中第 i 个技能首次升级可以提升 Ai 点攻击力，以后每次升级增加的点数都会减少 Bi。⌈ Ai Bi ⌉ (上取整) 次之后，再升级该技能将不会改变攻击力。现在小蓝可以总计升级 M 次技能，他可以任意选择升级的技能和次数。请你计算小蓝最多可以提高多少点攻击力？【输入格式】

输入第一行包含两个整数 N 和 M。以下 N 行每行包含两个整数 Ai 和 Bi。

【输出格式】输出一行包含一个整数表示答案。

【样例输入】

3 6

10 5

9 2

8 1

【样例输出】 47

思路及代码

只会暴力解，过了50%的数据
在这里插入图片描述

将所有技能以及所有升级后的攻击力统计在一起排序从大到小取前m项即可

具体代码：

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

public class Main {
    static int n;
    static int m;

    static int[] A;//首次升级的攻击力
    static int[] B;//第一次后每次升级的攻击力

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        ArrayList<Integer> list = new ArrayList<>();
        n= scan.nextInt();
        m=scan.nextInt();
        A=new int[n+5];
        B=new int[n+5];
        for (int i = 0; i < n; i++) {
            A[i]= scan.nextInt();
            B[i]= scan.nextInt();
            list.add(A[i]);
            int t= ((A[i]+B[i]-1)/B[i]);//t表示向上取整之后的可以升级次数
            int z=A[i];
            while (t>0){//每次升级之和所增加的攻击力统计下来
                z-=B[i];
                list.add(z);
                t--;
            }
        }
        list.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;//按从大到小排序
            }
        });
        int sum=0;
        for (int i = 0; i < m; i++) {
            sum+=list.get(i);
        }

        System.out.println(sum);
    }
}

试题I：最优清零方案

时间限制: 3.0s 内存限制: 512.0MB 本题总分：25 分

【问题描述】

给定一个长度为 N 的数列 A1, A2, · · · , AN。现在小蓝想通过若干次操作将这个数列中每个数字清零。每次操作小蓝可以选择以下两种之一： 1. 选择一个大于 0 的整数，将它减去 1； 2. 选择连续 K 个大于 0 的整数，将它们各减去 1。小蓝最少经过几次操作可以将整个数列清零？

【输入格式】输入第一行包含两个整数 N 和 K。第二行包含 N 个整数 A1, A2, · · · , AN。

【输出格式】输出一个整数表示答案。

【样例输入】

4 2

1 2 3 4

【样例输出】 6

思路及代码

这题难度不算大，容易判断出应该优先考虑操作2，操作2不满足条件的话再去考虑操作1

正常遍历去判断当前值之后的总共的k个值是否连续可减，可以的话当前最小值即此个区间内操作2的次数；

！！！这里要注意操作下次操作的范围是当前可以进行操作2的范围中最小值的位置的下一位—或者是当前范围中最后一个0的下一位置，这里如果不优化一下遍历会超时！！！

当操作2无法继续进行时，对数组进行求和的总值即要进行操作1的次数。

ac代码

import java.util.Scanner;

public class Main {
    static int n;
    static int k;
    static long cnt;//long防止操作次数爆int
    static int[] A;
    static int idx;//表示当前所查询范围中出现最后一个0的位置

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        k = scan.nextInt();
        A = new int[n + 5];

        for (int i = 0; i < n; i++) {
            A[i] = scan.nextInt();
        }
        
        for (int i = 0; i < n; i++) {
            int min = check(i);//求当前范围的最小值，若为-1则表示当前范围不支持进行操作2
            int right = 0;//记录进行操作2后最后一个最小值的位置，即变为0的最后一个元素的位置，下次循环从其下一位开始即可
            if (min != -1) {
                cnt += min;
                for (int j = i; j < i + k; j++) {
                    A[j] -= min;
                    if (A[j] == 0) {
                        right = j;
                    }
                }
                i = right;
            }
            else{
                i=idx;//当前范围存在的最后一个0的位置
            }
        }
        for (int i = 0; i < n; i++) {//统计剩下的元素进行操作1的次数
            cnt+=A[i];
        }

        System.out.println(cnt);
    }

    static int check(int n) {
        int min = A[n];
        for (int i = n; i < n+k; i++) {
            if (A[i] < min) {//求最小值
                min = A[i];
            }
            if (A[i] <= 0) {//当前范围中存在0
                idx=i;
                return -1;
            }
        }
        return min;
    }
}

试题J：推导部分和

时间限制: 1.0s 内存限制: 512.0MB 本题总分：25 分

【问题描述】

对于一个长度为 N 的整数数列 A1, A2, · · · AN，小蓝想知道下标 l 到 r 的部分和 ∑r i=l = Al + Al+1 + · · · + Ar 是多少？然而，小蓝并不知道数列中每个数的值是多少，他只知道它的 M 个部分和的值。其中第 i 个部分和是下标 li 到 ri 的部分和 ∑ri j=li = Ali + Ali+1 + · · · + Ari ，值是 S i。

【输入格式】第一行包含 3 个整数 N、M 和 Q。分别代表数组长度、已知的部分和数量和询问的部分和数量。接下来 M 行，每行包含 3 个整数 li ,ri , S i。接下来 Q 行，每行包含 2 个整数 l 和 r ，代表一个小蓝想知道的部分和。【输出格式】对于每个询问，输出一行包含一个整数表示答案。如果答案无法确定，输出 UNKNOWN。

【样例输入】

5 3 3

1 5 15

4 5 9

2 3 5

1 5

1 3

1 2

【样例输出】

15 6

格式】第一行包含 3 个整数 N、M 和 Q。分别代表数组长度、已知的部分和数量和询问的部分和数量。接下来 M 行，每行包含 3 个整数 li ,ri , S i。接下来 Q 行，每行包含 2 个整数 l 和 r ，代表一个小蓝想知道的部分和。【输出格式】对于每个询问，输出一行包含一个整数表示答案。如果答案无法确定，输出 UNKNOWN。

【样例输入】

5 3 3

1 5 15

4 5 9

2 3 5

1 5

1 3

1 2

【样例输出】

15 6

UNKNOWN