资讯专栏INFORMATION COLUMN

2018第九届蓝桥杯Java b组总结

codecook / 716人阅读

摘要:现在小明想统计有哪些帖子曾经是热帖。如果一个帖子曾在任意一个长度为的时间段内收到不少于个赞,小明就认为这个帖子曾是热帖。以下行列代表一张海域照片。照片保证第行第列第行第列的像素都是海洋。

2018年4月1日愚人节,我第一次参加了有关计算机算法类比赛“蓝桥杯”,这篇算是经验总结和题目回顾,水平有限,有不妥之处欢迎留言批评指正,也可以加QQ891465170交流~
下面进入正题:
第一题:第几天
2000年的1月1日,是那一年的第1天。 那么,2000年的5月4日,是那一年的第几天?

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

哈哈这激动的啊,太简单直接脑算,结果坑爹了,我把闰年二月记成28天普通年29天,直接错了,送分题都没拿到。

解法:2000年是闰年二月有29天,一月和三月有31天,四月有30天,所以:
31+29+31+30+4=125
第二题:方格记数
如图p1.png所示,在二维平面上有无数个1x1的小方格。

我们以某个小方格的一个顶点为圆心画一个半径为1000的圆。 你能计算出这个圆里有多少个完整的小方格吗?

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

这个题不太会做,计算出这个圆的内接正方形编成为1000sqrt(2)=1414,正方形中方格个数为14141414,关键在于正方形外不会计算。

第三题:复数幂
设i为虚数单位。对于任意正整数n,(2+3i)^n 的实部和虚部都是整数。 求 (2+3i)^123456 等于多少?
即(2+3i)的123456次幂,这个数字很大,要求精确表示。

答案写成 "实部±虚部i"
的形式,实部和虚部都是整数(不能用科学计数法表示),中间任何地方都不加空格,实部为正时前面不加正号。(2+3i)^2 写成: -5+12i,
(2+3i)^5 的写成: 122-597i

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

这个好办,写段程序,把实部和虚部存储,连乘123456次,即循环123456次

public class T3 {

    public static void main(String[] args) {
        int a = 2, b = 3;
        
        for(int i = 1; i<123456; i++){
            int temp = 2*a-3*b;
            b = 3*a+2*b;
            a = temp;
        }
        System.out.println(a+"+"+b+"i");
    }

}
答案:13483137+1100011648i

这题更正一下,由于是大数运算使用int类型当然是不行的,哎,第一次遇到这么大数运算也是无奈,使用BigInteger类型。

import java.math.BigInteger;

public class T3 {

    public static void main(String[] args) {
         BigInteger a = new BigInteger("2");
         BigInteger b = new BigInteger("3");
         BigInteger a1 = new BigInteger("2");
         BigInteger b1 = new BigInteger("3");
         BigInteger temp;
        for(int i = 1; i<123456; i++){
            temp = a.multiply(a1).subtract(b.multiply(b1));
            b = a.multiply(b1).add(b.multiply(a1));
            a = temp;
        }
        if(b.compareTo(BigInteger.valueOf(0))>0){
            System.out.println(a+"+"+b+"i");
        }else{
        System.out.println(a+""+b+"i");
        }
    }

}

如果在eclipse中输出会得到一个--i的东西,是一个 超长字符串,使用cmd控制台输出结果为:感受一下吧~

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

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

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

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

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

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

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

这个也简单,使用二分查找,最坏情况是1000层也不坏
二分查找算法代码如下:

public class T4 {

    public static void main(String[] args) {
        
        int x = 0, y=1000;
        int m = 0,count=0;
        while(y-x>1){
            m = x+(y-x)/2;
            if(m<1000) x = m;
            else y = m;
            count++;
        }
        System.out.println(count);
    }

}
答案:10
第五题:快速排序
以下代码可以从数组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));
    }
}
一个分治法进行快速排序 分治法三步
1.将问题分成尽量左右相等的左右两半
2.递归求解左右两半
3.合并左右两半问题和当前问题比较 熟悉的话一眼看出,这个也简单

答案:a,i,r,k

第六题:递增三元组

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

1 <= i, j, k <= N

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,否则按无效代码处理。

这个题我就比较坑了,程序设计

暴力求解做法

int count = 0;
for(int i = 0; i

时间复杂度为O(n^3),必定超时!
我的思路使用子列生成算法使用增量法生成长度为3的子列
假设数组A,B,C已经构造完成

public class Main{
    public void static main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int tlength = 0;
        int[] tuple = new int[n*3];
        int[] temp = new int[n*3];
        int[] count = {0};  //记录有多设个满足条件的三元组
        
        //根据输入构造ABC
        ...
        //构造一个下标数组{0,0,0,1,1,1,2,2,2,...,n-1,n-1,n-1}
        for(int i = 0; i3) return;
        if(cur==3){
            if(a[tuple[[temp[0]]]

时间复杂度:O(nlogn)
悲剧的是debug好久答案不正确,经验不足,时间比较紧张,导致后面几道题时间不够。

第七题:螺旋折线
如图所示的螺旋折线经过平面上所有整点恰好一次。   对于整点(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

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

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

观察后不难发现,可以看成每一步走一个折线,奇数步左上(x-n,y)(x-n,y+n),偶数步右下(x+n,y)(x+n,y-n),n为步数,在走的过程中判断最后加一个统计变量即可

import java.util.Scanner;

public class T7 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        boolean ok = false;
        int x1 = 0, y1 = 0,m=0,count=0;
        
        while(!ok){
            if(x1==x&&y1==y){
                ok = true;
                break;
            }
            m++;
            if(m%2==1){//奇数步
                for(int i = 0; i

第八题:日志统计
小明维护着一个程序员论坛。现在他收集了一份"点赞"日志,日志共有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

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

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

也不难,获取日志数组,构造HashMap统计最后判断满足k输出即可.
这里代码不在贴出。

第九题:全球变暖
你有一张某海域NxN像素的照片,"."表示海洋、"#"表示陆地,如下所示:

....... .##.... .##.... ....##. ..####. ...###. .......

其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。

由于全球变暖导致了海面上升,科学家预测未来几十年,岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋),它就会被淹没。

例如上图中的海域未来会变成如下样子:

....... ....... ....... ....... ....#.. ....... .......

请你计算:依照科学家的预测,照片中有多少岛屿会被完全淹没。

【输入格式】 第一行包含一个整数N。 (1 <= N <= 1000) 以下N行N列代表一张海域照片。

照片保证第1行、第1列、第N行、第N列的像素都是海洋。

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

【输入样例】 7
.......
.##....
.##....
....##.
..####.
...###.
.......

【输出样例】 1

资源约定: 峰值内存消耗(含虚拟机) < 256M CPU消耗 < 1000ms

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

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

不太会,主要基础不好,是一个图问题,对图不太熟悉,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

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

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

估计涉及到动态规划,没什么思路。
后续继续跟新!

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/68911.html

相关文章

  • 大学这么多比赛,我该参加哪个?

    摘要:针对计算机类的同学,数学建模,电子科技大赛,大创,,蓝桥杯这些都是值得参加的高含金量的比赛,无论是学校加分还是应届招聘,都被广泛认可。但近几届的蓝桥杯题目难度已经明显增大,准备参加的同学也决不可掉以轻心。 ...

    不知名网友 评论0 收藏0
  • 2015年第6届蓝桥Java B省赛试题解析

    摘要:比如,其循环节为共有位。答案牌型种数小明被劫持到赌城,被迫与其他人玩牌。还有另外一种写法主要的思路是假设牌是从到按顺序取的,表示取到牌数为的牌,表示目前一共取了多少张牌。 1、三角形面积 如图1所示。图中的所有小方格面积都是1。那么,图中的三角形面积应该是多少呢?请填写三角形的面积。不要填写任何多余内容或说明性文字。 showImg(https://segmentfault.com/i...

    felix0913 评论0 收藏0
  • 蓝桥-乌托邦树

    摘要:传送门题目描述实现一个算法得到乌托邦树的高度介绍如下乌托邦树每年经历个生长周期。每年夏天,它的高度都会增加米。对于一颗在春天开始时种下的高米的树,问经过指定周期后,树的高度为多少。输入描述输入一个数字,表示指定周期。 ...

    caiyongji 评论0 收藏0
  • 2021蓝桥你值得拥有

    摘要:文章目录一你应该知道的蓝桥杯含金量获奖率高不高支持哪些编程语言二川川带你体验蓝桥杯省赛蓝桥杯蓝桥杯三个人感受一你应该知道的蓝桥杯如果你是计算机相关专业,你不知蓝桥杯就过不去了,我们来看看蓝桥杯如何,不知道更应该来了解下了。 ...

    fanux 评论0 收藏0
  • 蓝桥 算法训练 审美课 java

    摘要:问题描述审美的历程课上有位学生,帅老师展示了幅画,其中有些是梵高的作品,另外的都出自五岁小朋友之手。输入格式第一行两个数和,表示学生数和图画数接下来是一个的矩阵如果,表示学生觉得第幅画是小朋友画的如果,表示学生觉得第幅画是梵高画的。 问题描述  《审美的历程》课上有n位学生,帅老师展示了m幅画,其中有些是梵高的作品,另外的都出自五岁小朋友之手。老师请同学们分辨哪些画的作者是梵高,但是老...

    worldligang 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<