2022-USTC-BDAA-考研机试全解

其他：

我是2024考研USTC的学生，在刘淇老师的主页上发现了CODIA平台，题目均来源自CODIA平台。本人能力有限，不足以成为刘淇老师的学生。但他的题目确实给了我许多启发。实话实说，题目难度并不简单。不愧是刘淇老师。本着开源精神，本人将能做的题目用自己的方式做了，分享给考研保研USTC的大家。如果涉及侵权，请联系我，将以第一时间删除，另外，如果有做过这个机试的学长学姐，也希望您能分享关于这个机试的其他感受，比如做多少题才能录取等等。就我的发现来说，BDAA实验室只有20年的面经，21年以后的算法题难度和20年简直是天壤之别，不知道是突然难度提升了，还是刘淇老师这里本来要求就高。

CODIA链接：首页 | CODIA (bdaa.pro)

2022-考研

计时

题目描述

给定一天中的一个起始时s和终止时t，求s到t的时间间隔。

输入描述

输入共一行，两个时刻s和t（用空格隔开）。起始时s和终止时t均为标准的HH:MM:SS.DDD形式，详见样例。

输出描述

输出一行表示s和t的时间间隔，同样以HH:MM:SS.DDD表示，详见样例。

数据范围

对于100%的数据，起始时s不晚于终止时t，两个时间点均属于同一天。

样例输入

08:00:00.000 22:15:47.368

样例输出

14:15:47.368

解：

//
// Created by liu'bo'yan on 2024/3/14.
//
#include <bits/stdc++.h>

using namespace std;
int main(){
    int sh,sm,ss,sms,th,tm,ts,tms,ah,am,as,ams;
    scanf("%d:%d:%d.%d %d:%d:%d.%d",&sh,&sm,&ss,&sms,&th,&tm,&ts,&tms);
    if(tms>=sms){
        ams=tms-sms;
    }else{
        ams=tms+1000-sms;
        ts--;
        if(ts<0){
            ts+=60;
            tm--;
            if(tm<0){
                tm+=60;
                th--;
            }
        }
    }
    if(ts>=ss){
        as=ts-ss;
    }else{
        as=ts+60-ss;
        tm--;
        if(tm<0){
            tm+=60;
            th--;
        }
    }
    if(tm>=sm){
        am=tm-sm;
    }else{
        am=tm+60-sm;
        th--;
    }
    ah=th-sh;
    if(ah==0){
        cout<<"00";
    }else if(ah<10){
        cout<<"0"<<ah;
    }else{
        cout<<ah;
    }
    cout<<":";
    if(am==0){
        cout<<"00";
    }else if(am<10){
        cout<<"0"<<am;
    }else{
        cout<<am;
    }
    cout<<":";
    if(as==0){
        cout<<"00";
    }else if(as<10){
        cout<<"0"<<as;
    }else{
        cout<<as;
    }
    cout<<".";
    if(ams==0){
        cout<<"000";
    }else if(ams<10){
        cout<<"00"<<ams;
    }else if(ams<100){
        cout<<"0"<<ams;
    }else{
        cout<<ams;
    }
}

评价：小模拟，笔者的代码有些啰嗦，可能读者有更好的解法。

螺旋矩阵

题目描述

一个n行m列的螺旋矩阵可由如下方法生成：从矩阵的左上角（第1行第1列）出发，初始时向右移动；如果前方是未曾经过的格子，则继续前进，否则右转；重复上述操作直至经过矩阵中所有格子。根据经过顺序，在格子中依次填入1,2,…,nm，便构成了一个螺旋矩阵。下图是一个n=3,m=4的螺旋矩阵。


1	2	3	4
10	11	12	5
9	8	7	6

现给定n和m构造一个螺旋矩阵，求这个矩阵第i行第j列的数字。

输入描述

输入共一行四个正整数n,m,i,j（用空格隔开）。

输出描述

输出共一行一个正整数，表示第i行第j列的数字。

数据范围

对于50%的数据，1≤n,m≤100。对于100%的数据，1≤n,m≤10^5，1≤i≤n，1≤j≤m。

样例输入

3 4 2 3

样例输出

//
// Created by liu'bo'yan on 2024/3/1.
//
#include <iostream>
using namespace std;
using ll = long long;
int main()
{
    int n,m,i,j;
    cin>>n>>m>>i>>j;
    int up=i,down=n-i+1,left=j,right=m-j+1;
    //确定矩阵中第i行第j列的数，在矩阵的第t层
    int t = min(min(up, down), min(left, right));
    ll ans = 1, r = 1, c = 1;
    for(int _=1;_<t; _++)
    {
        ans+=2*(m+n)-4; //第t层左上角的第一个数为ans
        r++,c++; //第t层左上角的位置为(r,c)
        n-=2,m-=2;//第t层的子矩阵大小减少2
    }
    if(i==r) ans+=j-c; //如果在该层的第一行上
        //如果在该层的最后一列
    else if(j==c+m-1) ans+=m-1+i-r;
        //如果在该层的最后一行
    else if(i==r+n-1)ans+=n+m*2-3-(j-c);
        //如果在该层的第一列
    else ans+=2*(m+n)-4-(i-r);
    cout<<ans;
    return 0;
}

不要使用二维数组模拟，会爆内存，另外别忘开ll。

摸球

题目描述

箱子里有n个红球和m个黑球。现采用不放回的方式随机依次从箱子里摸球，求摸到第一个黑球时，已摸到红球的期望数量。

输入描述

输入一行两个正整数n,m，分别表示红球数和黑球数。

输出描述

输出一行一个实数，表示所要求的期望答案，结果四舍五入保留3位小数。

数据范围

对于30%的数据，1≤m≤21≤n≤2。对于60%的数据，1≤m,n≤1051≤n,m≤105。对于100%的数据，1≤m,n≤1091≤n,m≤109。

样例输入

1 3

样例输出

0.250

AC代码

//
// Created by liu'bo'yan on 2024/3/14.
//
#include <bits/stdc++.h>

using namespace std;
using ll=long long;
int main(){
    ll n,m;
    cin>>n>>m;
    double ans=n*1.0/(m+1);
    printf("%.3f",ans);
}

参考负超几何分布，这道题急需要数学直觉，我的评价是逆天。转为（1，m+n,m)的负超几何分布的期望就行，最后-1减的是抽中黑球的那一次。

有n个红和m个黑。现采用不放回的方式随机依次从箱子里摸球，求摸到第一个黑时，已摸到红的期望数量? - 知乎 (zhihu.com)

这是本人在知乎上的提问，下面的大佬都从各个角度做出了精彩的证明。