蓝桥杯部分题解（java）

蓝桥杯部分题解（java）

蓝桥杯部分题解（java）

• 耐摔指数
• excel地址
• 日期问题
• 整数划分
• 一步之遥
• 机器人塔
• 七星填空

耐摔指数

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

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

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

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

如果已知了测试塔的高度，并且采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？

输入

输入数据，一个整数n（3 
题解：
 视频题解------>测试次数
 
首先要明白求最差运气啊，最佳次数啊一般考虑贪心算法和动态规划问题。
 而且由于手机个数有限所以不能使用二分法，若是手机个数无限可以考虑二分。
 首先要明白动态规划其实就是一个递推 的过程，即你只有把前面的推出来之后才可以知道后面的。
 所以我们可以先推推看规律
 即：
 1部手机很好理解
 当有2部手机时，在1层，2层，3层也很好理解
 
 
当手机个数为2时，前几层比较好计算。
 而当层数为4时，对于2部手机，有以下情况：
 
 
左边的1,2,3,4为代表第一次从第几层开始扔，由于题目要求，“最差运气”，“最佳策略”，所以由此可知，最佳策略即从以上第一次分别第几层扔的四种方法里找一个次数最少的，而最差运气又使每一个策略我都只能保存下来次数最多的那个，即不会出现类似“一步到位”的情况。
 所以二者结合便是为在四种策略的每个策略的最大次数里找其中最小的次数，即为在蓝色文字中找次数最少的。
 并且注意的是动态规划就是一种递推问题，所以意思为在求第三项时要用到第二项的内容，求第二项要用到第一项的内容。而求第三项时第二项肯定已经求过了，求第二项时也已经将第一项求过了。
 所以上述可求出答案。
 所以我们可先得到几个类推公式：
 我们设f1[n]中1代表为有1个手机时，n为1~1000中一个层数
 所以有f1[n]=n；
 设i为从1开始的，n为我们要求的那个1~1000中的某个层数
 则f2[n]=min(for i in n :max(1+f2[n-i],1+f1[i-1]))
 这里for i in n 意思就是我们上述图2的意思，即在n层时我们有很多策略，他们分别为在i=1层先扔一个，i=2层先扔一个… i为我们开始扔的时候的层数
 
这恰恰就是我原先所谈到的动态规划其实就是递推问题，要求1000层的情况，必须先求出999层的情况，999层要由998层得出，所以可知我们要每一个都求出来才可以。
 
所以我们也可以知道：
 f3[n]=min(for i in n :max(1+f3[n-i],1+f2[i-1]))
 知道这个表达式后就可以以此为根据编写代码：
 
public class Test {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        int[][] dp = new int[4][n+1];
        for(int i=1;i<=n;i++){
            dp[1][i] = i;
        }

        for(int i=1;i<=n;i++){
            int val = Integer.MAX_VALUE;
            for(int j=1;j<=i;j++){
                int temp = 1 + Math.max(dp[2][i-j],dp[1][j-1]);
                val = Math.min(val,temp);
            }
            dp[2][i] = val;
        }

        for(int i=1;i<=n;i++){
            int val = Integer.MAX_VALUE;
            for(int j=1;j<=i;j++){
                int temp = 1 + Math.max(dp[3][i-j],dp[2][j-1]);
                val = Math.min(val,temp);
            }
            dp[3][i] = val;
        }

        System.out.println(dp[3][n]);
    }
}
 
excel地址 
问题描述
 　　Excel单元格的地址表示很有趣，它使用字母来表示列号。
 　　比如，
 　　A表示第1列，
 　　B表示第2列，
 　　Z表示第26列，
 　　AA表示第27列，
 　　AB表示第28列，
 　　BA表示第53列，
 　　…
 　　
 　　当然Excel的最大列号是有限度的，所以转换起来不难。
 　　如果我们想把这种表示法一般化，可以把很大的数字转换为很长的字母序列呢？
 　　本题目即是要求对输入的数字, 输出其对应的Excel地址表示方式。
 
样例输入
　　26

样例输出
　　Z

样例输入
　　2054

样例输出
　　BZZ
 
题解：
 本题其实就是一个进制转换的问题，在于如何把正常的十进制转换为1-26的26进制即可。
 
class Test6 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        String str="";
        while (num != 0)
        {
            //判断是否整除
            if (num % 26 == 0)
            {
                str = (char)(26 + 64)+str;
                num -= 1;
            }
            else
            {
                str = (char)(num % 26 + 64)+str;
            }
            num /= 26;
        }
        //输出Excel
        System.out.print(str);
    }
}
 
日期问题 
问题描述
 　　小明正在整理一批历史文献。这些历史文献中出现了很多日期。小明知道这些日期都在1960年1月1日至2059年12月31日。令小明头疼的是，这些日期采用的格式非常不统一，有采用年/月/日的，有采用月/日/年的，还有采用日/月/年的。更加麻烦的是，年份也都省略了前两位，使得文献上的一个日期，存在很多可能的日期与其对应。
 
比如02/03/04，可能是2002年03月04日、2004年02月03日或2004年03月02日。
 
给出一个文献上的日期，你能帮助小明判断有哪些可能的日期对其对应吗？
 
输入格式
　　一个日期，格式是"AA/BB/CC"。 (0 <= A, B, C <= 9)
输出格式
　　输出若干个不相同的日期，每个日期一行，格式是"yyyy-MM-dd"。多个日期按从早到晚排列。
样例输入
02/03/04
样例输出
2002-03-04
2004-02-03
2004-03-02
 
题解：
 注意一下闰年和平年的判断，对月日满足条件的判断，对日期判重，要对结果进行从早到晚排序，在输入时如何保证前导0的输出即可。
 
class Test7 {
    public static TreeSet set = new TreeSet();
    public static List list =new ArrayList();
    public static void f(String year,String mon,String day) {
        int y = Integer.parseInt(year);
        int m = Integer.parseInt(mon);
        int d = Integer.parseInt(day);
        if(y<=59) {
            y+=2000;
        }else {
            y+=1900;
        }
        if(((y%4==0&&y%100!=0)||y%400==0) && m==2 && d>0 && d<=29) {
            set.add(Integer.parseInt(""+y+mon+day));
        }
        if(y%4!=0 && m==2 && d>0 &&d<=28) {
            set.add(Integer.parseInt(""+y+mon+day));
        }
        if((m==1||m==3||m==5||m==7||m==8||m==10||m==12) && d>0 && d<=31) {
            set.add(Integer.parseInt(""+y+mon+day));
        }
        if((m==4|| m==6|| m==9|| m==11) && d>0&&d<=30) {
            set.add(Integer.parseInt(""+y+mon+day));
        }

    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        String[] s =str.split("/");
        f(s[0],s[1],s[2]);
        f(s[2],s[0],s[1]);
        f(s[2],s[1],s[0]);
        list.addAll(set);
        for(int i=0;i 
整数划分 
题目内容：
 对于一个正整数n的划分，就是把n变成一系列正整数之和的表达式。注意，分划与顺序无关，例如6=5+1.跟6=1+5是同一种分划，另外，这个整数本身也是一种分划。
 例如：，对于正整数n=5，可以划分为：
 1+1+1+1+1
 1+1+1+2
 1+1+3
 1+2+2
 2+3
 1+4
 5
 
输入描述
输入一个正整数n

输出描述
输出n整数划分的总数k

输入样例
5

输出样例
7
 
题解：
 明显是一个递推问题，我们直接递归即可；
 
class Test2{
    public static void main(String[] args) {
        int n;
        int sum;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        sum = resolve(n,n);
        System.out.println(sum);
    }

    public static int resolve(int a,int max) {
        if(a == 1||max ==1)
            return 1;
        if(a == max)
            return resolve(a,max-1)+1;
        if(a > max)
            return resolve(a,max-1)+resolve(a-max,max);
        if(a < max)
            return resolve(a,a);
        else return 0;
    }

}
 
一步之遥 
题目描述
 从昏迷中醒来，小明发现自己被关在X星球的废矿车里。
 矿车停在平直的废弃的轨道上。
 他的面前是两个按钮，分别写着“F”和“B”。
 小明突然记起来，这两个按钮可以控制矿车在轨道上前进和后退。
 按F，会前进97米。按B会后退127米。
 透过昏暗的灯光，小明看到自己前方1米远正好有个监控探头。
 他必须设法使得矿车正好停在摄像头的下方，才有机会争取同伴的援助。
 或许，通过多次 *** 作F和B可以办到。矿车上的动力已经不太足，黄色的警示灯在默默闪烁…
 每次进行 F 或 B  *** 作都会消耗一定的能量。
 小明飞快地计算，至少要多少次 *** 作，才能把矿车准确地停在前方1米远的地方。
 
请填写为了达成目标，最少需要 *** 作的次数。注意，需要提交的是一个整数，不要填写任何无关内容（比如：解释说明等）
 题解：
 我们直接暴力解方程求x+y最小即可；
 
class Test3{
    public static void main(String[] args) {
        int res = Integer.MAX_VALUE;
        for(int x = 0; x < 100; x++){
            for(int y = 0; y < 100; y++){
                if(x*97 - y*127 == 1){
                    res = Math.min(x+y,res);
                }
            }
        }

        System.out.println(res);
    }
}
 
机器人塔 
机器人塔
 X星球的机器人表演拉拉队有两种服装，A和B。
 他们这次表演的是搭机器人塔。
 
类似：
 
A
 B B
 A B A
 A A B B
 B B B A B
 A B A B B A
 队内的组塔规则是：
 
A 只能站在 AA 或 BB 的肩上。
 B 只能站在 AB 或 BA 的肩上。
 
你的任务是帮助拉拉队计算一下，在给定A与B的人数时，可以组成多少种花样的塔。
 
输入一行两个整数 M 和 N，空格分开（0 
要求输出一个整数，表示可以产生的花样种数。
 
例如：
用户输入：
1 2

程序应该输出：
3

再例如：
用户输入：
3 3

程序应该输出：
4

资源约定：
峰值内存消耗 < 256M
CPU消耗 < 1000ms
 
题解：
 如果我们从上面开始往下面走，这时候，每走一步需要判断下一步是需要放A还是放B，在每一步的时候都有两种选择，第二种情况，我们从最底下往上面分析，我们只需要将最后一层安排好之后，上面的层数一定是固定的，因为A和A，B和B的上面只能放A，A和B的上面只能放B，这样的话，每一步我们只需要判断当前如果这一步放A或者放B的时候会不会发生A或者B不够的问题。因此选择第二种走法。
 我们将A当做0，B当做1，这时候我们只需要将最下面一层的情况尽数遍历一下就行，也就是从0000000…到1111111111，即全零到全一的所有情况。
 重点：在自下而上的时候，我们判断每一点的时候，如果使用if else的话会看着比较繁琐，这时候一个巧妙的点就是使用异或运算，如果 0 和 1 异或是1 ，1和1， 0 和 0 异或的结果都是零，这样的话效率会高很多。
 
class Test5 {
    public static int shu[][];
    public static int a,b,num = 0;
    public static void main(String[] args) {
        Scanner input= new Scanner(System.in);
        a = input.nextInt();
        b = input.nextInt();
        int all = (a+b)*2;
        int t = 1;
        for (int i = 1; i < 100000; i++) {
            if (i*i+i == all) {
                t =i;
                break;
            }
        }
        shu = new int[t][t];
        dfs(0);
        System.out.println(num);
    }
    public static void dfs(int index) {
        if (index == shu.length) {//现在已经完成了一种状态
            if (check()) {
                num++;
            }
            return;
        }
        int next[]= {0,1};
        int tx;
        for (int i = 0; i < next.length; i++) {
            tx = next[i];
            shu[shu.length-1][index] = tx;
            dfs(index+1);
            shu[shu.length-1][index] = 0;
        }
    }
    public static boolean check() {
        int count[] =new int[2];//0代表a，1代表b
        for (int i = shu.length-1; i < shu.length; i++) {
            for (int j = 0; j < shu.length; j++) {
                count[shu[i][j]]++;
                if (count[0] > a || count[1] > b) {
                    return false;//说明此时已经不够了
                }
            }
        }
        for(int i = shu.length-2;i >= 0;i--) {
            for (int j = 0; j <= i; j++) {
                shu[i][j] = shu[i+1][j]^shu[i+1][j+1];
                count[shu[i][j]]++;
                if (count[0] > a || count[1] > b) {
                    return false;//说明此时已经不够了
                }
            }
        }
        if (count[0] == a && count[1] == b)  {
            return true;
        }else {
            return false;
        }
    }
}
 
七星填空 
七星填数
 
如图【图1.png】所示。
 
在七角星的14个节点上填入1~14 的数字，不重复，不遗漏。
 要求每条直线上的四个数字之和必须相等。
 图中已经给出了3个数字。
 请计算其它位置要填充的数字，答案唯一。
 填好后，请提交绿色节点的4个数字（从左到右，用空格分开）
 
比如：12 5 4 8
 当然，这不是正确的答案。
 
注意：只提交4个用空格分开的数字，不要填写任何多余的内容。
 
答案：10 3 9 8
 
题解：
 我们首先要对这十四个结点编号，当然编号可以随意定，但是下面的判断语句要对应着修改。这个题就是简单的进行dfs即可。但是要注意这里一定要进行剪枝，虽然不是暴力循环枚举答案，但是回溯递归的的效率其实并没有强很多，所以如果不进行剪枝的话，一定会发生栈溢出
 
class Test4 {
    static int[] a = {1, 2, 3, 4, 5, 7, 8, 9, 10, 12, 13};
    static int [] b;
    static boolean[] c, d;
    public static void main(String[] args) {
        c = new boolean[14];
        d = new boolean[14];
        b = new int[14];

        b[0] = 6;
        b[8] = 14;
        b[10] = 11;
        c[0] = true;
        c[8] = true;
        c[10] = true;

        f(0);
    }
    private static void f(int i) {
        // 剪枝
        if (i == 9) {
            if (b[1] + b[2] + b[3] + b[4] != b[0] + b[2] + b[5] + b[8]) {
                return;
            }
        }
        if (i == 11) {
            if (b[1] + b[2] + b[3] + b[4] != b[0] + b[3] + b[6] + b[10]) {
                return;
            }
        }
        if (i == 12) {
            if (b[1] + b[2] + b[3] + b[4] != b[1] + b[5] + b[7] + b[11]) {
                return;
            }
        }
        if (i == 13) {
            if (b[1] + b[2] + b[3] + b[4] != b[9] + b[10] + b[11] + b[12]) {
                return;
            }
        }
        if (i == 14) {
            if (b[1] + b[2] + b[3] + b[4] != b[7] + b[8] + b[12] + b[13]) {
                return;
            }
            if (b[1] + b[2] + b[3] + b[4] != b[4] + b[6] + b[9] + b[13]) {
                return;
            }
            for (int j = 0; j < c.length; j++) {
                System.out.print(j==0 ? "" : " ");
                if(j==1 || j==2 || j==3 || j==4){
                    System.out.print(b[j]);
                }
            }
            return;
        }
        if (c[i] == false) {
            for (int j = 0; j < a.length; j++) {
                if (d[j] == false) {
                    d[j] = true;
                    c[i] = true;
                    b[i] = a[j];
                    f(i + 1);
                    c[i] = false;
                    d[j] = false;
                }
            }
        } else {
            f(i + 1);
        }
    }
}
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://www.outofmemory.cn/zaji/5691510.html