首页 > 专题系列 > Java解POJ > POJ 3482 ‘JBC’ [解题报告] Java
2013
11-12

POJ 3482 ‘JBC’ [解题报告] Java

‘JBC’

问题描述 :

Life can be taught, but sometimes simple problems are just very well hidden among difficult ones. Once identifying those simple problems you are almost on a half way of solving them as well as making one big step towards winning the contest. Just be careful, this is NOT the simplest problem!

Are you ready for that challenge?

Your task is to write a program that transforms numbers from various numeric systems to decade one (base=10).

输入:

Input file consists from multiple data sets separated by one or more empty lines.

First line of each set contains definition of digit ordering for some hypothetical numerical system. All ASCII printable characters (codes greater than 0×20 (space)) are allowed to appear as digits, and they are sorted according to increased decimal value (starting from zero).

Each line of the input data set (starting from second one) is one number coded with previously defined digits. Such numbers can have multiple decade interpretations (taking different base for hypothetical system) and your task is to find sum of all possible interpretations.

Explanation: If we define digit ordering as “0123456789” possible bases are 2..10 but number “6201” can be decoded only in systems with base 7..10.

Input lines can contain white space characters on both ends which should be ignored.

输出:

You are required to output one decimal number per each number from input data sets. That number represents sum of decimal representations for all valid numeric system bases.

Output data sets should be separated by one blank line.

样例输入:

0123456789
 90763
1

.1>C
CC.
>.1
1....

样例输出:

90763
9

60
52
353

解题代码:

//* @author: 
import java.util.*;
import java.io.FileReader;
import java.math.*;
public class Main {
    public static void main(String[] args)  throws Exception{
        int n=0;
        int [] dx=new int[1000];
        Scanner in=new Scanner(System.in);
        int fir=1;
        while (true) {
            String s;
            try {
                while (true) {
                    s=in.nextLine();
                    if (s.length()!=0) break;
                }
            }
            catch(Exception e) {
                break;
            }
            if (fir==1) fir=0;
            else System.out.println();
            int ll=s.length();
            n=0;
            for (int i=0;i< ll;i++) if (s.charAt(i)>0x20) {
                dx[s.charAt(i)]=n++;
            }
            while (true) {
                try{
                    s=in.nextLine();
                }
                catch(Exception e2) {
                    return;
                }
                int l=s.length();
                if (l==0) break;
                int max=0;
                for (int i=0;i< l;i++) 
                 if (s.charAt(i)>0x20&&max< dx[s.charAt(i)]) max=dx[s.charAt(i)];
                BigInteger ans=BigInteger.ZERO;
                for (int dig=max+1;dig<=n;dig++) {
                    BigInteger tmp=BigInteger.ZERO;
                    for (int i=0;i< l;i++) if (s.charAt(i)>0x20) {
                        tmp=tmp.multiply(BigInteger.valueOf(dig));
                        tmp=tmp.add(BigInteger.valueOf(dx[s.charAt(i)]));
                    }
                    ans=ans.add(tmp);
                }
                System.out.println(ans);
            }
        }
    }
}

  1. [email protected]

  2. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?