技术综合-后台11.01美团笔试的第二部分场景编程题是什么？

第一部分是普通的编程题，共四道题，80分。

第一题：

字符串解密。

第二题：

第三题：

给出一个树形结构，该树有n个节点。其中小美和小团在分别在节点a和b上，现在小美追小团，其中每经过一个单位时间，两个人都可以选择保持不动或移动到相邻的某个节点。
可以知道小美肯定可以抓到小团，小美和小团使用最优策略，问小团最长多长时间才能被抓到。其中 $3 \le n \le 5e4$

如n=3,树的边有（1，2），（1，3）, 小美在节点2，小团在节点3。最优策略下经过2个单位时间小团会被抓到。

我的思路：bfs，其中小美对经过的节点标记，按照bfs顺序，小团不能走小美标记过的节点。

#include<bits/stdc++.h>

#define mset(a,b) memset(a,b,sizeof(a))

#define pb push_back
#define fi first
#define se second

using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f;
const int N = 5e4+10;

vector<int> g[N];

struct State
{
    int who;
    int step;
    int u;
};

int maxstep=0;

bool vis[N];

#define black 0 // 小美.
#define white 1 // 小团.

set<pair<int,int>> sign; // 优化，队列中多个相同的状态（step,u）中让其出现一次.不然会内存超限

int solve(int x,int y) // x want to catch y.
{
    if( x == y ) return 0;
    vis[x] = 1;
    queue<State> Q;
    Q.push(State{black,0,x});
    Q.push(State{white,0,y});

    sign.insert(make_pair(0,y));
    while(!Q.empty())
    {

        State s = Q.front();
        Q.pop();

        if(s.who == white)
            maxstep = max(maxstep,s.step);

        if(s.who == white && vis[s.u] == false) // 小团保持位置不变.
        {
            if(sign.find(make_pair(s.step+1,s.u)) == sign.end())// 如果不存在该状态，才插入. 否则这次插入是赘余的.
            {
                Q.push(State{white,s.step+1,s.u});
                sign.insert(make_pair(s.step+1,s.u));
            }

        }
        for(auto v : g[s.u])
        {
            if(vis[v]) continue;
            if(s.who == black) // 小美将邻接的节点标记并加入队列.
            {
                Q.push(State{black,s.step+1,v});
                vis[v] = true;
            }
            else
            {
                if(sign.find(make_pair(s.step+1,v)) == sign.end()) // 如果不存在该状态，才插入. 否则这次插入是赘余的.
                {
                    Q.push(State{white,s.step+1,v});
                    sign.insert(make_pair(s.step+1,v));
                }
            }
        }
    }

    return maxstep+1;
}
int main()
{
    int n,x,y;
    scanf("%d%d%d",&n,&x,&y);
    for(int i=1; i<n; ++i)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].pb(v);
        g[v].pb(u);
    }

    printf("%d\n",solve(x,y));
}

第四题：

给定m和n，和一个数组w，该数组有n个元素，其中数组中的每个元素值在区间[1,m]内。对于 $l,r \in [1,n]$ 。求出有多少二元组 $(l,r)$ 满足以下条件：

$l \le r$
去除数组w中不在区间 $[1,l-1] \cup [r+1,m]$ 的数，且剩下的子序列要求单调不减。
其中 $n,m \in [1,1e5]$

例如 m=5, n=5, w=[4 1 4 1 2]，答案是10

#include<bits/stdc++.h>

#define mset(a,b) memset(a,b,sizeof(a))

#define pb push_back
#define fi first
#define se second

using namespace std;

typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 1e5+10;


int w[N];

vector<int> pos[N];

// rmin： rmin[k] 代表值在区间[k+1,m]的子序列的下标最小值，如果该子序列无序，则为inf
int rmin[N];
// lmax:  lmin[k] 代表值在区间[1,k-1]的子序列的下标最大值，如果该子序列无序，则为-1
int lmax[N];
int main()
{
    int n,m;
    scanf("%d%d",&m,&n);

    for(int i=1;i<=n;++i){
        scanf("%d",w+i);
        pos[w[i]].pb(i);
    }

    long long ans=0;
    for(int i=1;i<=m;++i) rmin[i]=-1; // initialize.

    int rlast = inf;
    for(int r=m;r>=1;--r)
    {
        if(pos[r+1].size() == 0)
        {
            rmin[r] = rlast;
        }
        else{
            int ep = pos[r+1].size()-1;
            if(pos[r+1][ep] < rlast){
                rlast = pos[r+1][0];
                rmin[r] = rlast;
            }
            else{
                break;
            }
        }
    }


    for(int l=1;l<=m;++l) lmax[l] = inf;// initialize.
    int llast = 0;
    for(int l=1;l<=m;++l){

        if(pos[l-1].size() == 0 || pos[l-1][0] > llast ){
            int ep = pos[l-1].size();
            if(ep != 0)
                llast = pos[l-1][ep-1];
            lmax[l] = llast;

        }
        else{
            break;
        }

    }

    for(int l=1;l<=m;++l){
        if(lmax[l] == inf) break;
        // 对于一个指定的l，如果二元组(l,r)可以，那么(l,r+1)也可以.
        // 我们枚举l，求出符合条件的最小的r.

        int th = upper_bound(rmin+l, rmin+m+1, lmax[l]) - rmin;

        if(th <= m){
            ans += (m - th+1ll);
        }
    }

    printf("%lld\n",ans);
    return 0;
}