-
2018-06-18 23:01:42
1.购物单:
题目:
小明刚刚找到工作,老板人很好,只是老板夫人很爱购物。老板忙的时候经常让小明帮忙到商场代为购物。小明很厌烦,但又不好推辞。 这不,XX大促销又来了!老板夫人开出了长长的购物单,都是有打折优惠的。
小明也有个怪癖,不到万不得已,从不刷卡,直接现金搞定。
现在小明很心烦,请你帮他计算一下,需要从取款机上取多少现金,才能搞定这次购物。
取款机只能提供100元面额的纸币。小明想尽可能少取些现金,够用就行了。
你的任务是计算出,小明最少需要取多少现金。
以下是让人头疼的购物单,为了保护隐私,物品名称被隐藏了。
-----------------
**** 180.90 88折
**** 10.25 65折
**** 56.14 9折
**** 104.65 9折
**** 100.30 88折
**** 297.15 半价
**** 26.75 65折
**** 130.62 半价
**** 240.28 58折
**** 270.62 8折
**** 115.87 88折
**** 247.34 95折
**** 73.21 9折
**** 101.00 半价
**** 79.54 半价
**** 278.44 7折
**** 199.26 半价
**** 12.97 9折
**** 166.30 78折
**** 125.50 58折
**** 84.98 9折
**** 113.35 68折
**** 166.57 半价
**** 42.56 9折
**** 81.90 95折
**** 131.78 8折
**** 255.89 78折
**** 109.17 9折
**** 146.69 68折
**** 139.33 65折
**** 141.16 78折
**** 154.74 8折
**** 59.42 8折
**** 85.44 68折
**** 293.70 88折
**** 261.79 65折
**** 11.30 88折
**** 268.27 58折
**** 128.29 88折
**** 251.03 8折
**** 208.39 75折
**** 128.88 75折
**** 62.06 9折
**** 225.87 75折
**** 12.89 75折
**** 34.28 75折
**** 62.16 58折
**** 129.12 半价
**** 218.37 半价
**** 289.69 8折
--------------------
需要说明的是,88折指的是按标价的88%计算,而8折是按80%计算,余者类推。
特别地,半价是按50%计算。
请提交小明要从取款机上提取的金额,单位是元。
答案是一个整数,类似4300的样子,结尾必然是00,不要填写任何多余的内容。
源代码:
import java.util.Scanner; public class 购物单 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); float [][] a = new float[50][2]; float sum = 0; for(int i=0; i<50; i++) { a[i][0] = sc.nextFloat(); a[i][1] = sc.nextFloat(); } for(int i=0; i<50; i++) sum += (a[i][0] * a[i][1] / 100); System.out.println(sum); } }
运行结果:
5136.8594
所以答案为: 5200
2.纸牌三角形:
题目:
A,2,3,4,5,6,7,8,9 共9张纸牌排成一个正三角形(A按1计算)。要求每个边的和相等。
下图就是一种排法(如有对齐问题,参看p1.png)。 A
9 6
4 8
3 7 5 2 这样的排法可能会有很多。
如果考虑旋转、镜像后相同的算同一种,一共有多少种不同的排法呢?
请你计算并提交该数字。
注意:需要提交的是一个整数,不要提交任何多余内容。
暴力破解.
源代码:
public class 纸牌三角形 { public static void main(String[] args) { int sum = 0; for (int a = 1; a <= 9; a++) for (int b = 1; b <= 9; b++) for (int c = 1; c <= 9; c++) for (int d = 1; d <= 9; d++) for (int e = 1; e <= 9; e++) for (int f = 1; f <= 9; f++) for (int g = 1; g <= 9; g++) for (int h = 1; h <= 9; h++) for (int i = 1; i <= 9; i++) if (a + b + c + d == a + e + f + g && a + b + c + d == d + h + i + g) { if (a != b && a != c && a != d && a != e && a != f && a != g && a != h && a != i) if (b != c && b != d && b != e && b != f && b != g && b != h && b != i) if (c != d && c != e && c != f && c != g && c != h && c != i) if (d != e && d != f && d != g && d != h && d != i) if (e != f && e != g && e != h && e != i) if (f != g && f != h && f != i) if (g != h && g != i) if (h != i) { sum++; } } System.out.println(sum / 2 / 3); } }
运行结果:
144
所以答案为:144
3.承压计算:
题目:
X星球的高科技实验室中整齐地堆放着某批珍贵金属原料。
每块金属原料的外形、尺寸完全一致,但重量不同。
金属材料被严格地堆放成金字塔形。 7
5 8
7 8 8
9 2 7 2
8 1 4 9 1
8 1 8 8 4 1
7 9 6 1 4 5 4
5 6 5 5 6 9 5 6
5 5 4 7 9 3 5 5 1
7 5 7 9 7 4 7 3 3 1
4 6 4 5 5 8 8 3 2 4 3
1 1 3 3 1 6 6 5 5 4 4 2
9 9 9 2 1 9 1 9 2 9 5 7 9
4 3 3 7 7 9 3 6 1 3 8 8 3 7
3 6 8 1 5 3 9 5 8 3 8 1 8 3 3
8 3 2 3 3 5 5 8 5 4 2 8 6 7 6 9
8 1 8 1 8 4 6 2 2 1 7 9 4 2 3 3 4
2 8 4 2 2 9 9 2 8 3 4 9 6 3 9 4 6 9
7 9 7 4 9 7 6 6 2 8 9 4 1 8 1 7 2 1 6
9 2 8 6 4 2 7 9 5 4 1 2 5 1 7 3 9 8 3 3
5 2 1 6 7 9 3 2 8 9 5 5 6 6 6 2 1 8 7 9 9
6 7 1 8 8 7 5 3 6 5 4 7 3 4 6 7 8 1 3 2 7 4
2 2 6 3 5 3 4 9 2 4 5 7 6 6 3 2 7 2 4 8 5 5 4
7 4 4 5 8 3 3 8 1 8 6 3 2 1 6 2 6 4 6 3 8 2 9 6
1 2 4 1 3 3 5 3 4 9 6 3 8 6 5 9 1 5 3 2 6 8 8 5 3
2 2 7 9 3 3 2 8 6 9 8 4 4 9 5 8 2 6 3 4 8 4 9 3 8 8
7 7 7 9 7 5 2 7 9 2 5 1 9 2 6 5 3 9 3 5 7 3 5 4 2 8 9
7 7 6 6 8 7 5 5 8 2 4 7 7 4 7 2 6 9 2 1 8 2 9 8 5 7 3 6
5 9 4 5 5 7 5 5 6 3 5 3 9 5 8 9 5 4 1 2 6 1 4 3 5 3 2 4 1
X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X其中的数字代表金属块的重量(计量单位较大)。
最下一层的X代表30台极高精度的电子秤。假设每块原料的重量都十分精确地平均落在下方的两个金属块上,
最后,所有的金属块的重量都严格精确地平分落在最底层的电子秤上。
电子秤的计量单位很小,所以显示的数字很大。工作人员发现,其中读数最小的电子秤的示数为:2086458231
请你推算出:读数最大的电子秤的示数为多少?
注意:需要提交的是一个整数,不要填写任何多余的内容。
处理过的数据,将最后一行X换成0。
7
5 8
7 8 8
9 2 7 2
8 1 4 9 1
8 1 8 8 4 1
7 9 6 1 4 5 4
5 6 5 5 6 9 5 6
5 5 4 7 9 3 5 5 1
7 5 7 9 7 4 7 3 3 1
4 6 4 5 5 8 8 3 2 4 3
1 1 3 3 1 6 6 5 5 4 4 2
9 9 9 2 1 9 1 9 2 9 5 7 9
4 3 3 7 7 9 3 6 1 3 8 8 3 7
3 6 8 1 5 3 9 5 8 3 8 1 8 3 3
8 3 2 3 3 5 5 8 5 4 2 8 6 7 6 9
8 1 8 1 8 4 6 2 2 1 7 9 4 2 3 3 4
2 8 4 2 2 9 9 2 8 3 4 9 6 3 9 4 6 9
7 9 7 4 9 7 6 6 2 8 9 4 1 8 1 7 2 1 6
9 2 8 6 4 2 7 9 5 4 1 2 5 1 7 3 9 8 3 3
5 2 1 6 7 9 3 2 8 9 5 5 6 6 6 2 1 8 7 9 9
6 7 1 8 8 7 5 3 6 5 4 7 3 4 6 7 8 1 3 2 7 4
2 2 6 3 5 3 4 9 2 4 5 7 6 6 3 2 7 2 4 8 5 5 4
7 4 4 5 8 3 3 8 1 8 6 3 2 1 6 2 6 4 6 3 8 2 9 6
1 2 4 1 3 3 5 3 4 9 6 3 8 6 5 9 1 5 3 2 6 8 8 5 3
2 2 7 9 3 3 2 8 6 9 8 4 4 9 5 8 2 6 3 4 8 4 9 3 8 8
7 7 7 9 7 5 2 7 9 2 5 1 9 2 6 5 3 9 3 5 7 3 5 4 2 8 9
7 7 6 6 8 7 5 5 8 2 4 7 7 4 7 2 6 9 2 1 8 2 9 8 5 7 3 6
5 9 4 5 5 7 5 5 6 3 5 3 9 5 8 9 5 4 1 2 6 1 4 3 5 3 2 4 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0解题思路:从第一层开始平均累加,将第i排的所有金属块放在第i排的第1~i位置。最后累加到最后一层,找出最大数与最小数,按照题目所给的最小数,从而根据比例求出最大读数。
源代码:
package 第八届蓝桥杯; import java.util.Scanner; public class 承压计算 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); double [][] a = new double[30][30]; for(int i=0; i<30; i++) for(int j=0; j<=i; j++) { a[i][j] = sc.nextDouble(); } for(int i=1; i<30; i++) { for(int j=0; j<=i; j++) { if(j == 0) a[i][j] = a[i-1][j]/2.0 + a[i][j]; else a[i][j] = a[i-1][j-1]/2.0 + a[i-1][j]/2.0 + a[i][j]; } } double min = 1000000; double max = 0; for(int i=0; i<30; i++) { max = Math.max(max, a[29][i]); min = Math.min(min, a[29][i]); } System.out.println(max + "\n" + min); System.out.println(max*2086458231/min); } }
程序运行结果:
135.34946863353252 3.8863313030451536 7.2665192664E10
所以最后答案:72665192664
5.取数位:
题目:
求1个整数的第k位数字有很多种方法。
以下的方法就是一种。对于题目中的测试数据,应该打印5。
请仔细分析源码,并补充划线部分所缺少的代码。
注意:只提交缺失的代码,不要填写任何已有内容或说明性的文字。。
解题思路:直接递归,很简单。
源代码:
public class 取数位 { static int len(int x){ if(x<10) return 1; return len(x/10)+1; } // 取x的第k位数字 static int f(int x, int k){ if(len(x)-k==0) return x%10; return f(x/10, k); //填空 } public static void main(String[] args) { int x = 23513; //System.out.println(len(x)); System.out.println(f(x,3)); } }
答案:f(x/10, k)
6.最大公共子串:
题目:
最大公共子串长度问题就是:
求两个串的所有子串中能够匹配上的最大长度是多少。
比如:“abcdkkk” 和 “baabcdadabc”,
可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。
下面的程序是采用矩阵法进行求解的,这对串的规模不大的情况还是比较有效的解法。
请分析该解法的思路,并补全划线部分缺失的代码。解题思路:动态规划思想。
源代码:
public class 最大公共子串 { static int f(String s1, String s2) { char[] c1 = s1.toCharArray(); char[] c2 = s2.toCharArray(); int[][] a = new int[c1.length+1][c2.length+1]; int max = 0; for(int i=1; i<a.length; i++){ for(int j=1; j<a[i].length; j++){ if(c1[i-1]==c2[j-1]) { a[i][j] = a[i-1][j-1] + 1; //填空 if(a[i][j] > max) max = a[i][j]; } } } return max; } public static void main(String[] args){ int n = f("abcdkkk", "baabcdadabc"); System.out.println(n); } }
8.包子凑数:
题目:
小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼,其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼,可以认为是无限笼。
每当有顾客想买X个包子,卖包子的大叔就会迅速选出若干笼包子来,使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼,分别能放3、4和5个包子。当顾客想买11个包子时,大叔就会选2笼3个的再加1笼5个的(也可能选出1笼3个的再加2笼4个的)。
当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼,分别能放4、5和6个包子。而顾客想买7个包子时,大叔就凑不出来了。
小明想知道一共有多少种数目是包子大叔凑不出来的。
输入
第一行包含一个整数N。(1 <= N <= 100)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100)输出
一个整数代表答案。如果凑不出的数目有无限多个,输出INF。
例如,
输入:
2
4
5程序应该输出:
6再例如,
输入:
2
4
6程序应该输出:
INF源代码:
package 第八届蓝桥杯; import java.util.Arrays; import java.util.Scanner; public class 包子凑数 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int a[] = new int[N+1]; int b[] = new int[101]; //一种蒸笼能凑出的数集 int vis[] = new int[101];//标记能否凑出 //初始化 for(int i=0;i<101;i++){ vis[i]=0; } for(int i=0;i<N;i++){ a[i]=sc.nextInt(); } //只拿一种蒸笼 int k=0; for(int i=0;i<N;i++){ for(int j=1;j*a[i]<101;j++){ vis[j*a[i]]=1; b[k]=j*a[i]; k++; } } //多个蒸笼 for(int i=0;i<k;i++){ int temp1=0; int temp2=0; for(int j=i+1;j<k;j++){ temp1= b[i]+b[j]; temp2+=b[j]; if(temp1<101) vis[temp1]=1; if(temp2<101) vis[temp2]=1; } } //小于最小蒸笼的数不能凑出 Arrays.sort(a); for(int i=1;i<a[0];i++){ vis[i]=1; } int sum = 0; for(int i=1;i<101;i++){ if(vis[i]==0) { sum++; } } if((sum+a[0]-1)>=50) System.out.println("INF"); else System.out.println(sum); } }
9.分巧克力:
题目:
儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有N块巧克力,其中第i块是Hi x Wi的方格组成的长方形。
为了公平起见,小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足:
1. 形状是正方形,边长是整数
2. 大小相同
例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。
当然小朋友们都希望得到的巧克力尽可能大,你能帮小Hi计算出最大的边长是多少么?
输入
第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000)
输入保证每位小朋友至少能获得一块1x1的巧克力。
输出
输出切出的正方形巧克力最大可能的边长。
样例输入:
2 10
6 5
5 6
样例输出:
2
资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 1000ms
解题思路:使用二分法。
源代码:
import java.util.Scanner; public class 分巧克力 { static int k; static int n; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); k = sc.nextInt(); int [][] a = new int[100010][2]; for(int i=0; i<n; i++) { a[i][0] = sc.nextInt(); a[i][1] = sc.nextInt(); } int low = 1; int high = 10000; while(low < high-1) { int mid = (high+low)/2; if(slove(a, mid)) low = mid; else high = mid; } System.out.println(low); } private static boolean slove(int [][] a, int mid) { int sum = 0; for(int i=0; i<n; i++) { int h = a[i][0]/mid; int w = a[i][1]/mid; sum += h*w; } if(sum >= k) return true; return false; } }
10.K倍区间:
题目:
给定一个长度为N的数列,A1, A2, … AN,如果其中一段连续的子序列Ai, Ai+1, … Aj(i <= j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。
你能求出数列中总共有多少个K倍区间吗?
输入
-----
第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)
输出
-----
输出一个整数,代表K倍区间的数目。
例如,
输入:
5 2
1
2
3
4
5
程序应该输出:
6
资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 2000ms
import java.util.Scanner; public class K倍区间 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int [] a = new int[n]; for(int i=0; i<n; i++) { a[i] = sc.nextInt(); } int s = 0; for(int i=0; i<n; i++) { long sum = 0; for(int j=i; j<n; j++) { sum += a[j]; if(sum % k == 0) { s++; } } } System.out.println(s); } }
送一个python小程序:
官网地址:http://weike.lanqiao.cn
有兴趣的可以运行下。# -*- coding: utf-8 -*- import requests from bs4 import BeautifulSoup import json import re import os # 获取课程的章节名称和章节对应的视频列表url # course_id :课程id,1-30,经过测试1-26有值。 def get_course_list(course_id): course_url = 'http://weike.lanqiao.cn/course/getDayClassList.do' data = {'courseid': course_id} json_data = requests.post(course_url, data=data).text if len(json_data) == 0: return None, None course_info = json.loads(json_data) #f = open('course.txt', 'a+', encoding='utf-8') # f.write(json_data+'\n') # f.flush() # f.close() if len(course_info['list']) == 0: return None, None # coures_name: 存放课程名字 course_name = course_info['list'][0]['chap_name'] # 获取每个课程的章节列表 chap_list = [] #存放章节列表和每章url地址 for chap in course_info['list']: chap_info = { 'chap_name' : chap['day_classname'], 'chap_url' : chap['videourl']} chap_list.append(chap_info) return course_name, chap_list def get_class_video_url(chap): site_url = 'http://weike.lanqiao.cn/static//' chap_name = chap['chap_name'] chap_url = site_url + chap['chap_url'] r = requests.get(chap_url) bs = BeautifulSoup(r.text, 'html.parser') video_url = [] #存放视频课程链接 for video in bs.find_all('source'): url_pre = re.search(r'(.*)/content', chap_url).group(1) video_url.append(url_pre + video.get('src')[2:]) return chap_name, video_url # 下载文件,传输需要保存的路径和文件名 def download_file(video_url, path): #url = 'http://weike.lanqiao.cn/static///coursehuifang/LNZT JavaB/sources/2017-Java-B题0简要说明.mp4' file_name = video_url.split('/')[-1] print('开始下载【%s】' % file_name) print('视频地址:%s\n下载中...\n' % video_url) r = requests.get(video_url) with open(path + file_name, 'wb+') as f: f.write(r.content) f.flush() f.close() print('【%s】下载完成\n' % file_name) if __name__ == "__main__": # 下面数字可填1-27.代表不同的课程。 course_name, chap_list = get_course_list(21) if course_name == None: print('没有课程') else: print('课程名:' + course_name+'\n') if '/' in course_name: course_name = course_name.replace('/', ' ') for chap in chap_list: chap_name, video_url = get_class_video_url(chap) print(video_url) path = './' + course_name + '/' + chap_name + '/' if os.path.exists(path) == False: os.makedirs(path) for video in video_url: download_file(video, path)
更多相关内容 -
2018第九届蓝桥杯javaB组真题
2018-04-02 11:47:262018年第九届蓝桥杯javaB组真题。2018年第九届蓝桥杯javaB组真题。 -
第九届蓝桥杯 2018年国赛真题 (Java 大学B组)
2020-11-06 14:29:59蓝桥杯 2018年决赛 Java大学B组#1 三角形面积#2 最大乘积#3 全排列#4 整理玩具#5 版本分支#6 防御力 希望决赛题目不搞我 先挂 #1 三角形面积 本题满分: 13分 问题描述 已知三角形三个顶点在直角坐标系下的坐标...
希望决赛题目不搞我
先挂
#1 三角形面积
本题满分: 13分
问题描述
已知三角形三个顶点在直角坐标系下的坐标分别为:
(2.3, 2.5)
(6.4, 3.1)
(5.1, 7.2)求该三角形的面积。
答案提交
注意,要提交的是一个小数形式表示的浮点数。
要求精确到小数后3位,如不足3位,需要补零。
8.795
calcCode:
public class Test { public static void main(String[] args) { Point X = new Point(2.3, 2.5), Y = new Point(6.4, 3.1), Z = new Point(5.1, 7.2); double a = Point.distance(X, Y), b = Point.distance(X, Z), c = Point.distance(Y, Z), p = (a + b + c) / 2; System.out.printf("%.3f\n", Math.sqrt(p * (p - a) * (p - b) * (p - c))); } static class Point { double a, b; Point(double a, double b) { this.a = a; this.b = b; } static double distance(Point a, Point b) { return Math.sqrt((a.a - b.a) * (a.a - b.a) + (a.b - b.b) * (a.b - b.b)); } } }
海伦公式
#2 最大乘积
本题满分: 39分
问题描述
把 1~9 这9个数字分成两组,中间插入乘号,
有的时候,它们的乘积也只包含1~9这9个数字,而且每个数字只出现1次。比如:
984672 * 351 = 345619872
98751 * 3462 = 341875962
9 * 87146325 = 784316925
…符合这种规律的算式还有很多,请你计算在所有这些算式中,乘积最大是多少?
答案提交
注意,需要提交的是一个整数,表示那个最大的积,不要填写任何多余的内容。
(只提交乘积,不要提交整个算式)
839542176
calcCode:
public class Test { public static void main(String[] args) { int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int add = 0, mul = 1, max = 0; for (int i = 0; i < 9; i++) { add += arr[i]; mul *= arr[i]; } do for (int i = 0, l = 0, r, v, a, m; i < 9; i++) { l = l * 10 + arr[i]; r = 0; for (int j = i + 1; j < 9; j++) r = r * 10 + arr[j]; v = l * r; if (v > max) { m = 1; a = 0; do { a += v % 10; m *= v % 10; } while ((v /= 10) > 0); if (m == mul && a == add) max = l * r; } } while (next(arr)); System.out.print(max); } static boolean next(int[] a) { int i = a.length - 2; while (i >= 0 && a[i] > a[i + 1]) i--; if (i < 0) return false; int j = i + 1, t = a[i]; while (j < a.length && a[j] > t) j++; a[i] = a[j - 1]; a[j - 1] = t; java.util.Arrays.sort(a, i + 1, a.length); return true; } }
声明一下,少了一步效验
不优雅,但实用
#3 全排列
本题满分: 27分
问题描述
对于某个串,比如:“1234”,求它的所有全排列。
并且要求这些全排列一定要按照字母的升序排列。
对于“1234”,应该输出(一共4!=24行):1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321
下面是实现程序,请仔细分析程序逻辑,并填写划线部分缺少的代码。
// 轮换前k个,再递归处理 import java.util.*; public class A { static void permu(char[] data, int cur){ if(cur==data.length-1){ System.out.println(new String(data)); return; } for(int i=cur; i<data.length; i++){ char tmp = data[i]; for(int j=i-1; j>=cur; j--) data[j+1] = data[j]; data[cur] = tmp; permu(data, cur+1); tmp = data[cur]; __________________________________________ ; data[i] = tmp; } } static void permu(String x){ permu(x.toCharArray(),0); } public static void main(String[] args){ permu("1234"); } }
答案提交
请注意:只需要填写划线部分缺少的内容,不要抄写已有的代码或符号。
for (int j =cur; j <i; j++) data[j] = data[j+1];
#4 整理玩具
时间限制: 1.0s 内存限制: 256.0MB 本题满分: 45 分
问题描述
小明有一套玩具,一共包含NxM个部件。这些部件摆放在一个包含NxM个小格子的玩具盒中,每个小格子中恰好摆放一个部件。
每一个部件上标记有一个0~9的整数,有可能有多个部件标记相同的整数。
小明对玩具的摆放有特殊的要求:标记相同整数的部件必须摆在一起,组成一个矩形形状。
如以下摆放是满足要求的:
00022 00033 44444 12244 12244 12233 01234 56789
以下摆放不满足要求:
11122 11122 33311 111111 122221 122221 111111 11122 11113 33333
给出一种摆放方式,请你判断是否符合小明的要求。
输入格式
输入包含多组数据。
第一行包含一个整数T,代表数据组数。 (1 <= T <= 10)
以下包含T组数据。
每组数据第一行包含两个整数N和M。 (1 <= N, M <= 10)
以下包含N行M列的矩阵,代表摆放方式。
输出格式
对于每组数据,输出YES或者NO代表是否符合小明的要求。
测试样例1
Input: 3 3 5 00022 00033 44444 3 5 11122 11122 33311 2 5 01234 56789 Output: YES NO YES
code:
import java.io.InputStream; import java.io.IOException; import java.io.PrintWriter; public class Main { public static void main(String[] args) throws IOException { InputReader in = new InputReader(System.in); PrintWriter out = new PrintWriter(System.out); int[][] map = new int[10][10]; int[] cnt = new int[128]; int c = in.nextInt(); while (c-- > 0) { for (int i = '0'; i <= '9'; i++) cnt[i] = 0; int n = in.nextInt(), m = in.nextInt(); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cnt[map[i][j] = in.nextChar()]++; boolean flag = true; agent: for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { if (map[i][j] == 0) continue; int col = i + 1, row = j + 1; int val = map[i][j]; while (col < n && map[col][j] == val) col++; while (row < m && map[i][row] == val) row++; if ((col - i) * (row - j) != cnt[val]) { flag = false; break agent; } for (int k = i; k < col; k++) for (int g = j; g < row; g++) if (map[k][g] != val) { flag = false; break agent; } else map[k][g] = 0; } out.println(flag? "YES": "NO"); } out.close(); } static class InputReader { InputStream in; int next, len; byte[] buff; InputReader(InputStream in) { this(in, 8192); } InputReader(InputStream in, int buffSize) { this.buff = new byte[buffSize]; this.next = this.len = 0; this.in = in; } int getByte() { if (next >= len) try { next = 0; len = in.read(buff); if (len == -1) return -1; } catch (IOException e) { e.fillInStackTrace(); } return buff[next++]; } int nextChar() { int c = getByte(); while (c <= 32 || c == 127) if (-1 == (c = getByte())) return -1; return c; } int nextInt() { int n = 0, c = nextChar(); boolean flag = true; if (c == '-') { c = getByte(); flag = false; } while(c >= '0' && c <= '9') { n = n * 10 + (c & 0xf); c = getByte(); } return flag? n: -n; } } }
#5 版本分支
时间限制: 1.0s 内存限制: 256.0MB 本题满分: 71 分
问题描述
小明负责维护公司一个奇怪的项目。这个项目的代码一直在不断分支(branch)但是从未发生过合并(merge)。
现在这个项目的代码一共有N个版本,编号1~N,其中1号版本是最初的版本。
除了1号版本之外,其他版本的代码都恰好有一个直接的父版本;即这N个版本形成了一棵以1为根的树形结构。如下图就是一个可能的版本树:
1 / \ 2 3 | / \ 5 4 6
现在小明需要经常检查版本x是不是版本y的祖先版本。你能帮助小明吗?
输入格式
第一行包含两个整数N和Q,代表版本总数和查询总数。
以下N-1行,每行包含2个整数u和v,代表版本u是版本v的直接父版本。
再之后Q行,每行包含2个整数x和y,代表询问版本x是不是版本y的祖先版本。
输出格式
对于每个询问,输出YES或NO代表x是否是y的祖先。
测试样例1
Input: 6 5 1 2 1 3 2 5 3 6 3 4 1 1 1 4 2 6 5 2 6 4 Output: YES YES NO NO NO
评测用例规模与约定
对于30%的数据,1 <= N <= 1000 1 <= Q <= 1000
对于100%的数据,1 <= N <= 100000 1 <= Q <= 100000
code:
import java.io.InputStream; import java.io.IOException; import java.io.PrintWriter; public class Main { static int[] link; public static void main(String[] args) throws IOException { InputReader in = new InputReader(System.in); PrintWriter out = new PrintWriter(System.out); int N = in.nextInt(), Q = in.nextInt(), u, v, w; link = new int[N + 1]; while (N-- > 1) { u = in.nextInt(); v = in.nextInt(); link[v] = u; } while (Q-- > 0) { v = in.nextInt(); w = in.nextInt(); if (v == 1) w = 1; else while (w != 1) { if (w == v) break; w = link[w]; } out.println(w == v? "YES": "NO"); } out.close(); } static class InputReader { InputStream in; int next, len; byte[] buff; InputReader(InputStream in) { this(in, 8192); } InputReader(InputStream in, int buffSize) { this.buff = new byte[buffSize]; this.next = this.len = 0; this.in = in; } int getByte() { if (next >= len) try { next = 0; len = in.read(buff); if (len == -1) return -1; } catch (IOException e) { e.fillInStackTrace(); } return buff[next++]; } int nextChar() { int c = getByte(); while (c <= 32 || c == 127) if (-1 == (c = getByte())) return -1; return c; } int nextInt() { int n = 0, c = nextChar(); boolean flag = true; if (c == '-') { c = getByte(); flag = false; } while(c >= '0' && c <= '9') { n = n * 10 + (c & 0xf); c = getByte(); } return flag? n: -n; } } }
用并查集硬搜吧,没有想到能在对数时间以内效验父节点内存不超限的数据结构
#6 防御力
时间限制: 1.0s 内存限制: 256.0MB 本题满分: 105 分
问题描述
小明最近在玩一款游戏。对游戏中的防御力很感兴趣。
我们认为直接影响防御的参数为“防御性能”,记作d,而面板上有两个防御值A和B,与d成对数关系,A=2d,B=3d(注意任何时候上式都成立)。
在游戏过程中,可能有一些道具把防御值A增加一个值,有另一些道具把防御值B增加一个值。
现在小明身上有n1个道具增加A的值和n2个道具增加B的值,增加量已知。现在已知第i次使用的道具是增加A还是增加B的值,但具体使用那个道具是不确定的,请找到一个字典序最小的使用道具的方式,使得最终的防御性能最大。
初始时防御性能为0,即d=0,所以A=B=1。
输入格式
输入的第一行包含两个数n1,n2,空格分隔。
第二行n1个数,表示增加A值的那些道具的增加量。
第三行n2个数,表示增加B值的那些道具的增加量。
第四行一个长度为n1+n2的字符串,由0和1组成,表示道具的使用顺序。0表示使用增加A值的道具,1表示使用增加B值的道具。输入数据保证恰好有n1个0,n2个1。
输出格式
对于每组数据,输出n1+n2+1行,前n1+n2行按顺序输出道具的使用情况,若使用增加A值的道具,输出Ax,x为道具在该类道具中的编号(从1开始)。若使用增加B值的道具则输出Bx。最后一行输出一个大写字母E。
测试样例1
Input: 1 2 4 2 8 101 Output: B2 A1 B1 E Explanation: 操作过程如下: 操作 d A B 初始 0 1 1 B2 2 4 9 A1 3 8 27 B1 log3(29) 2^(log3(29)) 29 可以证明,这个值是最大的。
测试样例2
Input: 3 0 7 11 13 000 Output: A1 A2 A3 E Explanation: 可见无论用什么顺序,A最后总为32,即d总为5,B总为243。
评测用例规模与约定
对于20%的数据,字符串长度<=10000;
对于70%的数据,字符串长度<=200000;
对于100%的数据,字符串长度<=2000000,输入的每个增加值不超过230。
code:
import java.io.InputStream; import java.io.IOException; import java.io.PrintWriter; import java.util.Arrays; import java.util.Comparator; public class Main { public static void main(String[] args) { InputReader in = new InputReader(System.in); PrintWriter out = new PrintWriter(System.out); int n1 = in.nextInt(), n2 = in.nextInt(); Props[] A = new Props[n1]; Props[] B = new Props[n2]; for (int i = 0; i < n1; i++) A[i] = new Props(i, in.nextInt()); for (int i = 0; i < n2; i++) B[i] = new Props(i, in.nextInt()); Arrays.sort(A, new Comparator<Props>() { public int compare(Props arg0, Props arg1) { return arg0.val == arg1.val? (arg0.id - arg1.id) : (arg0.val - arg1.val); } }); Arrays.sort(B, new Comparator<Props>() { public int compare(Props arg0, Props arg1) { return arg1.val == arg0.val? (arg0.id - arg1.id) : (arg1.val - arg0.val); } }); Comparator idcmp = new Comparator<Props>() { public int compare(Props arg0, Props arg1) { return arg0.id - arg1.id; } }; String line = in.nextLine().trim(); for (int i = 0, a = 0, b = 0, c, high = line.length(); i < high;) { int start = i; int end = i + 1; char key = line.charAt(start); while(end < high && line.charAt(end) == key) end++; i = end; if (end - start == 1) { if (key == '0') out.println("A" + (A[a++].id + 1)); else out.println("B" + (B[b++].id + 1)); } else { if (key == '0') { Arrays.sort(A, a, c = a + end - start, idcmp); while (a < c) out.println("A" + (A[a++].id + 1)); } else { Arrays.sort(B, b, c = b + end - start, idcmp); while (b < c) out.println("B" + (B[b++].id + 1)); } } } out.println("E"); out.close(); } static class Props { int id, val; Props(int id, int val) { this.id = id; this.val = val; } } static class InputReader { InputStream in; int next, len; byte[] buff; InputReader(InputStream in) { this(in, 8192); } InputReader(InputStream in, int buffSize) { this.buff = new byte[buffSize]; this.next = this.len = 0; this.in = in; } int getByte() { if (next >= len) try { next = 0; len = in.read(buff); if (len == -1) return -1; } catch (IOException e) { e.fillInStackTrace(); } return buff[next++]; } int getChar() { int c = getByte(); while (c != -1 && (c <= 32 || c == 127)) c = getByte(); return c; } int nextInt() { int n = 0, c = getChar(); boolean flag = true; if (c == '-') { c = getByte(); flag = false; } while (c >= '0' && c <= '9') { n = n * 10 + (c & 0xf); c = getByte(); } return flag? n: -n; } String nextLine() { StringBuilder res = new StringBuilder(); int c = getChar(); while (c != '\n') { res.appendCodePoint(c); c = getByte(); } return res.toString(); } } }
-
2018年蓝桥杯C/C++ B组与 JAVA B组 真题
2018-04-01 16:20:28新鲜出炉的2018蓝桥杯B组真题。先到先得!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! -
2018-蓝桥杯省赛-Java语言大学B组
2018-05-02 17:42:33蓝桥杯的试题,刚考了,拿了个省二,文件开头有惊喜哦。!!!值得下载。 -
第十三届蓝桥杯大赛软件组JAVA-A,B,C组省赛试题
2022-04-10 17:07:11内容概述:第十三届蓝桥杯大赛软件组JAVA-A,B,C组省赛试题。 注意:为了让更多人及时快速获得试题,现在试题现时进行 0 积分免费的下载,下载量提高后,系统会将积分随之上升,需要的请尽快下载。本试题包含A,B,C三... -
2018年省赛第九届蓝桥杯真题Java B组
2018-04-01 23:08:352018年4月1日省赛第九届蓝桥杯真题Java(B组),新鲜出炉 -
2019 第十届蓝桥杯Java省赛B组题目
2019-04-01 16:58:042019 第十届蓝桥杯Java省赛B组题目——河南赛区 -
2018省赛第九届蓝桥杯真题Java语言B组
2018-04-01 17:07:172018省赛第九届蓝桥杯真题Java语言B组;2018省赛第九届蓝桥杯真题Java语言B组;2018省赛第九届蓝桥杯真题Java语言B组;2018省赛第九届蓝桥杯真题Java语言B组; -
2019年第十届蓝桥杯省赛java B组题目
2019-03-24 15:05:192019年第十届蓝桥杯省赛java B组题目。 -
2018年蓝桥杯省赛B组Java真题
2020-09-19 23:28:37递增三元组 给定三个整数数组 A = [A1, A2, … AN], B = [B1, B2, … BN], C = [C1, C2, … CN], 请你统计有多少个三元组(i, j, k) 满足: 1. 1 , j, k 【输入格式】 第一行包含一个整数N。 第二行包含N个整数A1, ...1. 第几天
2000年的1月1日,是那一年的第1天。
那么,2000年的5月4日,是那一年的第几天?
注意:需要提交的是一个整数,不要填写任何多余内容。2. 方格计数
如图p1.png所示,在二维平面上有无数个1x1的小方格。
我们以某个小方格的一个顶点为圆心画一个半径为1000的圆。
你能计算出这个圆里有多少个完整的小方格吗?3. 复数幂
设i为虚数单位。对于任意正整数n,(2+3i)^n 的实部和虚部都是整数。
求 (2+3i)^123456 等于多少? 即(2+3i)的123456次幂,这个数字很大,要求精确表示。答案写成 “实部±虚部i” 的形式,实部和虚部都是整数(不能用科学计数法表示),中间任何地方都不加空格,实部为正时前面不加正号。(2+3i)^2 写成: -5+12i,
(2+3i)^5 的写成: 122-597i4. 测试次数
x星球的居民脾气不太好,但好在他们生气的时候唯一的异常举动是:摔手机。
各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试,并且评定出一个耐摔指数来,之后才允许上市流通。x星球有很多高耸入云的高塔,刚好可以用来做耐摔测试。塔的每一层高度都是一样的,与地球上稍有不同的是,他们的第一层不是地面,而是相当于我们的2楼。
如果手机从第7层扔下去没摔坏,但第8层摔坏了,则手机耐摔指数=7。
特别地,如果手机从第1层扔下去就坏了,则耐摔指数=0。
如果到了塔的最高层第n层扔没摔坏,则耐摔指数=n为了减少测试次数,从每个厂家抽样3部手机参加测试。
某次测试的塔高为1000层,如果我们总是采用最佳策略,在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢?
请填写这个最多测试次数。
5. 快速排序
以下代码可以从数组a[]中找出第k小的元素。
它使用了类似快速排序中的分治算法,期望时间复杂度是O(N)的。
请仔细阅读分析源码,填写划线部分缺失的内容。
#include <stdio.h> int quick_select(int a[], int l, int r, int k) { int p = rand() % (r - l + 1) + l; int x = a[p]; {int t = a[p]; a[p] = a[r]; a[r] = t;} 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 quick_select( _____________________________ ); //填空 else return quick_select(a, l, i - 1, k); } int main() { int a[] = {1, 4, 2, 8, 5, 7, 23, 58, 16, 27, 55, 13, 26, 24, 12}; printf("%d\n", quick_select(a, 0, 14, 5)); return 0; }
注意:只填写划线部分缺少的代码,不要抄写已经存在的代码或符号。
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 【输出格式】 一个整数表示答案 123456789101112 【样例输入】 3 1 1 1 2 2 2 3 3 3 【样例输出】 27
7. 螺旋折线
如图p1.png所示的螺旋折线经过平面上所有整点恰好一次。
对于整点(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) 123456789 【样例输入】 0 1 【样例输出】 3
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一行。 123456789 【输入样例】 7 10 2 0 1 0 10 10 10 10 1 9 1 100 3 100 3 【输出样例】 1 3
9. 全球变暖
你有一张某海域NxN像素的照片,".“表示海洋、”#"表示陆地,如下所示:
…
.##…
.##…
…##.
…####.
…###.
…其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升,科学家预测未来几十年,岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋),它就会被淹没。
例如上图中的海域未来会变成如下样子:
…
…
…
…
…#…
…
…####请你计算:依照科学家的预测,照片中有多少岛屿会被完全淹没。
【输入格式】 第一行包含一个整数N。 (1 <= N <= 1000) 以下N行N列代表一张海域照片。 照片保证第1行、第1列、第N行、第N列的像素都是海洋。 【输出格式】 一个整数表示答案。 12345678 【输入样例】 7 ....... .##.... .##.... ....##. ..####. ...###. ....... 【输出样例】 1
10. 乘积最大
给定N个整数A1, A2, … AN。请你从中选出K个数,使其乘积最大。
请你求出最大的乘积,由于乘积可能超出整型范围,你只需输出乘积除以1000000009的余数。
注意,如果X<0, 我们定义X除以1000000009的余数是负(-X)除以1000000009的余数。
即:0-((0-x) % 1000000009)【输出格式】 一个整数,表示答案。 12345678910 【输入样例】 5 3 -100000 -10000 2 100000 10000 【输出样例】 999100009 12345678910 再例如: 【输入样例】 5 3 -100000 -100000 -2 -100000 -100000 【输出样例】 -999999829
-
2018年省赛第九届蓝桥杯真题Java(B组)
2018-04-01 14:58:09这是2018年省赛第九届蓝桥杯真题Java(B组),新鲜出炉。。 -
2018年第九届蓝桥杯省赛C++B组和javaB组题目
2018-04-05 11:52:542018年第九届蓝桥杯省赛C++B组和javaB组题目,c++B组的部分题解可以看我的博客:https://blog.csdn.net/zuzhiang/article/details/79825178 -
第十三届蓝桥杯大赛软件赛省赛 Java 研究生组 赛题
2022-04-09 16:24:24第十三届蓝桥杯大赛软件赛省赛 Java 研究生组 赛题 研究生组、A组、B组、C组其实有些题应该都是一样的。免费分享、不要积分下载。 -
省赛国赛蓝桥杯C语言与java(B组)题库答案
2018-06-06 19:18:55省赛国赛蓝桥杯C语言与java(B组)题库答案,这是我参加蓝桥杯的时候整理出来的题库,很有帮助 -
2018年第九届蓝桥杯B组JAVA题解
2018-04-01 20:58:13我参加的B组 JAVA,整体感觉还行吧,只是比赛的时候出了点小意外。本来是下午1点钟结束的,因为提前了两分钟开始,然后到12点五十几的时候就交不了了,导致一个大题白白没交上去,当时心里有点炸。不过也没什么,...这是第一次参加蓝桥杯,应该也是最后一次。我参加的B组 JAVA,整体感觉还行吧,只是比赛的时候出了点小意外。本来是下午1点钟结束的,因为提前了两分钟开始,然后到12点五十几的时候就交不了了,导致一个大题白白没交上去,当时心里有点炸。不过也没什么,蓝桥杯这种比赛,就当是玩一下吧。然后就说说题目吧,水平有限,错了见谅。
第一题:
标题:第几天
2000年的1月1日,是那一年的第1天。那么,2000年的5月4日,是那一年的第几天?
注意:需要提交的是一个整数,不要填写任何多余内容。
这种题...直接口算吧。
我的答案:125
第二题 :
标题:方格计数
如图p1.png所示,在二维平面上有无数个1x1的小方格。
我们以某个小方格的一个顶点为圆心画一个半径为1000的圆。
你能计算出这个圆里有多少个完整的小方格吗?注意:需要提交的是一个整数,不要填写任何多余内容。
比赛的时候以为找到了规律:如果半径为R的话,那么所圈住的小正方形应该是[2 *(R-1)]^2。试了1,2,3都满足,然后就没多想,毕竟才第二个题目。
比赛完了才发现这式子有问题,R>根号2*(R-1)只有在R<4时才成立,唉,当时也没仔细看,就想当然的填了上去。写了个代码跑了一下,发现果然错了,还是太年轻啊...
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粘贴到记事本就可以看到结果了。结果就不贴了,太长了,刚刚粘贴的时候浏览器都卡了。反正思路应该不难,如果是c++的话,手写大数应该也还好,然后快速幂就不说了,算法基础。
看一下最右边的滚动滑轮感受一下数字规模。。。
第四题:
标题:测试次数
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
请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。这道题的话,比赛的时候为了节省时间直接O(N^3)暴力求解,虽然知道肯定不行,但想着花几分钟拿一部分分还是很划算的,之后有时间再优化,结果做着做着没时间了。下来又想了一下,可以先排序,然后以B数组为标杆,对于B的每一个元素Bi,统计A中比Bi小的元素,C中比Bi大的元素,然后相乘,最后把乘积累加起来。也不知道蓝桥的判题机怎么样,O(nlogn)对于1e5的数据规模,勉勉强强能过。
第七题
标题:螺旋折线
如图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
【输出样例】3
资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 1000ms
请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。这题考察的不是算法吧,就是思维,方法应该挺多的。我用的方法是把螺旋折线转变成一个个的同心正方形,像下面这样,
注意转化关系,转化之后就很标准了,非常好算。实在不行,分象限讨论,细心一点,肯定能做出来。
第八题
标题:日志统计
小明维护着一个程序员论坛。现在他收集了一份"点赞"日志,日志共有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比较。
第九题
标题:全球变暖
你有一张某海域NxN像素的照片,"."表示海洋、"#"表示陆地,如下所示:
.......
.##....
.##....
....##.
..####.
...###.
.......
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升,科学家预测未来几十年,岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋),它就会被淹没。
例如上图中的海域未来会变成如下样子:
.......
.......
.......
.......
....#..
.......
.......
请你计算:依照科学家的预测,照片中有多少岛屿会被完全淹没。
【输入格式】第一行包含一个整数N。 (1 <= N <= 1000)
以下N行N列代表一张海域照片。
照片保证第1行、第1列、第N行、第N列的像素都是海洋。
【输出格式】
一个整数表示答案。
【输入样例】
7
.......
.##....
.##....
....##.
..####.
...###.
.......
【输出样例】
1
资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 1000ms
请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。这题也是比较简单,几乎就是裸的dfs求联通分量,在求联通分量的时候做个标记,判断这个联通分量(岛屿)中是否存在不临海的陆地,存在的话,这样的联通分量(岛屿)才不会完全消失。
第十题
标题:堆的计数
我们知道包含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
请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。这题之前是在哪看到过,(好像是阿里)的面试题。比赛的时候就这道题没做出来,求个组合数就求炸了,乘法逆元想不起来了。这题应该是组合数加DP,之后有时间再看看吧。
总结:其实从上一届蓝桥杯开始,题目难度就慢慢上升了。今年的题目除了第一题,之后每一题想拿到满分都不是那么的容易,质量还行吧,摘掉了"暴力杯"的帽子。不过话说回来,蓝桥杯这种题目跟ACM,NOI,IOI这种级别的比赛,完全就是过家家了,蓝桥杯适合我这种菜鸡玩一玩,拿个奖还可以加点分,也挺好哈。
很少在csdn上写东西,也是第一次写这么多。emmm,就先说到这吧,蓝桥杯,再见了(应该不会再见了)。。。
-------4月9日更新----------
今天结果出来了,竟然水了个省一,又可以去水一下国赛了... ps:其实是想着终于能公费去北京旅游了
-
2019年第十届蓝桥杯国赛试题及解析(Java B组).docx
2021-12-07 17:28:172019年第十届蓝桥杯国赛试题及解析 -
蓝桥杯2011-2018国赛真题(Python,java,C)
2021-11-25 21:39:45包含2011年到2018年的蓝桥杯赛题,包括算法详解和相关文件 例如:评分标准、赛题数据、部分赛题解答等等相关文件 -
第十届蓝桥杯软件类省赛 Java 大学 B 组 题目以及详细解析
2020-12-21 13:35:56文章目录结果填空题ABCDE程序设计题FGHIJ 包含全部题目和解析以及AC代码,并确保代码正确性。 给参加蓝桥杯的小伙伴们...B 按子串长度从(1~n)对原字符串进行截取,并判断该字符串是否出现过,没有就把答案加一。 做 -
蓝桥杯大学B组JAVA 迷宫
2022-01-26 17:18:12(3)还需要一个数据结构Node来存储每一个可行点的坐标和行路方向 (4)要用BFS就需要一个队列 代码如下: import java.util.*; public class Main { public static void main(String[] args) { // TODO Auto-... -
2020 第十一届蓝桥杯Java国赛B组
2020-11-14 13:15:41蓝桥杯全国软件和信息技术专业人才大赛由工业和信息化部人才交流中心主办,包括北大、清华等在内的全国31个省市自治区1200多所院校参加,每年参赛人数超过30000人。 -
2019第十届蓝桥杯JavaB组题目
2019-03-24 16:16:20第十届蓝桥杯JavaB组题目(省赛) 、2019蓝桥杯JavaB组题目(省赛) -
2019第十届蓝桥杯B组题目
2019-03-24 19:11:432019年第十届蓝桥杯省赛B组题目、第十届蓝桥杯省赛本科B组赛题! -
2018年第九届蓝桥杯Java b组总结
2018-04-02 22:36:08原文点击打开链接2018年4月1日愚人节,我第一次参加了有关计算机算法类比赛“蓝桥杯”,这篇算是经验总结和题目回顾,水平有限,有不妥之处欢迎留言批评指正,也可以加QQ891465170交流~下面进入正题:第一题:第几天... -
第九届蓝桥杯Java真题B组
2018-04-08 09:00:4820180401 第九届蓝桥杯Java真题B组 ................. -
2018第九届蓝桥杯Java语言C组&答案(无第十题)
2018-04-18 16:46:15自己写的非正确答案 。2018第九届蓝桥杯Java语言C组&答案 -
2019第十届蓝桥杯JavaB组题目.zip
2019-06-18 16:08:022019第十届蓝桥杯JavaB组题目 -
2017蓝桥杯java B组承压计算
2021-01-20 02:52:03标题:承压计算 X星球的高科技实验室中整齐地堆放着某批珍贵金属原料。 每块金属原料的外形、尺寸完全一致,但重量不同。 金属材料被严格地堆放成金字塔形。 7 5 8 7 8 8 9 2 7 2 ...3 6 8 1 5 3 9 -
2018蓝桥杯java B组 方格计数
2020-04-09 23:36:30然后一分为二: 由图可见,利用勾股定理:矩形的长^2+宽 ^2=斜边 ^2 所以 我们只要保证:a^2+b ^2 ^2 就okay 答案: public class 方格计数 { public static void main(String[] args) { // TODO Auto-generated... -
第十一届蓝桥杯省赛C组Java试题
2020-10-18 10:15:23第十一届蓝桥杯第二次省赛C组Java试题,pdf格式可以复制。试题A: 约数个数;试题B: 寻找2020;试题C: 跑步锻炼;试题D: 平面分割;试题E: 七段码;试题F: 成绩统计;试题G: 单词分析;试题H: 数字三角形;试题I: ...