首页 > 专题系列 > Java解POJ > POJ 3331 The Idiot of the Year Contest! [解题报告] Java
2013
11-12

POJ 3331 The Idiot of the Year Contest! [解题报告] Java

The Idiot of the Year Contest!

问题描述 :

There is just one basic rule in the Idiot of the Year Contest (IYC)! The contestant picks a random digit between 0 and 9, computes the factorial of the day of the year he/she is born, and counts the how many times the digit picked appears in the factorial. The contestant with highest count is the Idiot of the Year! For example, if you are born on 5th of Mordad which is the 129th day of the year, and you pick the digit 6, your score will be the number of times the digit 6 appears in 129! (that is 1 × 2 × 3 × … × 129).

The chief judge of IYC wants you to write a program to get an integer which is the day of the year a contestant is born on and a digit and report the number of times the digit appears in the factorial of the first number.

输入:

The first line of the input contains a single integer T which is the number of test cases, followed by T lines each containing the data for a test case having two numbers. The first number is the day of the year a contestant is born and the second one is the digit he/she has picked.

输出:

The output contains T lines, each having one integer which is the number of times the digit appears in the factorial of the first number.

样例输入:

2
5 2
7 0

样例输出:

1
2 

解题代码:

import java.io.BufferedInputStream;   
import java.math.BigDecimal;   
import java.util.Scanner;   
  
/**  
 *  
 * poj3331  
 * @author NC  
 */  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        while (scan.hasNext()) {   
            int n = scan.nextInt();   
            for (int i = 0; i < n; i++) {   
                int a = scan.nextInt();   
                int b = scan.nextInt();   
                BigDecimal sum = BigDecimal.ONE;   
                while (a > 0) {   
                    BigDecimal aa = new BigDecimal(a);   
                    sum = sum.multiply(aa);   
                    a--;   
                }   
                char[] cs = sum.toString().toCharArray();   
                int count = 0;   
                String s = b+"";   
                for (int k = 0; k < cs.length; k++) {   
                    if ((cs[k]+"").equals(s)) {   
                        count++;   
                    }   
                }   
                System.out.println(count);   
            }   
        }   
    }   
}

  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯

  3. 您没有考虑 树的根节点是负数的情况, 若树的根节点是个很大的负数,那么就要考虑过不过另外一边子树了