2018年第九届蓝桥杯B组JAVA题解

Bertha 。 2022-05-26 07:46 317阅读 0赞

**2018年第九届蓝桥杯B组JAVA题解**

**-----------------------------------填空题-------------------------------------------**

**第一题：  
  
标题：第几天**  
  
2000年的1月1日，是那一年的第1天。

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

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

**答案：125**

**第二题 ：**

**标题：方格计数**  
  
如图p1.png所示，在二维平面上有无数个1x1的小方格。  
  
![20180401202319825][]  
  
  
我们以某个小方格的一个顶点为圆心画一个半径为1000的圆。  
你能计算出这个圆里有多少个完整的小方格吗？

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

import java.util.Scanner;
    
    public class 方格计数 {
    	static int N = 10000; // 方格图的大小, 10000够大了
    	static int X = 5000, Y = 5000; // 圆心坐标
    	static double[] l = new double[N]; 
    	static double[] r = new double[N];
    	static int R, ans = 0;
    
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		R = sc.nextInt();
    		for (int i = Y - R; i <= Y + R; i++) {
    			l[i] = X - Math.sqrt(R * R - (Y - i) * (Y - i));
    			r[i] = Math.min(N, (X << 1) - l[i]);
    			if (l[i] < 0) {
    				l[i] = 0;
    			}
    		}
    		for (int i = Y - R; i <= Y - 1; i++) {
    			int ll = (int) Math.ceil(l[i]), rr = (int) Math.floor(r[i]); 
    			ans += rr - ll;
    		}
    		for (int i = Y; i <= Y + R - 1; i++) {
    			int ll = (int) Math.ceil(l[i + 1]), rr = (int) Math.floor(r[i + 1]);
    			ans += rr - ll;
    		}
    		System.out.println(ans);
    	}
    }

我的答案： 3137548

**第三题：**

**标题：复数幂**  
设i为虚数单位。对于任意正整数n，(2+3i)^n 的实部和虚部都是整数。  
求 (2+3i)^123456 等于多少？ 即(2+3i)的123456次幂，这个数字很大，要求精确表示。  
答案写成 "实部±虚部i" 的形式，实部和虚部都是整数（不能用科学计数法表示），中间任何地方都不加空格，实部为正时前面不加正号。(2+3i)^2 写成: -5+12i，  
(2+3i)^5 的写成: 122-597i

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

用java大数加快速幂做的，应该是做对了，但是一开始eclipse控制台没显示出来，以为是大数爆了。

代码：

import java.math.BigInteger;
    
    public class 复数幂 {
    	public static void main(String[] args) {
    		Complex cmp = new Complex(BigInteger.valueOf(2), BigInteger.valueOf(3));
    		System.out.println(quickPow(cmp, 123456).toString());
    	}
    	
    	private static Complex quickPow(Complex cmp, int n) {
    		if (n == 0) {
    			return new Complex(BigInteger.valueOf(1), BigInteger.valueOf(0));
    		}
    		Complex temp = quickPow(cmp, n / 2);
    		temp.multiply(temp);
    		if (n % 2 != 0) {
    			temp.multiply(cmp);
    		}
    		return temp;
    	}
    }
    
    class Complex {
    	BigInteger a;  // 实部
    	BigInteger b;  // 虚部
    	
    	public Complex(BigInteger a, BigInteger b) {
    		this.a = a;
    		this.b = b;
    	}
    	
    	public void multiply(Complex cm) {
    		BigInteger tempa = a.multiply(cm.a).subtract(b.multiply(cm.b));
    		BigInteger tempb = a.multiply(cm.b).add(b.multiply(cm.a));
    		a = tempa;
    		b = tempb;
    	}
    	
    	@Override
    	public String toString() {
    		String aStr = "" + a;
    		String bStr = b + "i";
    		if (b.compareTo(BigInteger.valueOf(0)) > 0) {
    			bStr = "+" + bStr;
    		} else if (b.compareTo(BigInteger.valueOf(0)) == 0) {
    			bStr = "";
    		}
    		return aStr + bStr;
    	}
    }

eclipse控制台输出的结果是--i，不知道是什么鬼，比赛完了才知道把这个--i是一个超长的字符串，所以直接把eclipse输出的--i粘贴到记事本就可以看到结果了。

**第四题：**

**标题：测试次数**  
x星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机。  
各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试，并且评定出一个耐摔指数来，之后才允许上市流通。  
x星球有很多高耸入云的高塔，刚好可以用来做耐摔测试。塔的每一层高度都是一样的，与地球上稍有不同的是，他们的第一层不是地面，而是相当于我们的2楼。  
如果手机从第7层扔下去没摔坏，但第8层摔坏了，则手机耐摔指数=7。  
特别地，如果手机从第1层扔下去就坏了，则耐摔指数=0。  
如果到了塔的最高层第n层扔没摔坏，则耐摔指数=n  
为了减少测试次数，从每个厂家抽样3部手机参加测试。  
某次测试的塔高为1000层，如果我们总是采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？  
请填写这个最多测试次数。

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

100层，问最坏情况下最少几次？这个是最坏情况最多几次，我不知道是不是我多想了，比赛的时候二分答案，错了。。。比赛完结合之前的题目又想了一下，递推了一下，算出来19。

我的答案：19

代码：

public class 摔手机 {
    	public static void main(String[] args) {
    		System.out.println(DroppingPhone(3, 1000));
    	}
    
    	private static long DroppingPhone(long phone, long floors) {
    		long times = 1;
    		while (DroppingMax(phone, times) < floors) {
    			++times;
    		}
    		return times;
    	}
    
    	private static long DroppingMax(long phone, long times) {
    		if (phone == 1) {
    			return times;
    		}
    
    		if (phone >= times) {
    			return (long) Math.pow(2, times) - 1;
    		}
    
    		return DroppingMax(phone, times - 1) + DroppingMax(phone - 1, times - 1) + 1;
    	}
    }

**第五题：**

**标题：快速排序**  
以下代码可以从数组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));
    	}
    }
    
    注意：只提交划线部分缺少的代码，不要抄写任何已经存在的代码或符号。

利用快排的partition思想进行"选择"，是解决这类问题的高效方法，可以把复杂度从O（nlongn）（直接排序求a\[k - 1\]）降到O（n）（利用快排分组时左边刚好k-1个元素）。注意题目要求是O(n)，这题如果只求运行正确有几种写法，如果不注意直接写partition 的分治可能还是O（nlogn）。

我的答案：a, i + 1, r, k - i + l - 1

**-----------------------------------编程题-------------------------------------------**

**第六题：**

**标题：递增三元组**  
给定三个整数数组  
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  
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

这道题的话，可以先排序，然后直接三个for循环（两层）：以B数组为标杆，对于B的每一个元素Bi，二分统计A中比Bi小的元素，C中比Bi大的元素，然后相乘，最后把乘积累加起来。

import java.util.Scanner;
    
    class Main
    {
    	public static void main(String args[])
    	{
    		int n;
    		int a[],b[],c[],d[],e[];
    		long ans=0;
    		Scanner sc=new Scanner(System.in);
    		n=sc.nextInt();
    		a=new int[n];
    		b=new int[n];
    		c=new int[n];
    		d=new int[n];
    		e=new int[n];
    		for(int i=0;i<n;i++)
    			a[i]=sc.nextInt();
    		for(int i=0;i<n;i++)
    			b[i]=sc.nextInt();
    		for(int i=0;i<n;i++)
    			c[i]=sc.nextInt();
    		for(int i=0;i<n;i++)
    			for(int j=0;j<n;j++)
    				if(a[i]<b[j]) 
    				{
    					d[i]=j+1;break;
    				}
    		for(int i=0;i<n;i++)
    			for(int j=0;j<n;j++)
    				if(b[i]<c[j]) 
    				{
    					e[i]=j+1;break;
    				}
    		for(int i=0;i<n;i++)
    			if(d[i]!=0)
    			for(int j=d[i]-1;j<n;j++)
    				if(e[j]!=0)
    				ans+=n-e[j]+1;
    		System.out.println(ans);      
    	}
    }

**第七题**

**标题：螺旋折线**  
  
![70][]  
如图p1.pgn所示的螺旋折线经过平面上所有整点恰好一次。    
对于整点(X, Y)，我们定义它到原点的距离dis(X, Y)是从原点到(X, Y)的螺旋折线段的长度。    
  
例如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  
  
【输出样例】

资源约定：

峰值内存消耗（含虚拟机） < 256M  
CPU消耗  < 1000ms  
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

这题考察的不是算法，就是思维，方法应该挺多的。方法之一是把螺旋折线转变成一个个的同心正方形，像下面这样，

![70 1][]

注意转化关系，然后就好算多了。

import java.util.Scanner;
    
    class Main
    {
    	public static void main(String args[])
    	{
    		int a,b,p,q;
    		long ans=0;
    		Scanner sc=new Scanner(System.in);
    		a=sc.nextInt();
    		b=sc.nextInt();
    		if(Math.abs(a)>Math.abs(b))
    		{
    			p=a;q=1;
    		}
    		else {
    			p=b;q=2;
    		}
    		ans=4*Math.abs(p)*(Math.abs(p)-1);
    		if(q==1&&a<0)
    			ans+=b-a;
    		else if(q==1&&a>=0)
    			ans+=5*a-b;
    		else if(q==2&&b<0)
    			ans=-7*b-a;
    		else ans+=3*b+a;
    		System.out.println(ans);
    	}
    }

**第八题**

**标题：日志统计**  
小明维护着一个程序员论坛。现在他收集了一份"点赞"日志，日志共有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  
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

这题用的优先队列加hash（或者直接写一个二维的排序），这题计算点赞量，应该是以每一个点赞时间Ti为为起点，计算\[Ti,D)的点赞数（i = 1, 2, 3, ..., n），然后求最大值与K比较。

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Comparator;
    import java.util.Scanner;
    
    class Main
    {
    	public static void main(String args[])
    	{
    		int n,d,k;
    		Scanner sc=new Scanner(System.in);
    		n=sc.nextInt();
    		d=sc.nextInt();
    		k=sc.nextInt();
    		Node arr[]=new Node[n];
    		for(int i=0;i<n;i++)
    			arr[i]=new Node(sc.nextInt(),sc.nextInt());
    		Arrays.sort(arr);
    		int curid=arr[0].id;
    		int added=0;
    		for(int i=0;i<n;i++)
    		{			
    			if(i+k-1<n&&arr[i+k-1].id==curid&&arr[i+k-1].ts-arr[i].ts<d&&added==0)
    				{System.out.println(curid);added=1;}
    			else if(arr[i].id!=curid)
    			{
    				curid=arr[i].id;
    				added=0;
    				i=i-1;
    			}
    		}
    	
    	}
    }
    class Node implements Comparable<Node>
    {
    	int ts,id;
    	Node(int a,int b)
    	{
    		ts=a;
    		id=b;
    	}
    	
    	@Override
    	public int compareTo(Node o) {
    		if(id==o.id)
    			return ts-o.ts;
    		else
    			return id-o.id;
    	}
    	
    }

**第九题**

**标题：全球变暖**

你有一张某海域NxN像素的照片，"."表示海洋、"\#"表示陆地，如下所示：  
.......  
.\#\#....  
.\#\#....  
....\#\#.  
..\#\#\#\#.  
...\#\#\#.  
.......  
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。    
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。    
例如上图中的海域未来会变成如下样子：  
.......  
.......  
.......  
.......  
....\#..  
.......  
.......  
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。    
【输入格式】

第一行包含一个整数N。  (1 <= N <= 1000)

以下N行N列代表一张海域照片。

照片保证第1行、第1列、第N行、第N列的像素都是海洋。    
【输出格式】  
一个整数表示答案。  
【输入样例】  
7   
.......  
.\#\#....  
.\#\#....  
....\#\#.  
..\#\#\#\#.  
...\#\#\#.  
.......    
【输出样例】  
1    
资源约定：  
峰值内存消耗（含虚拟机） < 256M  
CPU消耗  < 1000ms  
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

dfs求联通分量，并且在求联通分量的时候做个标记，判断这个联通分量（岛屿）中是否存在不临海的陆地，存在的话，这样的联通分量（岛屿）才不会完全消失。

import java.util.Scanner;
    
    import org.omg.PortableInterceptor.SYSTEM_EXCEPTION;
    
    class Main
    {
    	static int n,map[][],vis[][];
    	static boolean dfs(int i,int j)
    	{
    		if(i<0||i>=n||j<0||j>=n||vis[i][j]==1) return false;
    		vis[i][j]=1;
    		boolean f=false;
    		if(map[i][j+1]==1&&map[i][j-1]==1&&map[i-1][j]==1&&map[i+1][j]==1)
    			f=true;
    		return dfs(i, j+1)||dfs(i, j-1)||dfs(i+1, j)||dfs(i-1, j)||f;
    	}
    	public static void main(String args[])
    	{
        int r=0,t=0;
    	Scanner sc=new Scanner(System.in);
    	n=sc.nextInt();
    	map=new int[n][n];
    	vis=new int[n][n];
    	for(int i=0;i<n;i++)
    	{
    		String s=sc.next();
    		for(int j=0;j<n;j++)
    			if(s.charAt(j)!='.')
    				map[i][j]=1;
    			else 
    				vis[i][j]=1;	
    	}
    	
    	for(int i=0;i<n;i++)
    		for(int j=0;j<n;j++)
    			if(vis[i][j]!=1)
    			{
    				
    				r++;
    				t+=dfs(i, j)?1:0;
    			
    			}
    		
    	System.out.println(r-t);
    	}
    }

**第十题**

**标题：堆的计数**  
我们知道包含N个元素的堆可以看成是一棵包含N个节点的完全二叉树。    
每个节点有一个权值。对于小根堆来说，父节点的权值一定小于其子节点的权值。    
假设N个节点的权值分别是1~N，你能求出一共有多少种不同的小根堆吗？    
例如对于N=4有如下3种：  
  
    1  
   / \\  
  2   3  
 /  
4  
  
    1  
   / \\  
  3   2  
 /  
4  
  
    1  
   / \\  
  2   4  
 /  
3  
  
由于数量可能超过整型范围，你只需要输出结果除以1000000009的余数。    
【输入格式】  
一个整数N。    
对于40%的数据，1 <= N <= 1000    
对于70%的数据，1 <= N <= 10000    
对于100%的数据，1 <= N <= 100000  
【输出格式】  
一个整数表示答案。    
【输入样例】  
4    
【输出样例】  
3  
资源约定：  
峰值内存消耗（含虚拟机） < 256M  
CPU消耗  < 1000ms  
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

想了一会，写了一个递推式，只验证了4，5两种，后面的没有去验证，不过应该是错了，就不贴了。感觉应该是组合数求和的问题，具体怎么个组合没想清楚，比赛的时候时间有限，没想太多。

> 本文摘自 [https://me.csdn.net/SG\_WGL][https_me.csdn.net_SG_WGL] [关于][Link 1]《2018年第九届蓝桥杯B组JAVA题解》

[20180401202319825]: /images/20220526/15a0306be0db4b44bab92499254c2c61.png
[70]: /images/20220526/2685fd45c96d45e09b4c251b2faa3db2.png
[70 1]: /images/20220526/22cb564c87e7408f9e26473683ba6cf7.png
[https_me.csdn.net_SG_WGL]: https://me.csdn.net/SG_WGL
[Link 1]: https://blog.csdn.net/SG_WGL/article/details/79781411