8.8 美团笔试
总共五道题，4+1的形式。
第一题，要特判等于0的情况，否则是91%
第二题，忘掉了。
第三题，对于a[i]，找到之前小于它的最大的数，可以维护一个set，每次处理完当前a[i]，就插入到set中。对于处理，可以直接利用set的lower_bound（val），然后根据迭代器减1判断情况。
第四题，任选x修改为y，使得序列前一半与后一半相同，可以处理出不同的 pair{ a[i] , a[i+n/2] }，然后默认first为较小值，去一下重 ( 相同的对计算一次贡献 )，然后建立无向图。优先从入度小的点出发DFS，每走一步就是一个花费，图遍历完就得答案。
第五题，对换左右子树，这个可以直接用数组表示存二叉树，点值对应题目要求的点序号，下标0开始，初始时左右儿子分别为2*x+1,2*x+2，然后根据修改，分别修改Lchild和Rchild的指向。第五题代码还没删掉，如下。
#include<bits/stdc++.h>
using namespace std;
int a[100020];
typedef pair<int,int> pii;
int n,m,k;
int loc[100020];
struct node{
int val;
int L,R;
}p[10000];
struct pre{
int L,R;
}has[10000];
void solve(int x) {
if(x>=n) return;
loc[p[x].val]=x;
p[x].L=p[x].R=0;
int cur=p[x].val;
int Lval=has[cur].L;
int Rval=has[cur].R;
if(Lval) {
p[x].L=2*x+1;
p[2*x+1].val=Lval;
solve(2*x+1);
}
if(Rval) {
p[x].R=2*x+2;
p[2*x+2].val=Rval;
solve(2*x+2);
}
}
void print(int x) {
if(p[x].L) print(p[x].L);
cout<<p[x].val<<" ";
if(p[x].R) print(p[x].R);
}
int main()
{
cin>>n>>m>>k;
p[0].val=k;
for(int i=1;i<=n;i++) {
cin>>has[i].L>>has[i].R;
}
solve(0);
for(int i=1;i<=m;i++) {
int x;
cin>>x;
int id=loc[x];
swap(p[id].L,p[id].R);
}
print(0);
}
拼多多集团-PDD成长空间 486人发布
查看3道真题和解析