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，需要先做离散化。其次是会出现一些不在离散化列表里的数据，和一些无意义的非法操作，需要针对性的特判，这里卡了我挺长时间）

240309 美团春招笔试代码-ak

全站热榜