美团3.28笔试

研发卷，10道选择题 + 3道编程题，选择题基本上都是AI/大模型相关：RAG、大模型等等，最近做笔试基本上都是AI相关的了，大家还是提前多刷刷AI的知识吧

编程题：

T1. 风不吹雨

操作 1 是把 $a_i$ 变成 $\lfloor a_i/2 \rfloor$ ，最多用 $a$ 次；操作 2 是减 $k$ ，最多用 $b$ 次。每个位置每种操作最多做一次，两种可以同时做，求最小元素和。

一个比较显然的结论：如果同时做两种操作，先除后减一定不差于先减后除（因为除法会把减掉的量也砍半）。所以同时做两种操作的减少量就是 $d_1 + k$ ，其中 $d_1 = a_i - \lfloor a_i/2 \rfloor$ 。

然后注意到操作 2 对每个元素的减少量都是 $k$ ，跟选哪个元素无关。所以操作 2 直接贡献 $b \times k$ 的减少量。操作 1 的减少量取决于选哪些元素，贪心选 $d_1$ 最大的前 $a$ 个就行。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int d[202020];
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int _;cin>>_;while(_--){
		int n,a,b,k,i,s=0;
		cin>>n>>a>>b>>k;
		for(i=0;i<n;i++){
			int x;cin>>x;
			s+=x;
			d[i]=x-x/2;
		}
		sort(d,d+n,greater<int>());
		for(i=0;i<a;i++)s-=d[i];
		s-=b*k;
		cout<<s<<"\n";
	}
}

T2. 交替子序列

选子序列 $b$ 使得 $F(b) = b_1 - b_2 + b_3 - b_4 + \cdots$ 最大。

DP 两个状态就行： $f$ 表示当前子序列最后一个元素在奇数位（被加）的最大值， $g$ 表示最后一个元素在偶数位（被减）的最大值。

对每个 $a_i$ ，要么放到奇数位（从 $g$ 转移过来加上 $a_i$ ，或者单独开一个新子序列），要么放到偶数位（从 $f$ 转移过来减去 $a_i$ ），要么跳过。 $O(n)$ 扫一遍就行了。

参考代码：

#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,i,x;
		cin>>n;
		int f=-1e18,g=-1e18;
		for(i=0;i<n;i++){
			cin>>x;
			int nf=max({f,g+x,x});
			int ng=max(g,f-x);
			f=nf;g=ng;
		}
		cout<<max({0LL,f,g})<<"\n";
	}
}

T3. 小美的区间

统计有多少区间 $[i,j]$ （ $i < j$ ）满足 $v_i + v_j > \max(v_i, \ldots, v_j)$ 。

先想一个关键观察：如果区间最大值在端点上（ $\max = v_i$ 或 $\max = v_j$ ），那么条件自动满足（因为 $v_i + v_j > v_i$ 等价于 $v_j > 0$ ，永远成立）。所以只有最大值在区间严格内部的情况可能不满足。

用「总对数 - 不满足的对数」来算。对每个位置 $k$ ，用单调栈求出 $k$ 作为区间最大值的左右边界 $L[k]$ 、 $R[k]$ 。不满足的对 $(i,j)$ 要求 $i \in (L[k], k)$ ， $j \in (k, R[k])$ ，且 $v_i + v_j \leq v_k$ 。

枚举左右较短的一侧，在另一侧用归并排序树做区间 $\leq x$ 的计数查询。按经典的「枚举较短侧」复杂度分析，总查询次数是 $O(n \log n)$ ，每次查询 $O(\log^2 n)$ ，总复杂度 $O(n \log^3 n)$ ， $n = 10^5$ 可以过。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long

int v[100010];
int L[100010],R[100010];
vector<int>seg[400040];

void build(int p,int l,int r){
	seg[p].clear();
	if(l==r){seg[p].push_back(v[l]);return;}
	int m=(l+r)/2;
	build(p*2,l,m);build(p*2+1,m+1,r);
	merge(seg[p*2].begin(),seg[p*2].end(),seg[p*2+1].begin(),seg[p*2+1].end(),back_inserter(seg[p]));
}

int query(int p,int l,int r,int ql,int qr,int x){
	if(ql>qr)return 0;
	if(ql<=l&&r<=qr)return upper_bound(seg[p].begin(),seg[p].end(),x)-seg[p].begin();
	int m=(l+r)/2,res=0;
	if(ql<=m)res+=query(p*2,l,m,ql,qr,x);
	if(qr>m)res+=query(p*2+1,m+1,r,ql,qr,x);
	return res;
}

signed main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int n,i;
	cin>>n;
	for(i=1;i<=n;i++)cin>>v[i];
	stack<int>st;
	for(i=1;i<=n;i++){
		while(!st.empty()&&v[st.top()]<v[i])st.pop();
		L[i]=st.empty()?0:st.top();
		st.push(i);
	}
	while(!st.empty())st.pop();
	for(i=n;i>=1;i--){
		while(!st.empty()&&v[st.top()]<=v[i])st.pop();
		R[i]=st.empty()?n+1:st.top();
		st.push(i);
	}
	build(1,1,n);
	int ans=n*(n-1)/2;
	for(int k=1;k<=n;k++){
		int ls=k-L[k]-1,rs=R[k]-k-1;
		if(ls<=0||rs<=0)continue;
		if(ls<=rs){
			for(i=L[k]+1;i<k;i++){
				int need=v[k]-v[i];
				if(need<1)continue;
				ans-=query(1,1,n,k+1,R[k]-1,need);
			}
		}else{
			for(i=k+1;i<R[k];i++){
				int need=v[k]-v[i];
				if(need<1)continue;
				ans-=query(1,1,n,L[k]+1,k-1,need);
			}
		}
	}
	cout<<ans<<"\n";
}

#美团笔试#