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

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

A 庙会

单点时限: 1.0 sec

内存限制: 256 MB

代码：

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

int main(){
    int m,n,k;
    cin>>m>>n>>k;
    queue<int> q1;
    queue<int> q2;
    for(int i=1;i<=m;i++) q1.push(i);
    for(int i=1;i<=n;i++) q2.push(i);

    for(int i=0;i<k;i++){
        int t1=q1.front(),t2=q2.front();
        cout<<t1<<" "<<t2<<endl;
        q1.pop();
        q2.pop();
        q1.push(t1);
        q2.push(t2);
    }
    return 0;
}

B 热河路

思路：找规律，1、2、4、7、11....这些位置上是1，其他是0，满足二元一次方程 y=0.5x^2-0.5x+1，即2y-2=x*(x-1)

细节：用cin、cout的时候最后一个样例超时了，改用scanf、printf后AC了。

代码：

#include <cmath>
#include <cstdio>

int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int y;
        scanf("%d",&y);
        int m=2*y-2;
        int x=sqrt(m)+1;
        if(m==x*(x-1)) printf("1\n");
        else printf("0\n");
    }
    return 0;
}

C 定西

单点时限: 1.0 sec

内存限制: 256 MB

这里用BFS解决。

代码：

#include <iostream>
#include <queue>

using namespace std;

bool IsBroken(int x,int* broken,int k){//检查是否是破损的阶梯
    for(int i=0;i<k;i++)
        if(x==broken[i]) return true;
    return false;
}

int main(){
    int n,k;
    cin>>n>>k;
    int broken[k];
    for(int i=0;i<k;i++) cin>>broken[i];
    queue<int> q;//用一个队列实现BFS
    q.push(1);
    q.push(2);
    q.push(3);

    int res=0;//记录有多少种方法
    while(q.empty()==0){
        int t=q.front();
        q.pop();
        if(IsBroken(t,broken,k)==1) continue;//如果走到破损的楼梯上，则不再考虑接下来的情况
        if(t==n) res++;//如果走到第n阶楼梯，表示成功找到一种可行的方法
        if(t+1<=n) q.push(t+1);
        if(t+2<=n) q.push(t+2);
        if(t+3<=n) q.push(t+3);
    }
    cout<<res<<endl;
    return 0;

}

D 和你在一起

单点时限: 1.0 sec

内存限制: 256 MB

代码：

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

int main(){
    int n;
    cin>>n;
    string a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    string res="";
    for(int i=n-1;i>=0;i--){
        res=res+a[i];
    }
    cout<<res<<endl;
    return 0;
}

E 梵高先生

单点时限: 1.0 sec

内存限制: 256 MB

代码：

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    int n;
    cin>>n;
    int a[n][n];
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            if(j==0) a[i][j]=1;
            else a[i][j]=0;
        }
    for(int i=1;i<n;i++)
        for(int j=1;j<n;j++)
            a[i][j]=a[i-1][j-1]+a[i-1][j];
    for(int i=0;i<n;i++)
        for(int j=0;j<=i;j++){
            if(j<i) cout<<a[i][j]<<" ";
            else if(j==i) cout<<a[i][j]<<endl;
        }

    return 0;
}

F 西班牙馅饼

单点时限: 1.0 sec

内存限制: 256 MB

代码：

#include <iostream>

using namespace std;

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

    int sum=0;
    for(int i=0;i<n;i++){
        int max=0;
        for(int j=0;j<m;j++){
            if(a[i][j]>max) max=a[i][j];
        }
        sum+=max;
    }
    cout<<sum<<endl;
    return 0;
}