倒计时2

倒计时2

一、树形显示
描述

对于分类结构可以用树形来形象地表示。比如：文件系统就是典型的例子。

树中的结节具有父子关系。我们在显示的时候，把子项向右缩进（用空格，不是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 = (parent);if(lst==null){lst = new ArrayList<String>();map_ch.put(parent, lst);}lst.add(child);}public String get_parent(String me){return (me);}public List<String> get_child(String me){return (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 = (x);if(pa==null) return true;List<String> lst = (pa);(lst.size()-1).equals(x);}public void show(String x){String s = "+--" + x;String pa = x;while(true){pa = (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 = (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",&#s");tree.add("YYcat",&#");		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.String(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.adLine());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.String(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&#Int();Nnum=new int[n];Snum=new int[n];for(int i=0;i<n;i++){Nnum[i]&#Int();}for(int i=0;i<n;i++){Snum[i]&#Int();}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.(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]&&!ains(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]++;
//				ve(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 = Int();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] = Int();}for(int i=1;i<=n;i++){b[i] = Int();}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]+" ");}it(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;}}