# 每日算法系列【EOJ 3031】二进制倒置

+关注继续查看

## 题目描述

https://acm.ecnu.edu.cn/problem/3031/

## 题解

while (n > 0) {
y.push_back(mod(x, a, b));
div(x, a, b);
n = x.size();
if (n == 1 && !x[0]) break;}

int mod(vector<int>& x, int a, int b) {
int n = x.size(), q = 0;
for (int i = n-1; i >= 0; --i) {
q = (q * a + x[i]) % b;
}
return q;
}

void div(vector<int>& x, int a, int b) {
int n = x.size(), q = 0;
for (int i = n-1; i >= 0; --i) {
x[i] += q * a;
q = x[i] % b;
x[i] /= b;
}
for (int i = n-1; i > 0; --i) {
if (x[i]) break;
x.pop_back();

}
}

## 代码

### c++

#include <bits/stdc++.h>using namespace std;
// string转化为vector<int>，倒序存储vector<int> s2i(string& s) {
vector<int> x;
int idx = 0, n = s.size();
for (; idx < n; ++idx) {
if (s[idx] != '0') break;
}
if (idx == n) idx = n - 1;
for (int i = n-1; i >= idx; --i) {
x.push_back(s[i]-'0');
}
return x;}
// a进制下x%b，x倒序存储int mod(vector<int>& x, int a, int b) {
int n = x.size(), q = 0;
for (int i = n-1; i >= 0; --i) {
q = (q * a + x[i]) % b;
}
return q;}
// a进制下x/b，x倒序存储void div(vector<int>& x, int a, int b) {
int n = x.size(), q = 0;
for (int i = n-1; i >= 0; --i) {
x[i] += q * a;
q = x[i] % b;
x[i] /= b;
}
for (int i = n-1; i > 0; --i) {
if (x[i]) break;
x.pop_back();
}
}
// a进制下s转化为b进制stringstring convert(string s, int a, int b) {
vector<int> x = s2i(s);
int n = x.size();
vector<int> y;
while (n > 0) {
y.push_back(mod(x, a, b));
div(x, a, b);
n = x.size();
if (n == 1 && !x[0]) break;
}
int m = y.size();
string res = "";
for (int i = m-1; i >= 0; --i) {
res += '0' + y[i];
}
return res; }

int main() {
int T;
cin >> T;
string x;
for (int t = 0; t < T; ++t) {
cin >> x;
string x2 = convert(x, 10, 2);
reverse(x2.begin(), x2.end());
string res = convert(x2, 2, 10);
cout << "case #" << t << ":" << endl;
cout << res << endl;
}
return 0;}


### python

x = int(input())for i in range(x):
print("case #%d:" %i)
print(int(str(bin(int(input())))[2::][::-1], 2))

24 0

29 0
JAVA常见算法题(三十一)---冒泡排序
package com.jege.spring.boot.hello.world; /** * java算法之冒泡排序 * 将数组按照从大到小的顺序排列 * * * @author Administrator * */ public class BubbleSort{ ...
742 0
JAVA常见算法题(一)
package com.xiaowu.demo; // 有一只兔子，从出生后第3个月起每个月都生一只兔子，小兔子长到第四个月后每个月又生一只兔子，假如兔子都不死，问每个月的兔子总数为多少？ /** * * @author WQ * */ public class Demo...
481 0
JAVA算法系列 冒泡排序
java算法系列之排序 手写冒泡 冒泡算是最基础的一个排序算法，简单的可以理解为，每一趟都拿i与i+1进行比较，两个for循环，时间复杂度为 O(n^2),同时本例与选择排序进行了比较，选择排序又叫直接排序，之所以直接，就是简单粗暴，不像冒泡，冒泡是紧挨着的两个小伙伴两两比较，直接排序是每一趟直接拿当前i与整个数组中所有元素进行比较，如果大小不一致，直接替换，相当于跳跃过去了，根本不考虑小伙伴的感受，我看到哪个小伙伴比我小，我就占领它的位置，彼此替换。
1131 0
JAVA算法系列 快速排序
java算法系列之排序 手写快排 首先说一下什么是快排，比冒泡效率要高，快排的基本思路是首先找到一个基准元素，比如数组中最左边的那个位置，作为基准元素key，之后在最左边和最右边设立两个哨兵，i 和 j 之后，开始按住左哨兵(i)，让右哨兵(j)往左走(j--)，找到比key小的元素后，按住右哨兵(...
802 0
Java利用IO流复制照片完整示例和详细分析
import java.io.FileInputStream; import java.io.FileOutputStream; /** * 该篇博客已经Deprecated,请参见I/O流的梳理和小结 * http://blog.
837 0
Java中实现的各种排序算法
Java中的冒泡排序算法 package cn.edu.hactcm; /**  * 冒泡排序算法  */ public class BubbleSortDemo { public static void main(String[] args) { int[] r = { 22, 12, 34, 123, 65, 34, 65, 34, 567, 3, 65, 546
1063 0
217

0