回帖:第一题:猫猫的小鱼
本题是一个数学题,主要牵涉到进制转换和高精度计算的知识。
我们注意到题目中所求的递增数列中的每个数都是整数,且每个数字都是由不同的3的整数次幂的和构成的,所以这个数字的三进制表示中只有0或1,我们注意到二进制也是由0和1组成的,结合题目中要我们求第k小的数字,因此不难想到在全体整数与数列之间建立一个一一对应,使得数字k的二进制表示与它所对应的三进制表示相同。举例说明:
K的值 对应的二进制 对应关系 相应的三进制 第k大的美观程度
1 1 1 1
2 10 10 3
3 11 11 4
4 100 100 9
5 101 101 10
6 110 110 12
7 111 111 13
因此我们需要做的就是把k这个数字转换成二进制,然后再把相应的二进制当作三进制转换成十进制就可以了,在k较大的时候需要高精度计算,似乎longint或者是extended可能也可以,但是我当时没有细细看。
时间复杂度:O(logk)