3031. 二进制倒置

10175102262 LarsPendragon

终于肝出来这道题了,虽然最后还是不得不看了一下官方pdf……感觉这道题难度和得分完全不匹配。先上C代码:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct {int dec[105]; int bin[335]; int cnt;}Big;
void decTurnToBin(Big *n)
{
    int i=0, j, lend=0, all, check, c=0;
    for(j=0; j<335; j++) n->bin[j]=0;
    while(n->cnt)
    {
        lend=0; 
        n->bin[i++]+=(n->dec[0])%2;
        if(n->dec[n->cnt-1]<2){n->cnt--;lend=1;check=1;}
        for(j=n->cnt-1; j>=0; j--)
        {
            if(n->cnt>1) all=lend*10+n->dec[j];
            else if(check==1) all=lend*10+n->dec[j];
            else all=n->dec[j];
            n->dec[j]=all/2;
            lend=all%2;
            check=0;
        }
    }
    n->cnt=i;
}
void binTurnToDec(Big *n)
{
    int i, j, k;
    for(i=0; i<n->cnt; i++)
        {if(n->bin[i]) break;}
    for(j=0; j<105; j++) n->dec[j]=0;
    for(; i<n->cnt; i++)
    {
        int add=0;
        for(k=0; k<104; k++)
        {
            n->dec[k]*=2;
            n->dec[k]+=add;
            add=n->dec[k]/10;
            n->dec[k]%=10;
        }
        n->dec[0]+=n->bin[i];
        for(k=0; k<104; k++) 
            if(n->dec[k]>9)
            {
                n->dec[k+1]+=n->dec[k]/10;
                n->dec[k]%=10;
            }
    }
}
int main()
{
    int T, I;
    scanf("%d",&T);
    getchar();
    for(I=0; I<T; I++)
    {
        Big n;
        char num[105];
        gets(num);
        int l=strlen(num), i;
        for(i=0; i<105; i++) n.dec[i]=0;
        for(i=0; i<335; i++) n.bin[i]=0;
        for(i=0; i<l; i++)
            n.dec[i]=num[l-i-1]-'0';
        n.cnt=i;
        if(l==1 && num[0]=='0') n.cnt=0;
        if(n.cnt)decTurnToBin(&n);
        if(n.cnt)binTurnToDec(&n);
        printf("case #%d:\n",I);
        for(i=104; i+1; i--) if(n.dec[i]) break;
        for(; i+1; i--) printf("%d",n.dec[i]);
        if(n.cnt==0) printf("0");
        printf("\n");
    }
    return 0;
}
13627999316
n = int(input())
i = 0
while i < n:
    v = int(input())
    print("case #%d:"%i)
    v = bin(v)[2:];v = v[::-1]
    v = int(v,2)
    print(v)
    i = i + 1
yoshino-s

It’s a non-pythonic program.
You should write like this.

print('\n'.join([f"case #{i}:\n{int(bin(int(input()))[2:][::-1],2)}" for i in range(int(input()))]))
13627999316

I’m a beginner in Python, and I think your code is not very readable

yoshino-s

It’s just a satire.

Canis

对于c程序还是辗转除以2得到二进制,去掉前面的0,倒转,然后用bignum计算

Fifnmar

这道题虽然麻烦,但算法上没有难度,暴力做就可以,是一道细心题。

有注释的代码在 这里

#include "bits/stdc++.h"

using namespace std;

using BigUIntDecimal = vector<uint8_t>;
using BigUIntBinary = vector<bool>;

BigUIntDecimal read_big_uint_from(istream& is) {
    static string raw;
    is >> raw;

    BigUIntDecimal ret;
    transform(rbegin(raw), rend(raw), back_inserter(ret), [](auto d) { return d - '0'; });

    return ret;
}

uint8_t rem_div_by_2(BigUIntDecimal& decimal) {
    uint8_t remainder = 0;
    for (auto i = decimal.rbegin(); i != decimal.rend(); ++i) {
        auto digit = (remainder * 10) + *i;
        *i = digit / 2;
        remainder = digit % 2;
    }
    return remainder;
}

BigUIntBinary to_chopped_binary(BigUIntDecimal&& decimal, uint32_t cnt) {
    BigUIntBinary ret(cnt, 0);
    for (uint32_t i = 0; i != cnt; ++i) {
        ret[i] = rem_div_by_2(decimal);
    }
    return ret;
}

void reverse(BigUIntBinary& num) {
    reverse(
        find(rbegin(num), rend(num), 1),
        rend(num)
    );
}


BigUIntDecimal to_decimal(BigUIntBinary const& binary) {
    BigUIntDecimal decimal;

    for (uint32_t i = binary.size() - 1; i != -1; --i) {
        decimal.push_back(0);

        for (auto& digit : decimal) {
            digit *= 2;
        }

        for (uint32_t j = 0, end = decimal.size() - 1; j != end; ++j) {
            if (decimal[j] >= 10) {
                decimal[j] -= 10;
                decimal[j + 1] += 1;
            }
        }

        if (binary[i] == 1) {
            decimal.push_back(0);
            decimal[0] += 1;
            uint32_t pos = 0;
            while (decimal[pos] >= 10) {
                decimal[pos] -= 10;
                decimal[pos + 1] += 1;
                pos += 1;
            }
        }
    }

    while (!decimal.empty() && decimal.back() == 0) {
        decimal.pop_back();
    }

    if (decimal.empty()) {
        decimal.push_back(0);
    }

    return decimal;
}

ostream& operator<<(ostream& os, BigUIntDecimal const& num) {
    transform(rbegin(num), rend(num), ostream_iterator<char>(os), [](auto i) { return i + '0'; });
    return os;
}

int main() {
    uint32_t t;
    cin >> t;

    for (uint32_t  i = 0; i != t; ++i) {
        cout << "case #" << i << ":\n";

        auto big_decimal = read_big_uint_from(cin);
        auto big_binary = to_chopped_binary(move(big_decimal), 334);
        reverse(big_binary);
        big_decimal = to_decimal(big_binary);

        cout << big_decimal << '\n';
    }
}
你当前正在回复 博客/题目
存在问题!