2022年华东师范大学复试机试

比赛两个小时，为OI赛制(可以暴力拿部分分)，一共六道题目。以下仅为本人练习记录，算法不是最优的。

A 整数排序

单点时限:2.0 sec

内存限制:512MB

代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int CountWeishu(int x){//计算位数
    int Weishu=1;
    while(x/10!=0){
        x=x/10;
        Weishu++;
    }
    return Weishu;
}

bool compare(int x,int y){//比较函数
    if(CountWeishu(x)== CountWeishu(y))
        return x<y;
    else
        return CountWeishu(x)>CountWeishu(y);
}

int main() {
    vector<int> arr;
    int n;
    while(cin>>n){
        arr.push_back(n);
        if(getchar()=='\n')//遇到换行符表示输入结束
            break;
    }
    sort(arr.begin(),arr.end(),compare);
    for(int i=0;i<arr.size();i++)
        cout<<arr[i]<<" ";

    return 0;
}

运行结果：

B 位运算

单点时限:2.0 sec

内存限制:512MB

代码：

#include <iostream>
using namespace std;

const int MAXN=32;
int dig[MAXN]={0};//记录二进制数字串

void H10ToH2(int x){//十进制转二进制
    for(int i=0;x!=0;i++){
        dig[i]=x%2;
        x=x/2;
    }
}

int H2ToH10(){//二进制转十进制
    int res=0;
    int i=MAXN-1;
    while(dig[i]==0) i--;
    while(i>=0){
        res=(res+dig[i])*2;
        i--;
    }
    return res/2;
}


int main() {
    int n,m,i,j;
    cin>>n>>i>>j;
    H10ToH2(n);
    swap(dig[i],dig[j]);//交换二进制串中对应位置元素
    m=H2ToH10();
    cout<<m<<endl;

    return 0;
}

运行结果：

C 差分计数

单点时限:0.5 sec

内存限制:512MB

优化没思路，直接上暴力解法，能得一部分分。

代码：

#include <iostream>
using namespace std;

int main(){
    int n,x;
    cin>>n>>x;
    int arr[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];

    int res=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            if(arr[i]-arr[j]==x) res++;
        }
    cout<<res<<endl;
    return 0;
}

运行结果：

D 罗马数字

单点时限:2 sec

内存限制:512MB

代码：

#include <iostream>
#include <map>
using namespace std;

int main(){
    map<int,string> rule;//定义转换规则
    rule[0]="";
    rule[1]="I",rule[2]="II",rule[3]="III",rule[4]="IV",rule[5]="V";
    rule[6]="VI",rule[7]="VII",rule[8]="VIII",rule[9]="IX",rule[10]="X";
    rule[20]="XX",rule[30]="XXX",rule[40]="XL",rule[50]="L";
    rule[60]="LX",rule[70]="LXX",rule[80]="LXXX",rule[90]="XC",rule[100]="C";
    rule[200]="CC",rule[300]="CCC",rule[400]="CD",rule[500]="D";
    rule[600]="DC",rule[700]="DCC",rule[800]="DCCC",rule[900]="CM",rule[1000]="M";

    int n;
    cin>>n;

    string str[4];//将十进制数字按位拆分，对应相应的罗马数字
    str[3]=rule[n/1000*1000],n=n%1000;
    str[2]=rule[n/100*100],n=n%100;
    str[1]=rule[n/10*10],n=n%10;
    str[0]=rule[n];

    string res=str[3]+str[2]+str[1]+str[0];//拼接各位的罗马数字
    cout<<res<<endl;

    return 0;
}

运行结果：

E 乘法

单点时限:1.0 sec

内存限制:256MB

优化还是没思路，直接上暴力得一部分分吧。

代码：

#include <iostream>
#include <algorithm>
using namespace std;

bool compare(int x,int y){
    return x>y;
}

int main(){
    int n,m,k;
    cin>>n>>m>>k;
    int a[n],b[m];
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<m;i++) cin>>b[i];

    int res[n*m];
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            res[i*m+j]=a[i]*b[j];

    sort(res,res+n*m,compare);
    cout<<res[k-1]<<endl;
    return 0;
}

运行结果：