题目:
- 试题A: 星期计算
- 试题B: 山
- 试题C: 字符统计
- 试题D: 最少刷题数
- 试题E: 求阶乘
- 试题F: 最大子矩阵
- 试题G: 数组切分
- 试题H: 回忆迷宫
- 试题I: 红绿灯
- 试题J: 拉箱子
- 总结
试题A: 星期计算
import java.math.BigInteger;public class Main {public static void main(String[] args) {BigInteger n = new BigInteger("20");for (int i = 1; i < 22; i++) {n = n.multiply(BigInteger.valueOf(20L));}// 6 7 1 2 3 4 5System.out.println(n.remainder(BigInteger.valueOf(7L))); // 1}}
结果对7取余是1,n个7天后回到周六,周六的一天后是周日,题目要求用1-7表示。
答案:
7
试题B: 山
public class Main {public static void main(String[] args) {int num = 0;for (int i = 2022; i <= 2022222022; i++) {if (a(i)) {num++;}}System.out.println(num);//3138}public static Boolean a(int n) {Boolean flag = true;char[] chars = String.valueOf(n).toCharArray();for (int i = 1; i < chars.length / 2 + (chars.length % 2); i++) {if (chars[i] < chars[i - 1]) {return false;}}for (int i = 0; i < chars.length / 2; i++) {if (chars[i] != chars[chars.length - i - 1]) {return false;}}return true;}}
纯暴力破解计算,不过这道题有个坑,题目只要求先单调不减,后单调不增,也就是2222这种连续的也在结果内,代码中 a(); 方法先判断是否先单调不减,后单调不增,再判断是否对称,写文时感觉顺序反下应该会快点,这个方法还是得跑一会的。
答案:
3138
试题C: 字符统计
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String s = sc.nextLine();char[] chars = s.toCharArray();int[] arr = new int[26];for (int i = 0; i < chars.length; i++) {arr[(int) chars[i] - 65]++;}int max = 0;for (int i = 0; i < arr.length; i++) {if (arr[i] > max) {max = arr[i];}}for (int i = 0; i < arr.length; i++) {if (arr[i] == max) {System.out.print((char) (i + 65));}}}}
这道题先统计输入的字符串每个字符的次数,然后遍历一遍找出最大次数,再遍历一遍输出次数与最大次数相同的字符。
试题D: 最少刷题数
import java.util.Comparator;import java.util.LinkedList;import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();LinkedList<Integer> list = new LinkedList<>();for (int i = 0; i < n; i++) {list.add(sc.nextInt());}Object[] arr = list.toArray();list.sort(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o1 > o2 ? 1 : -1;}});// 输入排序完成int length = list.size(), num = list.get(length / 2);if (length % 2 == 1) {if ((int) arr[0] < num) {System.out.print((num - (int) arr[0] + 1));} else {System.out.print(0);}for (int i = 1; i < arr.length; i++) {if ((int) arr[i] < num) {System.out.print(" " + (num - (int) arr[i] + 1));} else {System.out.print(" " + 0);}}} else {if ((int) arr[0] < num) {System.out.print(num - (int) arr[0]);} else {System.out.print(0);}for (int i = 1; i < arr.length; i++) {if ((int) arr[i] < num) {System.out.print(" " + (num - (int) arr[i]));} else {System.out.print(" " + 0);}}}}}
这道题首先对输入的刷题数进行排序,然后进行分情况考虑,奇数情况下需要超过中间值才能满足全班刷题比他多的学生数不超过刷题比他少的学生数。偶数情况下需要等于中间偏大的值就可以满足条件。
试题E: 求阶乘
import java.math.BigInteger;import java.util.Scanner;public class Main2 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);for (int k = 1; k < 100; k++) {// n表示当前0的位数,k表示需要0的位数// int k = sc.nextInt(), n = 0;int n = 0;BigInteger sum = BigInteger.ONE, i = BigInteger.ZERO;while (n < k) {i = i.add(BigInteger.ONE);sum = sum.multiply(i);//此时sum是i的去尾0阶乘// 给sum去0while (sum.remainder(BigInteger.TEN).toString().equals("0")) {sum = sum.divide(BigInteger.TEN);n++;}}System.out.println(k);if (n == k) {System.out.println(i);} else {System.out.println(-1);}System.out.println();}}}
这段代码的结果,通过结果不难发现规律,六个为一组(第一组可以认为从0开始)。首先(n+1)%6==0,则输出-1;其他数为 (n-组号)5,组号从0开始,每6个组号+1
如3是第一组(组号为0),所以3的值为(3-0)* 5=15,
再比如14为第三组(组号为2),所以14对应的值为(14-2)* 5=120。
计算组号可通过 n/6 计算,还是上面的例子, 3/6=0 ,14/6=2
152103154205-1625730835940104511-11250135514601565167017-11875198020852190229523-1
所以可以将代码简化
import java.math.BigInteger;import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String k = sc.nextLine();BigInteger bigK = new BigInteger(k);BigInteger n = bigK.divide(BigInteger.valueOf(6L));if (bigK.subtract(BigInteger.valueOf(5L)).remainder(BigInteger.valueOf(6L)).toString().equals("0")) {System.out.println(-1);} else {System.out.println(bigK.subtract(n).multiply(BigInteger.valueOf(5L)));}}}
试题F: 最大子矩阵
import java.util.Scanner;public class Main {public static int[][] map;public static int[][] v;public static int max;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();map = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {map[i][j] = sc.nextInt();}}int limit = sc.nextInt();Integer maxx = 0;// 从地图中每个点开始搜素for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {// 每次搜索把这个max初始化为0max = 0;v = new int[n][m];dfs(i, j, limit, i, i, j, j, n, m, map[i][j], map[i][j]);// 搜索结束与之前点搜出来的最大值比较if (maxx < max) {maxx = max;}}}System.out.println(maxx);}public static int[] px = {0, 0, 1, -1};public static int[] py = {1, -1, 0, 0};// x,y为当前访问坐标,limit为题目要求极限,udlr为上下左右边界// nn,mm为地图大小,dmax,dmin为当前访问过所有的点中最大值最小值public static void dfs(int x, int y, int limit, int u, int d, int l, int r, int nn, int mm, int dmax, int dmin) {// 判断是不是矩形Boolean flag = true;for (int i = u; i <= d; i++) {for (int j = l; j <= r; j++) {if (v[i][j] == 0) {flag = false;i = d + 1;break;}}}if (flag) {int m = (d - u + 1) * (r - l + 1);if (m > max) {max = m;}}int xx, yy;for (int i = 0; i < 4; i++) {xx = x + px[i];yy = y + py[i];if (xx >= 0 && xx < nn && yy >= 0 && yy < mm && v[xx][yy] == 0) {//考虑极限if (map[xx][yy] > dmax) {dmax = map[xx][yy];}if (map[xx][yy] < dmin) {dmin = map[xx][yy];}// 满足极限要求if (dmax - dmin <= limit) {v[xx][yy] = 1;// 判断下个访问的点是否超出边界,如果超出则扩大边界if (u > xx)u = xx;if (l > yy)l = yy;if (d < xx)d = xx;if (r < yy)r = yy;dfs(xx, yy, limit, u, d, l, r, nn, mm, dmax, dmin);// 这里搜索结束应该忘记把当前最大值最小值回溯了v[xx][yy] = 0;}}}}}
因为只学过搜索,但是不知道怎么判断是不是矩形,所以判断矩形部分非常暴力,思路是搜索一次就通过上下左右四个边界判断边界内的点是否都访问过,如果都访问过则代表当前为矩形。
上下左右边界则是每次搜索都要判断这个点是否超过边界,如果超过边界则将边界扩大。
从每个点都开始深搜,最后输出所有点搜出的结果的最大值。
试题G: 数组切分
import java.math.BigInteger;import java.util.ArrayList;import java.util.Comparator;import java.util.LinkedList;import java.util.Scanner;public class Main {public static int[] arr;public static int[] v;public static BigInteger summ = BigInteger.ZERO;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();arr = new int[n];for (int i = 0; i < n; i++) {arr[i] = sc.nextInt();}for (int i = 1; i < n; i++) {// 初始化标记数组v = new int[n - 1];// 从第0刀,切的总数1-(n-1)进行遍历dfs(0, i);}// 因为是1-n的排列,所以一定存在一刀不切且成立的情况System.out.println(summ.add(BigInteger.ONE));}public static void dfs(int n, int sum) {// 切的次数n与总次数sum相等if (n == sum) {// 当前切段开始位置和结束位置int start = 0, stop = 0;Boolean flag = true;// 遍历标记数组for (int i = 0; i < v.length; i++) {// 如果标记数组为1,代表从数组指定位置后方切割if (v[i] == 1) {stop = i + 1;LinkedList<Integer> list = new LinkedList<>();for (int j = start; j < stop; j++) {list.add(arr[j]);}list.sort(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o1 > o2 ? 1 : -1;}});// 排序后将linkedlist变为arraylist加快遍历速度ArrayList<Integer> aList = new ArrayList<>(list);for (int i1 = 1; i1 < aList.size(); i1++) {// 排序后的list如果相邻两个数相差不为1,代表集合不连续,这种切割情况不满足题意if (aList.get(i1) - aList.get(i1 - 1) != 1) {flag = false;i = v.length;break;}}start = i + 1;}}// 判断切的最后一刀之后是否连续LinkedList<Integer> list = new LinkedList<>();for (int j = start; j < arr.length; j++) {list.add(arr[j]);}list.sort(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o1 > o2 ? 1 : -1;}});// 排序后将linkedlist变为arraylist加快遍历速度ArrayList<Integer> aList = new ArrayList<>(list);for (int i1 = 1; i1 < aList.size(); i1++) {// 排序后的list如果相邻两个数相差不为1,代表集合不连续,这种切割情况不满足题意if (aList.get(i1) - aList.get(i1 - 1) != 1) {flag = false;break;}}if (flag) {summ = summ.add(BigInteger.ONE);// 输出切割情况for (int i = 0; i < v.length; i++) {System.out.print(v[i] + ",");}System.out.println();if (summ.compareTo(BigInteger.valueOf(1000000007L)) == 0) {summ = BigInteger.ZERO;System.out.println(1);}}// 达到切的次数,结束搜索return;}// 保证每次切的都在切过的地方的后方,防止重复int i = 0;for (int i1 = 0; i1 < v.length; i1++) {if (v[i1] == 1) {i = i1 + 1;}}for (; i < v.length; i++) {if (v[i] == 0) {v[i] = 1;dfs(n + 1, sum);v[i] = 0;}}}}
这道题思路是首先考虑能切几刀,然后找出1刀到n-1刀切的所有情况。
切的位置从前往后依次选择,注意的是,如果第一刀在第二个位置,那么要小心第二刀切在第一个位置,要避免这种情况,否则会与第一刀在第一个位置第二刀在第二个位置重复。
写法依旧暴力,所以就算交上估计也对不了,测试100000 输入1-100000,跑3个小时没跑出来放弃了,但是20 1-20还是很快能出来的。
试题H: 回忆迷宫
import java.util.Arrays;import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt();char[] step = sc.next().toCharArray();char[][] map = new char[204][204];for (int i = 0; i < map.length; i++) {Arrays.fill(map[i], '*');}// 当前坐标int x = 100, y = 100;map[x][y] = ' ';// 上下左右边界int u = 99, d = 101, l = 99, r = 101;for (int i = 0; i < step.length; i++) {switch (step[i]) {case 'U':x--;if (u >= x)u = x - 1;map[x][y] = ' ';break;case 'L':y--;if (l >= y)l = y - 1;map[x][y] = ' ';break;case 'D':x++;if (d <= x)d = x + 1;map[x][y] = ' ';break;case 'R':y++;if (r <= y)r = y + 1;map[x][y] = ' ';break;}}map[u][l] = ' ';map[u][r] = ' ';map[d][l] = ' ';map[d][r] = ' ';for (int i = u; i <= d; i++) {for (int j = l; j <= r; j++) {System.out.print(map[i][j]);}System.out.println();}}}
这道题也只会暴力,还不确定对,思路是通过边界围出一个爱丽丝走过的最小的矩形,同时矩形四个角也置空地,每走一步判断是否超过边界,超过将边界扩大。最后将地图输出,爱丽丝走过的与四角为空格,其余为 * 。
试题I: 红绿灯
这道题考试的时候写了一种能开氮气就直接开,计算最后时间,显然当时考虑简单了,所以代码不放了。
试题J: 拉箱子
后两题都太难了,我都没有写出来,欢迎大佬评论区说下思路,放下代码
总结
总的看今年还是比去年的难很多了,后面还是得每天花点时间学习下算法,最后祈祷今年能拿个省二吧!