240309 美团春招笔试代码-ak

很久不做题了，可能上次笔试还是去年10月的事情了。题目总的来说还是挺正常的，就是题面写的不太好，最后一题很多边界情况没解释清楚，需要自己推理尝试。写了一个小时ak了就交了，实习，秋招，春招三次笔试好像都是一个小时做完的。

int main(){
    int _t = 1;
//    cin>>_t;
    while(_t--) {
        int n,k;cin>>n>>k;
        string s;cin>>s;
        int left = 0;
        for(auto &c:s){
            left += c!='M' && c!='T';
        }
        left -= min(left,k);
        cout<<s.size() - left<<endl;
    }
    return 0;
}

int main(){
    int _t = 1;
//    cin>>_t;
    while(_t--) {
        int n,q;cin>>n>>q;
        int cnt = 0;
        for(int i = 1;i<=n;i++)scanf("%d",&a[i]),cnt+=a[i] == 0;
        ll summ = accumulate(a+1,a+1+n,0LL);
        while(q--){
            ll l,r;scanf("%lld %lld",&l,&r);
            cout<<summ + l * cnt <<" "<<summ + r *cnt<<endl;
        }
    }

    return 0;
}

知识点考的是二维前缀和，真的是好久没写过。因为求的是一个正方形的01数量，所以复杂度是nnn的。

int main(){
    int _t = 1;
//    cin>>_t;
    while(_t--) {
        memset(arr,0,sizeof arr);
        int n;cin>>n;
        int res = 0;
        map<int,int> m;
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=n;j++){
                char c;cin>>c;
                arr[i][j] = c-'0';
                arr[i][j] += arr[i][j-1] + arr[i-1][j] - arr[i-1][j-1];
                for(int len = 1;len<=min(i,j);len++){
                    int cnt = arr[i][j] - arr[i][j - len] - arr[i-len][j]+arr[i-len][j-len];
                    if(cnt * 2 == len * len)m[len]++;
                }
            }
        }
        for(int i = 1;i<=n;i++){
            cout<<m[i]<<endl;
        }
    }

    return 0;
}

老结论了，0的数量由2/5的数量共同决定。所以删除一个区间后，剩下的0的数量可以由2，5数量的最小值确定。我们先求整体的2，5数量。然后用双指针去更新，对于每一个i，找到其左边的合理的最左边的j，使得删除从j到i之间都能使得0的数量足够。

int main(){
    int _t = 1;
//    cin>>_t;
    while(_t--) {
        int n,k;cin>>n>>k;
        for(int i = 1;i<=n;i++)scanf("%d",&a[i]);
        vector<pii> v;
        v.push_back({0,0});
        int c2tt = 0,c5tt = 0;
        for(int i = 1;i<=n;i++){
            int ac = 0,bc = 0;
            int u = a[i];
            while((u%2)==0){
                ac++;
                u/=2;
            }
            while((u%5)==0){
                bc++;
                u/=5;
            }
            v.push_back({ac,bc});
            c2tt += ac,c5tt += bc;
        }
        int c2 = 0,c5 = 0;
        int j = 1;
        ll res = 0;
        for(int i = 1;i<=n;i++){
            c2 += v[i].first,c5+=v[i].second;
            while(j<=i && min(c2tt-c2,c5tt-c5)<k){
                c2-=v[j].first,c5-=v[j].second;
                j++;
            }
            res += max(i-j+1,0);
        }
        cout<<res<<endl;
    }

    return 0;
}

正难则反，因为传统并查集不支持删除操作（是有这么个数据结构，但是我不会），倒序把删除操作变成添加边的操作。然后正常查询是否连接，最后将结果倒序输出。（其实思路还是挺简单的，就是一个是序号是1-1e9，需要先做离散化。其次是会出现一些不在离散化列表里的数据，和一些无意义的非法操作，需要针对性的特判，这里卡了我挺长时间）

#include<iostream>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <cmath>
#include <list>
#include <functional>
#include <algorithm>
#include <memory>
#include <numeric>
#include <unordered_set>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
int a[200010];
int p[200010];
int find(int x){
    if(p[x]!=x){
        p[x] = find(p[x]);
    }
    return p[x];
}

int main(){
    int _t = 1;
//    cin>>_t;
    while(_t--) {

        int n,m,q;cin>>n>>m>>q;
        unordered_map<int,unordered_set<int>> gra;
        unordered_map<int,unordered_set<int>> old_gra;
        int id = 1;
        iota(p+1,p+1+200000,1);
        unordered_map<int,int> map_person;
        for(int i = 1;i<=m;i++){
            int u,v;scanf("%d %d",&u,&v);
            if(!map_person.count(u))map_person[u] = id++;
            if(!map_person.count(v))map_person[v] = id++;
            gra[map_person[u]].insert(map_person[v]);
            gra[map_person[v]].insert(map_person[u]);
            old_gra[map_person[u]].insert(map_person[v]);
            old_gra[map_person[v]].insert(map_person[u]);
        }
        vector<vector<int>> actions;

        for(int i = 1;i<=q;i++){
            int ty,u,v;scanf("%d %d %d",&ty,&u,&v);
            actions.push_back({ty,u,v});
            if(ty==1){
                if(map_person.count(u) && map_person.count(v)) {
                    if (old_gra[map_person[u]].count(map_person[v])) {
                        gra[map_person[u]].erase(map_person[v]);
                        gra[map_person[v]].erase(map_person[u]);
                    }
                }
            }
        }

        for(auto &[u,gu]:gra){
            for(auto &v:gu){
                p[find(u)] = find(v);
            }
        }
        vector<string> res;
        for(int i = actions.size()-1;i>=0;i--){
            int ty = actions[i][0],u = actions[i][1],v = actions[i][2];
            if(ty == 2){
                if(map_person.count(u) && map_person.count(v)){
                    int mu = map_person[u],mv = map_person[v];
                    if(find(mu) == find(mv)){
                        res.push_back("Yes");
                    }
                    else res.push_back("No");
                }else{
                    res.push_back("No");
                }
            }
            else{
                if(map_person.count(u) && map_person.count(v)){
                    int mu = map_person[u],mv = map_person[v];
                    if(old_gra[mu].count(mv)){
                        p[find(mu)] = find(mv);
                    }
                }
            }
        }

        for(int i = res.size()-1;i>=0;i--){
            cout<<res[i]<<endl;
        }

    }

    return 0;
}