第七届(16年)蓝桥杯java B组决赛真题及前四题解析

拼搏现实的明天。 2022-05-24 04:16 169阅读 0赞

1.  
愤怒小鸟  
  
X星球愤怒的小鸟喜欢撞火车！  
一根平直的铁轨上两火车间相距 1000 米  
两火车 （不妨称A和B） 以时速 10米/秒 相对行驶。  
愤怒的小鸟从A车出发，时速50米/秒，撞向B车，  
然后返回去撞A车，再返回去撞B车，如此往复....  
两火车在相距1米处停车。  
问：这期间愤怒的小鸟撞 B 车多少次？  
注意：需要提交的是一个整数（表示撞B车的次数），不要填写任何其它内容。

public class Main {
    	public static void main(String[] args) {
    		// 使用模拟法:
    		double flag_A = 0;
    		double flag_B = 1000;
    		double speed_niao = 60; // 此时车速是鸟速+车速
    		double speed_che = 20;	// 两辆车的速度叠加.
    		int conter = 0;//计算装上B的次数
    		double times = (flag_B - flag_A - 1) * 1.0 / speed_che;
            
    		while (flag_B - flag_A > 1 && times >0.00000000000000000000000000000000001) {
    			double time = (flag_B - flag_A) / speed_niao;
    			flag_A += time * speed_che;
    			times -= time;
    			System.out.println("此时车A前进到" + flag_A + ",两车相距:" + (flag_B - flag_A));
    			if ( flag_B - flag_A <= 1&& times >0.00000000000000000000000000000000001) {
    				break;
    			}//如果再装上B之后,距离小于1了,说明是在去往B的距离上截止,不应该被计数.
    			conter++;
    			time = (flag_B - flag_A) / speed_niao;
    			flag_B -= time * speed_che;
    			times -= time;
    			System.out.println("此时车B前进到" + flag_B + ",两车相距:" + (flag_B - flag_A));
    		}
    		System.out.println(conter);
    	}
    }

2.反幻方  
我国古籍很早就记载着  
2 9 4  
7 5 3  
6 1 8  
  
这是一个三阶幻方。每行每列以及对角线上的数字相加都相等。  
  
下面考虑一个相反的问题。  
可不可以用 1~9 的数字填入九宫格。  
使得：每行每列每个对角线上的数字和都互不相等呢？  
  
这应该能做到。  
比如：  
9 1 2  
8 4 3  
7 5 6  
  
你的任务是搜索所有的三阶反幻方。并统计出一共有多少种。  
旋转或镜像算同一种。  
  
比如：  
9 1 2  
8 4 3  
7 5 6  
  
7 8 9  
5 4 1  
6 3 2  
  
2 1 9  
3 4 8  
6 5 7  
等都算作同一种情况。  
  
请提交三阶反幻方一共多少种。这是一个整数，不要填写任何多余内容。

import java.util.*;
    
    public class Main {
        public static void main(String[] args) {
            boolean[] used = new boolean[9];
            int[] arr = new int[9];
            count = 0;
            count(used, 0, arr);
            // 镜像2种，旋转4种，所以除去8.
            System.out.println(count / 8);
        }
    
        static int count = 0;
    
        private static void count(boolean[] used, int index, int[] arr) {
            if (index == 9) {
                if (isLegal(arr)) {
                    count++;
                }
                return;
            }
            // 遍历找到还未被使用的used
            for (int i = 0; i < 9; i++) {
                if (!used[i]) {
                    used[i] = true;
                    arr[index] = i + 1;
                    count(used, index + 1, arr);
                    used[i] = false;
                }
            }
        }
    
        private static boolean isLegal(int[] arr) {
            // 三行三列双对角的值各不相同。
            int sum[] = new int[8];
            for (int i = 0; i < 3; i++) {
                sum[i] = arr[3 * i] + arr[1 + 3 * i] + arr[2 + 3 * i];
            }
            for (int i = 0; i < 3; i++) {
                sum[i + 3] = arr[i] + arr[i + 3] + arr[i + 6];
            }
    
            sum[6] = arr[0] + arr[4] + arr[8];
            sum[7] = arr[2] + arr[4] + arr[6];
            // 写一个简单的Set.
            // 和只可能是[6, 24] --> [0, 18]之间
            boolean[] used = new boolean[20];
            for (int i = 0; i < 8; i++) {
                if (!used[sum[i]]) {
                    used[sum[i]] = true;
                } else {
                    return false;
                }
            }
            return true;
        }
    }

答案:3120

3.  
打靶  
  
小明参加X星球的打靶比赛。  
比赛使用电子感应计分系统。其中有一局，小明得了96分。  
  
这局小明共打了6发子弹，没有脱靶。  
但望远镜看过去，只有3个弹孔。  
显然，有些子弹准确地穿过了前边的弹孔。  
  
不同环数得分是这样设置的：  
1,2,3,5,10,20,25,50  
  
那么小明的6发子弹得分都是多少呢？有哪些可能情况呢？  
  
下面的程序解决了这个问题。  
仔细阅读分析代码，填写划线部分缺失的内容。

public class Main
    {    
        static void f(int[] ta, int[] da, int k, int ho, int bu, int sc)
        {
            if(ho<0 || bu<0 || sc<0) return;
            if(k==ta.length){
                if(ho>0 || bu>0 || sc>0) return;
                for(int i=0; i<da.length; i++){
                    for(int j=0; j<da[i]; j++)
                        System.out.print(ta[i] + " ");
                }
                System.out.println();
                return;
            }
            
            for(int i=0; i<=bu; i++){
                da[k] = i;
                f(ta, da, k+1,  __________________ , bu-i, sc-ta[k]*i);   // 填空位置
            }
            
            da[k] = 0;
        }
        
        public static void main(String[] args)
        {
            int[] ta = {1,2,3,5,10,20,25,50};
            int[] da = new int[8];
            f(ta, da, 0, 3, 6, 96);
        }
    }

注意：只填写划线处缺少的内容，不要填写已有的代码或符号，也不要填写任何解释说明文字等。

解析过程：

import java.util.*;
    
    public class Main {
        // ta 是目标可选的值
        // da : 在目标可选值对应打了几枪的计数器
        // k  : 0 是index，计数
        // ho : 3是孔数
        // bu : 6 是剩余枪数
        // sc : 96 是目标值
        static void f(int[] ta, int[] da, int k, int ho, int bu, int sc) {
            // 不合法的话直接return
            if (ho < 0 || bu < 0 || sc < 0)
                return;
    
            if (k == ta.length) {
                // 虽然打够了 8 枪，但是孔数没打够，或者 枪数，
                if (ho > 0 || bu > 0 || sc > 0)
                    return;
                for (int i = 0; i < da.length; i++) {
                    for (int j = 0; j < da[i]; j++)
                        System.out.print(ta[i] + " ");
                }
                System.out.println();
                return;
            }
    
            for (int i = 0; i <= bu; i++) {
                // da 是一个标识值，表明是否被打过
                da[k] = i;
                // 如果 i == 0,那么没有打新的孔，如果i != 0,那么打了一个新孔
                f(ta, da, k + 1, i == 0 ? ho : ho - 1, bu - i, sc - ta[k] * i);   // 填空位置
            }
            da[k] = 0;
        }
    
        public static void main(String[] args) {
            int[] ta = {1, 2, 3, 5, 10, 20, 25, 50};
            int[] da = new int[8];
            f(ta, da, 0, 3, 6, 96);
        }
    }

答案：

da[k] != 0 ? ho - 1 : ho  //或者 i != 0 ? ho - 1 : ho

4.路径之谜  
  
小明冒充X星球的骑士，进入了一个奇怪的城堡。  
城堡里边什么都没有，只有方形石头铺成的地面。  
  
假设城堡地面是 n x n 个方格。【如图1.png】所示。  
  
按习俗，骑士要从西北角走到东南角。  
可以横向或纵向移动，但不能斜着走，也不能跳跃。  
每走到一个新方格，就要向正北方和正西方各射一箭。  
（城堡的西墙和北墙内各有 n 个靶子）  
  
  
同一个方格只允许经过一次。但不必做完所有的方格。  
  
如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？  
  
有时是可以的，比如图1.png中的例子。  
![70][]  
本题的要求就是已知箭靶数字，求骑士的行走路径（测试数据保证路径唯一）  
  
输入：  
第一行一个整数N(0<N<20)，表示地面有 N x N 个方格  
第二行N个整数，空格分开，表示北边的箭靶上的数字（自西向东）  
第三行N个整数，空格分开，表示西边的箭靶上的数字（自北向南）  
  
输出：  
一行若干个整数，表示骑士路径。  
  
为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号: 0,1,2,3....  
比如，图1.png中的方块编号为：  
  
0  1  2  3  
4  5  6  7  
8  9  10 11  
12 13 14 15  
  
  
示例：  
用户输入：  
4  
2 4 3 4  
4 3 3 3  
  
程序应该输出：  
0 4 5 1 2 3 7 11 10 9 13 14 15  
  
  
  
资源约定：  
峰值内存消耗 < 256M  
CPU消耗  < 1000ms  
  
  
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。  
  
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。  
注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。  
注意：主类的名字必须是：Main，否则按无效代码处理。

import java.util.*;
    
    public class Main {
        // 深搜,遍历所有可能性
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();
            int[] rows = new int[n];
            for (int i = 0; i < n; i++) {
                rows[i] = scanner.nextInt();
            }
            int[] clos = new int[n];
            for (int i = 0; i < n; i++) {
                clos[i] = scanner.nextInt();
            }
            boolean[][] used = new boolean[n][n];
            List<Integer> path = new ArrayList<>();
            getPath(used, path, rows, clos, 0, 0, n);
            for (int i = 0; i < path.size() - 1; i++) {
                System.out.print(path.get(i) + " ");
            }
            System.out.println(path.get(path.size() - 1));
        }
    
        private static boolean getPath(boolean[][] used, List<Integer> path, int[] rows, int[] clos, int i, int j, int n) {
            if (!(i >= 0 && i < n && j >= 0 && j < n && rows[j] > 0 && clos[i] > 0)) {
                return false;
            }
            used[i][j] = true;
            rows[j]--;
            clos[i]--;
            path.add(i * n + j);
            if (i == n - 1 && j == n - 1) {
                return true;
            }
            boolean res = getPath(used, path, rows, clos, i + 1, j, n) ||
                    getPath(used, path, rows, clos, i - 1, j, n) ||
                    getPath(used, path, rows, clos, i, j + 1, n) ||
                    getPath(used, path, rows, clos, i, j - 1, n);
            if (!res) {
                path.remove(path.size() - 1);
                return false;
            }
            return true;
        }
    }

5.  
碱基  
  
生物学家正在对n个物种进行研究。  
其中第i个物种的DNA序列为s\[i\]，其中的第j个碱基为s\[i\]\[j\],碱基一定是A、T、G、C之一。  
生物学家想找到这些生物中一部分生物的一些共性，他们现在关注那些至少在m个生物中出现的长度为k的连续碱基序列。准确的说，科学家关心的序列用2m元组(i1,p1,i2,p2....im,pm)表示，  
满足:  
1<=i1<i2<....<im<=n;  
且对于所有q(0<=q<k), s\[i1\]\[p1+q\]=s\[i2\]\[p2+q\]=....=s\[im\]\[pm+q\]。  
  
现在给定所有生物的DNA序列，请告诉科学家有多少的2m元组是需要关注的。如果两个2m元组有任何一个位置不同，则认为是不同的元组。  
  
【输入格式】  
输入的第一行包含三个整数n、m、k，两个整数之间用一个空格分隔，意义如题目所述。  
接下来n行，每行一个字符串表示一种生物的DNA序列。  
DNA序列从1至n编号，每个序列中的碱基从1开始依次编号，不同的生物的DNA序列长度可能不同。  
  
【输出格式】  
输出一个整数，表示关注的元组个数。  
答案可能很大，你需要输出答案除以1000000007的余数。  
  
【样例输入】  
3 2 2  
ATC  
TCG  
ACG  
  
【样例输出】  
2  
  
再例如：  
【样例输入】  
4 3 3  
AAA  
AAAA  
AAA  
AAA  
  
【样例输出】  
7  
  
  
【数据规模与约定】  
对于20%的数据，k<=5,所有字符串总长L满足L <=100  
对于30%的数据，L<=10000  
对于60%的数据，L<=30000  
对于100%的数据，n<=5,m<=5,1<=k<=L<=100000  
保证所有DNA序列不为空且只会包含’A’ ’G’ ’C’ ’T’四种字母  
  
资源约定：  
峰值内存消耗 < 256M  
CPU消耗  < 1000ms  
  
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。  
  
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。  
注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。  
注意：主类的名字必须是：Main，否则按无效代码处理。

题太长,,,看不懂.

圆圈舞  
  
春天温暖的阳光照耀着大地，正是草原上的小动物们最快乐的时候。小动物们在草原上开了一个舞会，欢度这美好的时光。  
  
舞会上最重要的一个环节就是跳圆舞曲，n只小动物手拉手围成一大圈，随着音乐跳起来。在跳的过程中，小动物们可能会变换队形。它们的变换方式是动物A松开自己右手，动物B松开自己的左手，动物A和B手拉到一起，而它们对应的松开的手（如果有的话）也拉到一起。  
  
例如，假设有10只小动物，按顺序围成一圈，动物1的右手拉着动物2的左手，动物2的右手拉着动物3的左手，依次类推，最后动物10的右手拉着动物1的左手。如果通过动物2和8变换队形，则动物2的右手拉着动物8的左手，而对应的动物3的左手拉着动物7的右手，这样形成了1-2-8-9-10和3-4-5-6-7两个圈。如果此时通过动物2和6变换队形，则将形成1-2-6-7-3-4-5-8-9-10一个大圈。注意，如果此时通过动物1和2变换队形，那么队形不会改变，因为动物1的右手和动物2的左手松开后又拉到一起了。  
  
在跳舞的过程中，每个动物i都有一个欢乐值Hi和一个感动值Fi。  
如果两个动物在一个圈中，欢乐值会彼此影响，产生欢乐能量。如果两个动物i, j（i≠j）在同一个大小为t的圈中，而动物i在动物j右手的第p个位置（动物j右手的第1个位置就是动物j右手所拉着的动物，而第2个位置就是右手第1个位置的动物右手拉着的动物，依次类推），则产生的欢乐能量为(t-p)\*Hj\*Fi。在跳舞的过程中，动物们的欢乐值和感动值有可能发生变化。  
  
圆舞曲开始的时候，所有的动物按编号顺序围成一个圈，动物n右手的第i个位置正好是动物i。现在已知小动物们变换队形的过程和欢乐值、感动值变化的过程，求每次变换后所有动物所产生的欢迎能量之和。  
  
【输入格式】  
输入的第一行包含一个整数n，表示动物的数量。  
接下来n行，每行两个用空格分隔的整数Hi, Fi，按编号顺序给出每只动物的欢乐值和感动值。  
接下来一行包含一个整数m，表示队形、欢乐值、感动值的变化次数。  
接下来m行，每行三个用空格分隔的整数k, p, q，当k=1时，表示小动物们通过动物p和动物q变换了队形，当k=2时，表示动物p的欢乐值变为q，当k=3时，表示动物p的感动值变为了q。  
  
【输出格式】  
输出m行，每行一个整数，表示每次变化后所有动物产生的能量之和。  
答案可能很大，你需要计算答案除以1000000007的余数。  
  
【样例输入】  
10  
1 1  
1 1  
1 1  
1 1  
1 1  
1 1  
1 1  
1 1  
1 1  
1 1  
9  
1 2 8  
1 2 6  
2 8 10  
3 5 10  
1 1 2  
1 2 1  
2 5 5  
1 4 8  
1 4 5  
  
【样例输出】  
100  
450  
855  
1341  
1341  
811  
923  
338  
923  
  
【数据规模与约定】  
对于20%的数据，2<=n,m<=100。  
对于30%的数据，2<=n,m<=1000。  
另有20%的数据，只有k=1的操作且Hi,Fi均为1。  
另有20%的数据，只有k=1或2的操作且Fi均为1。  
对于100%的数据，2<=n,m<=100000，0<=Hi,Fi<=10^9，1<=k<=3，k=1时1<=p,q<=n且p≠q，k=2或3时1<=p<=n且0<=q<=10^9。  
  
资源约定：  
峰值内存消耗 < 256M  
CPU消耗  < 5000ms  
  
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。  
  
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。  
注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。  
注意：主类的名字必须是：Main，否则按无效代码处理。  
  
想了想,算了,估计写不出来,写出来也不对,写对了估计也只能跑出来30%的数据...

[70]: /images/20220524/bf386a4017254cc6919f7a503e4b06c4.png