poj 部分题目源代码（共77题） for acm ，一年所做的

/*--------------------------------------------------------------*/ /* ACM ICPC 2007-2008 */ /* Northeastern European Regional Contest */ /* St Petersburg - Barnaul - Tashkent - Batumi, November 28, 200*/ /*--------------------------------------------------------------*/ /* Problem L. Language Recognition */ /*--------------------------------------------------------------*/ /* Solution */ /* */ /* Author Roman Elizarov */ /*--------------------------------------------------------------*/ /* Solution for NEERC'2007 Problem L: Language Recognition (C) Roman Elizarov Note: this solution attempts to check correctness of the input */ import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { new Main().go(); } class Node { boolean f; final Node[] next = new Node[26]; int hash; public boolean equals(Object obj) { if (!(obj instanceof Node)) return false; Node o = (Node)obj; if (f != o.f) return false; for (int i = 0; i < 26; i++) { if (next[i] == null ? o.next[i] != null : !next[i].equals(o.next[i])) return false; } return true; } public int hashCode() { if (hash != 0) return hash; int h = 1; for (int i = 0; i < 26; i++) { h *= 31; if (next[i] != null) h += next[i].hashCode(); } if (f) h ^= 958748917; return hash = h; } } void go() throws Exception { // read input Scanner in = new Scanner(System.in); //in.useLocale(Locale.US); int n = in.nextInt(); in.nextLine(); assert n >= 1 && n <= 5000; String[] w = new String[n]; for (int i = 0; i < n; i++) { w[i] = in.next(); in.nextLine(); assert w[i].length() >= 1 && w[i].length() <= 30; } //in.close(); // solve Node root = new Node(); for (int i = 0; i < n; i++) { Node cur = root; for (int j = 0; j < w[i].length(); j++) { char c = w[i].charAt(j); assert c >= 'a' && c <= 'z'; Node next = cur.next[c - 'a']; if (next == null) cur.next[c - 'a'] = next = new Node(); cur = next; } assert !cur.f : "duplicate word"; cur.f = true; } HashSet<Node> nodes = new HashSet<Node>(); addAll(root, nodes); // write output PrintWriter out = new PrintWriter("System.out"); out.println(nodes.size()); } private void addAll(Node cur, HashSet<Node> nodes) { if (nodes.add(cur)) for (int i = 0; i < 26; i++) if (cur.next[i] != null) addAll(cur.next[i], nodes); } //----------------- just for validation ------------------ /** * Strict scanner to veryfy 100% correspondence between input files and input file format specification. * It is a drop-in replacement for {@link java.util.Scanner} that could be added to a soulution source * (cut-and-paste) without breaking its ability to work with {@link java.util.Scanner}. */ public class XScanner { private final BufferedReader in; private String line = ""; private int pos; private int lineNo; private boolean localeset; public XScanner(File source) throws FileNotFoundException { in = new BufferedReader(new FileReader(source)); nextLine(); } public void close() { assert line == null : "Extra data at the end of file"; try { in.close(); } catch (IOException e) { throw new AssertionError("Failed to close with " + e); } } public void nextLine() { assert line != null : "EOF"; assert pos == line.length() : "Extra characters on line " + lineNo; try { line = in.readLine(); } catch (IOException e) { throw new AssertionError("Failed to read line with " + e); } pos = 0; lineNo++; } public String next() { assert line != null : "EOF"; assert line.length() > 0 : "Empty line " + lineNo; if (pos == 0) assert line.charAt(0) > ' ' : "Line " + lineNo + " starts with whitespace"; else { assert pos < line.length() : "Line " + lineNo + " is over"; assert line.charAt(pos) == ' ' : "Wrong whitespace on line " + lineNo; pos++; assert pos < line.length() : "Line " + lineNo + " is over"; assert line.charAt(0) > ' ' : "Line " + lineNo + " has double whitespace"; } StringBuilder sb = new StringBuilder(); while (pos < line.length() && line.charAt(pos) > ' ') sb.append(line.charAt(pos++)); return sb.toString(); } public int nextInt() { String s = next(); assert s.length() == 1 || s.charAt(0) != '0' : "Extra leading zero in number " + s + " on line " + lineNo; assert s.charAt(0) != '+' : "Extra leading '+' in number " + s + " on line " + lineNo; try { return Integer.parseInt(s); } catch (NumberFormatException e) { throw new AssertionError("Malformed number " + s + " on line " + lineNo); } } public double nextDouble() { assert localeset : "Locale must be set with useLocale(Locale.US)"; String s = next(); assert s.length() == 1 || s.startsWith("0.") || s.charAt(0) != '0' : "Extra leading zero in number " + s + " on line " + lineNo; assert s.charAt(0) != '+' : "Extra leading '+' in number " + s + " on line " + lineNo; try { return Double.parseDouble(s); } catch (NumberFormatException e) { throw new AssertionError("Malformed number " + s + " on line " + lineNo); } } public void useLocale(Locale locale) { assert locale == Locale.US; localeset = true; } } }