Home 校招 美团

# 美团 2024 年春招第一场笔试【算法策略】（实习）

本来早就想记录一下了，但是笔试的时候没有把题目和代码保存下来！今天 (2024-03-10) 在小红书看到了笔试题，于是乎打算重新写一遍。整体来说，对我而言感觉难度中等偏上一点。第五题没有得到全部分数，没有把正向删边等加成逆向加边

# Q1 easy

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#define rint register int
#define ull unsigned long long
using namespace std;
using ll = long long;
constexpr int N = 1e5 + 10;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, k;   cin >> n >> k;
    string s;   cin >> s;
    int cnt = 0;
    for(int i = 0; i < n; i ++ )    cnt += (s[i] == 'M' || s[i] == 'T');
    cout << min(cnt + k, n) << endl;
    return 0;
}
  • 时间复杂度:O(n)时间复杂度:O(n)
  • 空间复杂度:O(1)空间复杂度:O(1)

# Q2 easy

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#define rint register int
#define ull unsigned long long
using namespace std;
using ll = long long;
constexpr int N = 1e5 + 10;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, q;   cin >> n >> q;
    ll sum = 0, cnt0 = 0;
    for(int i = 0; i < n; i ++ ){
        ll tp;  cin >> tp;
        cnt0 += (tp == 0);
        sum += tp; 
    }
    while(q -- ){
        ll l, r;    cin >> l >> r;
        cout << sum + cnt0 * l << ' ' << sum + cnt0 * r << endl;
    }
    return 0;
}
  • 时间复杂度:O(n+q)时间复杂度:O(n + q)
  • 空间复杂度:O(1)空间复杂度:O(1)

# Q3 easy

/*
	枚举 + 二维前缀和
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#define rint register int
#define ull unsigned long long
using namespace std;
using ll = long long;
constexpr int N = 210;
int sum[N][N];
int get(int x1, int y1, int x2, int y2){
    return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;  cin >> n;
    for(int i = 1; i <= n; i ++ ){
        string tp;  cin >> tp;
        for(int j = 0; j < n; j ++ )    sum[i][j + 1] = (tp[j] == '1');
    }
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= n; j ++ )   sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
    }
    vector<int> res(n + 1, 0);
    for(int k = 1; k <= n; k ++ ){
        for(int x1 = 1; x1 <= n; x1 ++ ){
            for(int y1 = 1; y1 <= n; y1 ++ ){
                int x2 = x1 + k - 1;
                int y2 = y1 + k - 1;
                if(x2 > n || y2 > n)    break;
                int cnt1 = get(x1, y1, x2, y2);
                int cnt0 = k * k - cnt1;
                res[k] += (cnt0 == cnt1);
            }
        }
    }
    for(int i = 1; i <= n; i ++ )   cout << res[i] << endl;
    return 0;
}
  • 时间复杂度:O(n3)时间复杂度:O(n^{3})
  • 空间复杂度:O(n2)空间复杂度: O(n^{2})

# Q4 medium

/*
	方法一：前缀和 + 二分
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#define rint register int
#define ull unsigned long long
using namespace std;
using ll = long long;
constexpr int N = 1e5 + 10;
typedef pair<int, int> pii;
int sum2[N], sum5[N];
pii decompose(int x){
    pii cur = {0, 0};
    while(x % 2 == 0){
        cur.first ++ ;
        x /= 2;
    }
    while(x % 5 == 0){
        cur.second ++ ;
        x /= 5;
    }
    return cur;
}
int deal2(int index, int del){
    if(sum2[index] <= del)  return 0;
    int aim = sum2[index] - del;
    int l = 1, r = index;
    while(l < r){
        int mid = l + r >> 1;
        if(sum2[mid] >= aim)    r = mid;
        else    l = mid + 1;
    }
    return l;
}
int deal5(int index, int del){
    if(sum5[index] <= del)  return 0;
    int aim = sum5[index] - del;
    int l = 1, r = index;
    while(l < r){
        int mid = l + r >> 1;
        if(sum5[mid] >= aim)    r = mid;
        else    l = mid + 1;
    }
    return l;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, k;   cin >> n >> k;
    for(int i = 1; i <= n; i ++ ){
        int tp; cin >> tp;
        pii cur = decompose(tp);
        sum2[i] = sum2[i - 1] + cur.first;
        sum5[i] = sum5[i - 1] + cur.second;
    }
    int del2 = sum2[n] - k, del5 = sum5[n] - k;
    ll cnt = 0;
    for(int i = 1; i <= n; i ++ ){
        int index2 = deal2(i, del2);
        int index5 = deal5(i, del5);
        cnt = cnt + i - max(index2, index5);
    }
    cout << cnt << endl;
    return 0;
}
  • 时间复杂度:O(nlogn)时间复杂度:O(nlogn)
  • 空间复杂度:O(n)空间复杂度:O(n)
/*
	方法二：前缀和 + 哈希表
*/
  • 时间复杂度:O(n)时间复杂度:O(n)
  • 空间复杂度:O(n)空间复杂度:O(n)
/*
	方法三：双指针
*/
  • 时间复杂度:O(n)时间复杂度:O(n)
  • 空间复杂度:O(1)空间复杂度:O(1)

# Q5 hard

逆向思维，一眼并查集；但是并查集无法删除关系.

考虑重边

/*
	离散化 + 并查集（逆向）
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#define rint register int
#define ull unsigned long long
using namespace std;
using ll = long long;
constexpr int N = 1e5 + 10;
typedef pair<int, int> pii;
pii relation[N];
struct Node{
    int op;
    int u, v;
}query[N];
int p[N * 3];
unordered_map<int, int> mp;
int getHash(int x){
    return mp[x];
}
int find(int x){
    if(p[x] == x)   return x;
    return p[x] = find(p[x]);
}
void add(int x, int y){
    int px = find(getHash(x));
    int py = find(getHash(y));
    if(px == py)    return ;
    p[px] = py;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m, q;    cin >> n >> m >> q;
    set<int> S;
    for(int i = 0; i < m; i ++ ){
        int u, v;   cin >> u >> v;
        S.insert(u), S.insert(v);
        relation[i] = {min(u, v), max(u, v)};
    }
    map<pii, int> del;
    for(int i = 0; i < q; i ++ ){
        int op, u, v;   cin >> op >> u >> v;
        query[i] = {op, u, v};
        S.insert(u), S.insert(v);
        if(op == 1)  del[{min(u, v), max(u, v)}] ++ ;  
    }
    int idx = 1;
    for(auto &x : S)    mp[x] = idx ++ ;
    for(int i = 0; i <= idx; i ++ ) p[i] = i;
    for(int i = 0; i < m; i ++ ){
        if(del.find(relation[i]) == del.end())  add(relation[i].first, relation[i].second);
    }
    vector<int> res;
    for(int i = q - 1; i >= 0; i -- ){
        if(query[i].op == 2){
            int px = find(getHash(query[i].u));
            int py = find(getHash(query[i].v));
            res.push_back(px == py);
        }else{
            if(del[{query[i].u, query[i].v}] == 1){
                del.erase({query[i].u, query[i].v});
                add(query[i].u, query[i].v);
            }else   del[{query[i].u, query[i].v}] -- ;
        }
    }
    reverse(res.begin(), res.end());
    for(auto &x : res)  cout << (x ? "Yes" : "No") << endl;
    return 0;
}
/*
    5 3 5
    1 2 
    2 3
    4 5
    1 1 5
    2 1 3
    2 1 4
    1 1 2
    2 1 3
 */
  • 时间复杂度:O(max(n,q)log(max(n,q)))时间复杂度:O(max(n,q)log(max(n,q)))
  • 空间复杂度:O(n+q)空间复杂度:O(n+q)

# 美团 2024 年春招第二场笔试【算法策略】（实习）

2024-03-16 场的，这场没有参加。在网上找了原题，试着做一下

# Q1 easy

题目描述

小美是美团外卖的忠实用户，她经常去美团外卖 app 上面点外卖，因为会员红包的性价比太高。现在小美点了若干道菜，她希望你计算一个订单的总价。你能帮帮她吗？

输入描述

第一行输入一个正整数 n，代表菜品总数。 第二行输入 n 个正整数aia_{i}，代表每道菜的价格。 第三行输入两个正整数 x 和 y，x 代表满减的价格，y 代表红包的价格。

输出描述

一个正整数，代表小美最终应付的钱数。

样例

输入

4
10 20 10 20
25 10

输出

25

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#define rint register int
#define ull unsigned long long
using namespace std;
using ll = long long;
constexpr int N = 1e5 + 10;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;  cin >> n;
    int sum = 0;
    for(int i = 0; i < n; i ++ ){
        int tp; cin >> tp;
        sum += tp;
    }
    int x, y;   cin >> x >> y;
    cout << sum - x - y << endl;
    return 0;
}

# Q2 easy

题目描述

小美定义以下三种单词是合法的:

1. 所有字母都是小写。例如:good

2. 所有字母都是大写。例如：APP

3. 第一个字母大写，后面所有字母都是小写。例如：Alice

现在小美拿到了一个单词，她每次操作可以修改任意一个字符的大小写。小美想知道最少操作几次可以使得单词变成合法的？

输入描述

一个仅由大写字母和小写字母组成的字符串，长度不超过10^

输出描述

一个整数，代表操作的最小次数。

样例

输入

AbC

输出

1

说明

变成 ABC 或者 Abc 均可。只需要 1 次操作。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#define rint register int
#define ull unsigned long long
using namespace std;
using ll = long long;
constexpr int N = 1e5 + 10;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    string s;   cin >> s;
    int minv = s.size();
    int cnt1 = 0;
    for(auto &c : s)    cnt1 += (c >= 'a' && c <= 'z');
    minv = min(minv, (int)s.size() - cnt1);
    int cnt2 = 0;
    for(auto &c : s)    cnt2 += (c >= 'A' && c <= 'Z');
    minv = min(minv, (int)s.size() - cnt2);
    int cnt3 = !(s[0] >= 'A' && s[0] <= 'Z');
    for(int i = 1; i < s.size(); i ++ ) cnt3 += (s[i] >= 'A' && s[i] <= 'Z');
    minv = min(minv, cnt3);
    cout << minv << endl;
    return 0;
}

# Q3 medium

题目描述

小美拿到了一个数组，她每次操作会将除了第xx 个元素的其余元素翻倍，一共操作了qq 次。请你帮小美计算操作结束后所有元素之和。 由于答案过大，请对109+710^{9}+7 取模。

输入描述

第一行输入两个正整数nn 和qq，代表数组的大小和操作次数。
第二行输入nn 个正整数aia_{i}，代表数组的元素。
接下来的qq 行，每行输入一个正整数xix_{i}，代表第ii 次操作未被翻倍的元素。
1≤n,q≤1051 \leq n,q \leq 10^{5}
1≤ai≤1091 \leq a_{i} \leq 10^{9}
1≤xi≤n1 \leq x_{i} \leq n

输出描述

一个整数，代表操作结束后所有元素之和模109+710^{9}+7 的值。

样例

输入

4 2
1 2 3 4
1
2

输出

34

/*
	快速幂 + 反向记录
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#define rint register int
#define ull unsigned long long
using namespace std;
using ll = long long;
constexpr int N = 1e5 + 10, MOD = 1E9 + 7;
ll qmi(ll a, ll b, ll q){
    ll res = 1;
    while(b){
        if(b & 1)   res = res * a % q;
        b >>= 1;
        a = a * a % q;
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, q;   cin >> n >> q;
    vector<int> tp(n);
    for(int i = 0; i < n; i ++ )    cin >> tp[i];
    vector<int> cnt(n, 0);
    for(int i = 0; i < q; i ++ ){
        int index;  cin >> index;
        index -- ;
        cnt[index] ++ ;
    }
    ll sum = 0;
    for(int i = 0; i < n; i ++ )    sum = (sum + tp[i] * qmi(2, q - cnt[i], MOD) % MOD) % MOD;
    cout << sum << endl;
    return 0;
}

# Q4 medium

题目描述

小美拿到了一个数组，她希里你求出所有区间众数之和，你能帮帮她吗？

定义区间的众数为出现次数最多的那个数，如果有多个数出现次数最多，那么众数是其中最小的那个数。

输入描述

第一行输入一个正整数nn，代表数组的大小
第二行输入nn 个正整数aia_{i}, 代表数组的元素
1≤n≤2×1051 \leq n \leq 2×10^{5}
1≤ai≤21 \leq a_{i} \leq 2

输出描述

一个正整数，代表所有区间的众数之和。

样例

输入

3
2 1 2

输出

9

说明

[2],[2,1,2],[2] 的众数是 2.
[2,1],[1],[1,2] 的众数是 1.
因此答案是 9.

/*
	树状数组
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#define rint register int
#define ull unsigned long long
using namespace std;
using ll = long long;
constexpr int N = 2e5 + 10;
ll tr[N * 2];
int lowbit(int x){
    return x & -x;
}
ll query(int index){
    index += 1e5 + 10;
    ll sum = 0;
    for(int i = index; i; i -= lowbit(i))   sum += tr[i];
    return sum;
}
void add(int index, ll c){
    index += 1e5 + 10;
    for(int i = index; i < N; i += lowbit(i))   tr[i] += c;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;  cin >> n;
    ll res = 0;
    int cnt1 = 0, cnt2 = 0;
    add(0, 1);
    for(int i = 0; i < n; i ++ ){
        int tp; cin >> tp;
        cnt1 += (tp == 1), cnt2 += (tp == 2);
        int diff = cnt1 - cnt2;
        ll x = query(diff);
        res = res + x + (i + 1 - x) * 2;
        add(cnt1 - cnt2, 1);
        cout << i << ' ' << x << ' ' << res << endl;
    }   
    cout << res << endl;
    return 0;
}

# Q5 medium

题目描述

小美拿到了一个排列，她定义f(i)f(i) 为：将第ii 个元素取反后，形成的数组的逆序对数量。小美希望你求出f(1)f(1) 到f(n)f(n) 的值。排列是指一个长度为nn 的数组，1 到nn 每个元素恰好出现了一次。

输入描述

第一行输入一个正整数nn，代表排列的大小
第二行输入nn 个正整数aia_{i}，代表排列的元素。
1≤n≤2×1051 \leq n \leq 2×10^{5}
1≤ai≤n1 \leq a_{i} \leq n

输出描述

输出nn 个整数，第ii 个整数是f(i)f(i) 的值。

样例

输入

3
1 2 3

输出

0 1 2

说明

第一个元素取反，数组将变成 [-1,2,3]，逆序对数量为 0.
第二个元素取反，数组将变成 [1,-2,3]，逆序对数量为 1.
第三个元素取反，数组将变成 [1,2,-3]，逆序对数量为 2.

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#define rint register int
#define ull unsigned long long
using namespace std;
using ll = long long;
constexpr int N = 2e5 + 10;
ll tr[N];
int lowbit(int x){
    return x & -x;
}
ll query(int index){
    ll sum = 0;
    for(int i = index; i; i -= lowbit(i))   sum += tr[i];
    return sum;
}
void add(int index, ll c){
    for(int i = index; i < N; i += lowbit(i))   tr[i] += c;
}
ll a[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;  cin >> n;
    for(int i = 1; i <= n; i ++ )   cin >> a[i];
    vector<ll> pre(n, 0);
    for(int i = 1; i <= n; i ++ ){
        pre[i] = (i - 1) - query(a[i]);
        add(a[i], 1);
    }
    ll sum = accumulate(pre.begin(), pre.end(), 0);
    for(int i = 1; i <= n; i ++ )   cout << sum - pre[i] + (i - 1) << ' ';
    cout << endl;
    return 0;
}

# 美团秋招（8.11 第一场笔试）

# K 小姐的偶数因子探秘

题目表述

K 小姐对数字的因子充满了好奇，尤其是偶数因子。她想知道，对于给定的正整数xx，是否存在至少一个偶数因子（不包括 11 和 xx 本身）。请帮助 K 小姐解答这个问题。

输入描述

第一行输入一个整数 TT，表示询问的次数 (1≤T≤105)(1≤T≤10^5)。
接下来 TT 行，每行输入一个整数 xx，表示 K 小姐询问的正整数 (1≤x≤109)(1≤x≤10^9)。

输出格式

对于每次询问，如果 xx 存在至少一个偶数因子，输出 "YES"；否则输出 "NO"。

样例

输入

2
1
4

输出

NO
YES

数据范围

  • 1≤T≤1051≤T≤10^5
  • 1≤x≤1091≤x≤10^9

题解

要判断一个整数 xx 是否存在至少一个偶数因子，可以利用以下性质：如果 xx 是偶数且大于 2，那么 xx 至少有一个偶数因子 2。如果 xxx 是奇数或者等于 222，则没有符合条件的偶数因子。

  1. 如果 xxx 是偶数并且大于 222，则输出 "YES"。
  2. 否则，输出 "NO"。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#define rint register int
#define ull unsigned long long
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
using ll = long long;
constexpr int N = 1e5 + 10;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T;  cin >> T;
    while(T -- ){
        int x;  cin >> x;
        cout << ((x % 2 == 0 && x > 2) ? "YES" : "NO") << endl;
    }
    return 0;
}
Edited on Views times

Give me a cup of [coffee]~(￣▽￣)~*

Value WeChat Pay

WeChat Pay