历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

美团 2021 笔试题-08

作者：

崔金浩Felix , 2021-03-12 21:53:59 , 所有人可见 , 阅读 2763

2

3

美团2021笔试通用卷08

美团的题真的一如既往有水平太难了

01 - 小美的暑假

小美的书架上有很多书。小美是个爱读书的新时代好青年。
小团虽然也喜欢看书，但小团大多数时候都更喜欢来小美家蹭书读。
这就导致小美的书架上很多书都会被小团借走。
小美很烦这一点，就想出了一个招数，小美的书架是一行一行的，他会对一些行加锁，这样小团就借不走了。
现在小团想要借书，请你帮忙看看小团能不能借到书，如果可以借到的话在哪一行书架上有这本书。
为了简单起见，每本书将用一个正整数进行编号，小美的书架一共有N行。

这题模拟题

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <unordered_map>
using namespace std;
int n, m, T;

vector<int> shelf;
vector<bool> isonshelf, locker, ismei;

void add(int a, int b)
{
    if(!ismei[a] ||locker[shelf[a]] || locker[b])
        return;
    isonshelf[a] = true;
    ismei[a] = true;
    shelf[a] = b;
}
void lockered(int a)
{
    locker[a] = true;
}
void unlockered(int a)
{
    locker[a] = false;
}
int borrow(int a)
{
    if(!isonshelf[a] || locker[shelf[a]]) return -1;
    isonshelf[a] = false;
    ismei[a] = false;
    int ans = shelf[a];
    shelf[a] = 0;
    return ans;
}
void getback(int a)
{
    ismei[a] = true;
}
int main()
{
    scanf("%d%d%d", &n, &m, &T);
    shelf = vector<int>(2 * n + m + 10, 0); 
    isonshelf = vector<bool>(2 * n + m + 10, false);
    ismei = vector<bool>(2 * n + m + 10, true);
    locker = vector<bool>(2 * n + m + 10, false);
    while(T--)
    {
        int op, a, b;
        scanf("%d%d", &op, &a);
        if(op == 1)
        {
            scanf("%d", &b);
            add(a, b);
        } else if (op == 2)
        {
            lockered(a);
        } else if (op == 3)
        {
            unlockered(a);
        } else if(op == 4)
        {
            cout << borrow(a) << endl;
        } 
        else if (op == 5){
            getback(a);
        }
    }
    return 0;
}

02 - 偏爱字母

小美喜欢字母E，讨厌字母F。在小美生日时，小团送了小美一个仅包含字母E和F的字符串，小美想从中选出一个包含字母E数量与字母F数量之差最大的子串。

*子串：从字符串前面连续删去若干个字符，从后面连续删去若干个字符剩下的字符串（也可以一个都不删），例如abcab是fabcab的子串，而不是abcad的子串。我们将空串看作所有字符串的子串。

最大连续子序列和 -> 最大的前缀和和最小的前缀和之差就是最大的连续子序列和

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

int main()
{
    int n;
    string s;
    cin >> n;
    cin >> s;
    vector<int> f(n + 1);
    // 1. 預處理前綴和
    for(int i = 1; i <= n; i++)
    {
        if(s[i - 1] == 'E')
            f[i] = f[i - 1] + 1;
        else
            f[i] = f[i - 1] - 1;
    }
    int res = 0, minv = 0;

    for(int i = 0; i <= n; i++)
    {
        res = max(res, f[i] - minv);
        minv = min(minv, f[i]);
    }
    cout << res << endl;
    return 0;
}

03 - 搭配出售

服装店新进了a条领带，b条裤子，c个帽子，d件衬衫，现在要把这些搭配起来售卖。有三种搭配方式，一条领带和一件衬衫，一条裤子和一件衬衫，一个帽子和一件衬衫。卖出一套领带加衬衫可以得到e元，卖出一套裤子加衬衫可以得到f元，卖出一套帽子加衬衫可以得到g元。现在你需要输出最大的获利方式;

这题看起来是分组背包实际上是多重背包这里以衬衫的数量作为体积（因为每一组都是用到衬衫）这里多重背包的二进制优化复习一下

while(cin >> a >> b >> s)
{
    int k = 1;
    while(k <= s)
    {
        cnt++;
        w[cnt] = b * k;
        v[cnt] = a * k;
        s -= k;
        k *= 2;
    }
    if(s > 0)
    {
        cnt++;
        w[cnt] = b * s;
        v[cnt] = a * s;
    }
}
// 打包完就是0 1 背包了
for(int i = 1; i <= cnt; i++)
    for(int j = V; j >= v[i]; j--)
        f[j] = max(f[j], f[j - v[i]] + w[i]);

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
using LL = long long;
const int N = 1000010;
LL dp[N];
LL w[N], v[N];
int tmps[4], tmpw[4];
int n = 3, V, cnt = 0;;

int main()
{

    int a, b, c, d, e, f, g;
    cin >> a >> b >> c >> d >> e >>f >>g;
    V = d; // 以
    tmps[0] = a, tmpw[0] = e;
    tmps[1] = b, tmpw[1] = f;
    tmps[2] = c, tmpw[2] = g;
    for(int i = 0; i < n; i++)
    {
        int ia, ib, is;
        ia = 1, ib = tmpw[i], is = tmps[i];
        LL k = 1;
        while(k <= is)
        {
            cnt++;
            v[cnt] = (LL)ia * k;
            w[cnt] = (LL)ib * k;
            is -= k;
            k *= 2;
        }
        if(is > 0)
        {
            cnt ++;
            v[cnt] = (LL)ia * is;
            w[cnt] = (LL)ib * is;
        }

    }
    // 轉化為多重背包問題
    for(int i = 1; i <= cnt; i++)
        for(int j = V; j >= v[i]; j--)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    cout << dp[V] << endl;
    return 0;
}

04 - 十字路口

在小美和小团生活的城市中，有n行m列共计nm个十字路口，第i行j列的十字路口有两个属性aij，bij。当行人处在i行j列的路口，对于任意非负整数k:
当时间处在[k*aij+k*bij), (k+1)*aij+k*bij)时，行人可以选择走到i±1行j列的路口。
当时间处在[(k+1)*aij+k*bij), (k+1)*aij+(k+1)*bij)时，行人可以选择走到i行j±1列的路口。
每次移动花费的时间为1，且要保证将要去的十字路口存在，即属于nm个路口当中。可以选择原地静止不动。
在第0时刻，小美处在xs行ys列的十字路口处，要去xt行yt列的十字路口找小团。小团原地不动等小美，请问小美所花费的时间最少是多少?

哇这题真的是学到了这题很有水平

开始以为这种带时间的最短路只能搜索（搜索的只能过40%）来着后来发现其实并非依赖整个路程的时间只是依赖上一个状态的时间而已-> 完全可以利用最短路的解法来做这个题 只不过路径权值并非固定要根据从上一个状态转移来的计算

简单来说 这里的路径长度就是时间 学到了第一次做这样的题555

如果在这个时间区间内（这里用余（ai + bi)来计算) 可以直接转移 不然就得等一会到下个区间的起点 （这里最优性应该是显然的）

这里等的时间一个是0-> 直接可以走要么就是区间端点减去当前余值-> 最优的等待值

最短路的框架就用Dijktra好了

很有水平的一道题最近做题学到最多的一道了（流泪）

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

const int N = 110;
int n, m, sx, sy, ex, ey;
int a[N][N], b[N][N], s[N][N];
bool st[N][N];
int dist[N][N];
int dx[2] = {1, -1}, dy[2] = {1, -1};

struct Node
{
    int x, y, dist;
    Node( ) : x(0), y(0), dist(0) {}
    Node(int _x, int _y, int _dist) : x(_x), y(_y), dist(_dist) {}

    bool operator<(const Node& t) const{
        return dist > t.dist;
    }
};
priority_queue<Node> q;
void add_x(int x, int y, int distance, int cost)
{
    for(int i = 0; i < 2; i++)
    {
        int nx = x + dx[i];
        if(nx <= 0 || nx > n) continue;
        if(dist[nx][y] > distance + cost+ 1)
        {
            dist[nx][y] = distance+cost + 1;
            q.emplace(nx, y, distance+cost + 1);
        }
   }
}

void add_y(int x, int y, int distance, int cost)
{
    for(int i = 0; i < 2; i++)
    {
        int ny = y + dy[i];
        if(ny <= 0 || ny > m) continue;
        if(dist[x][ny] > distance + cost+ 1)
        {
            dist[x][ny] = distance+cost + 1;
            q.emplace(x, ny, distance+cost + 1);
        }
   }
}
int main()
{
    memset(dist, 0x3f, sizeof dist);
    scanf("%d%d%d%d%d%d", &n, &m, &sx, &sy, &ex, &ey);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            scanf("%d", &a[i][j]);
            s[i][j] += a[i][j];
        }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            scanf("%d", &b[i][j]);
            s[i][j] += b[i][j];
        }

    dist[sx][sy] = 0;
    q.emplace(sx, sy, 0);
    while(q.size())
    {
        auto t = q.top();
        q.pop();
        int x = t.x, y = t.y, distance = t.dist;
        if(st[x][y]) continue;
        st[x][y] = true;
        // 扩展
        if(distance % (s[x][y]) < a[x][y])
        {
            // 上下
            add_x(x, y, distance, 0);
            // 左右 -> 等到可以转移的时候
            int cost = a[x][y] - distance % (s[x][y]);
            add_y(x, y, distance, cost);
        } else{
            add_y(x, y, distance, 0);
            int cost = s[x][y] - distance %(s[x][y]);
            add_x(x, y, distance, cost);
        }
    }
    cout << dist[ex][ey] << endl;
    return 0;
}

2 评论

FrankCooper 2021-08-17 09:55

分享一个「搭配出售」的朴素解法

d 件衬衫比较关键，每个搭配都用到了衬衫，组成一个list，按一套衣物的价值+衣物的数量，排序该list，按从大到小的价值排序
每一轮，先优先处理价值高的搭配，不断更新d

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt(), d = sc.nextInt();
        int e = sc.nextInt(), f = sc.nextInt(), g = sc.nextInt();
        List<int[]> list = new ArrayList<int[]>() {{
            add(new int[]{e, a});
            add(new int[]{f, b});
            add(new int[]{g, c});
        }};
        list.sort(((o1, o2) -> o2[0] - o1[0]));
        long res = 0;
        for (int i = 0; i < list.size(); i++) {
            int[] cur = list.get(i);
            int value = cur[0];
            int cnt = Math.min(cur[1], d);
            res += (long) value * cnt;
            d -= cnt;
        }
        System.out.printf("%d", res);
    }

勇敢的心_6 2022-10-19 12:03

好思路，我也是这么想的，不需要那么麻烦

App 内打开