头疼的Litmxs

http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?id=4435

C++版本一

题解：

负进制，头一次听说

根据进制转换的权值来类比

1 -2 4 -8

奇次幂是负数说明在这个位置上有个1，不是加而是减一个权值

其他的见代码

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG

using namespace std;
typedef long long ll;
const int N=100;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k;
bool a[N];
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&k);
        int cnt=0;
        if(n==0){
            cout<<0<<endl;
            continue;
        }
        if(k==2){
            while(n!=0){
                a[cnt++]=n%2;
                n/=2;
            }
        }else{
            while(n!=0){
                a[cnt++]=n%2;
                if(a[cnt-1]==1&&cnt%2==0)
                    n=(n+1)/2;
                else
                    n/=2;
            }
        }
        for(int i=cnt-1;i>=0;i--){
            cout<<a[i];
        }
        cout<<endl;

    }

    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

题解：本题关键在-2 进制如何解决
 在做2 进制的时候，我们是直接对n=n/2,忽略掉将n 减去余数的过程，因为int 的除法会向下取整。
 对于-2 进制，我们只要补回减去余数的过程就可以了。 

#include<bits/stdc++.h>
using namespace std;

int ans[50], en;
int main()
{
//    freopen("data1.in", "r", stdin);
//    freopen("check1.out", "w", stdout);
    int t;
    scanf("%d", &t);
    assert(t <= 110);
    while(t--){
        int n, k;
        scanf("%d%d", &n, &k);
        assert(n <= 1000000000 && n >= 0);
        assert(k == 2 || k == -2);
        int gg = n;
        en = 0;
        while(n){
            ans[en] = n & 1;
            n >>= 1;
            if((en & 1) && (ans[en] & 1) && k == -2)    n++;
            en++;
        }
        if(en){
            for(int i = en - 1; i >= 0; --i) printf("%d", ans[i]);
            puts("");
        }
        else{
            puts("0");
        }
    }
    return 0;
}

C++版本三

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N=1e5+5;

int main(void){
    int n;
    int k;
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);
        if(n==0){
            cout << 0 << endl;
            continue;
        }
    //    cout <<n<<" "<<k<<endl;
        if(k==-2){
            string ans="";
            while(n){
                ll t=n%(-2);
                n/=(-2);
                if(t<0) t+=2,n++;// ¼ÇµÃ++
                ans+='0'+t;
            }
            reverse(ans.begin(),ans.end());
            cout << ans << endl;
        }
        else if(k==2){
            string ans="";
            while(n){
                ll t=n%2;
                n/=2;
                ans+='0'+t;
            }
            reverse(ans.begin(),ans.end());
            cout << ans << endl;
        }
    }
    return 0;
}