第九届蓝桥杯软件类省赛 Java B组题目及解析

落日映苍穹つ 2022-12-11 15:18 156阅读 0赞

###  ###

*   *  结果填空题
     *   *  1. 标题：第几天
         *  2. 标题：方格计数
         *  3. 标题：复数幂
         *  4. 标题：测试次数
         *  5. 标题：快速排序
     *  程序设计题
     *   *  6. 标题：递增三元组
         *  7. 标题：螺旋折线
         *  8. 标题：日志统计
         *

## 结果填空题 ##

### 1. 标题：第几天 ###

**问题描述**

2000年的1月1日，是那一年的第1天。  
那么，2000年的5月4日，是那一年的第几天？

注意：需要提交的是一个整数，不要填写任何多余内容。

**答案解析**

方法一：最简单的方法就是打开电脑日历数：125。

方法二：能被400整除，或者能被4整除但不能被100整除的就是闰年。故 31+29+31+30+4 = 125

### 2. 标题：方格计数 ###

**问题描述**

如图 p1.png 所示，在二维平面上有无数个 1x1 的小方格。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center]  
我们以某个小方格的一个顶点为圆心画一个半径为1000的圆。

你能计算出这个圆里有多少个完整的小方格吗？

注意：需要提交的是一个整数，不要填写任何多余内容。

**答案解析**

用方格右上角的点代表这个方格，双重遍历，用 i 代表 x 轴的点数不断递增，用 j 代表 y 轴的点数不断递增，只要 i 和 j 构成的矩阵面积小于 1000 \* 1000，那么就代表这个点在圆内。答案是：3137548。

public class Main { 
    
        public static void main(String[] args) { 
            // TODO Auto-generated method stub
            int d = 1000, ans =0;
            for (int i = 1; i <= d; i++) { 
                for (int j = 1; j <= d; j++) { 
                    if (i*i + j*j <=d*d)
                        ans++;
                }
            }
            System.out.println(ans*4);
        }
    
    }

### 3. 标题：复数幂 ###

**问题描述**

设 i 为虚数单位。对于任意正整数 n，(2+3i)^n 的实部和虚部都是整数。

求 (2+3i)^123456 等于多少？ 即 (2+3i) 的 123456 次幂，这个数字很大，要求精确表示。

答案写成 “实部±虚部i” 的形式，实部和虚部都是整数（不能用科学计数法表示），中间任何地方都不加空格，实部为正时前面不加正号。

(2+3i)^2 写成: -5+12i，(2+3i)^5 的写成: 122-597i

注意：需要提交的是一个很庞大的复数，不要填写任何多余内容。

**答案解析**

这道题数据比较大，所以要用大数来运算。可以直接输出到控制台，也可以输出到txt文件里。这里答案太长了就不贴出来了。

> 复数运算公式：  
> ( a + bi ) \* ( c + di ) = ( a \* c - b \* d ) + ( a \* d + b \* c )i

import java.io.File;
    import java.io.FileNotFoundException;
    import java.io.PrintStream;
    import java.math.BigInteger;
    
    public class Main { 
    
        public static void main(String[] args) throws FileNotFoundException { 
            // TODO Auto-generated method stub
            BigInteger a = BigInteger.valueOf(2);
            BigInteger b = BigInteger.valueOf(3);
            BigInteger c = BigInteger.valueOf(2);
            BigInteger d = BigInteger.valueOf(3);
            for (int i=1;i<123456;i++) { 
                BigInteger A = a.multiply(c).subtract(b.multiply(d));
                BigInteger B = a.multiply(d).add(b.multiply(c));
                a = A;
                b = B;
            }
            //方法一：可以直接输出到控制台，然后显示的是“-+-i”，但直接全选复制粘贴到记事本后就可以显示出来了
            System.out.println(a.toString() + "+" + b.toString() +"i");
            
            //方法二：输出到txt文件
            PrintStream ps = new PrintStream(new File("E:/ans.txt"));
            //下面两行代码就是要让结果输出到txt文件里
            System.setOut(ps);
            System.out.println(a.toString() + "+" + b.toString() +"i");
    
        }
    
    }

### 4. 标题：测试次数 ###

**问题描述**

x星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机。  
各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试，并且评定出一个耐摔指数来，之后才允许上市流通。

x星球有很多高耸入云的高塔，刚好可以用来做耐摔测试。塔的每一层高度都是一样的，与地球上稍有不同的是，他们的第一层不是地面，而是相当于我们的2楼。

如果手机从第7层扔下去没摔坏，但第8层摔坏了，则手机耐摔指数=7。  
特别地，如果手机从第1层扔下去就坏了，则耐摔指数=0。  
如果到了塔的最高层第n层扔没摔坏，则耐摔指数=n

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

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

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

注意：需要填写的是一个整数，不要填写任何多余内容。

**答案解析**

### 5. 标题：快速排序 ###

**问题描述**

以下代码可以从数组a\[\]中找出第k小的元素。

它使用了类似快速排序中的分治算法，期望时间复杂度是O(N)的。

请仔细阅读分析源码，填写划线部分缺失的内容。

import java.util.Random;
    public class Main{ 
    	public static int quickSelect(int a[], int l, int r, int k) { 
    		Random rand = new Random();
    		int p = rand.nextInt(r - l + 1) + l;
    		int x = a[p];
    		int tmp = a[p]; a[p] = a[r]; a[r] = tmp;
    		int i = l, j = r;
    		while(i < j) { 
                    	while(i < j && a[i] < x) i++;
                    	if(i < j) { 
                            	a[j] = a[i];
                            	j--;
                    	}
                    	while(i < j && a[j] > x) j--;
                    	if(i < j) { 
                            	a[i] = a[j];
                            	i++;
                    	}
            	}
            	a[i] = x;
            	p = i;
            	if(i - l + 1 == k) return a[i];
            	if(i - l + 1 < k) return quickSelect( _____________ ); //填空
            	else return quickSelect(a, l, i - 1, k);	
    	}
    	public static void main(String args[]) { 
    		int [] a = { 1, 4, 2, 8, 5, 7};
    		System.out.println(quickSelect(a, 0, 5, 4));
    	}
    }

注意：只提交划线部分缺少的代码，不要抄写任何已经存在的代码或符号。

**答案解析**

这道题就是随机快排思想，空白处就是递归调用快速排序函数的代码。我们要根据参数要改写。第一个参数是数组，不会改变；第二、三个参数，表示范围，要从右边找起，所以 l 变为 i + 1，r 不变。第四个参数，可以根据上一行代码来推断，k 表示第 k 小的下标，由于 i - l + 1 > k，所以现在要找的就不是第 k 小了，而是 k - (i - l + 1)，所以答案是 a,i+1,r,k-i+l-1

## 程序设计题 ##

### 6. 标题：递增三元组 ###

**问题描述**

给定三个整数数组  
A = \[A1, A2, … AN\],  
B = \[B1, B2, … BN\],  
C = \[C1, C2, … CN\]，  
请你统计有多少个三元组(i, j, k) 满足：

1.  1 <= i, j, k <= N
2.  Ai < Bj < Ck

【输入格式】  
第一行包含一个整数N。  
第二行包含N个整数A1, A2, … AN。  
第三行包含N个整数B1, B2, … BN。  
第四行包含N个整数C1, C2, … CN。

对于30%的数据，1 <= N <= 100  
对于60%的数据，1 <= N <= 1000  
对于100%的数据，1 <= N <= 100000 0 <= Ai, Bi, Ci <= 100000

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

【输入样例】  
3  
1 1 1  
2 2 2  
3 3 3

【输出样例】  
27

资源约定：  
峰值内存消耗（含虚拟机） < 256M  
CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。  
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。  
不要使用package语句。不要使用jdk1.7及以上版本的特性。  
主类的名字必须是：Main，否则按无效代码处理。

**答案解析**

三个for循环肯定超时，可以过60%的样例。这里我用了双重循环，再来一层二分，时间复杂度是 O(n^2 logn)。应该可以过80%的样例。

import java.util.Arrays;
    import java.util.Scanner;
    
    public class Main { 
    
        public static void main(String[] args) { 
            // TODO Auto-generated method stub
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int[] A = new int[n + 1];
            int[] B = new int[n + 1];
            int[] C = new int[n + 1];
    
            for (int i = 1; i <= n; i++)
                A[i] = sc.nextInt();
            for (int i = 1; i <= n; i++)
                B[i] = sc.nextInt();
            for (int i = 1; i <= n; i++)
                C[i] = sc.nextInt();
            
            Arrays.sort(A);
            Arrays.sort(B);
            Arrays.sort(C);
    
            long ans = 0;
            for (int i = 1; i <= n; i++) { 
                for (int j = 1; j <= n; j++) { 
                    if (A[i] <= B[j]) { 
                        int l = 1, r = n;
                        while (l <= r) { 
                            int mid = (l + r) / 2;
                            if(C[mid]>B[j]) r = mid-1;
                            else l = mid+1;
                        }
                        ans += (n-l+1);
                    }
                }
            }
            System.out.println(ans);
    
        }
    }

### 7. 标题：螺旋折线 ###

**问题描述**

如图所示的螺旋折线经过平面上所有整点恰好一次。

对于整点 (X, Y)，我们定义它到原点的距离 dis(X, Y) 是从原点到 (X, Y) 的螺旋折线段的长度。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 1]

例如dis(0, 1)=3, dis(-2, -1)=9

给出整点坐标(X, Y)，你能计算出dis(X, Y)吗？

【输入格式】  
X和Y

对于40%的数据，-1000 <= X, Y <= 1000  
对于70%的数据，-100000 <= X， Y <= 100000  
对于100%的数据, -1000000000 <= X, Y <= 1000000000

【输出格式】  
输出dis(X, Y)

【输入样例】  
0 1

【输出样例】  
3

资源约定：  
峰值内存消耗（含虚拟机） < 256M  
CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。  
不要使用package语句。不要使用jdk1.7及以上版本的特性。  
主类的名字必须是：Main，否则按无效代码处理。

**答案解析**

我们只要把左下的一条边顺时针旋转90°，就能得到一个矩形，如图

1、这个点之前的正方形长度

我们发现每个正方形都是一个等差数列；这个数列是8, 16, 24, 32… 也就是等差数列前n项和，注意算的是这个点之前所在所有正方形的和。

2、这个点占所在正方形的长度之和就行了。

将左下的边旋转之后，对应着的点是(-1, -1), (-2, -2), (-3, -3)…(-n, -n)，所以从这个点开始，计算这个点到point的边距离，这步有点难。

import java.util.Scanner;
    
    public class Main { 
    
        public static void main(String[] args) { 
            // TODO Auto-generated method stub
            Scanner sc = new Scanner(System.in);
            long x = sc.nextLong();
            long y = sc.nextLong();
            long n = Math.max(Math.abs(x), Math.abs(y));
    
            // 1、等差数列Sn=n*a1+n*(n-1)*d/2或者Sn=n*(a1+an)/2，计算之前正方形的长度和
            long Sn = 4 * (n - 1) * n;
    
            // 2、计算点（X,Y）到点（-n,-n）的距离
            long sum = 0;
            long px = -n, py = -n;
            long d1 = x - px, d2 = y - py;
            if (y > x) { 
                sum += (d1 + d2);
            } else { 
                sum += (8 * n - d1 - d2);
            }
            System.out.println(Sn + sum);
    
        }
    
    }

### 8. 标题：日志统计 ###

**问题描述**

小明维护着一个程序员论坛。现在他收集了一份"点赞"日志，日志共有N行。其中每一行的格式是：

ts id

表示在ts时刻编号id的帖子收到一个"赞"。

现在小明想统计有哪些帖子曾经是"热帖"。如果一个帖子曾在任意一个长度为D的时间段内收到不少于K个赞，小明就认为这个帖子曾是"热帖"。

具体来说，如果存在某个时刻T满足该帖在\[T, T+D)这段时间内(注意是左闭右开区间)收到不少于K个赞，该帖就曾是"热帖"。

给定日志，请你帮助小明统计出所有曾是"热帖"的帖子编号。

【输入格式】  
第一行包含三个整数N、D和K。  
以下N行每行一条日志，包含两个整数ts和id。

对于50%的数据，1 <= K <= N <= 1000  
对于100%的数据，1 <= K <= N <= 100000 0 <= ts <= 100000 0 <= id <= 100000

【输出格式】  
按从小到大的顺序输出热帖id。每个id一行。

【输入样例】  
7 10 2  
0 1  
0 10  
10 10  
10 1  
9 1  
100 3  
100 3

【输出样例】  
1  
3

资源约定：  
峰值内存消耗（含虚拟机） < 256M  
CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

**答案解析**

···java

···

###  ###

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/b05ebe5965bd42aa8202d06e2c10f503.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/21750fbb8523441b960fc9247784db7c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/421310220b6f4872892f5b1d2f9ff813.png