首页| 论坛| 消息
主题:NOIP复赛模拟题(测试数据丢失)
回帖:第一题:猫猫的小鱼
本题是一个数学题,主要牵涉到进制转换和高精度计算的知识。
我们注意到题目中所求的递增数列中的每个数都是整数,且每个数字都是由不同的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)
下一楼›:第二题:创意吃鱼法
本题是经典的DP题,题目比较简单。
我 ..
‹上一楼:偶第一题就有三个数据通不过~哭死。

--> 查看全部回帖(24)
«返回主帖