2020.08.29美团点评秋招笔试（AC 4.18题）

第一题：

添加一个头部字符串和一个尾部字符串。头部字符串满足至少包含一个“MT”子序列，

且以T结尾。尾部字符串需要满足至少包含一个“MT”子序列，且以M开头。求S是满

足头尾字符串合法的情况下的最长的字符串。

思路：AC 直接模拟

代码：

int main(void)
{
#ifndef ONLINE_JUDGE
    freopen("a.txt", "r", stdin);
#endif

    int n;
    string s;
    while(cin >> n) {
        cin >> s;
        int size = s.size();

        int l = 0;
        int mcnt = 0;
        for(int i = 0; i < size; ++i) {
            if(s[i] == 'M') {
                ++mcnt;
            } else if(s[i] == 'T' && mcnt > 0) {
                l = i; 
                break;
            }
        }
        int r = size-1;
        int tcnt = 0;
        for(int i = size-1; i >= l; i--) {
            if(s[i] == 'T') {
                ++tcnt;
            } else if(s[i] == 'M' && tcnt > 0) {
                r = i;
                break;
            }
        }
        cout << s.substr(l+1, r - l - 1);
    }
    return 0;
}

第二题：

本着能者优先的原则，公司将这n个人按照业务能力从高到底编号为1~n。编号靠前的人

具有优先选择的权力，每一个人都会填写一个意向，这个意向是一个1~n的排列，表示

一个人希望的去的业务区域顺序，如果有两个人同时希望去某一个业务区域则优先满足编号小的人，

思路：AC 直接模拟

代码：

const int maxn = 305;
int a[maxn][maxn];

int main(void)
{
#ifndef ONLINE_JUDGE
    freopen("b.txt", "r", stdin);
#endif

    int n;
    while(cin >> n) {
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j) {
                cin >> a[i][j];
            }
        }
        
        vector<int> ans(n+1, 0);
        vector<bool> visit(n+1, false);
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j) {
                if(visit[ a[i][j] ]) continue;
                ans[i] = a[i][j];
                visit[a[i][j]] = true;
                break;
            }
        }
        for(int i = 1; i <= n; ++i) {
            if(i < n) cout << ans[i] << " ";
            else cout << ans[i] << endl;
        }
    }
    
    return 0;
}

第三题：

小美要去找小团“讲道理”。小团望风而逃，他们住的地方可以抽象成一棵有n个结点的树，小美位于x位置，

小团位于y位置。小团和小美每个单位时间内都可以选择不动或者向相邻的位置转移，假设小美足够聪明，

很显然最终小团会无路可逃，只能延缓一下被“讲道理”的时间，请问最多经过多少个单位时间后，小团会被追上。

思路：AC 分别以 x y 为起点搜索到所有其他点的路径长度，然后取dx > dy得最大的dx就是答案

代码：

const int maxn = 50005;

void dfs(vector<vector<int>>& tree, vector<int>& dis, int u, int fa, int step) {
    for(int v : tree[u]) {
        if(v == fa) continue;
        dis[v] = step+1;
        dfs(tree, dis, v, u, step+1);
    }
}

int main(void)
{
#ifndef ONLINE_JUDGE
    freopen("c.txt", "r", stdin);
#endif

    int n, x, y;
    while(cin >> n >> x >> y) {
        vector<vector<int>> tree(n+1);
        for(int i = 1; i < n; ++i) {
            int u, v;
            cin >> u >> v;
            tree[u].push_back(v);
            tree[v].push_back(u);
        }

        vector<int> disx(n+1, 0);
        vector<int> disy(n+1, 0);
        dfs(tree, disx, x, -1, 0);
        dfs(tree, disy, y, -1, 0);

        int ans = 0;
        for(int i = 1; i <= n; ++i) {
            if(disx[i] > disy[i]) ans = max(ans, disx[i]);
        }
        cout << ans << endl;
    }
    return 0;
}

第四题：

小团和小美各自选择一个[1,m]之间的整数，设小美选择的是l，小团选择的是r，

我们认为两个人是默契的需要满足以下条件:

1. l 小于等于r。

2. 对于序列中的元素x，如果0<x<l,或r<x<m+1,则x按其顺序保留下来，要求保留下来的子序列单调不下降。

小团为了表现出与小美最大的默契，因此事先做了功课，他想知道能够使得两人默契的二元组<l,r>一共有

多少种。我们称一个序列A为单调不下降的，当且仅当对于任意的i>j,满足A_i>=A_j。输入第一行包含

两个正整数m和n，表示序列元素的最大值和序列的长度。(1<=n,m<=100000)

思路：AC 18%(我用的求逆序的算法，然后总数-逆序数), 题目真的没有读懂，好吧，不是不懂，

是完全没有一点思路（卡了30min 无果）希望路过的大佬们可以提供点思路。非常感谢！

代码：

const int maxn = 100005;
int a[maxn];
int t[maxn];

int quikSort(int left, int right) {
    if(left >= right) return 0;

    int m = (left + right) / 2;
    int l = quikSort(left, m);
    int r = quikSort(m+1, right);

    int i = left;
    int j = m+1;
    int k = left;
    int cnt = 0;
    while(i <= m && j <= right) {
        if(a[i] > a[j]) {
            cnt += (j - m);
            t[k++] = a[j++];
        } else {
            t[k++] = a[i++];
        }
    }
    while(i <= m) t[k++] = a[i++];
    while(j <= right) {
        if(a[m] > a[j]) cnt += (j-m);
        t[k++] = a[j++];
    }
    for(int k = left; k <= right; ++k) a[k] = t[k]; 
    return l + cnt + r;
} 

int main(void)
{
#ifndef ONLINE_JUDGE
    freopen("d.txt", "r", stdin);
#endif

    int n, m;
    while(cin >> m >> n) {
        for(int i = 1; i <= n; ++i) cin >> a[i];
        cout << n*(n+1)/2 - quikSort(1, n) << endl;
    }
    return 0;
}

附加题：

我们用如下的方式表示他的粘贴操作和查询操作：

粘贴操作：1 k x y，表示把A序列中从下标x位置开始的连续k个元素粘贴到B序列中从下标y开始的连续k个位置上，

原始序列中对应的元素被覆盖。（数据保证不会出现粘贴后k个元素超出B序列原有长度的情况）

查询操作：2 x，表示询问当前B序列下标x处的值是多少。

输入第一行包含一个正整数n，表示序列A和序列B的长度。(1<=n<=2000)

输入第二行包含n个正整数，表示序列A中的n个元素，第 i 个数字表示下标为 i 的位置上的元素，

每一个元素保证在10^9以内。

输入第三行是一个操作数m，表示进行的操作数量。(1<=m<=2000)

思路：AC 数据量比较小，直接模拟做就行了！n <= 2000, 所以直接n^2暴力即可。直觉告诉我一定会有

比n^2更优的复杂度，希望路过的大佬可以指点一下，非常感谢！

代码：

const int maxn = 2005;
int a[maxn];
int b[maxn];

int main(void)
{
#ifndef ONLINE_JUDGE
    freopen("e.txt", "r", stdin);
#endif

    int n, m;
    int op, k, x, y;
    while(cin >> n) {
        memset(b, -1, sizeof(b));
        for(int i = 1; i <= n; ++i) cin >> a[i];
        cin >> m;
        while(m--) {
            cin >> op;
            if(op == 2) {
                cin >> x;
                cout << b[x] << endl;
                continue;
            }
            cin >> k >> x >> y;
            int t = 0;
            for(int i = x; i < k + x; ++i, ++t) {
                b[y+t] = a[i];
            }
        }
    }
    return 0;
}

#笔试题目##美团#