美团0311笔试总结

写在前面：

作为整个人生求职生涯的第一场笔试，在做美团笔试时还是充满紧张和激动的，以至于最后一道题都没有看到，熟悉又陌生的 ACM 模式还是让我对本地 IDE 和 OJ 的差异性做出了过低的评估以至于第二题手忙脚乱浪费了不少时间。

本篇文章仅分享本人解答代码做学习交流，若涉密或侵权可联系我删除。

题目 1

题目内容

大意是给你一个字符串，让你把它改成相邻元素不同的状态，询问最少修改次数

例如，对于字符串 11222333 ，她可以进行 3 次修改将其变为 121212313 。

解题方法

模拟。遇到相同的就修改，记录次数。

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    while (cin>>s) {
        string now = s;
        int len = now.length(), ans = 0;
        for (int i = 1; i < len; i++) {
            if (now[i-1] == 0) {
                continue;
            }
            if (now[i] == now[i-1]) {
                ans++;
                now[i] = 0;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

题目 2

题目内容

小团在一个 n*m 的网格地图上探索。网格地图上第 i 行第 j 列的格子用坐标 (i, j) 简记。

初始时，小团的位置在地图的左上角，即坐标 (1, 1) 。地图上的每一个格子上都有一定的金币，特别地，小团位于的初始位置 (1, 1) 上的金币为 0 。小团在进行探索移动时，可以选择向右移动一格(即从 (x, y) 到达 (x, y + 1) ) 或向下移动一格 (即从 (x, y) 到达(x + 1, y)) 。

地图上的每个格子都有一个颜色，红色或蓝色。如果小团一次移动前后的两个格子颜色不同，那么他需要支付 k 个金币才能够完成这一次移动；如果移动前后的两个格子颜色相同，则不需要支付金币。小团可以在任意格子选择结束探索。

现在给你网格地图上每个格子的颜色与金币数量，假设小团初始时的金币数量为 0，请你帮助小团计算出最优规划，使他能获得最多的金币，输出能获得的最多金币数量即可注意：要求保证小团任意时刻金币数量不小于零。

输入

第一行 n， m， k 分别代表行数、列数和颜色转换需要的金币数

输入 colors 颜色二维数组

输入金币二维数组代表每点的金币个数

解题方法

动态规划。比较基础的一道 DP ，直接使用 \(dp[i][j]\) 表示到达位置 (i, j) 时的最大金币数。（第一次笔试，写的比较丑）

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n, m, k;
    while (cin>>n>>m>>k) {
        string graph[n];
        for (int i = 0; i < n; i++) {
            cin >> graph[i];
        }
        vector<vector<int>> val(n, vector<int>(m, 0));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> val[i][j];
            }
        }
        vector<vector<int>> dp(n, vector<int>(m, -1));
        int ans = 0;
        dp[0][0] = 0;
        for (int i = 1; i < n; i++) {
            int pre = dp[i-1][0] - (graph[i-1][0] == graph[i][0] ? 0:k);
            if (pre >= 0){
                dp[i][0] = pre + val[i][0];
            }
        }
        for (int j = 1; j < m; j++) {
            int pre = dp[0][j-1] - (graph[0][j-1] == graph[0][j] ? 0:k);
            if (pre >= 0) {
                dp[0][j] = pre + val[0][j];
            }
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                int l = dp[i-1][j] - (graph[i-1][j] == graph[i][j] ? 0:k);
                int r = dp[i][j-1] - (graph[i][j-1] == graph[i][j] ? 0:k);
                if (l >= 0) {
                    dp[i][j] = max(dp[i][j], l + val[i][j]);
                }
                if (r >= 0) {
                    dp[i][j] = max(dp[i][j], r + val[i][j]);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ans = max(ans, dp[i][j]);
            }
        }
        cout << ans << endl;
    }
}

题目 3

题目内容

小美是一位天文爱好者，她收集了接下来一段时间中所有会划过她所在的观测地上空的流星信息。具体地，她收集了 n 个流星在她所在观测地上空的出现时刻和消失时刻。

对于一个流星，若其的出现时刻为 s，消失时刻为 t，那么小美在时间段 [s, t] 都能够观测到它。对于一个时刻，观测地上空出现的流星数量越多，则小美认为该时刻越好。小美希望能够选择一个最佳的时刻进行观测和摄影，使她能观测到最多数量的流星。

现在小美想知道，在这个最佳时刻，她最多能观测到多少个流星以及一共有多少个最佳时刻可供她选择。

输入

第一行： n 代表区间个数

第二行， 输入所有区间的起始端点

第三行， 输入所有区间的末尾端点

解题方法

离散化 + 差分。基本上是裸的模板题，直接秒了。

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n;
    while (cin>>n) {
        vector<pair<int, int>> t(n);
        vector<int> node;
        for (int i = 0; i < n; i++) {
            cin>>t[i].first;
            node.push_back(t[i].first);
        }
        for (int i = 0; i < n; i++) {
            cin>>t[i].second;
            node.push_back(t[i].second);
        }
        sort(node.begin(), node.end());
        node.erase(unique(node.begin(), node.end()), node.end());
        unordered_map<int, int> hash;
        int len = node.size();
        for (int i = 0; i < len; i++) {
            hash[node[i]] = i;
        }
        vector<int> diff(len + 1, 0);
        sort(t.begin(), t.end());
        for (auto &[l, r] : t) {
            diff[hash[l]] += 1;
            diff[hash[r]+1] -= 1;
        }
        int cnt = 0;
        unordered_map<int, int> um;
        for (int i = 0; i <= len; i++) {
            cnt += diff[i];
            um[cnt]++;
        }
        int ans = 0, pos = 0;
        for (auto &[k, v] : um) {
            if (k > ans) {
                ans = k;
                pos = v;
            }
        }
        cout<<ans<<" "<<pos<<endl;
    }
}

赛后去学习离散化 + 差分时学到了一个很简洁的写法，借助 Map 的有序性和 Key 唯一性，代码如下：

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n;
    while (cin>>n) {
        map<int, int> m;
        int s, e;
        for (int i = 0; i < n; i++) {
            cin >> s;
            m[s]++;
        }
        for (int i = 0; i < n; i++) {
            cin >> e;
            m[e + 1]--;
            m[e];
        }
        int cnt = 0, ans = -1, times = -1;
        unordered_map<int, int> cnts;
        for (auto &[k, v] : m) {
            cnt += v;
            cnts[cnt]++;
        }
        for (auto &[k, v]: cnts) {
            if (v > ans) {
                ans = v;
                times = k;
            }
        }
        cout << times << " " << ans << endl;
    }
}

题目 4

题目内容

坦克大战，但我没来得及写

解题方法

等找到题面后，有时间做一下 > // todo

题目 5

题目内容

不知道，甚至都没有看到

解题方法

等找到题面后，有时间做一下 > // todo