为了保证制作简历的安全性和流畅性,建议您使用Chrome浏览器进行访问
iced americano 香港大学·2022届
APP 内打开
分享
12
23

2019年校招全国统一模拟笔试(五月场)编程题参考代码

牛牛偶像养成记

分析

题目给出了n次牛牛能够上台的起始时间和持续时间,那么,我们可以通过这两个时间求到每次表演的结束时间。要使得牛牛上台的次数越多,那么就只有让牛牛上一个节目的结束时间越早,能留出更多的时间来选择后面更多的上台机会。所以,我们只需要将牛牛所有节目的结束时间从小到大排序,每次取满足条件的结束时间最早的节目就行了。

时间复杂度分析

O(nlogn)

参考代码

复制代码

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

#include

 

using namespace std;

 

const int maxn = 1e5 + 5;

 

struct node {

    int start, ed;

};

node a[maxn];

int n, m;

 

bool cmp(node x,node y) {

    if(x.ed != y.ed)

        return x.ed < y.ed;

    else

        return x.start < y.start;

}

int main() {

    cin >> n;

    for(int i = 0; i < n; i++) {

        cin >> a[i].start >> m;

        a[i].ed = a[i].start + m;

    }

    sort(a, a + n, cmp);

    int ans = 0, t = 0;

    for(int i = 0; i < n; i++) {

        if(t <= a[i].start) {

            ans++;

            t = a[i].ed;

        }

    }

    cout << ans << endl;

    return 0;

}

牛牛与妞妞

分析

牛牛和妞妞一共可以取得有52张牌,在题目给出6张牌后,还有46张牌可以取。我们就把这46张牌全部放进一个数组里面,然后跑两重循环,枚举牛牛和妞妞最后一张牌分别可以取到什么牌,总的枚举数是分母,分子即为牛牛比妞妞多的数量,相除即可。

时间复杂度

O(13^2)

参考代码

复制代码

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

#include

 

using namespace std;

 

int a1,b1,c1,a2,b2,c2;

int vis[15];

int a[60];

 

int main() {

    memset(vis,0,sizeof(vis));

    scanf("%d%d%d", &a1, &b1, &c1);

    vis[a1]++;

    vis[b1]++;

    vis[c1]++;

    scanf("%d%d%d", &a2, &b2, &c2);

    vis[a2]++;

    vis[b2]++;

    vis[c2]++;

    int sum1 = a1 + b1 + c1;

    int sum2 = a2 + b2 + c2;

    int cnt = 0;

    double l=0,r=0;

    for(int i=1;i<=13;i++)

    {

        for(int j=0;j<4-vis[i];j++)

        {

            a[cnt++]=i;

        }

    }

    for(int i=0;i

    {

        sum1+=a[i];

        for(int j=0;j

        {

            if(i == j)

                continue;

            sum2+=a[j];

            r++;

            if(sum1>sum2)

                l++;

            sum2-=a[j];

        }

        sum1-=a[i];

    }

    printf("%.4f\n",l/r);

    return 0;

}

牛牛数星星

分析

从数据规模可以看到,我们一共有10万颗星星以及最多10万次查询,如果我们每次查询都把给出的范围内遍历一遍的话肯定会超时。那么,我们就需要换一种方法。因为我们只需要得到一个矩形范围内的星星的数量,我们就可以先跑一遍整个数据范围,找到这个点的左上方向一共有多少颗星星,并把它标记出来。那么,我们要得到的矩形范围内的星星数量就变为了这个矩形右下角的点的值减去这个矩形左下角左边那个点的值再减去这个矩形右上角上面那个点的值再加上这个矩形左上角的左上边那个点的值(可以想象一下容斥定理)。那么,我们只需要遍历一次1000*1000的地图就行了,每个查询可以O(1)来获取。

时间复杂度

O(N^2)

复制代码

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

#include

 

using namespace std;

 

const int maxn = 1e3 + 5;

 

int n, m;

int num[maxn][maxn];

int mp[maxn][maxn];

int x, y;

int a1, b1, a2, b2;

 

int main() {

    memset(num, 0, sizeof(num));

    memset(mp, 0, sizeof(mp));

    scanf("%d", &n);

    for(int i = 0; i < n; i++) {

        scanf("%d%d", &x, &y);

        mp[x][y]++;

    }

    for(int i = 1; i < maxn; i++) {

        for(int j = 1; j < maxn; j++) {

            num[i][j] = num[i - 1][j] + num[i][j - 1] + mp[i][j] - num[i - 1][j - 1];

        }

    }

    scanf("%d", &m);

    for(int i = 0; i < m; i++) {

        scanf("%d%d%d%d", &a1, &b1, &a2, &b2);

        printf("%d\n", num[a2][b2] - num[a1 - 1][b2] - num[a2][b1 - 1] + num[a1 - 1][b1 - 1]);

    }

    return 0;

}

牛牛与世界杯门票

分析

  这个题可以看做是一个完全背包,人的个数相当于背包的容量,票的价格相当于价值,dp[i]表示买到i张票时的最小花费为dp[i],最后dp[n]即为买到n张票时的最小花费(程序中的n是加上牛牛自己时的数量)。

时间复杂度

O(n*m)

参考代码

复制代码

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

#include  using namespace std;

 

const int maxn = 1e3 + 5;

 

int n,m,k,x,y;

int dp[maxn];

 

int main()

{

    scanf("%d%d%d",&n,&m,&k);

    n++;

    for(int i=1; i<=n; i++)

        dp[i]=i*k;

    while(m--)

    {

        scanf("%d%d",&x,&y);

        for(int i=1; i<=n; i++)

        {

            if(i-y>=0)

                dp[i]=min(dp[i],dp[i-y]+x);

            else

                dp[i]=min(dp[i],x);

        }

    }

    printf("%d\n",dp[n]);

    return 0;

}

牛牛游玩记

分析

如果只有一个入口,那么这个题就是一个裸的BFS(DFS),但是改成多个入口之后呢?每一个都计算一次BFS(DFS)么?当然不。我们可以假象有一个超级起点,把这个起点连接上所有的入口,那么,这个题不就相当于一个入口一个出口了么。所以,我们只要把所有的起点在一开始都放入BFS的队列中,后面就按照普通的BFS写法就行了。

时间复杂度

O(n^2)

参考代码

复制代码

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

#include

 

using namespace std;

 

const int maxn = 1e3 + 5;

 

const int dx[] = {0, 1, 0, -1};

const int dy[] = {-1, 0, 1, 0};

 

struct node {

    int x, y;

};

int n, m;

int dis[maxn][maxn];

char mp[maxn][maxn];

node a, ed;

int main() {

    memset(mp, 0, sizeof(mp));

    memset(dis, -1, sizeof(dis));

    queue q;

    scanf("%d%d", &n, &m);

    for(int i = 0; i < n; i++) {

        scanf("%s", mp[i]);

    }

    for(int i = 0; i < n; i++) {

        for(int j = 0; j < n; j++) {

            if(mp[i][j] == '@') {

                a.x = i;

                a.y = j;

                q.push(a);

                dis[i][j] = 0;

            }

            if(mp[i][j] == '*') {

                ed.x = i;

                ed.y = j;

            }

        }

    }

    while(q.size()) {

        node p = q.front();

        q.pop();

        for(int i = 0; i < 4; i++) {

            int px = p.x + dx[i];

            int py = p.y + dy[i];

            if(dis[px][py] == -1 && px >= 0 && px < n && py >= 0 && py < n && mp[px][py] != '#') {

                node pp;

                pp.x = px;

                pp.y = py;

                q.push(pp);

                dis[px][py] = dis[p.x][p.y] + 1;

                if(px == ed.x && py == ed.y)

                    break;

            }

        }

        if(dis[ed.x][ed.y] != -1) break;      

    }

    printf("%d\n", dis[ed.x][ed.y]);

    return 0;

}

发布时间:2020年07月08日
用户头像
我来说两句…
共 12 条评论
安枫 海南大学·2022届
请问这些题的题目在哪看啊 我没报名但想看看前几个月的行不行?
2020年08月20日 回复
Levana Dong 澳大利亚国立大学·2022届
牛牛与世界杯门票:存在问题 复制代码 1 2     for(inti=1; i<=n; i++)         dp[i]=i*k; 原因:上面代码没有将dp[0]赋值,导致dp[0]的值未知,应该赋值为0。再执行之后的代码时: 复制代码 1 2  if(i-y>=0)                 dp[i]=min(dp[i],dp[i-y]+x); 如果恰好出现 i == y的情况,就会出现错误。
2020年08月20日 回复
Prophet 河北工业大学·2022届
公园那题可以逆向思维,起点当终点,终点当起点,只有一个入口再BFS
2020年08月20日 回复
张小龙 中国传媒大学·2022届
Java虚拟机是一个可以执行Java字节码的虚拟机进程。Java源文件被编译成能被Java虚拟机执行的字节码文件。 Java被设计成允许应用程序可以运行在任意的平台,而不需要程序员为每一个平台单独重写或者是重新编译。Java虚拟机让这个变为可能,因为它知道底层硬件平台的指令长度和其他特性。
2020年08月20日 回复
温文尔雅 上海理工大学·2022届
是我记错了吗?星星那道题有限制网格的长宽吗?
2020年08月20日 回复
啊啊啊啊啊 中山大学·2022届
牛牛游玩记:将问题转化,可以直接使用BFS 过程如下: 对于多个入口,一个出口的问题。 可以将入口看做出口,将出口看做入口。 那么就变成,一个入口,多个出口的问题。 从现在的入口(之前的出口)为起始点使用BFS,直到遇到现在的出口(之前的入口)的路径,即为最短路径。
2020年08月19日 回复
阿寒 北京林业大学·2022届
膜拜大佬!希望各位大佬赐教,如果世界杯门票那道 按照大礼包的思路,遍历每种套餐,每次更新所需球票的数量N-y,然后递归求解。这样的话时间复杂度是多少?
2020年08月20日 回复
木子先生 太原理工大学·2022届
数星星那个有没有大佬帮我解释下,没看懂。。。
2020年08月20日 回复
嘎嘎嘎嘎-Xin 集美大学·2022届
强啊
2020年08月21日 回复
Charlie 莫纳什大学·2022届
厉害
2020年08月20日 回复
阿白 华南理工大学·2022届
最后一题用出口做起点也挺好。
2020年08月19日 回复
人在旅途呀 南京大学·2022届
tql
2020年08月19日 回复