老师叫我去给小朋友们讲他们的考试题,一共四道,前三题都傻逼题

第四题。。。我卡壳了

题面:

样例输入:

-13

样例输出:

110111

嗯,怎么做呢

其实题目就是要你找一个二进制上 $1, 3, 5, 7, …$位为 $0$的数字 $A$,以及一个二进制上 $0, 2, 4, 6, …$位为 $0$的数字 $B$,使得 $A – B$等于输入的 $n$

因为是 $-2$进制因此可以从 $2$进制角度考虑

对于 $n$的二进制在 $0, 2, 4, …$位上的 $1$,只要让 $A$的对应位 $+1$即可

对于 $n$在 $1, 3, 5, …$位上的 $1$,我们无法让 $A$直接增加,而是应该 “曲线救国”,让 $B$的这一位 $+1$,再让 $A$的下一位 $+1$,这样两者相减就能得到这一位了

现在的问题就是怎么 $+1$

拿 $A$举例,如果 $A$的这一位为 $0$,那直接把这一位设为 $1$即可

如果 $A$这一位为 $1$,有两种:

  • 如果 $B$的下一位为 $1$,那直接把 $A$的当前位设为 $0$,然后让 $B$的下一位也置为 $0$,这样相当于二进制下给 $A$进一位
  • 否则把 $B$的下一位置为 $1$,把 $A$的 “下一个位置的下一个位置” 置为 $1$,然后把 $A$的当前位置为 $0$,也相当于进了一位

$B$的同理

然后这个进位过程用递归处理即可

对于负数,可以先找到最小的一个 $\geq n$的 $2 ^ k$($k$为正整数),使得 $n + 2 ^ k \geq 0$,然后算出 $n + 2 ^ k$这个非负整数的答案,最后再给 $B$的第 $k$位 $+1$即可(减掉 $2 ^ k$)

多妙啊~

(其实我不确定我这个做法是否是最优的)

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

LL n, m;

bool A[70], B[70];

void markA(int), markB(int);

void markA(int a)
{
    if (!A[a]) A[a] = 1;
    else
    {
        if (B[a + 1]) B[a + 1] = 0;
        else markA(a + 2), markB(a + 1);
        A[a] = 0;
    }
}

void markB(int a)
{
    if (!B[a]) B[a] = 1;
    else
    {
        if (A[a + 1]) A[a + 1] = 0;
        else markB(a + 2), markA(a + 1);
        B[a] = 0;
    }
}

int main(int argc, char const* argv[])
{
    IN(n);
    if (n < 0)
    {
        m = 1;
        while (m + n < 0) m <<= 1;
        n += m;
    }
    int x = 0;
    while (n)
    {
        if (n & 1)
        {
            if (x & 1) markA(x + 1), markB(x);
            else markA(x);
        }
        n >>= 1, x++;
    }
    if (m)
    {
        x = 0;
        while ((1ll << x) < m) x++;
        if (x & 1) markB(x);
        else markB(x + 1), markA(x);
    }
    x = 64;
    while (!A[x] && !B[x] && x > 0) x--;
    while (x >= 0) printf("%d", (int)(A[x] || B[x])), x--;
    putchar(10);
    return 0;
}
分类: 文章

Remmina

No puzzle that couldn't be solved.

发表评论

电子邮件地址不会被公开。 必填项已用*标注