华科CS研究生复试机试题
2021 A卷
T1 50’
- 给出一些整数，要求将它们升序排列输出并去重
- 输入描述：第一行给出一个整数n，表示数组的整数个数。第二行给出n个整数，以空格分隔。
- 输出描述：第一行为升序排列后遍历的数组，第二行为去重后的升序数组
- 输入
- $5$
- $6 \space 2 \space 3 \space 3 \space 7$
- 输出
- $2 \space 3 \space 3 \space 6 \space 7$
- $2 \space 3 \space 6 \space 7$
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int n;
while(cin >> n){
vector<int> nums;
int num;
for(int i = 0;i < n;i++){
cin >> num;
nums.push_back(num);
}
//升序排序
sort(nums.begin(), nums.end());
//输出升序结果
for(int i = 0;i < n;i++)
cout << nums[i] << " ";
cout << endl;
//去重
vector<int> res;
int lastNum = nums[0];
res.push_back(lastNum);
for(int i = 1;i < n;i++){
if(lastNum == nums[i])
continue;
else{
lastNum = nums[i];
res.push_back(lastNum);
}
}
//输出去重结果
for(int i = 0;i < res.size();i++)
cout << res[i] << " ";
cout << endl;
}
}
T2 30’
- 数字加密的一种常见方法是对计算机中以二进制表示的它进行移位，下面有一种方法，对32位二进制数进行加密
\[\begin{array}{|c|c|c|c|c|c|c|c|} \hline
xxxx & vvvv & xxxx & eeee & xxxx & eeee & xxxx & eeee \\ \hline
\end{array}\]
- 上述标注$eeee$的三段数位左移8位，标注$vvvv$的一段类似于循环左移移动到低0~3bit处
- 输入描述：给出一个无符号整数$n∈[0, 2^{32}-1]$，十进制形式
- 输出描述：按上述加密方法进行移位后，输出加密后的数值，注意仍以十进制方式输出
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main(){
unsigned int number;
while(cin >> number){
//转换2进制字符串处理
string radix2_str;
while(number != 0){
char c = number % 2 + '0';
radix2_str = c + radix2_str;
number /= 2;
}
//如果不够32位则插入前导0
radix2_str.insert(0, 32 - radix2_str.size(), '0');
//32位每4位一片分为8片
vector<string> sections;
for(int i = 0;i < radix2_str.size();i += 4)
sections.push_back(radix2_str.substr(i, 4));
//依题意移动指定片
string tmp = sections[1];//vvvv -> (tmp)
sections[1] = sections[3];//1st eeee -> vvvv
sections[3] = sections[5];//2nd eeee -> 1st eeee
sections[5] = sections[7];//3rd eeee -> 2nd eeee
sections[7] = tmp; //(tmp) -> 3rd eeee
//拼合
tmp.clear();
for(int i = 0;i < sections.size();i++)
tmp += sections[i];
//转换为十进制
unsigned int res = 0;
for(int i = 0;i < tmp.size();i++){
res *= 2;
res += tmp[i] - '0';
}
cout << res << endl;
}
}
T3 20’
- 从数字的十进制表示中删除一定个数的数字字符，剩下的字符仍然能够组成一个新的数。你的任务是找出这个数删除一定字符后形成的新数中最小的数，注意删去后原数字各字符的左右次序不变。
- 输入描述：第一行有两个数，第一个为操作数，以十进制方式输入，第二个为要删去的字符个数n，注意n一定小于操作数的位数
- 输出描述：删去n个字符后，输出按原左右次序组合后最小的数
- 输入 $62354 \space \space 2$
- 输出 $234$
#include <iostream>
#include <string>
using namespace std;
//注意要保留左右次序，因此只需从左到右遍历一遍，数字次序两两比较，删掉比其后一位大的数字即可
int aim_len;
int len;//已经拼合的长度
//从给定的str中删除n个数，以分治的形式
string FindNext(string str, int n){
if(n == 0 || len == aim_len)
return "";
//找到第一个降序序列中最后一个数,删去前面序列里的数
char lastNum = str[0];
int pos = 0;
for(int i = 1;i < str.size();i++){
if(lastNum <= str[i]){
//本次遍历到的数字大于等于上一个数字，即前述逆序结束
break;
}else{
lastNum = str[i];
pos++;
}
}
//如果pos小于n，即前面删去的数字个数还不够指定删除个数，去右边的子串中继续找
if(pos < n){
//结果字符串字符个数加1，由于n为待删除的字符个数，如果每次寻找的降序最后的数是字符串第一个(即升序串)
//pos=0时，导致会一直在右子串中删除n-pos=n个数，这样会导致溢出，因此设置一个字符串长度与目标串长度比较，及时终止
len++;
return lastNum + FindNext(str.substr(pos + 1), n - pos);
}else{
//pos==n || pos>=n 返回后面aim_len长的子串即可
return str.substr(n);
}
}
int main(){
string src;
int n;
while(cin >> src >> n){
aim_len = src.size() - n;
len = 0;
cout << FindNext(src, n) << endl;
}
}
