F、旋转
试题 F: 旋转
时间限制: 1.0s 内存限制: 512.0MB 本题总分:15 分
【问题描述】
图片旋转是对图片最简单的处理方式之一,在本题中,你需要对图片顺时
针旋转 90 度。
我们用一个 n × m 的二维数组来表示一个图片,例如下面给出一个 3 × 4 的
图片的例子:
1 3 5 7
9 8 7 6
3 5 9 7
这个图片顺时针旋转 90 度后的图片如下:
3 9 1
5 8 3
9 7 5
7 6 7
给定初始图片,请计算旋转后的图片。
【输入格式】
输入的第一行包含两个整数 n 和 m,分别表示行数和列数。
接下来 n 行,每行 m 个整数,表示给定的图片。图片中的每个元素(像
素)为一个值为 0 至 255 之间的整数(包含 0 和 255)。
【输出格式】
输出 m 行 n 列,表示旋转后的图片。
【样例输入】
3 4
1 3 5 7
9 8 7 6
3 5 9 7
【样例输出】
3 9 1
5 8 3
9 7 5
7 6 7
【评测用例规模与约定】
对于 30% 的评测用例,1 ≤ n, m ≤ 10。
对于 60% 的评测用例,1 ≤ n, m ≤ 30。
对于所有评测用例,1 ≤ n, m ≤ 100。
题解:
package action; import java.util.Scanner; public class demo { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int [][] arr = new int[n+1][m+1]; for (int i = 1; i < arr.length; i++) { for (int j = 1; j < arr[i].length; j++) { arr[i][j] = sc.nextInt(); } } int [][] brr = new int[m+1][n+1]; // 转换 for (int i = 1; i < brr.length; i++) { for (int j = 1; j < brr[i].length; j++) { brr[i][j] = arr[n-j+1][i]; } } // 打印 for (int i = 1; i < brr.length; i++) { for (int j = 1; j < brr[i].length; j++) { System.out.print(brr[i][j]+" "); } System.out.println(); } } }
G、外卖店优先级
试题 G: 外卖店优先级
时间限制: 1.0s 内存限制: 512.0MB 本题总分:20 分
【问题描述】
“饱了么”外卖系统中维护着 N 家外卖店,编号 1 ∼ N。每家外卖店都有
一个优先级,初始时 (0 时刻) 优先级都为 0。
每经过 1 个时间单位,如果外卖店没有订单,则优先级会减少 1,最低减
到 0;而如果外卖店有订单,则优先级不减反加,每有一单优先级加 2。
如果某家外卖店某时刻优先级大于 5,则会被系统加入优先缓存中;如果
优先级小于等于 3,则会被清除出优先缓存。
给定 T 时刻以内的 M 条订单信息,请你计算 T 时刻时有多少外卖店在优
先缓存中。
【输入格式】
第一行包含 3 个整数 N、M 和 T。
以下 M 行每行包含两个整数 ts 和 id,表示 ts 时刻编号 id 的外卖店收到
一个订单。
【输出格式】
输出一个整数代表答案。
【样例输入】
2 6 6
1 1
5 2
3 1
6 2
2 1
6 2
【样例输出】
1
【样例解释】
6 时刻时,1 号店优先级降到 3,被移除出优先缓存;2 号店优先级升到 6,
加入优先缓存。所以是有 1 家店 (2 号) 在优先缓存中。
【评测用例规模与约定】
对于 80% 的评测用例,1 ≤ N, M, T ≤ 10000。
对于所有评测用例,1 ≤ N, M, T ≤ 100000,1 ≤ ts ≤ T,1 ≤ id ≤ N
题解:
package action; import java.util.Scanner; public class demo { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int t = sc.nextInt(); int[][] arr = new int[n + 1][t + 1]; for (int i = 0; i < m; i++) { int t1 = sc.nextInt(); // 时刻 int n1 = sc.nextInt(); // 几店 arr[n1][t1]++; // n店t时刻的订单数 } int count = 0; // 优先缓存个数 // 对每家店进行计算 for (int i = 1; i <= n; i++) { int num = 0; // 缓存值 boolean f = false; // 判断是否是优先缓存 for (int j = 1; j <= t; j++) { if (arr[i][j] == 0) { // 没有订单时 if (num <= 0) { num = 0; } else { num--; } } else { num += 2 * arr[i][j]; // 有订单时:缓存值是每个订加2 } if (num > 5) { f = true; } if (num <= 3) { f = false; } } if (f) { count++; } } System.out.println(count); } }
测试数据通过
H、人物相关性分析
试题 H: 人物相关性分析
时间限制: 1.0s 内存限制: 512.0MB 本题总分:20 分
【问题描述】
小明正在分析一本小说中的人物相关性。他想知道在小说中 Alice 和 Bob
有多少次同时出现。
更准确的说,小明定义 Alice 和 Bob“同时出现”的意思是:在小说文本
中 Alice 和 Bob 之间不超过 K 个字符。
例如以下文本:
This is a story about Alice and Bob. Alice wants to send a private message to Bob.
假设 K = 20,则 Alice 和 Bob 同时出现了 2 次,分别是”Alice and Bob”
和”Bob. Alice”。前者 Alice 和 Bob 之间有 5 个字符,后者有 2 个字符。
注意:
1. Alice 和 Bob 是大小写敏感的,alice 或 bob 等并不计算在内。
2. Alice 和 Bob 应为单独的单词,前后可以有标点符号和空格,但是不能
有字母。例如 Bobbi 並不算出现了 Bob。
【输入格式】
第一行包含一个整数 K。
第二行包含一行字符串,只包含大小写字母、标点符号和空格。长度不超
过 1000000。
【输出格式】
输出一个整数,表示 Alice 和 Bob 同时出现的次数。
【样例输入】
20
This is a story about Alice and Bob. Alice wants to send a private message to Bob.
【样例输出】
2
【评测用例规模与约定】
对于所有评测用例,1 ≤ K ≤ 1000000。
题解:
package action; import java.util.Scanner; public class demo { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int K = sc.nextInt(); sc.nextLine(); String str = sc.nextLine(); int count = 0; for (int i = 0; i < str.length() - 8; i++) { if (str.charAt(i) == 'A') { String alicestr = str.substring(i, i + 5); if (alicestr.equals("Alice")) { for (int j = 0; j < K - 3; j++) { if (str.charAt(i + j) == 'B') { String bobstr = str.substring(i + j, i + j + 3); if (bobstr.equals("Bob")) { count++; } } } } } if (str.charAt(i) == 'B') { String bobstr = str.substring(i, i + 3); System.out.println(bobstr); if (bobstr.equals("Bob")) { for (int j = 0; j < K - 5; j++) { if (str.charAt(i + j) == 'A') { String alicestr = str.substring(i + j, i + j + 5); System.out.println(alicestr); if (alicestr.equals("Alice")) { count++; } } } } } } System.out.println(count); } }
测试数据通过
I、等差数列
试题 I: 等差数列
时间限制: 1.0s 内存限制: 512.0MB 本题总分:25 分
【问题描述】
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一
部分的数列,只记得其中 N 个整数。
现在给出这 N 个整数,小明想知道包含这 N 个整数的最短的等差数列有
几项?
【输入格式】
输入的第一行包含一个整数 N。
第二行包含 N 个整数 A1, A2, · · · , AN。(注意 A1 ∼ AN 并不一定是按等差数
列中的顺序给出)
【输出格式】
输出一个整数表示答案。
【样例输入】
5
2 6 4 10 20
【样例输出】
10
【样例说明】
包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、
18、20。
【评测用例规模与约定】
对于所有评测用例,2 ≤ N ≤ 100000,0 ≤ Ai ≤ 109。
题解:
package action; import java.util.Arrays; import java.util.Scanner; public class demo { 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 < arr.length; i++) { arr[i] = sc.nextInt(); } Arrays.sort(arr); // 获取最小差值 int min = arr[arr.length - 1]; for (int i = 1; i < arr.length; i++) { if ((arr[i] - arr[0]) < min) { min = (arr[i] - arr[0]); } } System.out.println((arr[arr.length - 1] - arr[0]) / min + 1); } }
J、打扫机器人
试题 J: 扫地机器人
时间限制: 1.0s 内存限制: 512.0MB 本题总分:25 分
【问题描述】
小明公司的办公区有一条长长的走廊,由 N 个方格区域组成,如下图所
示。
走廊内部署了 K 台扫地机器人,其中第 i 台在第 Ai 个方格区域中。
已知扫地机器人每分钟可以移动到左右相邻的方格中,并将该区域清扫干
净。
请你编写一个程序,计算每台机器人的清扫路线,使得
1. 它们最终都返回出发方格,
2. 每个方格区域都至少被清扫一遍,
3. 从机器人开始行动到最后一台机器人归位花费的时间最少。
注意多台机器人可以同时清扫同一方块区域,它们不会互相影响。
输出最少花费的时间。
在上图所示的例子中,最少花费时间是 6。第一台路线:2-1-2-3-4-3-2,清
扫了 1、2、3、4 号区域。第二台路线 5-6-7-6-5,清扫了 5、6、7。第三台路线
10-9-8-9-10,清扫了 8、9 和 10。
【输入格式】
第一行包含两个整数 N 和 K。
接下来 K 行,每行一个整数 Ai。
案例:
输入:
10 3
3 5 8
输出:
6
题解视频:
【JavaC组第十届第十题扫地机器人_哔哩哔哩_bilibili】
题解:
package action; import java.util.Arrays; import java.util.Scanner; public class demo { static int N,K; static int arr[];//存储机器人坐标 public static void main(String[] args) { Scanner sc=new Scanner(System.in); N=sc.nextInt(); K=sc.nextInt(); arr=new int[K]; for (int i = 0; i < K; i++) { arr[i]=sc.nextInt(); } //输入流没用了 sc.close(); Arrays.sort(arr);//自然排序 int l=0,r=N,mid=0; while (l <= r) { //相当于二分查找 mid=(r+l)>>>1; if(check(mid)) { r = mid-1; }else l = mid+1; } System.out.println((mid-1)*2); } private static boolean check(int m) { int sum=0;//记录扫描区域 for (int i = 0; i < K; i++) {//遍历每个机器人 if(arr[i]-m<=sum) { if(arr[i]<=sum) { sum=arr[i]+m-1; }else sum+=m; }else return false; } return sum >= N; } }
测试数据:
10 3 5 2 10