校招全国统一模拟笔试技术类编程题参考题解(六月)

牛牛偶像养成记

分析

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

时间复杂度分析

O(nlogn)

参考代码

#include <bits/stdc++.h>

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)

参考代码

#include <bits/stdc++.h>

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<cnt;i++)
    {
        sum1+=a[i];
        for(int j=0;j<cnt;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)

#include <bits/stdc++.h>

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)

参考代码

#include<bits/stdc++.h>  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)

参考代码

#include <bits/stdc++.h>

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<node> 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;
}