2013
12-12

# 九度-1090-路径打印[解题代码]

a\b\c
a\d\e
b\cst
d\

a
b
c
d
e
b
cst
d

每个测试案例第一行为一个正整数n（n<=10）表示有n个路径，当n为0时，测试结束，接下来有n行，每行有一个字串表示一个路径，长度小于50。

4
a\b\c
a\d\e
b\cst
d\
0

a
b
c
d
e
b
cst
d



java 代码如下：
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.util.Scanner;
import java.util.TreeSet;

public class Main{
static int n;
static Node root; //定义一个根节点
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNextInt()) {
n = scanner.nextInt();
if(n == 0)
break;
String str;
Node root = new Node();
root.key = "";
root.subString = "";
root.children = new TreeSet<Node>();
for (int i = 0; i < n; i++) {
str = scanner.next();
}

root.print();
System.out.println();
}
}
}

class Node implements Comparable<Node> {
public String key;
public String subString;
public TreeSet<Node> children;
public Node father;
public int pre;

public int compareTo(Node o) { //定义比较函数。即比较前缀 a\b\ == a\b\, 是一个目录
return this.subString.compareTo(o.subString);
}
public Node() {}
public Node(String str[], int index, Node f) {
this.subString = "";
if (index == str.length)
return;
for (int i = 1; i <= index; i++)
this.subString += str[i] + '\\';
if (index == 0)
this.subString = str[0];
this.key = str[index];
this.pre = f.pre + f.key.length() + 1;
this.father = f;
if (index != str.length) {
if (this.children == null)
this.children = new TreeSet<Node>();
children.add(new Node(str, index + 1, this));
}
}

public void addChild(Node n) {  //添加一个孩子节点
//由于孩子节点可能重复，重新合并
if (children.contains(n)) {
Node temp = null;
for (Node temp2 : children) {
if (temp2.compareTo(n) == 0)
temp = temp2;
}
} else {
}
}

public void print() {
if (this.key == null)
return;
if(this.key != ""){
pre--; //由于第一个位置会多个空格
while (pre-- > 0)
System.out.print(" ");
System.out.println(key);
}
if (this.children != null && children.size() > 0) {
for (Node n : children)
n.print();
}
}
}

/**************************************************************
Problem: 1090
User: coder
Language: Java
Result: Accepted
Time:110 ms
Memory:15720 kb
****************************************************************/

cpp 代码如下：

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.util.Scanner;
import java.util.TreeSet;

public class Main{
static int n;
static Node root; //定义一个根节点
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNextInt()) {
n = scanner.nextInt();
if(n == 0)
break;
String str;
Node root = new Node();
root.key = "";
root.subString = "";
root.children = new TreeSet<Node>();
for (int i = 0; i < n; i++) {
str = scanner.next();
}

root.print();
System.out.println();
}
}
}

class Node implements Comparable<Node> {
public String key;
public String subString;
public TreeSet<Node> children;
public Node father;
public int pre;

public int compareTo(Node o) { //定义比较函数。即比较前缀 a\b\ == a\b\, 是一个目录
return this.subString.compareTo(o.subString);
}
public Node() {}
public Node(String str[], int index, Node f) {
this.subString = "";
if (index == str.length)
return;
for (int i = 1; i <= index; i++)
this.subString += str[i] + '\\';
if (index == 0)
this.subString = str[0];
this.key = str[index];
this.pre = f.pre + f.key.length() + 1;
this.father = f;
if (index != str.length) {
if (this.children == null)
this.children = new TreeSet<Node>();
children.add(new Node(str, index + 1, this));
}
}

public void addChild(Node n) {  //添加一个孩子节点
//由于孩子节点可能重复，重新合并
if (children.contains(n)) {
Node temp = null;
for (Node temp2 : children) {
if (temp2.compareTo(n) == 0)
temp = temp2;
}
} else {
}
}

public void print() {
if (this.key == null)
return;
if(this.key != ""){
pre--; //由于第一个位置会多个空格
while (pre-- > 0)
System.out.print(" ");
System.out.println(key);
}
if (this.children != null && children.size() > 0) {
for (Node n : children)
n.print();
}
}
}

/**************************************************************
Problem: 1090
User: coder
Language: Java
Result: Accepted
Time:90 ms
Memory:15760 kb
****************************************************************/

1. #include <stdio.h>
int main()
{
int n,p,t[100]={1};
for(int i=1;i<100;i++)
t =i;
while(scanf("%d",&n)&&n!=0){
if(n==1)
printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
else {
if(n%4) p=n/4+1;
else p=n/4;
int q=4*p;
printf("Printing order for %d pages:n",n);
for(int i=0;i<p;i++){
printf("Sheet %d, front: ",i+1);
if(q>n) {printf("Blank, %dn",t[2*i+1]);}
else {printf("%d, %dn",q,t[2*i+1]);}
q–;//打印表前
printf("Sheet %d, back : ",i+1);
if(q>n) {printf("%d, Blankn",t[2*i+2]);}
else {printf("%d, %dn",t[2*i+2],q);}
q–;//打印表后
}
}
}
return 0;
}

2. 这道题目的核心一句话是：取还是不取。
如果当前取，则index+1作为参数。如果当前不取，则任用index作为参数。