第十三届蓝桥杯 2022年省赛真题（Java 大学C组）

举报
随性. 发表于 2022/04/28 13:28:57 2022/04/28
【摘要】 第十三届蓝桥杯 2022年省赛真题（Java 大学C组）

​

试题 A: 排列字母

【问题描述】

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


        例如，LANQIAO 排列后为 AAILNOQ。


        又如，GOODGOODSTUDYDAYDAYUP 排列后为 AADDDDDGGOOOOPSTUUYYY。


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


        WHERETHEREISAWILLTHEREISAWAY

【答案提交】

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

这道题就不用说了吧，就算是一个一个找也可以找出来的。也可以用代码，我觉得太麻烦，就没整。

AAAEEEEEEHHHIIILLRRRSSTTWWWY 

试题 B: 特殊时间 

【问题描述】

        2022 年 2 月 22 日 22:20 是一个很有意义的时间，年份为 2022，由 3 个 2 和 1 个 0 组


成，如果将月和日写成 4 位，为 0222，也是由 3 个 2 和 1 个 0 组 成，如果将时间中的时和


分写成 4 位，还是由 3 个 2 和 1 个 0 组成。


         小蓝对这样的时间很感兴趣，他还找到了其它类似的例子，比如 111 年 10 月 11 日


01:11，2202 年 2 月 22 日 22:02 等等。


        请问，总共有多少个时间是这种年份写成 4 位、月日写成 4 位、时间写成 4 位后由 3


个一种数字和 1 个另一种数字组成。注意 1111 年 11 月 11 日 11:11 不算，因为它里面没有


两种数字。

【答案提交】

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

 212

 提前说明，这是看的网上大佬的代码：在 3个相同的个位数中插入 1 个个位数，显然可以组成 4个不同的数字（不一定是 4 位数），于是我们可以另一个合法的 月日时分 与 4 个不同的年份组成映射关系，只要统计出合法的 日月时分 个数，将其乘上一个 ，答案就被计算出来了。 

import java.time.format.DateTimeFormatter;
import java.time.LocalDateTime;

public class Test {

    public static void main(String[] args) { new Test().run(); }

    void run() {
        DateTimeFormatter date = DateTimeFormatter.ofPattern("MMdd");
        DateTimeFormatter time = DateTimeFormatter.ofPattern("HHmm");
        LocalDateTime start = LocalDateTime.of(0000, 01, 01, 00, 00);
        LocalDateTime end = LocalDateTime.of(0000, 12, 31, 23, 59);
        int[] buff = new int[128];
        int ans = 0;
        for (; start.compareTo(end) <= 0; start = start.plusMinutes(1)) {
            for (char i = '0'; i <= '9'; ++i) buff[i] = 0;
            for (byte b : start.format(date).getBytes()) ++buff[b];
            boolean flag1 = true, flag3 = true;
            for (char i = '0'; i <= '9'; ++i)
                if (buff[i] == 1) flag1 = false;
                else if (buff[i] == 3) flag3 = false;
            if (flag1 || flag3) continue;
            for (byte b : start.format(time).getBytes()) --buff[b];
            for (char i = '0'; i <= '9'; ++i)
                if (buff[i] != 0) flag1 = true;
            if (!flag1) ++ans;
        }
        System.out.println(4 * ans);
    }
}

试题 C: 纸张尺寸 

【问题描述】

        在 ISO 国际标准中定义了 A0 纸张的大小为 1189mm × 841mm，将 A0 纸 沿长边对折


后为 A1 纸，大小为 841mm × 594mm，在对折的过程中长度直接取 下整（实际裁剪时可能


有损耗）。将 A1 纸沿长边对折后为 A2 纸，依此类推。

        

输入纸张的名称，请输出纸张的大小。

【输入格式】

        输入一行包含一个字符串表示纸张的名称，该名称一定是 A0、A1、A2、 A3、A4、


A5、A6、A7、A8、A9 之一。

【输出格式】

输出两行，每行包含一个整数，依次表示长边和短边的长度。

【样例输入 1】

A0

【样例输出 1】

1189

841

【样例输入 2】

A1

【样例输出 2】

841

594

这道题就是定义两个变量，然后循环判断，然后输出就行了。 

import java.util.*;
 
public class Main
{
    public static void main(String args[])
    {
        //纸张尺寸
		Scanner sc = new Scanner(System.in);
		int a = 1189;
		int b = 841;
		String c = sc.next();
		for (int i = 0; i < c.charAt(1) - 48; i++) {
			if (a >= b) {
				a /= 2;
			} else {
				b /= 2;
			}
		}
		if (a >= b) {
			System.out.println(a);
		}
		System.out.println(b);
		if (a<b) {
			System.out.println(a);
		}
    }
}

试题 D: 求和 

【问题描述】

        给定 n 个整数 a1, a2, · · · , an ，求它们两两相乘再相加的和，即 S = a1 · a2 + a1 · a3


+ · · · + a1 · an + a2 · a3 + · · · + an−2 · an−1 + an−2 · an + an−1 · an.

【输入格式】

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


        第二行包含 n 个整数 a1, a2, · · · an。

【输出格式】

        输出一个整数 S，表示所求的和。请使用合适的数据类型进行运算。

【样例输入】

4

1 3 6 9

【样例输出】

117

【评测用例规模与约定】

        对于 30% 的数据，1 ≤ n ≤ 1000，1 ≤ ai ≤ 100。

        对于所有评测用例，1 ≤ n ≤ 200000，1 ≤ ai ≤ 1000。

这道题就是定义一个数组，然后循环数组的长度，然后在和计数器相加相乘，最后输出计数器就可以。 

import java.util.*;
 
public class Main
{
    public static void main(String args[])
    {
        //求和
		Scanner sc=new Scanner(System.in);
		int a=sc.nextInt();
		int[] array=new int[a];
		long count=0;
		for (int i = 0; i < array.length; i++) {
			array[i]=sc.nextInt();
		}
		for (int i = 0; i < array.length; i++) {
			for (int j = i+1; j < array.length; j++) {
				count+=array[i]*array[j];
			}
		}
		System.out.println(count);
    }
}

试题 E: 矩形拼接 

【问题描述】

        已知 3 个矩形的大小依次是 a1 × b1, a2 × b2 和 a3 × b3。用这 3 个矩形能拼 出的所有


多边形中，边数最少可以是多少？

         例如用 3 × 2 的矩形（用 A 表示）、4 × 1 的矩形（用 B 表示）和 2 × 4 的矩 形（用 C


表示）可以拼出如下 4 边形。

 例如用 3 × 2 的矩形（用 A 表示）、3 × 1 的矩形（用 B 表示）和 1 × 1 的矩 形（用 C


表示）可以拼出如下 6 边形。


【输入格式】

        输入包含多组数据。


         第一行包含一个整数 T，代表数据组数。


         以下 T 行，每行包含 6 个整数 a1, b1, a2, b2, a3, b3，其中 a1, b1 是第一个矩 形的边


长，a2, b2 是第二个矩形的边长，a3, b3 是第三个矩形的边长。

【输出格式】

        对于每组数据，输出一个整数代表答案。

【样例输入】

2

2 3 4 1 2 4

1 2 3 4 5 6

【样例输出】

4

8

【评测用例规模与约定】

        对于 10% 的评测用例，1 ≤ T ≤ 5，1 ≤ a1, b1, a2, b2, a3, b3 ≤ 10，a1 = a2 = a3。

         对于 30% 的评测用例，1 ≤ T ≤ 5，1 ≤ a1, b1, a2, b2, a3, b3 ≤ 10。

        对于 60% 的评测用例，1 ≤ T ≤ 10，1 ≤ a1, b1, a2, b2, a3, b3 ≤ 20。

         对于所有评测用例，1 ≤ T ≤ 1000，1 ≤ a1, b1, a2, b2, a3, b3 ≤ 100。 

这道题呢，有点麻烦，所以我也没做出来，有大佬做出来的可以分享一下。然我明白明白。

试题 F: 选数异或 

【问题描述】

        给定一个长度为 n 的数列 A1, A2, · · · , An 和一个非负整数 x，给定 m 次查 询, 每次询


问能否从某个区间 [l,r] 中选择两个数使得他们的异或等于 x 。

【输入格式】

        输入的第一行包含三个整数 n, m, x 。


        第二行包含 n 个整数 A1, A2, · · · , An 。


         接下来 m 行，每行包含两个整数 li ,ri 表示询问区间 [li ,ri ] 。

【输出格式】

对于每个询问, 如果该区间内存在两个数的异或为 x 则输出 yes, 否则输出 no。

【样例输入】

4 4 1

1 2 3 4

1 4

1 2

2 3

3 3

【样例输出】

yes

no

yes

no

【样例说明】

        显然整个数列中只有 2, 3 的异或为 1。

【评测用例规模与约定】

        对于 20% 的评测用例，1 ≤ n, m ≤ 100；

        对于 40% 的评测用例，1 ≤ n, m ≤ 1000；

        对于所有评测用例，1 ≤ n, m ≤ 100000 ，0 ≤ x < 2 20 ，1 ≤ li ≤ ri ≤ n ， 0 ≤ Ai < 2 20。


 动态规划

import java.io.*;

public class Main {

    public static void main(String[] args) { new Main().run(); }

    void run() {
        PrintWriter out = new PrintWriter(System.out);
        int n = nextInt(), m = nextInt(), x = nextInt();
        int[] map = new int[1 << 20];
        int[] f = new int[n + 1];
        for (int r = 1; r <= n; ++r) {
            int a = nextInt();
            f[r] = max(f[r - 1], map[a ^ x]);
            map[a] = r;
        }
        for (int i = 0; i < m; ++i) {
            int l = nextInt();
            int r = nextInt();
            out.println(f[r] >= l ? "yes" : "no");
        }
        out.flush();
    }

    int max(int arg1, int arg2) { return arg1 > arg2 ? arg1 : arg2; }

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

    int nextInt() {
        try {
            in.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int)in.nval;
    }
}
这是网上大佬的解法，我是真不懂，给你copy到这，你们看看，顺便给我讲解一下。

试题 G: GCD

【问题描述】

        给定两个不同的正整数 a, b，求一个正整数 k 使得 gcd(a + k, b + k) 尽可能 大，其中


gcd(a, b) 表示 a 和 b 的最大公约数，如果存在多个 k，请输出所有满 足条件的 k 中最小的那


个。

【输入格式】

        输入一行包含两个正整数 a, b，用一个空格分隔。

【输出格式】

        输出一行包含一个正整数 k。

【样例输入】

5 7

【样例输出】

1

【评测用例规模与约定】

        对于 20% 的评测用例，a < b ≤ 105 ；

        对于 40% 的评测用例，a < b ≤ 109 ；

        对于所有评测用例，1 ≤ a < b ≤ 1018 。

这是蓝桥杯考试的时候写的，不知道对不对。。。觉得是有点小问题。 

import java.util.*;
 
public class Main
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
		long a = sc.nextLong();
		long b = sc.nextLong();
		long x = sc.nextLong();
		int max = Integer.MAX_VALUE;
		for (int i = 100; i >= 1; i--) {
			long y = gcd(a + i, b + i);
			if (y > x) {
				x = y;
			}
			if (y == x) {
				max = i;
			}
		}
		System.out.println(max);

	}

	private static long gcd(long a, long b) {
		for (long i = Math.min(a,b); i >0; i--) {
			if (a%i==0&&b%i==0) {
				return i;
			}
		}
		return 0;
	}
    }
}

试题 H: 青蛙过河 

【问题描述】

        小青蛙住在一条河边，它想到河对岸的学校去学习。小青蛙打算经过河里 的石头跳到对岸。

         河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。 不过，每


块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就 会下降 1，当石头的高


度下降到 0 时小青蛙不能再跳到这块石头上（某次跳跃 后使石头高度下降到 0 是允许的）。


         小青蛙一共需要去学校上 x 天课，所以它需要往返 2x 次。当小青蛙具有 一个跳跃能力


y 时，它能跳不超过 y 的距离。


        请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x 次课。

【输入格式】

        输入的第一行包含两个整数 n, x，分别表示河的宽度和小青蛙需要去学校 的天数。请注


意 2x 才是实际过河的次数。

         第二行包含 n − 1 个非负整数 H1, H2, · · · , Hn−1，其中 Hi > 0 表示在河中与 小青蛙的


家相距 i 的地方有一块高度为 Hi 的石头，Hi = 0 表示这个位置没有石头。

【输出格式】

        输出一行，包含一个整数，表示小青蛙需要的最低跳跃能力。

【样例输入】

5 1

1 0 1 0

【样例输出】

4

【样例解释】

        由于只有两块高度为 1 的石头，所以往返只能各用一块。第 1 块石头和对 岸的距离为 4，如果小青蛙的跳跃能力为 3 则无法满足要求。所以小青蛙最少 需要 4 的跳跃能力。

【评测用例规模与约定】

        对于 30% 的评测用例，n ≤ 100；

         对于 60% 的评测用例，n ≤ 1000；

         对于所有评测用例，1 ≤ n ≤ 105 , 1 ≤ x ≤ 109 , 1 ≤ Hi ≤ 104。

二分 + 贪心 

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

public class Main {

    public static void main(String[] args) { new Main().run(); }
    
    void run() {
    	int n = nextInt(), x = nextInt() << 1;
    	int[] H = new int[n + 1], S = new int[n + 1];
    	long[] V = new long[n + 1];
    	for (int i = 1; i < n; ++i) H[i] = nextInt();
    	int mid, ans = 1, right = n;
    	V[0] = Long.MAX_VALUE;
    	while (ans < right) {
    		mid = ans + right >> 1;
    		int l = 0, r = 0;
    		for (int i = 1; i <= n; ++i) {
    			while (l <= r && S[l] < i - mid) ++l;
    			if (H[i] > 0) {
    				int Hk = 0;
    				while (l <= r && Hk < H[i])
    					if (V[l] <= H[i] - Hk) Hk += V[l++];
    					else {V[l] -= H[i] - Hk; Hk = H[i];}
    				if (Hk > 0) { S[++r] = i; V[r] = Hk; }
    			}
    		}
    		long cnt = 0;
    		while (l <= r)cnt += V[l++];
    		if (cnt >= x) right = mid; else ans = mid + 1;
    	}
    	System.out.println(ans);
    }
    
    StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    
    int nextInt() {
    	try {
			in.nextToken();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return (int)in.nval;
    }
}

借鉴于大佬的解题思路，我还是不理解。

试题 I: 因数平方和 

【问题描述】

        记 f(x) 为 x 的所有因数的平方的和。例如：f(12) = 12 + 22 + 32 + 42 + 62 + 122。


        定义 g(n) = ∑n i=1 f(i) 。给定 n, 求 g(n) 除以 109 + 7 的余数。

【输入格式】

        输入一行包含一个正整数 n。

【输出格式】

        输出一个整数表示答案 g(n) 除以 109 + 7 的余数。

【样例输入】

100000

【样例输出】

394827960

【评测用例规模与约定】

        对于 20% 的评测用例，n ≤ 105。

         对于 30% 的评测用例，n ≤ 107。

         对于所有评测用例，1 ≤ n ≤ 109。

数论分块 

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

public class Main {

    public static void main(String[] args) { new Main().run(); }

    int p = 1000000007, inv6 = 166666668;

    void run() {
        int n = nextInt();
        long tmp, sum = 0, ans = 0;
        for (int l = 1, r; l <= n; l = r + 1) {
            r = n / (n / l);
            tmp = sum;
            sum = r * (r + 1L) % p * (2 * r + 1) % p * inv6 % p;
            ans = (ans + (n / l) * (sum - tmp) + p) % p;
        }
        System.out.println(ans);
    }

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

    int nextInt() {
        try {
            in.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int)in.nval;
    }
}
这个我更不会了。。。

试题 J: 最长不下降子序列 

【问题描述】

        给定一个长度为 N 的整数序列：A1, A2, · · · , AN。现在你有一次机会，将其 中连续的


K 个数修改成任意一个相同值。请你计算如何修改可以使修改后的数 列的最长不下降子序列


最长，请输出这个最长的长度。


        最长不下降子序列是指序列中的一个子序列，子序列中的每个数不小于在 它之前的数。

【输入格式】

        输入第一行包含两个整数 N 和 K。

        第二行包含 N 个整数 A1, A2, · · · , AN。

【输出格式】

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

【样例输入】

5 1

1 4 2 8 5

【样例输出】

4

【评测用例规模与约定】

        对于 20% 的评测用例，1 ≤ K ≤ N ≤ 100；

         对于 30% 的评测用例，1 ≤ K ≤ N ≤ 1000；

        对于 50% 的评测用例，1 ≤ K ≤ N ≤ 10000；

         对于所有评测用例，1 ≤ K ≤ N ≤ 105，1 ≤ Ai ≤ 106

从试题 H-试题 J在考试的时候就没做出来，上边的代码，是copy网上大佬的，大家有问题可以评论哟。

​

【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
Java 大赛 数据结构
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入