美团2024届秋招第七场笔试9.23【技术】

转开发后的第一场笔试，100 100 100 100 90

1、一个遍历即可

2、模拟时钟，实现进位和借位即可，注意要开long long和输出前导0

3、数学推导，用到了等差数列求和、平方和公式，以及乘法逆元

4、个人做法是直接枚举，首先枚举两个数值a、b，然后在序列中轮流选取a与b，时间复杂度是O(n^3)

其实可以优化选数的过程，只需要先用桶存一下，即维护每个数值出现的位置，然后控制双指针在桶里移动即可

由于每个数在桶里只会出现一次，因此是均摊复杂度O(n^2 + n)

5、只做了暴力，感觉可以枚举每个素因子，然后区间线段树，复杂度O(q * sqrt(n) * log(n))？

附第四题AC代码

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

map<int, vector<int> >h;

int count(vector<int>a, vector<int>b)
{
    int sz1=a.size(), sz2=b.size();
    int l=0,r=0;
    int now=0, ret=0;
    while(true)
    {
        while(l<sz1 && a[l] <= now) l++;
        if(l<sz1)
            now = a[l];
        else
            break;
        ret++;
        while(r<sz2 && b[r] <= now) r++;
        if(r<sz2)
            now = b[r];
        else
            break;
        ret++;
    }
    return ret;
}
int main() {
    int n;
    cin>>n;
    int ai;
    for(int i=1;i<=n;i++) {
        cin >> ai;
        h[ai].push_back(i);
    }
    int ans=0;
    for(auto it1=h.begin(); it1!=h.end(); ++it1)
        for(auto it2=h.begin(); it2!=h.end(); ++it2)
        {
            auto l1 = it1->second;
            auto l2 = it2->second;
            ans = max(ans, count(l1, l2));
        }
    cout<<ans;
    return 0;
}