美团算法笔试

挺难的，感觉比上周难☹️，8 选择 + 4 编程，120 分钟。T1 签到，T2 是 sklearn 大题跳过了，T3 折半搜索经典套路，T4 笛卡尔树分治有点东西。

选择题：RAG 文档更新后检索旧内容的原因、SVM 模型压缩方法、迁移学习微调策略、CV 预训练任务选择、GBDT 特性、二分查找比较次数、度为4的树求叶结点数

T1. 风不吹雨

每个位置可以做操作1（除以2取整，最多 次总共）和操作2（减 ，最多 次总共），求最小总和。

两种操作的收益是独立的：操作1的收益是 （不管有没有做操作2），操作2的收益恒为 （不管有没有做操作1）。所以直接贪心：操作1选收益最大的 个位置，操作2随便选 个位置（收益都是 ）。

（顺带一提，两种操作同时做的时候，先做操作1再做操作2更优，因为先砍半再减 比先减 再砍半少得更多。不过因为收益可分离，这个细节不影响最终答案。）

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int _;cin>>_;
    while(_--){
        int n,ca,cb,k,i;
        cin>>n>>ca>>cb>>k;
        int s=0;
        vector<int>sv(n);
        for(i=0;i<n;i++){
            int x;cin>>x;
            s+=x;
            sv[i]=(x+1)/2;
        }
        sort(sv.rbegin(),sv.rend());
        int s1=0;
        for(i=0;i<min(ca,n);i++)s1+=sv[i];
        cout<<s-s1-min(cb,n)*k<<"\n";
    }
}

T2. SVM异常检测

参考代码：

import numpy as np
import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.svm import OneClassSVM
from sklearn.metrics import roc_auc_score, f1_score

def solve(train_data, test_data, gamma_list, nu_list):
    X = train_data.drop(columns=['y'])
    y = train_data['y']

    # Step 1: 数据拆分
    X_normal = X[y == 0]
    X_anomaly = X[y == 1]
    X_tr, X_val_norm = train_test_split(X_normal, test_size=0.25, random_state=42, shuffle=True)
    X_val_anom = X_anomaly

    # Step 2: 标准化（只用 X_tr 估计 mean/std）
    mean = X_tr.mean(axis=0)
    std = X_tr.std(axis=0)
    std[std == 0] = 1
    X_tr_s = (X_tr - mean) / std
    X_val_norm_s = (X_val_norm - mean) / std
    X_val_anom_s = (X_val_anom - mean) / std

    X_val = pd.concat([X_val_norm_s, X_val_anom_s])
    y_val = np.array([0]*len(X_val_norm_s) + [1]*len(X_val_anom_s))

    # Step 3-4: 网格搜索 + 评估
    results = []
    for gamma in gamma_list:
        for nu in nu_list:
            model = OneClassSVM(kernel="rbf", gamma=gamma, nu=nu,
                                shrinking=False, tol=1e-4, cache_size=200, max_iter=-1)
            model.fit(X_tr_s)

            scores = -model.decision_function(X_val)  # 取负！
            auc = roc_auc_score(y_val, scores)

            preds = model.predict(X_val)
            y_pred = (preds == -1).astype(int)  # -1→异常(1), +1→正常(0)
            f1 = f1_score(y_val, y_pred)

            results.append({'gamma': gamma, 'nu': nu, 'auc': auc, 'f1': f1})

    # Step 5: 选最优（AUC降序 → F1降序 → nu升序 → gamma升序）
    results.sort(key=lambda x: (-x['auc'], -x['f1'], x['nu'], x['gamma']))
    best = results[0]

    # Step 6: 全量正常数据重训 + 预测
    X_full = pd.concat([X_tr_s, X_val_norm_s])
    best_model = OneClassSVM(kernel="rbf", gamma=best['gamma'], nu=best['nu'],
                              shrinking=False, tol=1e-4, cache_size=200, max_iter=-1)
    best_model.fit(X_full)

    X_test_s = (test_data - mean) / std
    test_preds = best_model.predict(X_test_s)
    return (test_preds == -1).astype(int)

T3. 糟糕，忘记给红黑树浇水了

天（），每天三种选择：给红树加 ，给黑树加 ，或者跳过（最多跳 天）。最小化红树和黑树高度差的绝对值。

直接暴力 肯定不行，但折半搜索 万就很轻松了。

把天数分成前后两半。对前半部分枚举所有 种选择，记录每种方案的（高度差 ，跳过次数 ）。按跳过次数分组后排序，再做前缀合并——这样查询"跳过次数 的所有方案中，高度差最接近目标值"就是一个二分。

后半部分同样枚举所有方案，对每个方案在前半的合并表里二分找最优配对。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[22],b[22];
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int n,k,i;
    cin>>n>>k;
    for(i=0;i<n;i++)cin>>a[i];
    for(i=0;i<n;i++)cin>>b[i];
    int h=n/2,h2=n-h;
    int pw=1;
    for(i=0;i<h;i++)pw*=3;
    vector<vector<int>>lf(h+1);
    for(int mask=0;mask<pw;mask++){
        int t=mask,d=0,sk=0;
        for(int j=0;j<h;j++){
            int c=t%3;t/=3;
            if(c==0)d+=a[j];
            else if(c==1)d-=b[j];
            else sk++;
        }
        if(sk<=k)lf[sk].push_back(d);
    }
    vector<vector<int>>cum(h+1);
    for(int s=0;s<=h;s++){
        sort(lf[s].begin(),lf[s].end());
        if(s==0)cum[s]=lf[s];
        else{
            cum[s].resize(cum[s-1].size()+lf[s].size());
            merge(cum[s-1].begin(),cum[s-1].end(),lf[s].begin(),lf[s].end(),cum[s].begin());
        }
    }
    int pw2=1;
    for(i=0;i<h2;i++)pw2*=3;
    int ans=LLONG_MAX;
    for(int mask=0;mask<pw2;mask++){
        int t=mask,d=0,sk=0;
        for(int j=0;j<h2;j++){
            int c=t%3;t/=3;
            if(c==0)d+=a[h+j];
            else if(c==1)d-=b[h+j];
            else sk++;
        }
        int al=k-sk;
        if(al<0)continue;
        int s=min(al,(int)h);
        if(cum[s].empty())continue;
        int tg=-d;
        auto it=lower_bound(cum[s].begin(),cum[s].end(),tg);
        if(it!=cum[s].end())ans=min(ans,abs(*it+d));
        if(it!=cum[s].begin()){--it;ans=min(ans,abs(*it+d));}
    }
    cout<<ans<<"\n";
}

T4. 小美的区间

统计区间 （）满足 的数量。

一个关键观察：如果区间最大值就是 或 （即端点之一），那条件自动成立（ 当 ，恒成立）。只有最大值在内部的时候才可能不满足。

所以对每个"区间最大值"统计贡献。用笛卡尔树分治：找到区间 的最大值位置 ，那么所有跨过 的区间的最大值就是 。端点包含 的 pair 直接计入答案，跨过 的 pair （）需要 。

用 sparse table 做 区间最大值查询，分治时对较小的一侧遍历、在较大一侧的排序数组中二分。递归过程中顺便做归并排序，总复杂度 。

有个坑：如果元素有大量相同值，笛卡尔树会退化成链，merge 变 。解决办法是给 sparse table 的比较加一个随机 tiebreaker，让等值元素的树结构随机化，避免退化。一开始没加这个 T 了三发才找到原因。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int ori[100020],a[100020],tmp[100020];
int sp[100020][17],lg[100020];
int n,ans;
void build(){
    for(int i=1;i<=n;i++)sp[i][0]=i;
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i+(1<<j)-1<=n;i++){
            int x=sp[i][j-1],y=sp[i+(1<<(j-1))][j-1];
            sp[i][j]=ori[x]>=ori[y]?x:y;
        }
    lg[1]=0;
    for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
}
int qm(int l,int r){
    int k=lg[r-l+1];
    int x=sp[l][k],y=sp[r-(1<<k)+1][k];
    return ori[x]>=ori[y]?x:y;
}
void solve(int l,int r){
    if(l>r)return;
    if(l==r){a[l]=ori[l];return;}
    int m=qm(l,r);
    solve(l,m-1);solve(m+1,r);
    ans+=(m-l)+(r-m);
    int ls=m-l,rs=r-m;
    if(ls&&rs){
        if(ls<=rs){
            for(int i=l;i<m;i++){
                int th=ori[m]-a[i];
                ans+=(a+r+1)-upper_bound(a+m+1,a+r+1,th);
            }
        }else{
            for(int j=m+1;j<=r;j++){
                int th=ori[m]-a[j];
                ans+=(a+m)-upper_bound(a+l,a+m,th);
            }
        }
    }
    merge(a+l,a+m,a+m+1,a+r+1,tmp);
    for(int i=0;i<ls+rs;i++)a[l+i]=tmp[i];
    a[r]=ori[m];
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>ori[i];
    build();ans=0;
    solve(1,n);
    cout<<ans<<"\n";
}