001 - 美团2024年春招第一场笔试

避免笔试/面试算法题挂，决定刷题，还是太菜了。。。

题目链接：https://www.nowcoder.com/exam/test/55750560/summary

标※的是没有独立思考出来的。。。

编程题

小美的MT

首先统计长度为n的字符串中，M和T的出现的次数cnt。然后我们可以修改min(n - cnt, k)个字符，让M和T出现的次数最多。答案就是cnt + min(n - cnt, k) = min(n, cnt + k)。

参考代码如下：

#include <iostream>
#include <string>
using namespace std;

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

    string str;
    cin >> str;

    int cnt = 0;
    for (auto ch : str)
        if (ch == 'M' || ch == 'T')
            cnt++;

    cout << cnt + min(n - cnt, k);
}

小美的数组询问

在输入数据的同时，记录数组所有元素和sum，以及0的个数cnt。然后在询问过程中，最小值就是sum + l * cnt，最大值就是sum + r * cnt。

参考代码如下：

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

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

    vector<int> a(n);
    long long sum = 0, cnt = 0;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        if (a[i])
            sum += a[i];
        else
            cnt ++;
    }

    while (q--)
    {
        int l, r;
        cin >> l >> r;
        cout << sum + l * cnt << " " << sum + r * cnt << '\n';
    }
}

小美的平衡矩阵

数据范围比较小，可以暴力枚举每个矩形，如果它1的数量刚好是矩阵元素的一半，那么它就是一个完美矩形。可以用二维前缀和加速计算。

参考代码如下：

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

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

    // 求二维前缀和, 注意输入
    vector<vector<int>> mat(n + 5, vector<int>(n + 5)), s(mat);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
        {
            char ch;
            cin >> ch;
            mat[i][j] = ch - '0';
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + mat[i][j];
        }

    // 枚举矩阵左上角的点, 求矩阵内1的个数: (i,j) ~ (i + len - 1, j + len - 1)的前缀和
    for (int len = 1; len <= n; ++len)
    {
        if (len % 2)
        {
            cout << 0 << '\n';
            continue;
        }

        int ans = 0;
        for (int i = 1; i <= n - len + 1; ++i)
            for (int j = 1; j <= n - len + 1; ++j)
            {
                int x2 = i + len - 1, y2 = j + len - 1;
                int sum = s[x2][y2] - s[x2][j - 1] - s[i - 1][y2] + s[i - 1][j - 1];
                if (sum * 2 == len * len)
                    ans++;
            } 
        cout << ans << '\n';
    }
}

※小美的朋友关系

由于并查集仅支持插入关系而不能删除已有的关系，因此要进行“删除”的话得反向思考。先遍历所有关系和事件，提取出所有事件结果后仍保持的关系，将它们加入并查集中。然后逆序遍历事件，正序时遇到的“删除”事件相当于逆序下的“添加”，因此碰到删除时进行添加操作即可。

参考代码如下：

#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

struct UF
{
    // 题给范围n太大, 用map存储
    map<int, int> pa;

    int find(int a)
    {
        if (pa[a] != a)
            pa[a] = find(pa[a]);
        return pa[a];
    }

    bool isConnect(int a, int b)
    {
        return find(a) == find(b);
    }

    void add(int x, int y)
    {
        pa[find(x)] = find(y);
    }
};

int main() {
    int n, m, q;
    cin >> n >> m >> q;

    // 存储关系
    UF uf;
    set<pair<int, int>> relations;
    while (m --)
    {
        int a, b;
        cin >> a >> b;

        // 初始化
        uf.pa[a] = a;
        uf.pa[b] = b;

        if (a > b)
            swap(a, b);
        relations.insert({a, b});
    }

    // 存储事件并维护关系
    vector<vector<int>> acts;
    while (q --)
    {
        int op, a, b;
        cin >> op >> a >> b;

        // 初始化
        uf.pa[a] = a;
        uf.pa[b] = b;

        if (a > b)
            swap(a, b);      
        // 删除操作, 合法就删除, 不合法就跳过
        if (op == 1)
        {
            if (relations.find({a, b}) != relations.end())
                relations.erase({a, b});
            else
                continue;
        }

        vector<int> tmp = {op, a, b};
        acts.emplace_back(tmp);
    }

    // 用剩余的关系建立并查集
    for (auto& [a, b] : relations)
        uf.add(a, b);
    
    // 逆向遍历事件
    reverse(acts.begin(), acts.end());
    stack<string> ans;
    for (auto& act : acts)
    {
        int op = act[0], a = act[1], b = act[2];
        if (op == 1)
            uf.add(a, b);
        else
        {
            if (uf.isConnect(a, b))
                ans.push("Yes");
            else
                ans.push("No");
        }
    }

    // 输出答案
    while (!ans.empty())
    {
        cout << ans.top() << '\n';
        ans.pop();
    }
}

※小美的区间删除

首先分析乘积末尾0的个数：

• 只要乘数的因子含有2和5，那乘积末尾必然是0。例如$5\times6=5\times2\times3=30$。因此要求乘积末尾0的个数，只需求乘积中$5,2$因子对的数量就行了。
• 为了快速得到数组一段元素中5和2的因子个数，可以使用 前缀和 预处理出区间中因子2和因子5的个数。那么当删掉区间$[l,r]$后，剩下因子2/因子5的个数为$S_n-(S_r-S_{l-1})$。

然后是删除区间的方案数问题：

• 假设要删除区间$[l, r]$，那么最多可以删除$len=r-l$个元素：

  • 删除1个元素，有$len$种方案；
  • 删除2个元素，有$len-1$种方案
  • ...
  • 删除$len$个元素，有1种方案。

• 那么总方案数为：$\frac{len\times(1+len)}{2}$，（1~len的和）。

最后就剩下如何求可删除的最长区间，让数组剩余元素乘积末尾0的个数至少为k的问题了：

• 利用滑动窗口（双指针），固定左边界$l$，让右边界$r$移动，直到删除$[l,r]$后，乘积末尾0的个数小于k。此时$[l,r-1]$就是要删除的区间。
• 删除区间后，让$l$向右移动，直到到达右边界$r$或乘积末尾0的个数大于等于k时停止移动，然后$r$继续向右移动。
• 有时候会发生重复删除的现象，例如删除区间$[1,3]$，$[2,4]$时重复删除了区间$[2,3]$，因此要减一次此区间的方案数。

此外，需要注意这里1起点和long long问题。

参考代码如下：

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

int getCount(const vector<int>& s2, const vector<int>& s5, int l, int r, int n)
{
    int sum2 = s2[n] - s2[r] + s2[l - 1];
    int sum5 = s5[n] - s5[r] + s5[l - 1];
    return min(sum2, sum5);
}

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

    vector<int> s2(n + 1, 0), s5(n + 1, 0);
    for (int i = 1; i <= n; ++i)
    {
        int a;
        cin >> a;

        while (a % 2 == 0)
        {
            a /= 2;
            s2[i]++;
        }
        while (a % 5 == 0)
        {
            a /= 5;
            s5[i]++;
        }
        
        s2[i] += s2[i - 1];
        s5[i] += s5[i - 1];
    }

    long long ans = 0;
    int lastR = 0;
    for (int left = 1, right = 1; right <= n;)
    {
        right = max(left, right);
        while (right <= n && getCount(s2, s5, left, right, n) >= k)
            ++right;

        int len = right - left;
        ans += static_cast<long long>(len) * (1 + len) / 2;
        if (left <= lastR)
        {
            len = lastR - left;
            ans -= static_cast<long long>(len) * (1 + len) / 2;
        }
        lastR = right;

        while (left <= right && getCount(s2, s5, left, right, n) < k)
            ++left;
    }

    cout << ans;
}

参考资料

【刷题节】美团2024年春招第一场笔试【算法策略】题解_小美的朋友关系美团-CSDN博客