

第 1 题,100 分,没什么好说的,照着模拟就行了。
我是读进来一个字符串,补全到 8 的倍数,然后每 8 位一取,加入到 List,然后排序,最后输出。
顺利通过所有数据。

import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; public class Main{ public static void main(String args[]){ Scanner in = new Scanner(System.in); int n = in.nextInt(); ArrayList<String> list = new ArrayList<>(); for (int i = 0; i < n; i++) { StringBuffer sb = new StringBuffer(); sb.append(in.next()); while (sb.length() % 8 != 0) sb.append("0"); for (int j = 0; j < sb.length(); j += 8) { list.add(sb.substring(j, j + 8)); } } Collections.sort(list); boolean isFirst = true; for (String s : list) { if (isFirst) isFirst = false; else System.out.print(" "); System.out.print(s); } in.close(); } }
第 2 题,200 分,也没什么好说的,就是模拟。
括号是等价的,如果遇到括号,就找到匹配的括号组,对括号组内的部分可以递归地调动相同的处理函数,对于数组,就是重复后面的括号运算若干次,最后取反。
有 StringBuffer 以后事情变得简单,但是不知道为什么最后我是只通过了 80% 的数据,说数组下标越界。
要说超时或者答案错误还能理解,数组下标越界我是想不通,可能是哪里写炸了。

import java.util.Scanner; public class Main { public static void main(String args[]) { Scanner in = new Scanner(System.in); StringBuffer sb = new StringBuffer(); String inputString = in.next(); sb.append(decodeRecursively(inputString)); System.out.println(sb.reverse()); in.close(); } private static String decodeRecursively(String processingString) { StringBuffer sb = new StringBuffer(); int index = 0; int length = processingString.length(); while (index < length) { if (Character.isLetter(processingString.charAt(index))) { sb.append(processingString.charAt(index)); index++; } else if (Character.isDigit(processingString.charAt(index))) { StringBuffer num = new StringBuffer(); while (Character.isDigit(processingString.charAt(index))) { num.append(processingString.charAt(index)); index++; } long x = Long.parseLong(num.toString()); int end = findBracedSub(processingString, index); String sub = processingString.substring(index + 1, end - 1); index = end; while (x-- != 0) sb.append(decodeRecursively(sub)); } else { int end = findBracedSub(processingString, index); String sub = processingString.substring(index + 1, end - 1); index = end; sb.append(decodeRecursively(sub)); } } return sb.toString(); } private static int findBracedSub(String s, int index) { int end = index++; int[] braceNumber = new int[4]; boolean allClear = false; while (!allClear) { char c = s.charAt(end); switch (c) { case '(': braceNumber[0]++; break; case ')': braceNumber[0]--; break; case '[': braceNumber[1]++; break; case ']': braceNumber[1]--; break; case '{': braceNumber[2]++; break; case '}': braceNumber[2]--; break; case '<': braceNumber[3]++; break; case '>': braceNumber[3]--; break; } allClear = braceNumber[0] == 0 && braceNumber[1] == 0 && braceNumber[2] == 0 && braceNumber[3] == 0; end++; } return end; } }

第 3 题,DP,感觉动态规划总是要考的。
题目思想很简单,到达某个点的可能条数,就是这个点的上、下、左、右四个方向的可能条数全加到自己身上。
动态转移方程的计算必须按照一定顺序,这个顺序显然是海拔高度。
因此,就是先对所有的高度排序,然后从起点开始,每次一层一层地扫,把自己的条数加到自己上下左右的四个方向上的合法的点。
所谓合法,就是高度满足要求,且不越界。
我的实现没有排序,直接用了优先级队列。
Point 类实现了 Comparable 接口,比较的标准是海拔高度,小的优先,这样的话每次都是处理了海拔最小的才会算更高的(不然的话,计算高度为 5 的点有多少可能,由于 5 右边可能是 3,如果此时 3 的条数是不正确的,那么 5 的条数也是不正确的,因此必须先算高度低的,由于路径只能一路更大,所以当比它小的都算完了,它的值肯定也就唯一确定了)。
加入队列我用了 BFS,从起点开始,合法的点加入队列,直到队列空。
非常容易就过了。

import java.util.PriorityQueue; import java.util.Scanner; public class Main { public static void main(String args[]) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int m = in.nextInt(); int[][] g = new int[n][m]; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) g[i][j] = in.nextInt(); int s_x = in.nextInt(); int s_y = in.nextInt(); int t_x = in.nextInt(); int t_y = in.nextInt(); final int[][] DIRECTIONS = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }; final int MOD = 1000000000; int[][] dp = new int[n][m]; dp[s_x][s_y] = 1; PriorityQueue<Point> q = new PriorityQueue<>(); q.add(new Point(s_x, s_y, g[s_x][s_y])); while (!q.isEmpty()) { Point p = q.poll(); for (int k = 0; k < 4; k++) { int x = p.x + DIRECTIONS[k][0]; int y = p.y + DIRECTIONS[k][1]; if (x >= 0 && x < n && y >= 0 && y < m) { if (g[x][y] > g[p.x][p.y]) { Point pp = new Point(x, y, g[x][y]); if (!q.contains(pp)) q.add(pp); dp[x][y] += dp[p.x][p.y]; dp[x][y] %= MOD; } } } } System.out.println(dp[t_x][t_y]); in.close(); } } class Point implements Comparable<Point> { int x; int y; int g; public Point(int x, int y, int g) { super(); this.x = x; this.y = y; this.g = g; } @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + g; result = prime * result + x; result = prime * result + y; return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; Point other = (Point) obj; if (g != other.g) return false; if (x != other.x) return false; if (y != other.y) return false; return true; } @Override public int compareTo(Point o) { return Integer.compare(g, o.g); } } //4 5 //0 1 0 0 0 //0 2 3 0 0 //0 5 4 5 0 //0 6 7 6 0 //0 1 3 2 //Expected: 4