美团笔试 - 0831

BraumAce2024年9月1日约 1722 字大约 6 分钟

美团笔试 - 0831

24年秋招【技术】第四场

小美的姓名统计

题面

小美写单词喜欢横着写，她记录了若干个人的名字，但是不小心加进去了一些无关的单词。
一个名字单词以大写字母开头，请你帮助她统计共有多少个人的名字.

输入描述：
在一行上输入一个长度为 $n (1 \le n \le 10^5)$ 、且由大小写字母和空格混合构成的字符串 $s$ 代表小美的全部单词，每个单词之间使用空格间隔。
除此之外，保证字符串的开头与结尾字符不为空格。

输出描述：
在一行上输出一个整数，代表人名的个数。

简单模拟。判断每一个字符的首字母是否为大写即可，注意空格。

#include <iostream>
#include <string>

using namespace std;

int main() {
    string s;
    getline(cin, s);
    
    int count = 0;
    int n = s.length();
    
    for (int i = 0; i < n; i++) {
        if (isupper(s[i]) && (i == 0 || s[i-1] == ' ')) {
            count++;
        }
    }
    
    cout << count << endl;
    
    return 0;
}

长度无限长的公路上，小美雇佣了 $n$ 位工人来种树，每个点最多种一棵树。
从左向右数，工人所站的位置为 $a_1, a_2, \ldots, a_n$ 。已知每位工人会将自己所在位置的右侧一段长度的区间种满树，且每位工人的种树区间长度相同。
现在小美希望公路上至少有 $k$ 棵树，为了节约成本，他希望位工人种树的区间长度可能短，请你帮他求出，工人们的种树区间至少多长，才能使得公路被种上至少 $k$ 棵树。

输入描述：
第一行输入两个正整数 $n, k$ $(1 \leq n, k \leq 2 \times 10^5)$ ，分别表示工人的数量，以及小美要求的最少数量。
第二行输入 $n$ 个正整数 $a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq 2 \times 10^5)$ ，表示每名工人的位置。

输出描述：
在一行上输出一个整数，代表工人们最短的种树区间长度。

二分答案。

先对工人的位置进行排序。
二分枚举种树区间，初始化左边界 l = 0，右边界 r = a_n。
每次二分后判断：当前种树区间为 x 的情况下，是否可以种 k 棵树？超过则缩小，不够则增加。
判断逻辑：end 记录的是上一次种到的边界，当前可以种的边界应该是 pos + x - 1，只要保证不会超过边界即可。

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

bool check(vector<int>& pos, int x, int k) {
    int n = pos.size();
    int cnt = 0;
    int end = 0;
    for (int i = 0; i < n; i++){
        int p = pos[i] + x - 1;
        if (pos[i] > end){
            cnt += p - pos[i] + 1;
            end = p;
        } else {
            cnt += p - end;
            end = p;
        }
    }

    return cnt >= k;
}

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }

    sort(v.begin(), v.end());
    
    int l = 1, r = v.back();
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (check(v, mid, k)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }

    cout << l << endl;

    return 0;
}

小美和小团的游戏

题面

小美和小团在玩一个游戏，游戏中有一个长度为 $n$ 的数组 $a$ ，她们会玩 $q$ 轮游戏，每轮游戏都是独立的。

游戏规则如下，双方都会执行最优策略：

第一步，游戏给出一个区间 [l, r]。
第二步，小团在 [l, r] 区间中选择一个数。
第三步，小美将区间扩展为 [L, R]（[L, R] 必须包含 [l,r]），然后在 [L, R] 区间中选择一个数，但不能跟小团选择同一个数。
第四步，小美和小团选择的数字较大的一方获胜，若相同则平局。

小美想知道自她每一轮的输赢状态，并且她想知道要达到输赢状态所需的 [L,R] 区间长度最小是多少。

输入描述：
第一行输入两个整数 $n,q(2 ≤ n,q ≤ 2 × 10^5)$ ，表示数组长度和询问次数。
第二行输入 $n$ 个整数 $a(1 ≤ ai ≤ 10^9)$ ，表示数组。
接下来 $q$ 行，每行输入两个整数 $(1 ≤ l ≤ r ≤ n)$ ，表示询问。

输出描述：
对于每个询问输出一行，若小美以获胜输出 "win"，若平局则输出 "draw"，失败则输出 "lose"。
第二行输出达到最终状态所需的区间长度的最小值。

ST表 + 单调栈 + 二分

使用ST表预处理，便于后续求出 [l, r] 区间的最大值的下标。
对于每一个元素使用单调栈处理，方便求每一个元素下一个更大的元素的下标。
如果 [l, r] 的区间的最大值已经是整个数组的最大值，那么此时的判断就非常清晰：
- 最大值的数量超过 $2$ 个，那么必然是平局，我们只需要搜索距离区间最近的最大值即可。
- 否则一定是输的，此时需要特判一下，如果区间大小只有 $1$ ，那么最少需要扩大一个才可以选择。
否则，应该使用ST表找到当前区间的最大值的下标 mx_index，并且使用单调栈找到 mx_index 的下一个更大的元素/前一个更大的元素，比较哪个更接近即可。

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>
#include <climits>
using namespace std;

int n, q;
vector<int> arr;
vector<int> log;
vector<vector<int>> table;

void init() {
    log.resize(n + 1, 0);
    for (int i = 2; i <= n; ++i) {
        log[i] = log[i / 2] + 1;
    }

    table = vector<vector<int>>(n, vector<int>(log[n] + 1, 0));
    for (int i = 0; i < n; ++i) {
        table[i][0] = i;
    }

    for (int j = 1; (1 << j) <= n; ++j) {
        for (int i = 0; i <= n - (1 << j); ++i) {
            int left_idx = table[i][j - 1];
            int right_idx = table[i + (1 << (j - 1))][j - 1];
            table[i][j] = (arr[left_idx] >= arr[right_idx]) ? left_idx : right_idx;
        }
    }
}

int rmq(int l, int r) {
    int s = log[r - l + 1];
    int left_idx = table[l][s];
    int right_idx = table[r - (1 << s) + 1][s];
    return (arr[left_idx] >= arr[right_idx]) ? left_idx : right_idx;
}

int main() {
    cin >> n >> q;
    arr.resize(n);
    log.resize(n + 1, 0);
    for (int &a : arr) {
        cin >> a;
    }

    init();

    vector<int> sk;
    vector<int> rights(n, -1);
    for (int i = 0; i < n; ++i) {
        while (!sk.empty() && arr[sk.back()] <= arr[i]) {
            rights[sk.back()] = i;
            sk.pop_back();
        }
        sk.push_back(i);
    }

    sk.clear();
    vector<int> lefts(n, -1);
    for (int i = n - 1; i >= 0; --i) {
        while (!sk.empty() && arr[sk.back()] <= arr[i]) {
            lefts[sk.back()] = i;
            sk.pop_back();
        }
        sk.push_back(i);
    }

    int MAX = *max_element(arr.begin(), arr.end());
    int cnt = count(arr.begin(), arr.end(), MAX);
    vector<int> max_indexs;
    for (int i = 0; i < n; ++i) {
        if (arr[i] == MAX) {
            max_indexs.push_back(i);
        }
    }

    while (q--) {
        int l, r;
        cin >> l >> r;
        --l;
        --r;

        int mx_index = rmq(l, r);

        if (arr[mx_index] == MAX) {
            if (cnt >= 2) {
                cout << "draw" << endl;
                int left = lower_bound(max_indexs.begin(), max_indexs.end(), l) - max_indexs.begin();
                int right = upper_bound(max_indexs.begin(), max_indexs.end(), r) - max_indexs.begin() - 1;
                if (left < right) {
                    cout << r - l + 1 << endl;
                } else {
                    int ans = INT_MAX;
                    if (left > 0) {
                        ans = min(ans, max_indexs[left] - l);
                    }
                    if (right < max_indexs.size() - 1) {
                        ans = min(ans, r - max_indexs[right]);
                    }
                    cout << r - l + 1 + ans << endl;
                }
            } else {
                cout << "lose" << endl;
                cout << (l == r ? 2 : r - l + 1) << endl;
            }
        } else {
            int L = (lefts[mx_index] != -1) ? lefts[mx_index] : INT_MIN;
            int R = (rights[mx_index] != -1) ? rights[mx_index] : INT_MAX;
            cout << "win" << endl;
            cout << min(R - r, l - L) + (r - l + 1) << endl;
        }
    }

    return 0;
}

美团笔试 - 0831

美团笔试 - 0831

小美的姓名统计

小美种树

小美和小团的游戏