蓝桥杯2016年真题 | Java组

1、煤球数目

有一堆煤球，堆成三角棱锥形。具体： 第一层放 1个， 第二层 3 个（排列成三角形）， 第三层 6 个（排列成三角形）， 第四层 10 个（排列成三角形）， .... 如果一共有 100层，共有多少个煤球？

    public static void main(String[] args) {
        int sum = 0, num = 0;
        for (int i = 1; i <= 100; i++){
            num += i;
            sum += num;
        }
      System.out.println (sum);
    }

总结：这里看错以为是输出第100个，输出5050没过，少个sum += num; 总数每行加起来

2、生日蜡烛

某君从某年开始每年都举办一次生日 partyparty，并且每次都要吹熄与年龄相同根数的蜡烛。

现在算起来，他一共吹熄了 236根蜡烛。请问，他从多少岁开始过生日 party的？

请输出他开始过生日party的年龄数。

public class Main {
    public static void main(String[] args) {
        int sum = 0;
        for (int i = 1; i < 50; i++) {
            for (int j = i; j < 50; j++) {
                sum += j;
                if (sum == 236) {
                    System.out.println(i);
                    return;
                }
                if (sum > 236) break; 
            }
            sum = 0;
        }
    }
}

总结：用的双重循环第一个开始年龄 第二个结束年龄，然后就判断找，但是容易超时。我们当sum在某次大于236直接break，找到直接return来减少循环次数。

3、搭积木

小明最近喜欢搭数字积木， 一共有 10 块积木，每个积木上有一个数字，0 ~ 9。

搭积木规则： 每个积木放到其它两个积木的上面，并且一定比下面的两个积木数字小。 最后搭成 4 层的金字塔形，必须用完所有的积木。

public class Main {
    private static int ans;
    private static int[] a = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 
    public static void main(String[] args) {
        f(0);
        System.out.println(ans);
    }
 
    private static void f(int k) {
        if (k == 10) {
            ans++;
        }
        for (int i = k; i < a.length; i++) {
            int t = a[i];
            a[i] = a[k];
            a[k] = t;
 
            if(k == 1 && a[1]0] ||
               k == 2 && a[2]0]||
               k == 3 && a[3]1]||
               k == 4 && (a[4]1]||a[4]2])||
               k == 5 && a[5] < a[2]||
               k == 6 && a[6]3]||
               k == 7 && (a[7]3]|| a[7]4])||
               k == 8 && (a[8]4]|| a[8]5])||
               k == 9 && a[9]5]) {
                t = a[i];
                a[i] = a[k];
                a[k] = t;
                continue;
            }
            f(k + 1);
 
            t = a[i];
            a[i] = a[k];
            a[k] = t;
        }
 
    }
 
    private static void check() {
        if (a[0] > a[1] || a[0] > a[2] || a[1] > a[3] || a[1] > a[4] || a[2] > a[4] || a[2] > a[5] || a[3] > a[6]
                || a[3] > a[7] || a[4] > a[7] || a[4] > a[8] || a[5] > a[8] || a[5] > a[9])
            return;
        ans++;
    }
}

总结：看到1到9就应该想到全排列了，基本上每年都有全排列，这个就是全排列加减枝。全排列一定要熟练默写。

4、分小组

9名运动员参加比赛，需要分3组进行预赛。 有哪些分组的方案呢？

我们标记运动员为 A,B,C,... I。下面的程序列出了所有的分组方法。代码填空题

public class Main
{
    public static String remain(int[] a)
    {
        String s = "";
        for(int i=0; i
            if(a[i] == 0) s += (char)(i+'A');
        }    
        return s;
    }
    
    public static void f(String s, int[] a)
    {
        for(int i=0; i
            if(a[i]==1) continue;
            a[i] = 1;
            for(int j=i+1; j
                if(a[j]==1) continue;
                a[j]=1;
                for(int k=j+1; k
                    if(a[k]==1) continue;
                    a[k]=1;
                    if(k==3)
                    System.out.println(____________________________);
                    a[k]=0;
                }
                a[j]=0;
            }
            a[i] = 0;
        }
    }
    
    public static void main(String[] args)
    {
        int[] a = new int[9];        
        a[0] = 1;
        
        for(int b=1; b
            a[b] = 1;
            for(int c=b+1; c
                a[c] = 1;
                String s = "A" + (char)(b+'A') + (char)(c+'A');
                f(s,a);
                a[c] = 0;
            }
            a[b] = 0;
        }
    }
}

答案：s+" "+(char)(i+'A') + (char)(j+'A')+ (char)(k+'A')+" "+remain(a)

总结：先把填空那行注释掉，然后运行一下，发现打出500多知道是总数，然后就知道横线是输出每一行，然后下面发现传s和数组进来，然后debug发现s是abc就知道s为前3个数，退出我们这个代码是中间3个数，然后照猫画虎，最后发现remain方法没用过，idea黑色，然后发现是最后3个数，拼接上去。

5、抽签

X星球要派出一个 5 人组成的观察团前往 W 星。

其中：

A 国最多可以派出 4 人。B 国最多可以派出 2 人。C 国最多可以派出 2 人。

那么最终派往 W 星的观察团会有多少种国别的不同组合呢？

代码填空题

public class Main
{
    public static void f(int[] a, int k, int n, String s)
    {
        if(k==a.length){ 
            if(n==0) System.out.println(s);
            return;
        }
        
        String s2 = s;
        for(int i=0; i<=a[k]; i++){
            ______________________;
            s2 += (char)(k+'A');
        }
    }
    
    public static void main(String[] args)
    {
        int[] a = {4,2,2,1,1,3};
        
        f(a,0,5,"");
    }
}

答案：f(a,k+1,n-i,s2)

总结：我们看到当k==什么什么然后return的一般都是递归，然后又发现k一开始是0，n是5就知道，k肯定是变大，然后当大到length就return，n是5，判断可能是应该要减小，然后一直是a数组，s2没有用到，所有大概猜测出答案。这种递归要搞清楚每个参数的含义和变化方向

6、寒假作业

一看就是全排列

public class Main {
    static int a[] = {1,2,3,4,5,6,7,8,9,10,11,12,13};
    static int count;
    
    public static void main(String[] args) {
        f(0);
        System.out.print(count);
    }
 
    public static void f(int k){
        if(k==13){
          if(check())count++;
        }
        for(int i=k;i<13;i++){
          int t=a[k];a[k]=a[i];a[i]=t;
          if(k==2&&a[0]+a[1]!=a[2] ||
        	 k==5&&a[3]-a[4]!=a[5]){
            t=a[k];a[k]=a[i];a[i]=t;
            continue;
          }
          f(k+1);
          t=a[k];a[k]=a[i];a[i]=t;
        }
    }
    public static boolean check(){
      if(a[0]+a[1]==a[2] &&
         a[3]-a[4]==a[5] &&
         a[6]*a[7]==a[8] &&
         a[9]%a[10]==0 &&
         a[9]/a[10]==a[11]){
           return true;
         }
      return false;
    }
}

总结：全排列模板必须熟练默写，这个第一次交换进递归的时候可以进行减枝，跟上面题3一样。没什么好说，交换递归交换回去，然后达到if条件就根据题目来check()

7、凑算式

public class test {
	  
	static int a[]= {1,2,3,4,5,6,7,8,9};
	static int count;
	
    public static void main(String[] args) {
        f(0);
        System.out.print(count);
    }
    
    public static void f(int k) {
    	if(k==9) {
    		if(check()) {
    			count++;
    		}
    	}
    	for(int i=k;i<9;i++) {
    		int t=a[i];a[i]=a[k];a[k]=t;
    		f(k+1);
    		t=a[i];a[i]=a[k];a[k]=t;
    	}
    }
    
    public static boolean check() {
    	int num1 = a[3]*100+a[4]*10+a[5];
        int num2 = a[6]*100+a[7]*10+a[8];
        int num3 = a[1]*num2+a[2]*num1;
        int num4 = a[2]*num2;
        if(num3%num4 != 0)return false;
        if(a[0]+num3/num4 == 10)return true;
        return false;
    }
}

总结：又是全排列，但是这里有坑，可能除不尽这里必须通分一下，才能除尽。 

8、方格填数

import java.util.Scanner;
import static java.lang.Math.abs;
// 1:无需package
// 2: 类名必须Main, 不可修改
 
public class Main {
    static int[] a={0,1,2,3,4,5,6,7,8,9};
    static int ans=0;
    public static void main(String[] args) {
        f(0);
        System.out.println(ans);
    }
 
    private static void f(int k) {
        if (k==10){
            if (check())
                ans++;
            return;
        }
        for (int i=k;i<10;i++){
            int t=a[i];
            a[i]=a[k];
            a[k]=t;
 
            f(k+1);
 
            t=a[i];
            a[i]=a[k];
            a[k]=t;
        }
    }
 
    private static boolean check() {
        if (    abs(a[0]-a[1])==1||
                abs(a[0]-a[3])==1||
                abs(a[0]-a[4])==1||
                abs(a[0]-a[5])==1||
 
                abs(a[1]-a[2])==1||
                abs(a[1]-a[4])==1||
                abs(a[1]-a[5])==1||
                abs(a[1]-a[6])==1||
 
                abs(a[2]-a[5])==1||
                abs(a[2]-a[6])==1||
 
                abs(a[3]-a[4])==1||
                abs(a[3]-a[7])==1||
                abs(a[3]-a[8])==1||
 
                abs(a[4]-a[5])==1||
                abs(a[4]-a[7])==1||
                abs(a[4]-a[8])==1||
                abs(a[4]-a[9])==1||
 
                abs(a[5]-a[6])==1||
                abs(a[5]-a[8])==1||
                abs(a[5]-a[9])==1||
 
                abs(a[6]-a[9])==1||
 
                abs(a[7]-a[8])==1||
 
                abs(a[8]-a[9])==1){
            return false;
        }
        return true;
    }
}

总结：还是全排列，但是这次的check是个体力活，用到 abs(a-b) 是不会的，绝对值，学习一下

9、四平方和

import java.awt.*;
import java.util.Scanner;
 
public class Main {
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int m=(int)Math.sqrt(n);
        for (int i = 0; i <= m; i++) {
            for (int j = i; j <= m; j++) {
                for (int k = j; k <= m; k++) {
                    for (int l = k; l <=m ; l++) {
                        if (i*i+j*j+k*k+l*l==n){
                            System.out.println(i+" "+j+" "+k+" "+l);
                            return;
                        }
                    }
                }
            }
        }
    }
}

总结：就是暴力枚举4个数字，但是直接暴力超时，我们要优化，后面的数是从前面的数开始循环，所有数都不大于输入的开根号。int m=(int)Math.sqrt(n);

10、有奖猜谜

小明很喜欢猜谜语。 最近，他被邀请参加了 X 星球的猜谜活动。

每位选手开始的时候都被发给 777777 个电子币。 规则是：猜对了，手里的电子币数目翻倍， 猜错了，扣除 555555 个电子币, 扣完为止。

小明一共猜了 1515 条谜语。 战果为：vxvxvxvxvxvxvvxvxvxvxvxvxvxvvx 其中 vv 表示猜对了，xx 表示猜错了。

请你计算一下，小明最后手里的电子币数目是多少。

public class Main {
    public static void main(String[] args) {
        String string = new String();
        string="vxvxvxvxvxvxvvx";
        int coin=777;
        for (int i = 0; i < 15; i++) {
            if(string.charAt(i)=='v'){
                coin*=2;
            }
            else if (string.charAt(i)=='x'){
                coin-=555;
            }
            if (coin==0){
                System.out.println("game over"+i);
            }
        }
        System.out.println(coin);
    }
}

总结：送分题，我用了数组的形式，要学会用String，能直接从题目复制，节省时间string.charAt(i)=='v'

11、骰子游戏

同时掷出 3 个普通骰子（6 个面上的数字分别是 1~6）。 如果其中一个骰子上的数字等于另外两个的和，你就赢了。

下面的程序计算出你能获胜的精确概率（以既约分数表示） 填空

import java.util.*;
public class Main
{
    public static int gcd(int a, int b)
    {
        if(b==0) return a;
        return gcd(b,a%b);
    }
    
    public static void main(String[] args)
    {    
        int n = 0;
        for(int i=0; i<6; i++)
        for(int j=0; j<6; j++)
        for(int k=0; k<6; k++){
            if(________________________________) n++;
        }
        
        int m = gcd(n,6*6*6);
        System.out.println(n/m + "/" + 6*6*6/m);
    }
}

答案：(i+j+1==k) || (i+k+1==j) || (j+k+1==i)

总结：这题有坑，下标是从下标为0开始的，我们的骰子是从1到6，所以必须加1，我题目也看错了，一开始看题看错以为两个骰子相等就赢。