【算法】2022第五届“传智杯”全国大学生计算机大赛（练习赛）

news/2024/4/28 14:23:20/文章来源:https://blog.csdn.net/Jruo911/article/details/128050964

【参考：第五届“传智杯”全国大学生计算机大赛（练习赛） - 洛谷 | 计算机科学教育新生态】

练习赛满分程序（多语言）：https://www.luogu.com.cn/paste/fi60s4yu

CPU一秒大概运行 $10^8$ 次，题目一般限时1000ms，自己计算时间复杂度吧！

B：时钟

【参考：T292112 [传智杯 #5 练习赛] 时钟 - 洛谷 | 计算机科学教育新生态】
在这里插入图片描述

先计算一天的好时刻

import java.util.Scanner;class Main {public static void main(String[] args) {// Main main = new Main();Scanner scanner = new Scanner(System.in);// 计算一天的好时刻 0:00-23:59int result = 0;int n = 1440; // 一天有1440分钟for (int h = 0; h < 24; h++) {for (int m = 0; m < 60; m++) {// h1h2:m1m2int h1 = h / 10; // 小时的第一位int h2 = h % 10; // 小时的第二位，下同int m1 = m / 10;int m2 = m % 10;// 判断等差if (h >= 10 && h2 - h1 == m1 - h2 && m1 - h2 == m2 - m1) {result++;System.out.printf("%d%d:%d%d\n", h1, h2, m1, m2);}if (h <= 9 && m1 - h2 == m2 - m1) {result++;System.out.printf("%d%d:%d%d\n", h1, h2, m1, m2);}n--;// 过去一分钟if (n < 0) // 遍历完了break;}}System.out.println(result);}}

最后答案

import java.util.Scanner;class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int day = n / 1440;n %= 1440; // 还剩多少分钟int result = day * 39;for (int h = 0; h < 24; h++) {for (int m = 0; m < 60; m++) {// h1h2:m1m2int h1 = h / 10; // 小时的第一位int h2 = h % 10; // 小时的第二位，下同int m1 = m / 10;int m2 = m % 10;// 判断等差if (h >= 10 && h2 - h1 == m1 - h2 && m1 - h2 == m2 - m1) {result++;// System.out.printf("%d%d:%d%d\n", h1, h2, m1, m2);}if (h <= 9 && m1 - h2 == m2 - m1) {result++;// System.out.printf("%d%d:%d%d\n", h1, h2, m1, m2);}n--;// 过去一分钟if (n < 0) // 遍历完了break;}}System.out.println(result);}}

C：平等的交易

【参考：T292113 [传智杯 #5 练习赛] 平等的交易 - 洛谷 | 计算机科学教育新生态】

贪心

只买一次，无限次交换
为了尽可能的交换，那就尽可能先买最贵的，然后交换价值最低的物品
在这里插入图片描述

需使用快读模板

import java.io.*;
import java.util.*;class Main {public static void main(String[] args) throws IOException {// 快速读取 int double long （char不行）StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));in.nextToken();int n = (int) in.nval;int[] a = new int[n];for (int i = 0; i < n; i++) {in.nextToken();a[i] = (int) in.nval;}in.nextToken();int w = (int) in.nval;int result = 0;Arrays.sort(a);int k = 0; // 买的物品的价值// 尽可能买最贵的那个for (int i = n - 1; i >= 0; i--) {if (w >= a[i]) {k = a[i];break;}}for (int i = 0; i < n; i++) {if (k <= 0)break;if (k >= a[i]) {result++;k -= a[i];}}System.out.println(result);}
}

D：清洁工

【参考：T292114 [传智杯 #5 练习赛] 清洁工 - 洛谷 | 计算机科学教育新生态】

思路：由于题目给的数据范围比较小，直接暴力即可。只要坐标不是被走到的那一个，灰尘就可以直接加1，如果是被走到的点，灰尘数不变并将记录的灰尘累计单位清零。最后按照题目要求的格式输出每个坐标的灰尘数即可。

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);int n, m, x, y;n = input.nextInt();m = input.nextInt();x = input.nextInt();y = input.nextInt();String S = input.next();char[] cArr = S.toCharArray();int num = (m * (1 + m)) / 2;int[][] arr = new int[n + 1][n + 1]; // 计算格子上的灰的数量int[][] arr2 = new int[n + 1][n + 1]; // 存储格子上的灰的增量，默认初始为0int t = 1; // 移动次数for (char c : cArr) {if (t > m)break;arr2[x][y] = 0; // 经过当前格子，有人经过时不会落灰但灰也不会清零for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (i != x || j != y) {arr2[i][j]++; // 落灰arr[i][j] += arr2[i][j]; // 加上落灰的量}}}if (c == 'N')y += 1;else if (c == 'S')y -= 1;else if (c == 'W')x -= 1;elsex += 1;t++;}// 输出每一个位置上落下的灰的量// 第 i 行的第 j 个数表示坐标 (j,n-i+1)上的灰的数量for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {System.out.print(arr[j][n - i + 1] + " ");}System.out.println();}}
}