首页 > 技术综合-后台11.01美团笔试的第二部分场景编程题是什么?
头像
KetchupZ
编辑于 2020-11-03 08:15
+ 关注

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

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

第一题:

字符串解密。

第二题:

第三题:

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

如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]内。对于。求出有多少二元组满足以下条件:

  • 去除数组w中不在区间的数, 且剩下的子序列要求单调不减。
    其中

例如 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;
}

第二部分好像叫场景编程题,20分,但是当时没做完没看这个题,有看过的大佬分享下是什么题吗?

全部评论

(2) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐