2024年美团春招技术岗第一批笔试

#include<bits/stdc++.h>
using namespace std;
const int N=220;
int a[N][N],s[N][N];
signed main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            char c;
            cin>>c;
            int x=c-'0';
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+x;
        }
    }
    for(int sz=1;sz<=n;sz++){
        int ans=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                int L=i-sz,R=j-sz;
                if(L<0||R<0)continue;
                int x=s[i][j]-s[i][R]-s[L][j]+s[L][R];
                int sum=sz*sz;
                if(x==sum-x)ans++;
            }
        }
        cout<<ans<<'\n';
    }
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int a[N],n,q,sum,cnt0;
signed main() {
    cin>>n>>q;
    for(int i=1,x;i<=n;i++){
        cin>>x;
        sum+=x;
        if(x==0)cnt0++;
    }
    while(q--){
        int l,r,maxx=0,minn=0;
        cin>>l>>r;
        maxx=sum+r*cnt0;
        minn=sum+l*cnt0;
        cout<<minn<<" "<<maxx<<'\n';
    }
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int a,b,c,n,k;
signed main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        char c;
        cin>>c;
        if(c=='M')a++;
        else if(c=='T')b++;
        else c++;
    }
    int ans=(a+b+k);
    cout<<min(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;
        // 使用set和强制规定a < 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();
    }
}v

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int n,k,a[N],b[N],ans;
int check(int l,int r){
    int A=a[l-1]+a[n]-a[r];
    int B=b[l-1]+b[n]-b[r];
    // cout<<"L="<<l<<" R="<<r<<" A="<<A<<" B="<<B<<endl;
    return min(A,B)>=k;
}
signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        while(x%5==0)a[i]++,x/=5;
        // cout<<" a["<<i<<"]="<<a[i];
        a[i]+=a[i-1];
        while(x%2==0)b[i]++,x/=2;
        // cout<<" b["<<i<<"]="<<b[i];
        b[i]+=b[i-1];
    }
    for(int i=1;i<=n;i++){
        int l=i,r=n;
        while(l<r){
            int mid=(l+r+1)/2;
            if(check(i,mid))l=mid;
            else r=mid-1;
        }
        // cout<<" i="<<i<<" l="<<l<<endl;
        if(check(i,l))ans+=l-i+1;
    }
    cout<<ans;
}