题目来源：北邮2018计算机院考研复试机试上机题解+结果统计
进制 | 2018.计算机院.Problem A.二进制数字翻转
题目描述
输入数据组数t
每组数据输入一个十进制数x(032)，将其二进制位反转(共32位)，然后输出对应的十进制数
思路
int类型的表示范围为-231 ~ 231-1, 所以此题无法用int类型，可以使用long long类型。
代码
#include
using namespace std;
const int maxn = 100;
int A[maxn];
int main()
{
int T;
cin >> T;
while( T-- )
{
long long int n, sum = 0;
int i = 0;
cin >> n;
while( n )
{
A[i++] = n%2;
n /= 2;
}
for( int j = 0; j < i; j++ )
{
sum = sum*2 + A[j];
}
cout << sum << endl;
}
return 0;
}
模拟| 2018.计算机院.Problem B.数字填充
题目描述
就是用点阵表示数字，5*3的方格表示0~9，具体见样例及代码，0是然后输入一个数字串，用点阵输出
样例输入
02
样例输出
111111
101001
101111
101100
111111
这道题实在不想动手，请看**北邮2018计算机院考研复试机试上机题解+结果统计**中这道题的代码。
数学 | 2018.计算机院.Problem C.发财数
题目描述
一个大于等于2的整数，如果可以分解为8个或8个以上的素数相乘，则称其为发财数，输出第n个发财数(n<=105)
样例输入
1
1
样例输出
256
分析
要求第任意个发财数，可预先求出所有的发财数保存在数组中，题目需要第几个发财数直接取即可，所以发财数的数量应该不超过10^5;
首先本地上不设发财数的数量上限，计算尽可能多的发财数，然后取第10000个发财数，发现其值为330912
所以本题可直接取上限为400000；
打印素数表最快的方法是欧拉线性筛法，直接写上线性筛模板
判断x是否是发财数时，用x除最小的素数，每除一次计数自增，直到除到自身是素数并且计数值小于8。
代码
#include
#include
#include
#include
using namespace std;
const int MAXNUM = 400000;
const int maxn = 40000;
bool prime[MAXNUM] = {false};
int p[maxn];
vector facai;
//线性筛素数
int FindPrime()
{
int index = 0;
for(int i = 2; i < MAXNUM; i++)
{
//如果未标记则得到一个素数
if( !prime[i] )
p[index++] = i;
//标记目前得到的素数的i倍为非素数
for( int j = 0; j < index && p[j] * i < MAXNUM; j++ )
{
prime[i * p[j]] = true;
if( i % p[j] == 0 )
break;
}
}
return index;
}
bool isfacai( int x )
{
int i = 0;
int cnt = 0;
while( i < maxn )
{
if( !prime[x] )
{
cnt++;
break;
}
if( x%p[i] == 0 )
{
cnt++;
x /= p[i];
if( cnt >= 8 )
break;
}
else
i++;
}
if( cnt >= 8 )
return true;
else
return false;
}
int main()
{
FindPrime();
int T;
for( int i = 256; i < MAXNUM; i++ )
if( isfacai(i) )
facai.push_back( i );
cin >> T;
while( T-- )
{
int n;
cin >> n;
cout << facai[n-1] << endl;
}
return 0;
}
DP | 2018.计算机院.Problem D.最长平衡子串
题目描述
给定只含01的字符串，找出最长平衡子串的长度(平衡串：包含0和1的个数相同)，串长最大106
思路
用dp0数组存储当前位置左边包含的0的个数(包括当前位置)
用dp1数组存储当前位置左边包含的1的个数(包括当前位置)
则区间(i, j]包含的0的个数为dp0[j]-dp0[i]; 区间(i, j]包含的1的个数为dp1j]-dp1[i];
设双指针分别指向首末位置，若0的数量多余1的数量，则从两端找到含0的一端向另一端移动，若两边都是1，则左指针向右移动，对于1数量多于0的情况同样如此，直至0和1的数量相等，打印结果。
时间复杂度为O(n)
代码
#include
using namespace std;
const int maxn = 100010;
int dp0[maxn] = {0};
int dp1[maxn] = {0};
int main()
{
int T;
cin >> T;
string str;
while( T-- )
{
cin >> str;
int len = str.size();
if( str[0] == '0' )
dp0[0] = 1;
else
dp1[0] = 1;
for( int i = 1; i < len; i++ )
{
if( str[i] == '0' )
{
dp0[i] = dp0[i-1] + 1;
dp1[i] = dp1[i-1];
}
else
{
dp1[i] = dp1[i-1] + 1;
dp0[i] = dp0[i-1];
}
}
if( dp0[len-1] == dp1[len-1] )
{
cout << str << endl;
continue;
}
int i = 0, j = len-1;
while( i < j )
{
if( dp0[j] - dp0[i] == dp1[j] - dp1[i] )
{
for( int k = i+1; k <= j; k++ )
cout << str[k];
cout << endl;
break;
}
else if( dp0[j] - dp0[i] > dp1[j] - dp1[i] )
{
if( str[i] == '0' )
i++;
else if( str[j] == '0' )
j--;
else
i++;
}
else
{
if( str[i] == '1' )
i++;
else if( str[j] == '1' )
j--;
else
i++;
}
}
}
return 0;
}