一、树形显示 描述
对于分类结构可以用树形来形象地表示。比如：文件系统就是典型的例子。
树中的结节具有父子关系。我们在显示的时候，把子项向右缩进（用空格，不是tab），并添加必要的连接线，以使其层次关系更醒目。
下面的代码就是为了这个目的的，请仔细阅读源码，并填写划线部分缺少的代码。
注意，只填写划线部分缺少的代码，不要抄写已有的代码或符号。
输入 没有输入。
输出
思路：我同学竟然试出来了，神奇，我也是按照他的思路进行试出来的/…
package day2; import java.util.*; class MyTree { private Map<String, List<String>> map_ch = new HashMap<String, List<String>>(); private Map<String,String> map_pa = new HashMap<String,String>(); public void add(String parent, String child) { map_pa.put(child, parent); List<String> lst = map_ch.get(parent); if(lst==null){ lst = new ArrayList<String>(); map_ch.put(parent, lst); } lst.add(child); } public String get_parent(String me){ return map_pa.get(me); } public List<String> get_child(String me){ return map_ch.get(me); } private String space(int n) { String s = ""; for(int i=0; i<n; i++) s += ' '; return s; } private boolean last_child(String x){ String pa = map_pa.get(x); if(pa==null) return true; List<String> lst = map_ch.get(pa); return lst.get(lst.size()-1).equals(x); } public void show(String x){ String s = "+--" + x; String pa = x; while(true){ pa = map_pa.get(pa); if(pa==null) break; s = (pa=="root"||pa=="duck"||pa=="YYcat"||pa=="XXcat-qq"||pa=="TTduck")?". "+s:"| "+s; // 填空 } System.out.println(s); } public void dfs(String x){ show(x); List<String> lst = map_ch.get(x); if(lst==null) return; for(String it: lst){ dfs(it); } } } public class TreeView { public static void main(String[] args) { MyTree tree = new MyTree(); tree.add("root", "dog"); tree.add("root", "cat"); tree.add("root", "duck"); tree.add("dog", "AAdog"); tree.add("dog", "BBdog"); tree.add("dog", "CCdog"); tree.add("AAdog", "AAdog01"); tree.add("AAdog", "AAdog02"); tree.add("cat", "XXcat"); tree.add("cat", "YYcat"); tree.add("XXcat","XXcat-oo"); tree.add("XXcat","XXcat-qq"); tree.add("XXcat-qq", "XXcat-qq-hahah"); tree.add("duck", "TTduck"); tree.add("TTduck", "TTduck-001"); tree.add("TTduck", "TTduck-002"); tree.add("TTduck", "TTduck-003"); tree.add("YYcat","YYcat.hello"); tree.add("YYcat","YYcat.yes"); tree.add("YYcat","YYcat.me"); tree.dfs("root"); } }二、 小计算器 描述
题目.txt
模拟程序型计算器，依次输入指令，可能包含的指令有
1. 数字：'NUM X'，X为一个只包含大写字母和数字的字符串，表示一个当前进制的数 2. 运算指令：'ADD','SUB','MUL','DIV','MOD'，分别表示加减乘，除法取商，除法取余 3. 进制转换指令：'CHANGE K'，将当前进制转换为K进制(2≤K≤36) 4. 输出指令：'EQUAL'，以当前进制输出结果 5. 重置指令：'CLEAR'，清除当前数字指令按照以下规则给出：
数字，运算指令不会连续给出，进制转换指令，输出指令，重置指令有可能连续给出
运算指令后出现的第一个数字，表示参与运算的数字。且在该运算指令和该数字中间不会出现运算指令和输出指令
重置指令后出现的第一个数字，表示基础值。且在重置指令和第一个数字中间不会出现运算指令和输出指令
进制转换指令可能出现在任何地方
运算过程中中间变量均为非负整数，且小于2^{63}2 63 。 以大写的'A'~'Z'表示10~35 输入 第1行：1个n，表示指令数量， 第2..n+1行：每行给出一条指令。指令序列一定以'CLEAR'作为开始，并且满足指令规则。输出 依次给出每一次’EQUAL’得到的结果。
输入样例 1
7 CLEAR NUM 1024 CHANGE 2 ADD NUM 100000 CHANGE 8 EQUAL 输出样例 1
2040 过60%数据的超时代码：
import java.io.IOException; import java.util.Scanner; public class Main { static String op = ""; static int hex = 10; static long[] num = new long[2]; public static void main(String[] args) throws IOException { Scanner sc=new Scanner(System.in); int n = sc.nextInt(); for (int i = 0; i <=n; i++) { String[] tmp = sc.nextLine().split(" "); // System.out.println(tmp[0]); operate(tmp); } } //操作 public static void operate (String[] tmp) throws IOException { if(tmp[0].equals("NUM") ){ if(op.equalsIgnoreCase("")){ num[0] = Long.valueOf(tmp[1], hex); } else { num[1] = Long.valueOf(tmp[1], hex); num[0] = caculate(); op = ""; } }else if(tmp[0].equals("ADD") ){ op = "ADD"; }else if(tmp[0].equals("SUB") ){ op = "SUB"; }else if(tmp[0].equals("MUL") ){ op = "MUL"; }else if(tmp[0].equals("DIV") ){ op = "DIV"; }else if(tmp[0].equals("MOD") ){ op = "MOD"; }else if(tmp[0].equals("CHANGE") ){ hex = Integer.parseInt(tmp[1]); }else if(tmp[0].equals("EQUAL") ){ print(); }else if(tmp[0].equals("CLEAR") ){ num[0] = 0; num[1] = 0; op = ""; } } //输出 public static void print(){ System.out.println(Long.toString(num[0], hex).toUpperCase()); // System.out.println(); } //计算 public static long caculate(){ long ret = 0; if(op.equals( "ADD")){ ret = num[0]+num[1]; // System.out.println(num[0]+" "+num[1]+" "+ret); }else if(op.equals("SUB")){ ret = num[0]-num[1]; }else if(op.equals("MUL")){ ret = num[0]*num[1]; }else if(op.equals("DIV")){ ret = num[0]/num[1]; }else if(op.equals("MOD")){ ret = num[0]%num[1]; } return ret; } }下面是ac的代码： 注意： BufferedReader sc=new BufferedReader(new InputStreamReader(System.in));比Scanner更快 但是上面的代码是<=n，下面的代码是<n，神奇…
package day2; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class t4 { static String op = ""; static int hex = 10; static long[] num = new long[2]; public static void main(String[] args) throws Exception { BufferedReader sc=new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(sc.readLine()); for (int i = 0; i <n; i++) { String[] tmp = sc.readLine().split(" "); // System.out.println(tmp[0]); operate(tmp); } } //操作 public static void operate (String[] tmp) throws IOException { if(tmp[0].equals("NUM") ){ if(op.equalsIgnoreCase("")){ num[0] = Long.valueOf(tmp[1], hex); } else { num[1] = Long.valueOf(tmp[1], hex); num[0] = caculate(); op = ""; } }else if(tmp[0].equals("ADD") ){ op = "ADD"; }else if(tmp[0].equals("SUB") ){ op = "SUB"; }else if(tmp[0].equals("MUL") ){ op = "MUL"; }else if(tmp[0].equals("DIV") ){ op = "DIV"; }else if(tmp[0].equals("MOD") ){ op = "MOD"; }else if(tmp[0].equals("CHANGE") ){ hex = Integer.parseInt(tmp[1]); }else if(tmp[0].equals("EQUAL") ){ print(); }else if(tmp[0].equals("CLEAR") ){ num[0] = 0; num[1] = 0; op = ""; } } //输出 public static void print(){ System.out.println(Long.toString(num[0], hex).toUpperCase()); // System.out.println(); } //计算 public static long caculate(){ long ret = 0; if(op.equals( "ADD")){ ret = num[0]+num[1]; // System.out.println(num[0]+" "+num[1]+" "+ret); }else if(op.equals("SUB")){ ret = num[0]-num[1]; }else if(op.equals("MUL")){ ret = num[0]*num[1]; }else if(op.equals("DIV")){ ret = num[0]/num[1]; }else if(op.equals("MOD")){ ret = num[0]%num[1]; } return ret; } }三、 路径之谜 描述
小明冒充X星球的骑士，进入了一个奇怪的城堡。
城堡里边什么都没有，只有方形石头铺成的地面。
假设城堡地面是 n x n 个方格。【如图1.png】所示。
图1.png
按习俗，骑士要从西北角走到东南角。
可以横向或纵向移动，但不能斜着走，也不能跳跃。
每走到一个新方格，就要向正北方和正西方各射一箭。
（城堡的西墙和北墙内各有 n 个靶子）
同一个方格只允许经过一次。但不必做完所有的方格。
如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？
有时是可以的，比如图1.png中的例子。
本题的要求就是已知箭靶数字，求骑士的行走路径（测试数据保证路径唯一）
输入 第一行一个整数N(0<N<20)，表示地面有 N x N 个方格
第二行N个整数，空格分开，表示北边的箭靶上的数字（自西向东）
第三行N个整数，空格分开，表示西边的箭靶上的数字（自北向南）
输出 一行若干个整数，表示骑士路径。
为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号: 0,1,2,3…
比如，图1.png中的方块编号为：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
输入样例 1
4 2 4 3 4 4 3 3 3 输出样例 1
0 4 5 1 2 3 7 11 10 9 13 14 15 过一组数据：
package day3; import java.util.LinkedList; import java.util.Scanner; public class t4 { static int [][]step={{-1,0},{1,0},{0,1},{0,-1}}; static boolean[][]vis; static int [] Nnum; static int []Snum; static LinkedList<Integer> hms=new LinkedList(); public static void main(String[] args) { Scanner sc=new Scanner( System.in); int n=sc.nextInt(); Nnum=new int[n]; Snum=new int[n]; for(int i=0;i<n;i++){ Nnum[i]=sc.nextInt(); } for(int i=0;i<n;i++){ Snum[i]=sc.nextInt(); } int [][]num=new int[n][n]; vis=new boolean[n][n]; hms.push(0); Nnum[0]--; Snum[0]--; dfs(num, 0, 0); } public static void dfs(int [][]num,int x,int y){ if(x==num.length-1&&y==num[0].length-1){ int flag=1; for(int i=0;i<num.length;i++){ // System.out.print(Nnum[i]+" "); if(Nnum[i]!=0){ flag=0; } } // System.out.println(); for(int i=0;i<num.length;i++){ // System.out.print(Snum[i]+" "); if(Snum[i]!=0){ flag=0; } } // System.out.println(); // System.out.println(); if(flag==1){ // Set<Integer> ss=hms.keySet(); for(int i=hms.size()-1;i>=0;i--){ System.out.print(hms.get(i)+" "); } } return; } vis[x][y]=true; for(int i=0;i<4;i++){ int tx=x+step[i][0]; int ty=y+step[i][1]; int loc=tx*4+ty; if(tx>=0&&tx<num.length&&ty>=0&&ty<num.length&&!vis[tx][ty]&&!hms.contains(loc)){ vis[tx][ty]=true; Nnum[ty]--; Snum[tx]--; // if(Nnum[ty]<0||Snum[tx]<0){ // Nnum[ty]++; // Snum[tx]++; // return; // } // System.out.println(tx+" "+ty); hms.push(loc); dfs(num, tx, ty); vis[tx][ty]=false; Nnum[ty]++; Snum[tx]++; // hms.remove(loc); hms.pop(); } } } }ac代码：
package day3; import java.util.Scanner; /** a:自西向东靶子上箭的数目。 b:自南向北靶子上箭的数目。 c:记录有没有走过第i,j个格子。 d:记录走过的路线。 a1:当前自西向东靶子上箭的数目。 b1:当前自南向北靶子上箭的数目。 * */ public class t4_new { static int[] a; static int[] b; static boolean[][] c; static int[] d; static int n; public static void main(String[] args) { Scanner input = new Scanner(System.in); n = input.nextInt(); a = new int[n+1]; b = new int[n+1]; c = new boolean [n+2][n+2]; d = new int[n*n+1]; c[1][1] = true; for(int i=0;i<=n;i++){ c[0][i] = true; } for(int i=0;i<=n;i++){ c[n+1][i] = true; } for(int i=0;i<=n;i++){ c[i][0] = true; } for(int i=0;i<=n;i++){ c[i][n+1] = true; } for(int i=1;i<=n;i++){ a[i] = input.nextInt(); } for(int i=1;i<=n;i++){ b[i] = input.nextInt(); } a[1]--; b[1]--; f(a,b,1,1,1); } public static void f(int[] a1,int[] b1,int i,int j,int h){ if(f1(a1,b1)){ return; } if(f2(a1,b1)&&i==n&&j==n){ d[h] = n*n-1; for(int k=1;k<=h;k++){ System.out.print(d[k]+" "); } System.exit(0); } if(i==n&&j==n){ return; } d[h] = (i-1)*n+j-1; if(!c[i-1][j]){ c[i-1][j] = true; a1[j]--; b1[i-1]--; f(a1,b1,i-1,j,h+1); c[i-1][j] = false; a1[j]++; b1[i-1]++; } if(!c[i+1][j]){ c[i+1][j] = true; a1[j]--; b1[i+1]--; f(a1,b1,i+1,j,h+1); c[i+1][j] = false; a1[j]++; b1[i+1]++; } if(!c[i][j-1]){ c[i][j-1] = true; a1[j-1]--; b1[i]--; f(a1,b1,i,j-1,h+1); c[i][j-1] = false; a1[j-1]++; b1[i]++; } if(!c[i][j+1]){ c[i][j+1] = true; a1[j+1]--; b1[i]--; f(a1,b1,i,j+1,h+1); c[i][j+1] = false; a1[j+1]++; b1[i]++; } } public static boolean f1(int[] a1,int[] b1){ for(int i=1;i<=n;i++){ if(a1[i]<0||b1[i]<0){ return true; } } return false; } public static boolean f2(int[] a1,int[]b1){ for(int i=1;i<=n;i++){ if(a1[i]!=0||b1[i]!=0){ return false; } } return true; } }