米鼠商城

多快好省,买软件就上米鼠网

最新项目

人才服务

靠谱的IT人才垂直招聘平台

2018年第九届蓝桥杯JavaB组决赛题

  • DDAlex
  • 9
  • 2020-11-14 10:45

题目1:三角形面积

已知三角形三个顶点在直角坐标系下的坐标分别为: (2.3, 2.5) (6.4, 3.1) (5.1, 7.2)

求该三角形的面积。

注意,要提交的是一个小数形式表示的浮点数。 要求精确到小数后3位,如不足3位,需要补零。

思路:

把这个三个点构造成一个矩形,入下图,通过观察不难发现,只需用矩形面积减去四周的三角形面积就可得出所求三角形面积。

public static void main(String[] args) {
   
   
        double c = 6.4 - 2.3;
        double h = 7.2 - 2.5;
        double s = c * h - c * (3.1 - 2.5) / 2 - (7.2 - 3.1) * (6.4 - 5.1) / 2 - h * (5.1 - 2.3) / 2;
        System.out.println(s); // 8.795000000000002
    }

题目2:最大乘积

把 1~9 这9个数字分成两组,中间插入乘号, 有的时候,它们的乘积也只包含1~9这9个数字,而且每个数字只出现1次。

比如: 984672 * 351 = 345619872 98751 * 3462 = 341875962 9 * 87146325 = 784316925 …

符合这种规律的算式还有很多,请你计算在所有这些算式中,乘积最大是多少?

注意,需要提交的是一个整数,表示那个最大的积,不要填写任何多余的内容。 (只提交乘积,不要提交整个算式)

思路:全排列

这题只要简单的全排列一下,然后检测就可得出结果。

public class Main {
   
   
    static int[] a = new int[]{
   
   1,2,3,4,5,6,7,8,9};
    static int ans = 0;
    public static void main(String[] args) {
   
   
        f(a, 0);
        System.out.println(ans); // 876943125
    }

    private static void f(int[] a, int k) {
   
   
        if(k == 9) {
   
   
            check();
            return;
        }

        for(int i = k; i < 9; i++) {
   
   
            int t = a[i];
            a[i] = a[k];
            a[k] = t;
            f(a, k + 1);
            t = a[i];
            a[i] = a[k];
            a[k] = t;
        }
    }

    private static void check() {
   
   
        int[] b = new int[9];
        b[8] = 9;
        int bz = 10;
        for(int i = 7; i >= 0; i--) {
   
   
            b[i] = b[i + 1] + a[i] * bz;
            bz *= 10;
        }

        int q = 0;
        for(int i = 0; i < 8; i++) {
   
   
            q = q * 10 + a[i];
            int z = q * b[i + 1];
            check1(z);
        }
    }

    private static void check1(int z) {
   
   
        boolean[] is = new boolean[10];
        int c = z;
        while(z > 0) {
   
   
            int cur = z % 10;
            if(!is[cur] && cur >= 1 && cur <= 9) is[cur] = true;
            else return;
            z /= 10;
        }
        ans = Math.max(ans, c);
    }
}

题目3:全排列

对于某个串,比如:“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”); }

}

请注意:只需要填写划线部分缺少的内容,不要抄写已有的代码或符号。

代码:

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]; 
            for(int j = cur-1; j >= i; j--) data[j + 1] = data[j];
			// __________________________________________ ;
			data[i] = tmp;			
		}
	}
	
	static void permu(String x){
   
   
		permu(x.toCharArray(),0);
	}
	
	public static void main(String[] args){
   
   
		permu("1234");
	}
}

题目4:整理玩具

小明有一套玩具,一共包含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代表是否符合小明的要求。

【样例输入】 3 3 5 00022 00033 44444 3 5 11122 11122 33311 2 5 01234 56789

【样例输出】 YES NO YES

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

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

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

思路:

遍历整个矩阵,每遇到一个数,就检查一遍是否符合要求,然后将这个数标记为已检查(其它地方不能在出现这个数)。

算法

  • 找到与这个数相同的最大的长宽
  • 在这个矩阵里检查是否存在其它数字,如果存在则返回false
  • 当这个矩阵都检查完之后还没有返回false,则返回true
  • 在检查的时候将所有检查了的点都打上记号
public class Main {
   
   

    private static int n;
    private static int m;

    public static void main(String[] args) {
   
   
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for(int i = 0; i < t; i++) {
   
   
            n = sc.nextInt();
            m = sc.nextInt();
            sc.nextLine();
            char[][] a = new char[n][m];
            for(int j = 0; j < n; j++) {
   
   
                a[j] = sc.nextLine().toCharArray();
            }
            System.out.println(check(a));
        }
    }

    private static boolean check(char[][] a) {
   
   
        boolean[][] is = new boolean[n][m];
        boolean[] isc = new boolean[10];

        for(int i = 0; i < n; i++) {
   
   
            for(int j = 0; j < m; j++) {
   
   
                if(!is[i][j]) {
   
   
                    if(isc[a[i][j] - '0']) return false;
                    isc[a[i][j] - '0'] = true;
                    if(check(is, a, i, j)) return false;
                }
            }
        }
        return true;
    }

    public static boolean check(boolean[][] is, char[][] a, int x, int y) {
   
   
        char t = a[x][y];
        int c = y;
        while(c < m && a[x][c] == t) c++;
        int h = x;
        while(h < n && a[h][y] == t) h++;
        for(int i = x; i < h; i++) {
   
   
            for(int j = y; j < c; j++) {
   
   
                is[i][j] = true;
                if(a[i][j] != t) return true;
            }
        }
        return false;
    }
}

题目5:版本分支

小明负责维护公司一个奇怪的项目。这个项目的代码一直在不断分支(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的祖先版本。

对于30%的数据,1 <= N <= 1000 1 <= Q <= 1000 对于100%的数据,1 <= N <= 100000 1 <= Q <= 100000

输出

对于每个询问,输出YES或NO代表x是否是y的祖先。

【样例输入】 6 5 1 2 1 3 2 5 3 6 3 4 1 1 1 4 2 6 5 2 6 4

【样例输出】 YES YES NO NO NO

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

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

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

思路:时间上会超

通过输入的数据生成一棵树,每个子节点都指向它的父节点,执行查找操作的时候就通过子节点往上找,看是否找得到父节点。

但当整棵树形成一条链时(当这棵树的高度过高时),会超时

我也在网上查了一些题解,大多数在空间上回超。

public class Main {
   
   
    public static void main(String[] args) {
   
   
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] tree = new int[n + 1];
        tree[1] = 1;
        int q = sc.nextInt();
        int x, y, t;
        for(int i = 1; i < n; i++) {
   
   
            x = sc.nextInt();
            y = sc.nextInt();
            tree[y] = x;
        }

        for(int i = 0; i < q; i++) {
   
   
            x = sc.nextInt();
            y = sc.nextInt();
            if(x == 1) System.out.println("YES");
            else {
   
   
                while(y != 1) {
   
   
                    if(y == x){
   
   
                        System.out.println("YES");
                        break;
                    }
                    y = tree[y];
                }
                if(y == 1) System.out.println("NO");
            }
        }
    }
}

题目6:防御力

小明最近在玩一款游戏。对游戏中的防御力很感兴趣。 我们认为直接影响防御的参数为“防御性能”,记作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】 1 2 4 2 8 101

【样例输出1】 B2 A1 B1 E

【样例输入2】 3 0 7 11 13

000

【样例输出2】 A1 A2 A3 E

【样例说明】 对于第一组测试数据,操作过程如下: 操作 d A B 初始 0 1 1 B2 2 4 9 A1 3 8 27 B1 log3(29) 2^(log3(29)) 29

可以证明,这个值是最大的。 对于第二组测试数据,可见无论用什么顺序,A最后总为32,即d总为5,B总为243。

【数据规模】 对于20%的数据,字符串长度<=10000; 对于70%的数据,字符串长度<=200000; 对于100%的数据,字符串长度<=2000000,输入的每个增加值不超过2^30。

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

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

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

思路:贪心

贪心的证明并不是那么好证明,简单写了一下,把B从大到小排,把A从小到达大排就是答案了。

public class Main {
   
   
    public static void main(String[] args) {
   
   
        long start = System.currentTimeMillis();
        Scanner sc = new Scanner(System.in);
        int n1 = sc.nextInt();
        int n2 = sc.nextInt();

        int[][] a = new int[n1][2];
        int[][] b = new int[n2][2];
        for(int i = 0; i < n1; i++) {
   
   
            a[i][0] = sc.nextInt();
            a[i][1] = i + 1;
        }
        sc.nextLine();
        for(int i = 0; i < n2; i++) {
   
   
            b[i][0] = sc.nextInt();
            b[i][1] = i + 1;
        }
        sc.nextLine();

        String s = sc.nextLine();

        Arrays.sort(a, (o1, o2) -> {
   
   
            double o11 = Math.log(o1[0] + 1) / Math.log(2);
            double o22 = Math.log(o2[0] + 1) / Math.log(2);
            if(o11 == o22) return 0;
            else if(o11 > o22) return 1;
            else return -1;
        });
        Arrays.sort(b, (o1, o2) -> {
   
   
            double o11 = Math.log(o1[0] + 1) / Math.log(3);
            double o22 = Math.log(o2[0] + 1) / Math.log(3);
            if(o11 == o22) return 0;
            else if(o11 > o22) return -1;
            else return 1;
        });

        int n = n1 + n2;
        StringBuilder[] ans = new StringBuilder[n];
        int i1 = 0;
        int i2 = 0;
        for(int i = 0; i < n; i++) {
   
   
            ans[i] = new StringBuilder();
            if(s.charAt(i) == '0') {
   
   
                ans[i].append("A").append(a[i1++][1]);
            }else {
   
   
                ans[i].append("B").append(b[i2++][1]);
            }
        }
        for (StringBuilder x :
                ans) {
   
   
            System.out.println(x);
        }
        System.out.println("E");
        System.out.println(System.currentTimeMillis() - start);
    }
}


城市合伙人全球招募中:400-150-9800

参与线下宏伟蓝图,用业绩说话!
软件线索、软件需求,米鼠网帮你变现!
更灵活的合作模式(不限地域、不限金额、不限项目)
更高额的提成比例(提成是软件项目利润的80%)
利润的核算方式:
以平台公开招标的最低价中标价格为基准,剩下的为利润部分,如对平台的最低中标价格有异议,可以推荐供应商进行竞标。
义务:
1、作为城市合伙人,在该城市利用自身优势推广“米鼠网平台”,拓展甲 方所拥有的“米鼠网平台”实名认证用户和 VIP 用户
2、作为城市合伙人,在该城市利用自身优势推广“米鼠网商城”,并寻求该地域软件产品销售商,促成软件产品销售商委托甲方在“米鼠网商城”上代理销售软件产品销售商的软件产品的交易,并拓展软件产品采购用户促成与甲方的采购交易。



如有侵权请联系邮箱(service@misuland.com)

猜你喜欢

评论留言