首页 > 专题系列 > Java解POJ > POJ 1894 Alternative Scale of Notation [解题报告] Java
2013
11-10

POJ 1894 Alternative Scale of Notation [解题报告] Java

Alternative Scale of Notation

问题描述 :

One may define a map of strings over an alphabet ΣB = { C1, C2, . . . CB } of size B to non-negative integer numbers, using characters as digits C1 = 0, C2 = 1, . . . , CB = B – 1 and interpreting the string as the representation of some number in a scale of notation with base B. Let us denote this map by UB , for a string α[ 1...n ] of length n we put

UB(α)=Σ0<=i<=n-1α[n-i]*Bi


For example, U3(1001) = 1*27 + 0*9 + 0*3 + 1*1 = 28.

However, this correspondence has one major drawback: it is not ont-to-one. For example,

28 = U3(1001) = U3(01001) = U3(001001) = … ,

infinitely many strings map to the number 28.

In mathematical logic and computer science this may be unacceptable. To overcome this problem, the alternative interpretation is used. Let us interpret characters as digits, but in a slightly different way: C1 = 1, C2 = 2, . . . , CB = B . Note that now we do not have 0 digit, but rather we have a rudiment B digit. Now we define the map VB in a similar way, for each string α[ 1...n ] of length n we put

VB(α)=Σ0<=i<=n-1α[n-i]*Bi


For an empty string ε we put VB(ε) = 0.

This map looks very much like UB , however, the set of digits is now different. So, for example, we have V3(1313) = 1*27 + 3*9 + 1*3 + 3*1 = 60.

It can be easily proved that the correspondence defined by this map is one-to-one and onto. Such a map is called bijective, and it is well known that every bijective map has an inverse. Your task in this problem is to compute the inverse for the map VB . That is, for a given integer number x you have to find the string α, such that VB(α) = x.

输入:

The first line contains B (2 <= B <= 9) and the second line contains an integer number x given in a usual decimal scale of notation, 0 <= x <= 10100.

输出:

Output in one line such string α, consisting only of digits from the set { 1, 2, . . . , B }, that VB(α) = x .

样例输入:

3
60

样例输出:

1313

解题代码:

方法一:
import java.io.*; import java.util.*; import java.math.*; public class Main { public static void main(String[] args) { BigInteger sum,m,D[] = new BigInteger[2]; int i,b[] = new int[340]; Scanner cin = new Scanner(System.in); m = cin.nextBigInteger(); sum = cin.nextBigInteger(); int k = 0; while(sum.compareTo(BigInteger.ZERO) != 0) { D = sum.divideAndRemainder(m); sum = D[0]; if(D[1].compareTo(BigInteger.ZERO) == 0) { sum = sum.subtract(BigInteger.ONE); b[++k] = m.intValue(); } else b[++k] = D[1].intValue(); } for(i = k;i >= 1;i --) System.out.print(b[i]); System.out.println(); } } 方法二: import java.io.BufferedInputStream; import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); BigInteger base = null, input = null; BigInteger zero = BigInteger.valueOf(0); String res = ""; while(cin.hasNextBigInteger()) { base = cin.nextBigInteger(); input = cin.nextBigInteger(); if(input.compareTo(zero) == 0) continue; //System.out.println("hell0"); BigInteger cur = BigInteger.valueOf(1); int len = 0; while(input.compareTo(cur) >= 0) { len++; input = input.subtract(cur); cur = cur.multiply(base); } res = ""; BigInteger residual = null; BigInteger quotient = null; while(input.compareTo(zero) != 0) { quotient = input.divide(base); residual = input.mod(base); input = quotient; res = residual.toString() + res; } int l = res.length(); while(l < len) { res = "0" + res; l++; } for(l = 0; l < res.length(); l++) System.out.print((char)(res.charAt(l) + 1)); } } }

  1. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept