美团算法笔试
挺难的，感觉比上周难☹️，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";
}
