56-2016年第七届蓝桥杯国赛试题及详解(Java本科B组)

时间:2021-11-01 13:11:49

以下为个人答案,或参考网上,不能保证一定正确。


1、愤怒小鸟

X星球愤怒的小鸟喜欢撞火车!

一根平直的铁轨上两火车间相距 1000 米
两火车 (不妨称A和B) 以时速 10米/秒 相对行驶。

愤怒的小鸟从A车出发,时速50米/秒,撞向B车,
然后返回去撞A车,再返回去撞B车,如此往复....
两火车在相距1米处停车。

问:这期间愤怒的小鸟撞 B 车多少次?

注意:需要提交的是一个整数(表示撞B车的次数),不要填写任何其它内容。

 ---------------------------------------------------------

思路: 分向a和b车两种考虑,注意是问:撞B的次数!!!

注意相向撞击速度为二者之和。

package lq2016_gs;

public class t1 {
	public static void main(String[] arg) {
		double a = 0, b = 1000;
		double niao = 0;
		int vn = 50;
		int allans = 0;
		int aans = 0;
		int bans = 0;
		
		while(b - a > 1) {
			// 向 b 车
			if(vn > 0) {
				double d = b - niao;  // 距离
				double t = d / 60;    // 相撞速度
				niao = niao + 50 * t;
				vn = -50;
				b = b - 10 * t;
				a = a + 10 * t;
				if(b - a <= 1) {  // 只有在距离大于一米的相撞才算
					break;
				}
				allans++;
				bans++;
				System.out.println("ans = " + allans + "; a = " + a + "; b = " + b + "; niao = " + niao + "; t = " + t);
			}
			// 向 a 车
			else {
				double d = niao - a;
				double t = d / 60;
				vn = 50;
				niao = niao - 50 * t;
				b = b - 10 * t;
				a = a + 10 * t;
				if(b - a <= 1) {
					break;
				}
				allans++;
				aans++;
				System.out.println("ans = " + allans + "; a = " + a + "; b = " + b + "; t = " + t);
			}
		}
		System.out.println("总次数 : " + allans);
		System.out.println("a : " + aans);
		System.out.println("b : " + bans);
	}
	
}
// ans = 9

  


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

等都算作同一种情况。

请提交三阶反幻方一共多少种。这是一个整数,不要填写任何多余内容。

 ----

思路:全排列找到所有可能,然后在判断是否满足,一定要细心啊啊啊啊,最后要除去,旋转4种,对称两种,总数除以8.

package lq2016_gs;

import java.util.Arrays;

public class t2 {
	public static int[] data = new int[10];
	public static int[] visi = new int[10];
	public static int N = 9;
	public static int ans = 0;

	public static void main(String[] arg) {

		dfs(0);
		System.out.println(ans);
		System.out.println("ans = " + ans / 8);

	}

	public static void dfs(int ct) {
		if(ct == N) {
			//			ans++;
			//			for(int i = 1; i <= N; i++) {
			//				System.out.print(data[i]);
			//			}
			//			System.out.println();
			int b[] = new int[8];
			b[0] = data[1] + data[2] + data[3];
			b[1] = data[4] + data[5] + data[6];
			b[2] = data[7] + data[8] + data[9];
			b[3] = data[1] + data[4] + data[7];
			b[4] = data[2] + data[5] + data[8];
			b[5] = data[3] + data[6] + data[9];
			b[6] = data[1] + data[5] + data[9];
			b[7] = data[3] + data[5] + data[7];
			int flag = 1;
			Arrays.sort(b);
			for(int j = 0; j < 7; j++) {
				if(b[j + 1] == b[j]) {
					flag = 0;
					break;
				}
			}
			if(flag == 1) {
				ans++;
			}
		}

		for(int i = 1; i <= N; i++) {
			if(visi[i] == 0) {
				visi[i] = 1;
				data[ct + 1] = i;
				dfs(ct + 1);
				visi[i] = 0;
			}
		}
	}

}

/*
24960     
ans = 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);
	}
}

  

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

 

package lq2016_gs;

public class t3
{  
    static void f(int[] ta, int[] da, int k, int ho, int bu, int sc)
    {   //  f(ta, da, 0, 3, 6, 96);
        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, i == 0 ? ho : ho - 1, bu-i, sc-ta[k]*i);   // 填空位置
            // 注意hu表示还可以使用的种数
        }
         
        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);
    }
}

  


4、路径之谜

小明冒充X星球的骑士,进入了一个奇怪的城堡。
城堡里边什么都没有,只有方形石头铺成的地面。

假设城堡地面是 n x n 个方格。【如图1.png】所示。

按习俗,骑士要从西北角走到东南角。
可以横向或纵向移动,但不能斜着走,也不能跳跃。
每走到一个新方格,就要向正北方和正西方各射一箭。
(城堡的西墙和北墙内各有 n 个靶子)


同一个方格只允许经过一次。但不必做完所有的方格。

如果只给出靶子上箭的数目,你能推断出骑士的行走路线吗?

有时是可以的,比如图1.png中的例子。

本题的要求就是已知箭靶数字,求骑士的行走路径(测试数据保证路径唯一)

输入:
第一行一个整数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,否则按无效代码处理。

 

56-2016年第七届蓝桥杯国赛试题及详解(Java本科B组)

思路:直接深搜,然后判断是否可走以及最终到达的判断要加上射的箭的数量。

MY CODE:

package lq2016_gs;

import java.util.Scanner;

public class t4 {
	public static int mp[][] = new int[20][20];
	public static int vi[][] = new int[20][20];
	public static int dx[] = {0, 0, 1, -1};
	public static int dy[] = {1, -1, 0, 0};
	public static int one[] = new int[20];
	public static int two[] = new int[20];
//	public static int path[] = new int[404];
//	public static int len = 0;
	public static int n; 
	
	public static void main(String[] arg) {
		Scanner cin = new Scanner(System.in);
		n = cin.nextInt();
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				mp[i][j] = i * n + j;
			}
		}
		// 上方
		for(int i = 0; i < n; i++) {
			one[i] = cin.nextInt();
		}
		// 左侧
		for(int i = 0; i < n; i++) {
			two[i] = cin.nextInt();
		}
		int[] path = new int[n * n];
		one[0]--;
		two[0]--;
		vi[0][0] = 1;
		path[0] = 0;
		dfs(0, path, 1);
	}
	public static void dfs(int s, int[] path, int len) {
		if(s == n * n -1) {
			int flag = 1;
			for(int i = 0; i < n; i++) {
				if(one[i] != 0) {
					flag = 0;
					break;
				}
				if(two[i] != 0) {
					flag = 0;
					break;
				}
//				System.out.print(two[i] + "-");
			}
//			System.out.println("laole ");
			if(flag == 1) {
				for(int i = 0; i < len; i++) {
					System.out.print(path[i] + " ");
				}
				System.out.println();
			}
		}
		for(int i = 0; i < 4; i++) {
			int x = dx[i] + s / n;
			int y = dy[i] + s % n;
			if(x >= 0 && x < n && y >= 0 && y < n &&
					vi[x][y] == 0 && one[y] != 0 && two[x] != 0) {
				vi[x][y] = 1;
				int s0 = x * n + y;
				path[len] = s0; 
				one[y]--;
				two[x]--;
				dfs(s0, path, len + 1);
				vi[x][y] = 0;
				one[y]++;
				two[x]++;
			}
		}
	}
}

  


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

 ----------------------------------

思路: 首先要进行字符串匹配,直接用string的 indexof函数吧,在较小数据时,反而比kmp快,很神奇啊。

暴力,暴力判断吧,最后在那几个组合,就是用的dfs, 但是脑抽,dfs还写错了啊啊。

package lq2016_gs;

import java.util.HashSet;
import java.util.Scanner;

public class t5 {
	public static int n, m, k, ct;
	public static int num[] = new int[6];
	
	public static void main(String[] arg) {
		Scanner cin = new Scanner(System.in);
		
		String nums = cin.nextLine().trim();
		n = Integer.parseInt(nums.split(" ")[0]);
		m = Integer.parseInt(nums.split(" ")[1]);
		k = Integer.parseInt(nums.split(" ")[2]);
		String[] strs = new String[n];
		for(int i = 0; i < n; i++) {
			strs[i] = cin.nextLine();
		}
		
		HashSet<String> set = new HashSet<>();
		int ans = 0;
		
		for(int i = 0; i < n; i++) {
			int len = strs[i].length();
			for(int j = 0; j <= len - k; j++) {
				String str = strs[i].substring(j, j + k);
//				String str = "TC";
				if(set.contains(str) == false) { // 每种字符串搜索一次
					set.add(str);
					for(int e = 0; e < n; e++) {
						num[e] = 0;
					}
					for(int e = 0; e < n; e++) {
						int x = strs[e].indexOf(str);
						while(x != -1) {
							num[e]++;
							x = strs[e].indexOf(str, x + 1);
						}
					}
					// 统计是否有m个不同的组包含这个串
					int f = 0;
					for(int e = 0; e < n; e++) {
						if(num[e] > 0) {
							f++;
						}
//						System.out.print(" " + num[e] + " ");
					}
					if(f >= m) {
						ct = 0;
						int[] rd = new int[5];
//						System.out.println("str: " + str);
						dfs(0, 0, 1, rd); 
//						System.out.println("ct: " + ct);
						ans += ct;
					}
				}
			}
		}
		
		System.out.println(ans);
		
	}
	
	// x表示检测当前dna, cnt选择的数量, 本次的种数,记录选择的dna
	public static void dfs(int x, int cnt, int typ, int[] rd) {
		if(cnt == m) {
			if(m == 1) {
				typ = 1;
			}
			ct += typ;
//			for(int i = 0; i < n; i++) {
//				System.out.print(rd[i] + " ");
//			}
//			System.out.println();
			return ;
		}
		if(x >= n) {
			return ;
		} 
		// 下面的之间判断递归即可,不要循环,不要循环!!!
		if(num[x] > 0) {
			int t = num[x];
			num[x] = 0;
			dfs(x + 1, cnt, typ, rd);
			rd[x] = t;
			dfs(x + 1, cnt + 1, typ * t % 1000000007, rd);
			rd[x] = 0;
			num[x] = t;
		}
	}
	
}	

  


6、圆圈舞

春天温暖的阳光照耀着大地,正是草原上的小动物们最快乐的时候。小动物们在草原上开了一个舞会,欢度这美好的时光。

舞会上最重要的一个环节就是跳圆舞曲,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,否则按无效代码处理。

 -----------------------------------------------------

思路: 暴力模拟吧,感觉想不到什么方法,而且题目这么长!!!不认真看都看不懂。

package lq2016_gs;

import java.util.Scanner;

public class t6 {
	public static Peo[] peos = new Peo[100002];
	
	public static void main(String[] arg) {
		Scanner cin = new Scanner(System.in);
		int n = cin.nextInt();
		
		for(int i = 0; i < n; i++) {
			peos[i] = new Peo( (i - 1 + n) % n, (i + 1) % n, cin.nextInt(), cin.nextInt());
		}
		// 变形
		int m = cin.nextInt();
		int k, p, q;
		int[] num = new int[n];
		int f = 0; // 表示队形没变
		for(int i = 0; i < m; i++) {
			k = cin.nextInt();
			p = cin.nextInt() - 1; // 从0开始计算
			q = cin.nextInt();
			if(k == 1) { 		// 变化队形
				f = 0; // 队形改变
				int[] y = new int[n];
				num = y; // 清空数组
				q--;
				int pR = peos[p].right;
				int qL = peos[q].left;
				peos[p].right = q;
				peos[q].left = p;
				peos[pR].left = qL;
				peos[qL].right = pR;
			}
			else if(k == 2) {   // p的欢乐值变为q
				peos[p].H = q;
			}
			else{               // p的感动值变为了q
				peos[p].F = q;
			}
			// 计算当前能量和
			int ans = 0;
			for(int j = 0; j < n; j++) {
				int next = peos[j].right;
				int t = 1;   // (t-p)*Hj*Fi
				if(f == 0 && num[j] == 0) {
					// 获取j所在圈子的大小
					while(next != j) {
						t++;
						next = peos[next].right;
					}
					num[j] = t;
				}
				else {
					t = num[j];
				}
				int pp = 0;
				next = peos[j].right;
				while(next != j) {
					pp++;
					num[next] = t; // 每个人所在圈子的大小
					ans += (t - pp) * peos[next].F * peos[j].H;
					next = peos[next].right;
				}
			}
			System.out.println(ans);
			f = 1; // 已经更新
		}
	}
	
}

class Peo{
	int left;
	int right;
	int H; //快乐值
	int F; //感动值
	Peo(){
		
	}
	Peo(int left, int right, int H, int F){
		this.left = left;
		this.right = right;
		this.H = H;
		this.F = F;
	}
}