蓝桥杯校选赛题目

2023-12-16数据结构与算法15 分钟128 次阅读
AI 摘要鱼粮不足,AI 今天先歇着 · 正文在下面

前言

该题目为学校蓝桥与天梯校选题目,总分:310,在此记录下自己比赛时的答案,以及不足的地方进行分析。

1、重要的话说三遍(5分)

这道超级简单的题目没有任何输入。

你只需要把这句很重要的话 —— “I'm gonna WIN!”——连续输出三遍就可以了。

注意每遍占一行,除了每行的回车不能有任何多余字符。

shell 复制代码
代码长度限制 					16 KB
时间限制 					400 ms
内存限制 					64 MB

我的答案

得分:5分

java 复制代码
public class Main {
	public static void main(String[] args) {
		int i=0;
		while(i<3) {
			System.out.println("I'm gonna WIN!");
			i++;
		}
	}
}

标准答案

2、计算阶乘和(10分)

对于给定的正整数N,需要你计算 S=1!+2!+3!+...+N!。

输入格式:
输入在一行中给出一个不超过10的正整数N。

输出格式:
在一行中输出S的值。

输入样例:

shell 复制代码
3

输出样例:

shell 复制代码
9
shell 复制代码
代码长度限制					16 KB
时间限制						400 ms
内存限制						64 MB

我的答案

得分:10分

java 复制代码
import java.util.*;
import java.math.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
        	if(n==1){
			System.out.println(1);
			return;
		}
		int[] arr=new int[n];
		arr[0]=1;
		arr[1]=2;
		int sum=arr[0]+arr[1];
		for(int i=2;i<n;i++) {
			arr[i]=(i+1)*arr[i-1];
			sum+=arr[i];
		}
		System.out.println(n==1?1:sum);
	}
}    

标准答案

分析:这里由于要计算的阶乘是逐一递增的,故可以计算当前的阶乘,临时存储起来,用于下一次的阶乘计算。
代码实现:

java 复制代码
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int count = 1, sum = 0;
        for (int i = 1; i <= n; i++) {
            // 计算当前阶乘
            count *= i;
            sum += count;
        }
        System.out.println(sum);
    }
}

3、天平和砝码(15分)

image.png

输入格式:
image.png

输出格式:
一个整数,代表答案

输入样例:
在这里给出一组输入。例如:

shell 复制代码
3
1 4 6

输出样例:
在这里给出相应的输出。例如:

shell 复制代码
10
shell 复制代码
代码长度限制 					16 KB
时间限制						400 ms
内存限制						64 MB
栈限制						8192 KB

我的答案

由于我对天平这块的使用忘记了,做题也是硬算出结果,取部分分。
得分:5分

java 复制代码
import java.util.*;
import java.math.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int[] arr=new int[n];
		for(int i=0;i<n;i++) {
			arr[i]=sc.nextInt();
		}
		HashSet<Integer> set=new HashSet<>();
		for(int i=0;i<n;i++) {
			int sum=arr[i];
			for(int j=0;i<n;i++) {
				sum+=arr[j];
				if(!set.contains(sum)) {
					set.add(sum);
				}
			}
		}
		System.out.println((n+set.size())*2-2);
	}
}    

标准答案

分析:由所给的测试条件为例,输入3个砝码:1、4、6,得出他能称出10种重量。分别如下:

能称出的 10 种重量是: 1、2、3、4、5、6、7、9、10、11 。
1=1
2=6−4( 天平一边放 6, 另一边放 4)
3=4−1
4=4
5=6−1
6=6
7=1+6
9=4+6−1
10=4+6
11=1+4+6

知道以上的情况后,我这里画出图解下:

  1. 分析先放入a,再放入b,在放入c的图解
    image.png
  2. 分析不放入a,再放入b,再放入c的情况
    image.png
    代码实现:
java 复制代码
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 用于存放砝码能称出来的重量
        Set<Integer> sets = new HashSet<>();
        int n = sc.nextInt();
        int[] fama = new int[n];
        for (int i = 0; i < n; i++) {
            fama[i] = sc.nextInt();
        }
        sets.add(0);
        for (int i = 0; i < n; i++) {
            // 再还没加入新的砝码前,将之前称得的重量放入集合中,用于与之后新的
            List<Integer> list = new ArrayList<>(sets);
            for (Integer k : list) {
                // 同一边
                sets.add(k + fama[i]);
                // 放不同边
                sets.add(Math.abs(k - fama[i]));
            }
        }
        sets.remove(0);
        System.out.println(sets.size());
    }
}

4、子序列问题(15分)

image.png
输入格式:
image.png
输出格式:
输出一个整数,表示答案

输入样例:
在这里给出一组输入。例如:

shell 复制代码
ABCDEABCD
AABZ

输出样例:
在这里给出相应的输出。例如:

shell 复制代码
3
shell 复制代码
代码长度限制					16 KB
时间限制						400 ms
内存限制						64 MB
栈限制						8192 KB

我的答案

得分:0分

java 复制代码
import java.util.*;
import java.math.*;

public class Main {
	public static void main(String[] args) {
		test33();
	}

	private static void test33() {
		Scanner sc = new Scanner(System.in);
		String str = sc.nextLine();
		String sub = sc.nextLine();
		int res = 0;
		for (int i = 0; i < sub.length(); i++) {
			int k = 0;
			String ss=str;
			while (k < sub.length()) {
				char c = sub.charAt(k);
				int index = ss.indexOf(c);
				if (index != -1) {
					ss = ss.substring(index);
					res++;
				}
				k++;
			}
//			if(max<res) {
//				max=res;
//				res=0;
//			}
		}
		System.out.println(res);
	}
}

5、n皇后问题解法数量(15分)

n*n的放个棋盘上放置n个皇后,要求每个皇后不同行,不同列,不同左右对角线。

输入格式:
n皇后的n值

输出格式:
n皇后对应的解法

输入样例:
在这里给出一组输入。例如:

shell 复制代码
4

输出样例:
在这里给出相应的输出。例如:

shell 复制代码
2
shell 复制代码
代码长度限制					16 KB
时间限制						400 ms
内存限制						64 MB
栈限制						8192 KB

标准答案

分析:N皇后问题就如题目所说,在同一行,同一列,或者同一条斜线上,只能存在一个皇后,而这种情况可能有多个,我这里也是学习了别人的思路,使用回溯算法,生成一种情况后,重新回退到上一步,看看有没有其他走法,没有就继续回退回去。
代码实现:

java 复制代码
import java.util.*;

/**
 * n皇后问题解法数量
 *
 * @author Salmon
 * @since 2024-02-25
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner((System.in));
        int n = sc.nextInt();
        boolean[][] board = new boolean[n][n];
        List<List<String>> res = new ArrayList<>();
        HashSet<Integer> cols = new HashSet<>();
        HashSet<Integer> pies = new HashSet<>();
        HashSet<Integer> nas = new HashSet<>();
        dfs(0, n, board, cols, pies, nas, res);
        System.out.println(res.size());
        System.out.println(res);
    }

    /**
     * 深度优先遍历
     *
     * @param level 当前在哪一层放皇后
     * @param col   棋盘的行列数
     * @param board 棋盘
     * @param cols  已存在的列
     * @param pies  左斜线
     * @param nas   右斜线
     * @param res   结果集
     */
    public static void dfs(int level, int col, boolean[][] board, HashSet<Integer> cols, HashSet<Integer> pies, HashSet<Integer> nas, List<List<String>> res) {
        if (level == col) {
            generate_res(col, res, board);
            return;
        }
        for (int i = 0; i < col; i++) {
            if (cols.contains(i) || pies.contains(i + level) || nas.contains(i - level)) {
                continue;
            }
            board[level][i] = true;
            cols.add(i);
            pies.add(i + level);
            nas.add(i - level);

            dfs(level + 1, col, board, cols, pies, nas, res);

            cols.remove(i);
            pies.remove(i + level);
            nas.remove(i - level);
            board[level][i] = false;
        }

    }

    /**
     * 生成结果
     *
     * @param n     行列个数
     * @param res   结果集
     * @param board 当前棋盘
     */
    private static void generate_res(int n, List<List<String>> res, boolean[][] board) {
        List<String> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                if (board[i][j]) {
                    sb.append('Q');
                } else {
                    sb.append('.');
                }
            }
            list.add(sb.toString());
        }
        res.add(list);
    }
}

6、活动时间最长(20分)

现有一系列活动,每个活动有开始时间和结束时间。只有一个会议室,会议室每个时刻只能有一个活动进行。需要安排活动,使得活动占用会议室的总时长最长。

输入格式:
输入多行,第一行为活动个数。后面若干行为每个活动的开始时间和结束时间,两时间空格隔开

输出格式:
所有活动占用最长时长

输入样例:
在这里给出一组输入。例如:

shell 复制代码
4
1 2
3 5
1 4
4 5

输出样例:
在这里给出相应的输出。例如:

shell 复制代码
4
shell 复制代码
代码长度限制					16 KB
时间限制						400 ms
内存限制						64 MB
栈限制						8192 KB

我的答案

得分:14分

java 复制代码
import java.util.*;
import java.math.*;

public class Main {
	public static void main(String[] args) {
		test322();
	}
	
	private static void test322() {
		Scanner sc = new Scanner(System.in);
		int num=sc.nextInt();
		Integer min=Integer.MAX_VALUE,max=0;
		for (int i = 0; i < num; i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			if(a<min) {
				min=a;
			}
			if(b>max) {
				max=b;
			}
		}
		System.out.println(max-min);
	}
}

标准答案

java 复制代码

7、字符串排序(20分)

本题要求编写程序,读入5个字符串,按由小到大的顺序输出。

输入格式:
输入为由空格分隔的5个非空字符串,每个字符串不包括空格、制表符、换行符等空白字符,长度小于80。

输出格式:
按照以下格式输出排序后的结果:

shell 复制代码
After sorted:
每行一个字符串

输入样例:

shell 复制代码
red yellow blue black white

输出样例:

shell 复制代码
After sorted:
black
blue
red
white
yellow

鸣谢贵州民族大学张玉全老师修正数据!

shell 复制代码
代码长度限制					16 KB
时间限制						400 ms
内存限制						64 MB

我的答案

得分:20分

java 复制代码
import java.util.*;
import java.math.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		String[] arr=new String[5];
		for(int i=0;i<5;i++) {
			arr[i]=sc.next();
		}
		Arrays.sort(arr);
		System.out.println("After sorted:");
		for(String s:arr) {
			System.out.println(s);
		}
	}
}    

标准答案

8、宿舍谁最高?(20分)

学校选拔篮球队员,每间宿舍最多有 4 个人。现给出宿舍列表,请找出每个宿舍最高的同学。定义一个学生类 Student,有身高 height,体重 weight 等。

输入格式:
首先输入一个整型数 n(1≤n≤106){n(1\leq n\leq10^6)},表示有 n{n} 位同学。

紧跟着 n{n} 行输入,每一行格式为:宿舍号 name height weight。
宿舍号的区间为 [0, 999999], name 由字母组成,长度小于 16,height,weight 为正整数。

输出格式:
按宿舍号从小到大排序,输出每间宿舍身高最高的同学信息。题目保证每间宿舍只有一位身高最高的同学。

注意宿舍号不足 6 位的,要按 6 位补齐前导 0。

输入样例:

shell 复制代码
7
000000 Tom 175 120
000001 Jack 180 130
000001 Hale 160 140
000000 Marry 160 120
000000 Jerry 165 110
000003 ETAF 183 145
000001 Mickey 170 115

输出样例:

shell 复制代码
000000 Tom 175 120
000001 Jack 180 130
000003 ETAF 183 145

鸣谢用户 钓台移柳 补充数据格式说明!

shell 复制代码
代码长度限制					16 KB
时间限制						400 ms
内存限制						64 MB

我的答案

得分:20分

java 复制代码
import java.util.*;
import java.math.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		TreeMap<Integer, Student> map = new TreeMap<>();
		for (int i = 0; i < n; i++) {
			int id = sc.nextInt();
			String name = sc.next();
			int h = sc.nextInt();
			int w = sc.nextInt();
			Student stu = new Student(id, name, h, w);
			Student e = map.get(id);
			if (e == null) {
				map.put(id, stu);
			} else {
				if (e.height < stu.height) {
					map.put(id, stu);
				}
			}
		}
		for (Student s : map.values()) {
			String idStr=s.id+"";
			int len=idStr.length();
			for(int i=0;i<6-len;i++) {
				idStr="0"+idStr;
			}
			System.out.printf("%s %s %d %d\n",idStr,s.name,s.height,s.weight);
		}
    }
}
class Student {
	int id;
	String name;
	int height;
	int weight;

	public Student(int id, String name, int height, int weight) {
		this.id = id;
		this.name = name;
		this.height = height;
		this.weight = weight;
	}

	public int getId() {
		return id;
	}

	public void setId(int id) {
		this.id = id;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public int getHeight() {
		return height;
	}

	public void setHeight(int height) {
		this.height = height;
	}

	public int getWeight() {
		return weight;
	}

	public void setWeight(int weight) {
		this.weight = weight;
	}

	@Override
	public String toString() {
		return "Student [id=" + id + ", name=" + name + ", height=" + height + ", weight=" + weight + "]";
	}

}

标准答案

9、单身狗(25分)

“单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人,以便给予特殊关爱。

输入格式:
输入第一行给出一个正整数 N(≤50000),是已知夫妻/伴侣的对数;随后 N 行,每行给出一对夫妻/伴侣——为方便起见,每人对应一个 ID 号,为 5 位数字(从 00000 到 99999),ID 间以空格分隔;之后给出一个正整数 M(≤10000),为参加派对的总人数;随后一行给出这 M 位客人的 ID,以空格分隔。题目保证无人重婚或脚踩两条船。

输出格式:
首先第一行输出落单客人的总人数;随后第二行按 ID 递增顺序列出落单的客人。ID 间用 1 个空格分隔,行的首尾不得有多余空格。

输入样例:

shell 复制代码
3
11111 22222
33333 44444
55555 66666
7
55555 44444 10000 88888 22222 11111 23333

输出样例:

shell 复制代码
5
10000 23333 44444 55555 88888
shell 复制代码
代码长度限制					16 KB
时间限制						200 ms
内存限制						64 MB

我的答案

得分:17分

java 复制代码
import java.util.*;
import java.math.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		// 用于查找另一方
		Map<String, String> qinlv = new HashMap<>();
		for (int i = 0; i < n; i++) {
			String s1 = sc.next();
			String s2 = sc.next();
			qinlv.put(s1, s2);
			qinlv.put(s2, s1);
		}
		int m = sc.nextInt();
		// 存储参加派对的用户
		TreeSet<String> list = new TreeSet<>();
		for (int i = 0; i < m; i++) {
			String s = sc.next();
			list.add(s);
			if (qinlv.get(s) != null) {
				if (list.contains(qinlv.get(s))) {
					list.remove(s);
					list.remove(qinlv.get(s));
				}
			}
		}
//		for (String key : qinlv.keySet()) {
//			if (list.contains(key)) {
//				if (list.contains(qinlv.get(key))) {
//					list.remove(key);
//					list.remove(qinlv.get(key));
//				}
//			}
//		}
		int size = list.size();
		System.out.println(size);
		int i = 0;
		for (String luodan : list) {
			System.out.print(luodan);
			if (i < size - 1) {
				System.out.print(" ");
			}
			i++;
		}
	}
}    

标准答案

10、深入虎穴(25分)

著名的王牌间谍 007 需要执行一次任务,获取敌方的机密情报。已知情报藏在一个地下迷宫里,迷宫只有一个入口,里面有很多条通路,每条路通向一扇门。每一扇门背后或者是一个房间,或者又有很多条路,同样是每条路通向一扇门…… 他的手里有一张表格,是其他间谍帮他收集到的情报,他们记下了每扇门的编号,以及这扇门背后的每一条通路所到达的门的编号。007 发现不存在两条路通向同一扇门。

内线告诉他,情报就藏在迷宫的最深处。但是这个迷宫太大了,他需要你的帮助 —— 请编程帮他找出距离入口最远的那扇门。

输入格式:
输入首先在一行中给出正整数 N(≤105){N(\leq 10^5)},是门的数量。最后 N{N} 行,第 i{i} 行(1≤i≤N{1\leq i\leq N})按以下格式描述编号为 i 的那扇门背后能通向的门:

shell 复制代码
K D[1] D[2] ... D[K]

其中 K 是通道的数量,其后是每扇门的编号。

输出格式:
在一行中输出距离入口最远的那扇门的编号。题目保证这样的结果是唯一的。

输入样例:

shell 复制代码
13
3 2 3 4
2 5 6
1 7
1 8
1 9
0
2 11 10
1 13
0
0
1 12
0
0

输出样例:

shell 复制代码
12
shell 复制代码
代码长度限制					16 KB
时间限制						400 ms
内存限制						64 MB

标准答案

分析:按照题意我们知道:每个入口可以前往其他入口,或者没有路可走,而这刚好和有向图差不多,我们可以将其以邻接表的形式展现,求距离入口最远的门相当于是求从某一点出发,进行深度遍历,深度最大的时候的结点编号即为结果,按照这个思路,进行解答即可。

java 复制代码
import java.util.*;

/**
 * 深入虎穴
 *
 * @author Salmon
 * @since 2024-03-05
 */
public class X_10 {

    static int n, // 结点数
            maxDepth, // 最大深度
            maxId; // 最远结点编号
    static List<List<Integer>> graph; // 邻接表

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

        // 门的数量(邻接表的结点数)
        n = scanner.nextInt();

        // 初始化邻接表
        graph = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; i++) {
            graph.add(new LinkedList<>());
        }

        for (int door = 1; door <= n; door++) {
            int count = scanner.nextInt(); // 入口可以去的其他门数量(当前结点有多少个邻接结点)
            for (int j = 0; j < count; j++) {
                int dest = scanner.nextInt();
                graph.get(door).add(dest); // 往当前入口添加其可以前往的门编号
            }
        }


        for (int i = 1; i <= n; i++) {
            // 当前结点可到达其他结点
            if (!graph.get(i).isEmpty()) {
                // 从该位置进行深度遍历
                dfs(i, 1);
            }
        }

        System.out.println("最远的节点是: " + maxId);
    }

    /**
     * 深度优先遍历
     *
     * @param cur   当前遍历的结点编号
     * @param depth 当前深度
     */
    public static void dfs(int cur, int depth) {
        // 深度更大的情况更新编号
        if (depth > maxDepth) {
            maxDepth = depth;
            maxId = cur;
        }
        // 遍历其邻接结点
        for (int neighbor : graph.get(cur)) {
            // 从当前位置结点继续访问其邻接结点
            dfs(neighbor, depth + 1);
        }
    }
}

11、删除字符串中的子串(20分)

输入2个字符串S1和S2,要求删除字符串S1中出现的所有子串S2,即结果字符串中不能包含S2。

输入格式:
输入在2行中分别给出不超过80个字符长度的、以回车结束的2个非空字符串,对应S1和S2。

输出格式:
在一行中输出删除字符串S1中出现的所有子串S2后的结果字符串。

输入样例:

shell 复制代码
Tomcat is a male ccatat
cat

输出样例:

shell 复制代码
Tom is a male 
shell 复制代码
代码长度限制					16 KB
时间限制						400 ms
内存限制						64 MB

我的答案

得分:20分

java 复制代码
import java.util.*;
import java.math.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String str = sc.nextLine();
		String sub = sc.nextLine();
		while(str.indexOf(sub)!=-1) {
			str=str.replace(sub,"");
		}
		System.out.println(str);
	}
}    

标准答案

12、字符串循环左移(20分)

输入一个字符串和一个非负整数N,要求将字符串循环左移N次。

输入格式:
输入在第1行中给出一个不超过100个字符长度的、以回车结束的非空字符串;第2行给出非负整数N。

输出格式:
在一行中输出循环左移N次后的字符串。

输入样例:

shell 复制代码
Hello World!
2

输出样例:

shell 复制代码
llo World!He
shell 复制代码
代码长度限制					16 KB
时间限制						400 ms
内存限制						64 MB

我的答案

得分:14分

java 复制代码
import java.util.*;
import java.math.*;

public class Main {
	public static void main(String[] args) {
		test12();
	}
	
	private static void test12() {
		Scanner sc = new Scanner(System.in);
		String str = sc.nextLine();
		int n = sc.nextInt();
		int len=str.length();
		for(int i=n;i<len+n;i++) {
			int k=i;
			if(i>=len) {
				k=i-len;
			}
			System.out.print(str.charAt(k));
		}
	}
}

标准答案

分析:这里其实可以用字符串的截取直接输出结果,简单高效。
代码:

java 复制代码
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        int n = sc.nextInt();
        // 防止输入的n,超过了字符串的长度,这里进行取模
        n = n % str.length();
        System.out.print(str.substring(n, str.length() - 1));
        System.out.print(str.substring(0, n));
    }
}

13、整数分解为若干项之和(20分)

将一个正整数N分解成几个正整数相加,可以有多种分解方法,例如7=6+1,7=5+2,7=5+1+1,…。编程求出正整数N的所有整数分解式子。

输入格式:
每个输入包含一个测试用例,即正整数N (0<N≤30)。

输出格式:
按递增顺序输出N的所有整数分解式子。递增顺序是指:对于两个分解序列N1={n1,n2,⋯}{N_1=\{n_1,n_2,⋯\}}和N2={m1,m2,⋯}{N_2=\{m_1,m_2,⋯\}},若存在i{i}使得n1=m1,⋯,ni=mi{n_1=m_1,⋯,n_i=m_i},但是ni+1<mi+1{n_{i+1}<m_{i+1}},则N1{N_1}序列必定在N2{N_2}序列之前输出。每个式子由小到大相加,式子间用分号隔开,且每输出4个式子后换行。

输入样例:

shell 复制代码
7

输出样例:

shell 复制代码
7=1+1+1+1+1+1+1;7=1+1+1+1+1+2;7=1+1+1+1+3;7=1+1+1+2+2
7=1+1+1+4;7=1+1+2+3;7=1+1+5;7=1+2+2+2
7=1+2+4;7=1+3+3;7=1+6;7=2+2+3
7=2+5;7=3+4;7=7
shell 复制代码
代码长度限制					16 KB
时间限制						800 ms
内存限制						64 MB

标准答案

14、玩转二叉树(25分)

给定一棵二叉树的中序遍历和前序遍历,请你先将树做个镜面反转,再输出反转后的层序遍历的序列。所谓镜面反转,是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

输入格式:
输入第一行给出一个正整数N(≤30{\leq30}),是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。

输出格式:
在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。

输入样例:

shell 复制代码
7
1 2 3 4 5 6 7
4 1 3 2 6 5 7

输出样例:

shell 复制代码
4 6 1 7 5 3 2
shell 复制代码
代码长度限制					16 KB
时间限制						400 ms
内存限制						64 MB

标准答案

15、三角形的问题(25分)

image.png
输入格式:
输入一个整数N

输出格式:
输出一个整数代表答案

输入样例:
在这里给出一组输入。例如:

shell 复制代码
6

输出样例:
在这里给出相应的输出。例如:

shell 复制代码
13
shell 复制代码
代码长度限制					16 KB
时间限制						400 ms
内存限制						64 MB
栈限制						8192 KB

我的答案

得分:25分

java 复制代码
import java.util.*;
import java.math.*;

public class Main {
	public static void main(String[] args) {
		test15();
	}
	
	private static void test15() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[][] arr=new int[100000][];
		arr[0]=new int[]{1};
		arr[1]=new int[]{1,1};
//		String s=new String(",1,1,1");
		int k=3;
		boolean flag=true;
		for(int i=2;flag;i++) {
			arr[i]=new int[i+1];
			arr[i][0]=1;
			k++;
//			s+=","+1;
			for(int j=1;j<arr[i].length-1;j++) {
				arr[i][j]=arr[i-1][j]+arr[i-1][j-1];
				k++;
//				s+=","+arr[i][j];
				if(arr[i][j]==n) {
					flag=false;
					break;
				}

			}
			arr[i][i]=1;
			k++;
//			s+=","+1;
		}
		System.out.println(k-1);
    }
}

标准答案

用我之前写的代码跑学校的题目时是能通过全部测试用例,但在测试蓝桥杯真题时,发现只能得40分,其它用例都报内存超出限制,故我们需要优化下,由于我之前的方法是用二维数组,占用内存约等于O(n2){O(n^2)}。故对其做优化,我们不难发现杨辉三角形是对称的,我们可以利用这一特性简化之前代码的复杂度。

这是图示:
image.png

代码实现:

java 复制代码
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		if (n == 1) {
			System.out.println(1);
			return;
		}
		long[] arrs = new long[100000];
		arrs[0] = 1;
		int counts = 1;
		for (int i = 1; i < arrs.length; i++) {
			// 从尾到前计算中间的数字
			for (int j = i; j > 0; j--) {
				arrs[j] = arrs[j] + arrs[j - 1];
				if (arrs[j] == n) {
					// 上一次已统计的次数 + 当前这个数在这一行的第几个数的位置(这一行有多少个数(i-j)+1 )
					// 因为杨辉三角形其实是对称的,左边相同数字的下标 = 最大下标位置 - 右边元素对应的下标
					// +1 是得出这个数在这一行的第几个数字
					System.out.println(counts + i - j + 1);
					return;
				}
			}
			counts += i + 1; // 累加以寻找的数字个数
		}
		// 如果走到这里,表示这个数字在第 n+1 行处的第二个位置
		// 这是因为对于杨辉三角形中的任意数字 n,如果它不是三角形的第一个数字或最后一个数字,它都可以通过一个等差数列来计算出来。
		// 对于最后一行的第二个位置,我们可以使用如下的等差数列来计算:
		// (1+n)*n/2+2
		System.out.println(((1 + n) * n / 2) + 2);
	}
}

16、非常弹的球(30分)

刚上高一的森森为了学好物理,买了一个“非常弹”的球。虽然说是非常弹的球,其实也就是一般的弹力球而已。森森玩了一会儿弹力球后突然想到,假如他在地上用力弹球,球最远能弹到多远去呢?他不太会,你能帮他解决吗?当然为了刚学习物理的森森,我们对环境做一些简化:

  • 假设森森是一个质点,以森森为原点设立坐标轴,则森森位于(0, 0)点。
  • 小球质量为w{w}/100 千克(kg),重力加速度为9.8米/秒平方(m/s2{m/s^2})。
  • 森森在地上用力弹球的过程可简化为球从(0, 0)点以某个森森选择的角度ang(0<ang<π/2){ang (0<ang<π/2)} 向第一象限抛出,抛出时假设动能为1000 焦耳(J)。
  • 小球在空中仅受重力作用,球纵坐标为0时可视作落地,落地时损失p{p}%动能并反弹。
  • 地面可视为刚体,忽略小球形状、空气阻力及摩擦阻力等。

森森为你准备的公式:

  • 动能公式:m×v2/2{m\times v^2/2}
  • 牛顿力学公式:F=m×a{F=m\times a}
  • 重力:G=m×g{G=m\times g}

其中:

  • E - 动能,单位为“焦耳”
  • m - 质量,单位为“千克”
  • v - 速度,单位为“米/秒”
  • a - 加速度,单位为“米/秒平方”
  • g - 重力加速度

输入格式:
输入在一行中给出两个整数:1≤w≤1000{1\leq w\leq1000} 和 1≤p≤100{1\leq p\leq100},分别表示放大100倍的小球质量、以及损失动力的百分比p{p}。

输出格式:
在一行输出最远的投掷距离,保留3位小数。

输入样例:

shell 复制代码
100 90

输出样例:

shell 复制代码
226.757
shell 复制代码
代码长度限制					16 KB
时间限制						150 ms
内存限制						64 MB

标准答案

觉得有用就点个赞,不用登录也能读

评论

0 条
登录 之后才能评论
—
还没有评论,来说第一句