首页 > ACM题库 > HDU-杭电 > HDU 2889-Without Zero-分治-[解题报告]HOJ
2014
02-17

HDU 2889-Without Zero-分治-[解题报告]HOJ

Without Zero

问题描述 :

Everyone is familiar to the natural number system: 1, 2, 3… Today we will consider a different one: a no-zero number system, which means it only uses the digits 1 through 9. So counting begins with 1, the first “counting number”, and continues: 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12…, 19, 21…, 98, 99, 111, 112…
So, in this system 9 is the ninth counting number and 11 is the tenth counting number. As usual, addition can be defined by reference to the counting sequence. Addition of the i-th counting number and the j-th counting number is defined to mean the (i+j)-th counting number. Thus, in this system 5 + 8 = 14, since 5 is the fifth counting number, 8 is the eighth, and 14 is the thirteenth counting number. Subtraction is the reverse of addition.
Here is your task, given two numbers: a and b, you should output a subtract b which is defined in no-zero number system.

输入:

Multiple test cases, each line contains two positive integers: a and b, 1 <= b < a < 1000000000, it is guaranteed that both a and b will not contain digit 0.

输出:

Multiple test cases, each line contains two positive integers: a and b, 1 <= b < a < 1000000000, it is guaranteed that both a and b will not contain digit 0.

样例输入:

14 5
111 99
191 111

样例输出:

8
1
79

Analysis: 我的想法是先将Without Zero的进制给转化成10进制,做减法以后再转化为Without Zero进制。实际上,我们很容易可以看出,Without Zero只是一个变相的9进制,我们完全可以按照9进制进行计算。但是从10进制转化回去就不那么容易,我在这里采取的是这样的办法,对于十进制A,查看其Without Zero进制有多少位;对于每一位,尝试1到9之间的数字x,如果该位为数字x时刚好其10进制等于A,那么输出即可,否则设置该位为x-1。Source Code:

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
char a[20], b[20];__int64 getValue(char * p){//Without Zero进制转化为10进制
__int64 v = 0;
for(int i = 0; i < strlen(p); ++i){
   v = v * 9 + p[i] - '0';
}
return v;
}int main(){
while(scanf("%s%s", b, a) != EOF){
   __int64 sb = 0, sa = 0;
   sb = getValue(b);
   sa = getValue(a);
   sb -= sa;
   sa = 0;   memset(a, '1', sizeof(a));//计算Without Zero进制有多少位
   a[19] = 0;
   int idx = 0;
   for(; ; ++idx){
    sa = sa * 9 + a[idx] - '0';
    if(sa == sb){
     a[idx+1] = 0;
     printf("%s\n", a);
     goto Exit;
    }
    else if(sa > sb){
     a[idx] = 0;
     break;
    }
   }
   for(int i = 0; i < idx; ++i){//计算Without Zero进制
    for(char j = '2'; j <= '9'; ++j){
     a[i] = j;
     sa = getValue(a);
     if(sa == sb){
      printf("%s\n", a);
      goto Exit;
     }
     if(sa > sb){
      a[i] = j - 1;
      break;
     }
    }
   }
Exit:;
}
return 0;
}

运行结果如下:13 0MS 212K 1097 BC++2009-08-31 21:43:13

效果还不错,但应该有其他更好的办法。因这样时间复杂度实际上为O(10*log(n)^2)。实际上,我们可以对程序做一些改动,使得程序的时间复杂度为O(log(n)),注意在最后根据rank求Without Zero值时,每次都要调用getValue(),显然这个是不需要的,只要使用一个值pow[]来保存9^n,每次加上这个值即可。另外对于每一位,从2循环到9也可以改成二分,但是意义不大。代码写的有点恶心,下面的代码稍稍工整一点,实现了同样的功能:

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
char a[20], b[20];__int64 parseInt64(const char * p, int radix){
__int64 v = 0;
for(size_t i = 0; i < strlen(p); ++i){
   v = v * radix + p[i] - '0';
}
return v;
}__int64 getWithoutZeroValue(__int64 rank){
memset(a, '1', sizeof(a));
__int64 val = 0;
for(int idx = 0; ; ++idx){
   val = val * 9 + a[idx] - '0';
   if(val == rank){
    a[idx+1] = 0;
    return parseInt64(a, 10);
   }
   else if(val > rank){
    a[idx] = 0;
    break;
   }
}
for(size_t i = 0; i < strlen(a); ++i){
   for(char j = '2'; j <= '9'; ++j){
    a[i] = j;
    val = parseInt64(a, 9);
    if(val == rank){
     return parseInt64(a, 10);
    }
    if(val > rank){
     a[i] = j - 1;
     break;
    }
   }
} return 0;
}int main(){
while(scanf("%s%s", b, a) != EOF){
   __int64 rank = parseInt64(b, 9) - parseInt64(a, 9);
   printf("%I64d\n", getWithoutZeroValue(rank));
}
return 0;
}

  1. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!