本文主要是介绍【算法】实验室2024年二面纳新题复盘,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
实验室2024年二面纳新题复盘
P1258 小车问题
原题链接:
P1258 小车问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
小车问题
题目描述
甲、乙两人同时从 A 地出发要尽快同时赶到 B 地。出发时 A 地有一辆小车,可是这辆小车除了驾驶员外只能带一人。已知甲、乙两人的步行速度一样,且小于车的速度。问:怎样利用小车才能使两人尽快同时到达。
输入格式
仅一行,三个实数,分别表示 AB 两地的距离 s,人的步行速度 a,车的速度 b。
输出格式
两人同时到达 B 地需要的最短时间,保留 6 位小数。
样例 #1
样例输入 #1
120 5 25
样例输出 #1
9.600000
提示
数据规模与约定
对于 100% 的数据,保证 0 <= s, a, b <= 10^9。
首先确定最优解应该是让A与B同时开始走,开车带其中一人,而后走到一定时间再让车上的人下车,车返程去接另一人,然后再带着这一人前往终点,同时另一人步行,最终两人同时到达终点。
多说无益,上图:
这里B优先坐车,A步行为例。第一段时间B乘车走了S-X的路程,而A走了X的路程,车同时回到A所在的位置接到A,再带着A到终点,同时B也步行到了终点。
根据上述过程,可以找到不变量s,a,b。同时,只要让 A步行的时间 等于车行走的时间,就可以求出两人到达时的最小时间。未知的变量是X与时间T。
可以列出方程如下图:
解方程求出X,而后将X带入原式可以得出答案,这里贴出代码如下:
import java.util.Scanner;
public class Main{public static void main(String[] args) {Scanner sn = new Scanner(System.in);double s = sn.nextDouble();double a = sn.nextDouble();double b = sn.nextDouble();double x = (2 * a*s) /(3 *a+b);double t = x / a + (s - x) / b;System.out.printf("%f",t);}
}
值得注意的是:
本题中笔者首次接触到java的格式化输出,原来java里面是么得lf格式的(报错好久没发现问题)。此处贴出java f格式的用法,警钟长鸣。
f格式:用来输出实数(包括单、双精度),以小数形式输出。有以下几种用法:
%f:不指定宽度,整数部分全部输出并输出6位小数。
%m.nf:输出共占m列,其中有n位小数,如数值宽度小于m左端补空格。
%-m.nf:输出共占n列,其中有n位小数,如数值宽度小于m右端补空格。
P1125 [NOIP2008 提高组] 笨小猴
原题链接:
[P1125 NOIP2008 提高组] 笨小猴 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
[NOIP2008 提高组] 笨小猴
题目描述
笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用这种方法去选择选项的时候选对的几率非常大!
这种方法的具体描述如下:假设 maxn 是单词中出现次数最多的字母的出现次数,minn 是单词中出现次数最少的字母的出现次数,如果 maxn-minn 是一个质数,那么笨小猴就认为这是个 Lucky Word,这样的单词很可能就是正确的答案。
输入格式
一个单词,其中只可能出现小写字母,并且长度小于 100 。
输出格式
共两行,第一行是一个字符串,假设输入的的单词是 Lucky Word,那么输出
Lucky Word
,否则输出No Answer
;第二行是一个整数,如果输入单词是
Lucky Word
,输出 \text{maxn}-\text{minn} 的值,否则输出 0 。样例 #1
样例输入 #1
error
样例输出 #1
Lucky Word 2
样例 #2
样例输入 #2
olympic
样例输出 #2
No Answer 0
数组中找出最大的数和最小的数,相减判断质数即可。
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String string = scanner.next();int[] hash = new int[26]; // 使用26来表示英文字母个数for (int i = 0; i < string.length(); i++) {char ch = string.charAt(i);if (Character.isLowerCase(ch)) { // 仅处理小写字母hash[ch - 'a']++;}}int max = 0;int min = 100;for (int i = 0; i < 26; i++) {if(hash[i] != 0){max = Math.max(max, hash[i]);min = Math.min(min, hash[i]);}}if (Check(max - min)) {System.out.println("Lucky Word");System.out.println(max - min);} else {System.out.println("No Answer");System.out.println(0);}}static boolean Check(int num) {if (num <= 1) {return false;}for (int i = 2; i * i <= num; i++) {if (num % i == 0) {return false;}}return true;}
}
P1506 拯救oibh总部
原题链接:
P1506 拯救oibh总部 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
拯救oibh总部
题目背景
oibh 总部突然被水淹没了!现在需要你的救援……
题目描述
oibh 被突来的洪水淹没了,还好 oibh 总部有在某些重要的地方起一些围墙。用
*
号表示,而一个四面被围墙围住的区域洪水是进不去的。oibh 总部内部也有许多重要区域,每个重要区域在图中用一个
0
表示。现在给出 oibh 的围墙建设图,问有多少个没被洪水淹到的重要区域。
输入格式
第一行为两个正整数 x,y 。
接下来 x 行,每行 y 个整数,由
*
和0
组成,表示 oibh 总部的建设图。输出格式
输出没被水淹没的 oibh 总部的
0
的数量。样例 #1
样例输入 #1
4 5 00000 00*00 0*0*0 00*00
样例输出 #1
1
样例 #2
样例输入 #2
5 5 ***** *0*0* **0** *0*0* *****
样例输出 #2
5
笔者对DFS暂且理解不深,就不献丑了,贴上题解代码,日后深入学习了DFS,再将本题拿出来拷打。
import java.util.*;
public class Main{static Scanner sc=new Scanner(System.in);static int N=sc.nextInt();static int M=sc.nextInt();static char a[][]=new char[501][501];static int dx[]= {0,1,0,-1};static int dy[]= {1,0,-1,0};public static void main(String[] args) {// TODO Auto-generated method stubfor(int i=1;i<=N;i++){String s=sc.next();for(int j=1;j<=M;j++){a[i][j]=s.charAt(j-1);}}//本质上就是外围的0全部被淹没,里面被包围的0幸存 因此从外围开始dfs,把外围的0全都染色了for(int i=1;i<=M;i++) //这里的N和M搞错了!固定行,求列应该用M{//第一行if(a[1][i]=='0') dfs(1,i);//最后一行if(a[N][i]=='0') dfs(N,i);}for(int j=1;j<=N;j++){//第一列if(a[j][1]=='0') dfs(j,1);//最后一列if(a[j][M]=='0') dfs(j,M);}int count=0;for(int i=1;i<=N;i++){for(int j=1;j<=M;j++){if(a[i][j]=='0') count++;}}System.out.println(count);}public static void dfs(int x,int y){a[x][y]=3; //先染色for(int i=0;i<4;i++){int newx=x+dx[i];int newy=y+dy[i];if(newx>=1&&newx<=N&&newy>=1&&newy<=M&&a[newx][newy]=='0'){//不越界且为0,则继续给这些外围的0染色dfs(newx,newy);}}}}
P1160 队列安排2
原题链接:
P1160 队列安排 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
队列安排
题目描述
一个学校里老师要将班上 N 个同学排成一列,同学被编号为 1 ~ N ,他采取如下的方法:
先将 1 号同学安排进队列,这时队列中只有他一个人;
2 ~ N 号同学依次入列,编号为 i 的同学入列方式为:老师指定编号为 i 的同学站在编号为 1 ~ i - 1 中某位同学(即之前已经入列的同学)的左边或右边;
从队列中去掉 M 个同学,其他同学位置顺序不变。
在所有同学按照上述方法队列排列完毕后,老师想知道从左到右所有同学的编号。
输入格式
第一行一个整数 N ,表示了有 N 个同学。
第 2 ~ N 行,第 i 行包含两个整数 k,p ,其中 k 为小于 i 的正整数, p 为 0 或者 1 。若 p 为 0 ,则表示将 i 号同学插入到 k 号同学的左边, p 为 1 则表示插入到右边。
第 N+1 行为一个整数 M ,表示去掉的同学数目。
接下来 M 行,每行一个正整数 x ,表示将 x 号同学从队列中移去,如果 x 号同学已经不在队列中则忽略这一条指令。
输出格式
一行,包含最多 N 个空格隔开的整数,表示了队列从左到右所有同学的编号。
样例 #1
样例输入 #1
4 1 0 2 1 1 0 2 3 3
样例输出 #1
2 4 1
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;class Node {int value;Node prev, next;Node(int value) {this.value = value;}
}public class Main {static BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));public static void main(String[] args) throws IOException {int N = Integer.parseInt(scan.readLine());Map<Integer, Node> nodeLookup = new HashMap<>();Node head = new Node(1);nodeLookup.put(1, head);//首先读取一个整数N,然后读取N行输入。每一行都包含一个整数X和一个标志B。//它在列表中查找值为X的元素,然后在其之前(如果B为0)或者之后(如果B为1)插入新的元素。//新元素的值为当前的循环次数(从2开始)。如果找不到值为X的元素,那么新元素将不会被插入。for (int i = 2; i <= N; i++) {String[] input = scan.readLine().split(" ");int X = Integer.parseInt(input[0]);int B = Integer.parseInt(input[1]);Node newNode = new Node(i);Node oldNode = nodeLookup.get(X);if (B == 0) {newNode.next = oldNode;newNode.prev = oldNode.prev;if (oldNode.prev != null) {oldNode.prev.next = newNode;}oldNode.prev = newNode;if (oldNode == head) {head = newNode;}} else {newNode.prev = oldNode;newNode.next = oldNode.next;if (oldNode.next != null) {oldNode.next.prev = newNode;}oldNode.next = newNode;}nodeLookup.put(i, newNode);}//然后,读取一个整数M,然后读取M行输入。每一行包含一个整数,表示需要从列表中删除的元素。int M = Integer.parseInt(scan.readLine());for (int i = 0; i < M; i++) {int data = Integer.parseInt(scan.readLine());Node nodeToRemove = nodeLookup.get(data);if (nodeToRemove != null) {if (nodeToRemove.prev != null) {nodeToRemove.prev.next = nodeToRemove.next;}if (nodeToRemove.next != null) {nodeToRemove.next.prev = nodeToRemove.prev;}if (nodeToRemove == head) {head = nodeToRemove.next;}nodeLookup.remove(data);}}for (Node node = head; node != null; node = node.next) {System.out.print(node.value + " ");}}
}
B3640 T3 句子反转
原题链接:
B3640 T3 句子反转 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
T3 句子反转
题目背景
请尽量在 30min 之内写完题目。这是指「写代码」的时间;「读题」时间不计算在内。
题目描述
给定一行句子,每个词之间用空格隔开,要么是全小写英文单词,要么是全大写英文单词,要么是自然数。
要求将这些单词倒序输出。而且对于每个单词,如果是小写词,应当转为大写;如果是大写词,应当转为小写;如果是自然数,应该倒转输出。
举一个例子:
we choose TO go 2 the 123 moon
程序应当输出:
MOON 321 THE 2 GO to CHOOSE WE
输入格式
仅一行,即需要反转的句子。
输出格式
仅一行,表示程序对句子的处理结果。
样例 #1
样例输入 #1
we choose TO go 2 the 123 moon
样例输出 #1
MOON 321 THE 2 GO to CHOOSE WE
提示
样例解释
首先应当按单词逆序,即:
moon 123 the 2 go TO choose we
小写变大写、大写变小写、倒转自然数之后,得到最终结果:
MOON 321 THE 2 GO to CHOOSE WE
数据规模与约定
对于 100% 的数据,句子中包含的单词数量不超过 1000 ,每个单词长度不超过 6 。
字符串反转并不陌生,但如果加上一些限制条件呢?
其实也不难,笔者做的时候居然在获取字符串的地方犯难了,罪过罪过,后来查资料才知道java应该如何获取字符串,而后对字符串进行一些操作:
先介绍思路,再贴上一些没用过的方法吧~
首先将整个字符串反转,然后用快慢指针找到每个单词,分别对这些单词进行操作即可。
import java.util.Scanner;
public class Main{static void Reverse(char[] string,int left,int right){while(left <= right) {char temp = string[left];string[left] = string[right];string[right] = temp;left++;right--;}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);String s = sc.nextLine();char[] string = s.toCharArray();int len = string.length;int slow = 0;int fast = len;//先将整体翻转Reverse(string,slow,fast-1);//fast指向某个单词的结尾,slow指向某个单词的开始for(fast = 0;fast < len;fast++){//fast指针停在某个单词后的空格处while(fast < len && string[fast] != ' '){fast++;}Reverse(string,slow,fast-1);int left = slow;int right = fast -1;//按照题目要求分别处理if (Character.isLowerCase(string[left])) {while (left <= right) {string[left] = Character.toUpperCase(string[left]);left++;}} else if (Character.isUpperCase(string[left])) {while (left <= right) {string[left] = Character.toLowerCase(string[left]);left++;}} else {while (left <= right) {char t = string[left];string[left] = string[right];string[right] = t;left++;right--;}}// 继续向后移动slow = fast + 1;}System.out.println(string);}
}
这里贴上笔者写题的时候不会用或者比较陌生的方法:
Character 类
序号 方法与描述 1 isLetter() 是否是一个字母 2 isDigit() 是否是一个数字字符 3 isWhitespace() 是否是一个空白字符 4 isUpperCase() 是否是大写字母 5 isLowerCase() 是否是小写字母 6 toUpperCase() 指定字母的大写形式 7 toLowerCase() 指定字母的小写形式 8 toString() 返回字符的字符串形式,字符串的长度仅为1
P1059 [NOIP2006 普及组] 明明的随机数
原题链接:
[P1059 NOIP2006 普及组] 明明的随机数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
[NOIP2006 普及组] 明明的随机数
题目描述
明明想在学校中请一些同学一起做一项问卷调查,为了实验的客观性,他先用计算机生成了 N 个 1 到 1000 之间的随机整数 (N\leq100) ,对于其中重复的数字,只保留一个,把其余相同的数去掉,不同的数对应着不同的学生的学号。然后再把这些数从小到大排序,按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。
输入格式
输入有两行,第 1 行为 1 个正整数,表示所生成的随机数的个数 N。
第 2 行有 N 个用空格隔开的正整数,为所产生的随机数。
输出格式
输出也是两行,第 1 行为 1 个正整数 M,表示不相同的随机数的个数。
第 2 行为 M 个用空格隔开的正整数,为从小到大排好序的不相同的随机数。
样例 #1
样例输入 #1
10 20 40 32 67 40 20 89 300 400 15
样例输出 #1
8 15 20 32 40 67 89 300 400
全部放到数组中,两次遍历代替去重操作,然后sort排序即可。
import java.util.Scanner;import static java.util.Arrays.sort;public class Main{public static void main(String[] args) {int num = 0;Scanner s = new Scanner(System.in);num = s.nextInt();int[] hash = new int[1001];for(int i = 0;i < num;i++){int tmp = 0;tmp = s.nextInt();hash[tmp]++;}int j = 0;for(int i = 0;i <= 1000;i++){if(hash[i] > 0){j++;}}int[] arr = new int[j];int cnt = 0;for(int i = 0;i <= 1000;i++){if(hash[i] > 0){arr[cnt++] = i;}}sort(arr);System.out.println(j);for(int i = 0;i < arr.length;i++){System.out.printf("%d ",arr[i]);}}
}
P3817 小A的糖果
原题链接:
P3817 小A的糖果 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
小A的糖果
题目描述
小 A 有 n 个糖果盒,第 i 个盒中有 a_i 颗糖果。
小 A 每次可以从其中一盒糖果中吃掉一颗,他想知道,要让任意两个相邻的盒子中糖的个数之和都不大于 x ,至少得吃掉几颗糖。
输入格式
输入的第一行是两个用空格隔开的整数,代表糖果盒的个数 n 和给定的参数 x 。
第二行有 n 个用空格隔开的整数,第 i 个整数代表第 i 盒糖的糖果个数 a_i 。
输出格式
输出一行一个整数,代表最少要吃掉的糖果的数量。
样例 #1
样例输入 #1
3 3 2 2 2
样例输出 #1
1
样例 #2
样例输入 #2
6 1 1 6 1 2 0 4
样例输出 #2
11
样例 #3
样例输入 #3
5 9 3 1 4 1 5
样例输出 #3
0
提示
样例输入输出 1 解释
吃掉第 2 盒中的一个糖果即可。
样例输入输出 2 解释
第 2 盒糖吃掉 6 颗,第 4 盒吃掉 2 颗,第 6 盒吃掉 3 颗。
import java.util.Scanner;
public class Main{public static void main(String[] args) {long sum = 0;Scanner sc = new Scanner(System.in);int n = sc.nextInt();int x = sc.nextInt();long[] a = new long[n + 1];a[1] = sc.nextInt();if(a[1] > x){sum += a[1] - x;a[1] = x;}for(int i = 2;i <= n;i++){a[i] = sc.nextInt();if(a[i] + a[i-1] > x){sum += a[i] + a[i-1] - x;a[i] = x - a[i-1];}}System.out.println(sum);}
}
Sp. 低洼地
先去重再遍历,没啥好说的,放代码~
import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[] arr = new int[n];for (int i = 0; i < n; i++) {arr[i] = scanner.nextInt();}int newIndex = 0;for (int i = 0; i < n; i++) {if (i == 0 || arr[i] != arr[i - 1]) {arr[newIndex++] = arr[i];}}n = newIndex;int cnt = 0;for (int i = 1; i < n - 1; i++) {if (arr[i] < arr[i + 1] && arr[i] < arr[i - 1]) {cnt++;}}System.out.println(cnt);}
}
这篇关于【算法】实验室2024年二面纳新题复盘的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!