华农oj Problem K: 负2进制【有技巧构造/待补】

Problem K: 负2进制

Time Limit: 2 Sec  Memory Limit: 128 MB

Submit: 51  Solved: 6

[Submit][Status][Web Board]

Description

如果我16岁，我可以悄悄的说我好喜欢你；如果我26岁，我可以大声告诉你我很爱你；可惜我6岁，我什么都给不了你，我还要上小学。

我们都知道2进制，每一位的权值如下:

1 2 4 8 16 32 64

现在我们定义一种-2进制,每一位的权值如下:

1 -2 4 -8 16 -32 64

现在我们给一个正数x，用-2进制表示,输出ceil(x/2)，用-2进制表示。

什么是ceil(x)?     ceil(x)就是对x向上取整。

什么是对x向上取整 ?     向上取整就是取≥x的最小整数

什么是≥ ? 就是不小于

什么是不小于？ 呵呵

Input

第一行为T代表有T组样例.(T<=20)

接下来有T行，每一行有一个用-2进制表示的正数(保证是正数且位数不超过5*10^5)

Output

对于每组测试输出一行，每行代表一个用-2进制表示的ceil(x/2).(注意不含前导0)

Sample Input

2

10101

10100

Sample Output

11111

11110

HINT

10101 用10进制表示是 21 ， ceil(21/2) = 11

10100 用10进制表示是 20 ， ceil(20/2) = 10 

注意不要输出前导0

[Submit][Status]

OJ地址

10 -> 11,  002 -> 110, 12 -> 00

第一条是 ceil(x/2) 的变化，后面两条是为了消除 2

---

推出结论，除以2相当于把原来二进制数的每一位变成这一位与后一位都加上1，而第0位不变即可，于是得到新的二进制数，可能存在一些位为2，而这些位可与前面的一位消去，消去后就是答案

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const double eps = 1e-7;

const int maxn = 5e5 + 5;

const double pi = acos(-1.0);

char a[maxn];

int b[maxn];

int main(int argc, char const *argv[]) {

  int t;

  std::cin >> t;

  while(t--)

  {

    memset(b,0,sizeof(b));

    scanf("%s", &a);

    int len = strlen(a);

    for(int i = 0; i < len - 1; i++) {

      if(a[i] =='1') {

        b[i]++;

        b[i+1]++;

      }

    }

    if(a[len-1]=='1') {

      b[len-1]++;

    }

    for(int i = len - 1; i >= 0; --i) {

      if(b[i] >= 2) {

        if(b[i-1] >= 1) {

          b[i-1]--;

          b[i] -= 2;

        }

        else{

          b[i-1]++;

          b[i-2]++;

        }

      }

    }

    int k = 0;

    while (b[k]==0) {

      k++;

    }

    while(k < len) {

      std::cout << b[k];

      k++;

    }

    std::cout << '\n';

  }

  return 0;

}

巴特西

华农oj Problem K: 负2进制【有技巧构造/待补】

最新文章

热门文章