huring
0%

51nod-1925-进制转换

Posted on In

题目

有一个变进制系统从低位到高位的权值依次是 1，3，7，15，31，… 。即第i（i>=0）位的权值是 2𝑖+1−1 。每一位数字是0，1，或者2。现在有一个十进制的数字n，想要把它转换成变进制系统下面的表示。由于有2的存在，这种转换可能会有多种可能，现在规定2只能作为最低非0位出现，这种情况下，表示就唯一了。

比如44可能用15+15+7+7(2200)来表示，但是这样前面那个2就没有作为最低非0位出现，所以不符合要求，正确的转换是10120。

输入

多组测试数据。
第一行有一个整数T（1<=T<=5），表示测试数据的数目。
接下来T行，每行一个整数n（0<=n<=1000000000）。

输出

对于每一个n，输出它的变进制表示。

输入样例

样例输入1

1
2
3
4
5
6
4
1
2
3
4

输出样例
样例输出1

1
2
3
4
1
2
10
11

解法：

暴力即可

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
ll POW(ll n, ll m)
{
    ll ans = 1;
    for(int i = 0; i < m; i++)
        ans *= n;
    return ans;
}
int main()
{
    int t;
    scanf("%d", &t);
    while(t--){
        ll n,p;
        scanf("%lld", &n);
        if(n == 0)
            {
                printf("0\n");
                continue;
            }
        queue<int> q;
        for(int i = 0; i < 40; i++){
            while(!q.empty())
                q.pop();
            p = n - 2*POW(2,i) + 2;
            for(int j = 35; j >= 1; j--)
            {
                if(j == i){
                    q.push(2);
                    if(p != 0){
                        p = -1;
                        break;
                    }
                    continue;
                }
                if(p >= POW(2,j) - 1){
                    p -= POW(2,j) - 1;
                    q.push(1);
                }
                else{
                    q.push(0);
                }
            }
            if(p == 0){
                while(q.front() == 0){
                    q.pop();
                }
                while(!q.empty()){
                    printf("%d",q.front());
                    q.pop();
                }
                break;
            }
        }
        printf("\n");
    }
}