本文写于 2019年04月11日，距今已超过 1 年，距 2020年03月27日 的最后一次修改也已超过 3 个月，部分内容可能已经过时，您可以按需阅读。如果图片无法显示或者下载链接失效，请给我反馈，谢谢！
Visits: 396
第 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