題目來源：北郵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;
}