Problem B
Accepts: 2515
Submissions: 9216
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
1 3 8
Hint
如果序列是:(111)。可以构造出如下三个新序列:(111), (21), (12)。可以直接递推,会发现是斐波拉契数列。大数JAVA。
import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { BigInteger [] F = new BigInteger[205]; F[1] = BigInteger.valueOf(1); F[2] = BigInteger.valueOf(2); for(int i=3;i<=200;i++){ F[i] = F[i-1].add(F[i-2]); } Scanner sc = new Scanner(System.in); while(sc.hasNext()){ int num = sc.nextInt(); System.out.println(F[num]); } } }
/**
在hdoj上要这样写..我不知道为什么
if(num>=1&&num<=200)
System.out.print(F[num]);
System.out.println();
**/
Problem C
Accepts: 832
Submissions: 6612
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 131072/131072 K (Java/Others)
Yes No
字典树。
import java.util.Arrays; import java.util.Scanner; class Trie { private Node root; public Trie() { root = new Node(); } public void insert(String str){ Node t = root; for(int i=0;i<str.length();i++){ if(t.nodes[str.charAt(i)-'a']==null){ Node node = new Node(); t.nodes[str.charAt(i)-'a'] = node; } t = t.nodes[str.charAt(i)-'a']; t.num++; } } public int search(String str){ Node t = root; for(int i=0;i<str.length();i++){ if(t.nodes[str.charAt(i)-'a']==null){ return 0;} t = t.nodes[str.charAt(i)-'a']; if(t.num==0) return 0; } return t.num; } public void delete(String str){ Node t = root; int num = search(str); if(num==0) return; for(int i=0;i<str.length();i++){ int idx = str.charAt(i)-'a'; if(t.nodes[idx]==null) return; t = t.nodes[idx]; t.num = t.num-num; } for(int i=0;i<26;i++){ t.nodes[i]=null; } } class Node{ int num; Node []nodes; public Node() { num= 0; nodes = new Node[26]; } } } public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); Trie tree = new Trie(); while (n-- > 0) { String str1 = sc.next(); String str2 = sc.next(); if (str1.equals("insert")) { tree.insert(str2); } else if (str1.equals("search")) { if (tree.search(str2)==0) System.out.println("No"); else System.out.println("Yes"); } else tree.delete(str2); } } }
Problem D
Accepts: 2916
Submissions: 8882
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)