美团笔试 - 技术方向 0322 题解

T1

求完全由轴对称字母 AHIMOTUVWXY 构成的回文串数量。

数据范围 $n\le 100$ ，直接 $O(n^3)$ 暴力枚举区间判断。
按非轴对称字母分段，每一段单独 manacher 统计回文串数量， $O(n)$ 。

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
char s[N];
set<char> st = {'A', 'H', 'I', 'M', 'O', 'T', 'U', 'V', 'W', 'X', 'Y'};
int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1), cnt = 0;
    for (int l = 2; l <= n; ++l) {
        for (int i = 1; i + l - 1 <= n; ++i) {
            int f = 1;
            for (int j = 1; j <= l; ++j)
                if (!st.count(s[i + j - 1])) {
                    f = 0;
                    break;
                }
            if (!f) continue;
            for (int j = 1; j * 2 <= l; ++j)
                if (s[i + j - 1] != s[i + l - j]) {
                    f = 0;
                    break;
                }
            cnt += f;
        }
    }
    printf("%d\n", cnt);
    return 0;
}

T2

给定一个排列 $p$ ，求对子区间排序后，子区间中位数位置不变的子区间数量。

枚举中位数的位置，从中间同时向左右扩展，统计比 $p_i$ 大/小的数的数量，如果相等，说明当前子区间满足题意， $O(n^2)$ 。由于 $n\le 10^4$ ，所以可以通过。

#include <bits/stdc++.h>
using namespace std;
void solve() {
    int n, ans = 0;
    scanf("%d", &n);
    vector<int> a(n);
    for (auto &x : a) scanf("%d", &x);
    for (int i = 0; i < n; ++i) {
        int l = 0, r = -2;
        for (int j = 0; i - j >= 0 && i + j < n; ++j) {
            (a[i - j] < a[i] ? l : r)++;
            (a[i + j] < a[i] ? l : r)++;
            ans += l == r;
        }
    }
    printf("%d\n", ans);
}
int main() {
    int t;
    scanf("%d", &t);
    while (t--) solve();
    return 0;
}

T3

在 $1$ 到 $n$ 的数轴上，有一个初始位置为 $k$ 的机器人。给定一个指令序列 $s$ ，指令集由 L（向左移动，若在 $1$ 则不动）、R（向右移动，若在 $n$ 则不动）以及 ?（随机转为 L 或 R 并移动）组成。问机器人所有可能的最终位置。 $1\le k\le n\le10^6,1\le|s|\le 10^6$ 。

注意到，最终的答案一定是形如 $111...1\ 1010101\ 1...1111$ ，即一个大区间套小区间，小区间部分答案为 $01$ 交替，大区间的剩余部分为连续的 $1$ 。
维护两个区间的端点 $[L,R]\subseteq[sL, sR]$ ，其中 $ans[L,R]=1010...101$ 。
先不考虑任何冲突，对于每个指令：
- L ：全部左移，即全 $-1$ ；
- R ：全部右移，即全 $+1$ ；
- ? ：
  - 如果 $sL=L$ ，即没有连续 $1$ 前缀，则同时左移；
  - 如果 $sL<L$ ，说明存在连续 $1$ 段，而连续 $1$ 段会同时向左右两边扩充，即 $...000111\ 10101...\to...0011111\ 1010...$ ，此时 $sL$ 会左移，但是 $L$ 会右移；
  - 对于 $R$ 和 $sR$ 的讨论同理。
考虑在什么情况下会产生连续 $1$ 段：对于 $L$ ，情况为 $101010...\to1\ 10101...$ ，即当前指令为 ? 且 $L<1<R$ ，可以理解为最左边的 $1$ 再次左移时移出去了，但实际上因为“撞墙”了只能继续留在 $1$ ，此时 $sL=1,\ L=2$ ； $R$ 的情况和 $L$ 是对称的。
考虑如何处理冲突，定义修正函数 $f(x)=\min(n,\max(1, x))$ ：
- 以上操作的执行均满足 $[L,R]\subseteq[sL,sR]$ 的条件，不会产生区间冲突；
- 区间端点可能超出 $[1,n]$ ：直接对所有区间端点进行修正即可；
- 可能会出现 $01$ 段消失， $L>R$ 的情况：直接令 $L=R$ 即可。
时间复杂度 $O(n)$ 。
特别注意，题目没说 $|s|=n$ ，虽然样例都是这样的（笔试的时候因为这个卡 $96\%$ 卡了一个小时）。
题外话：从笔试题的角度来说，这题确实考得非常难了，而且如果不继续想一下性质，直接用大量 if-else 条件处理所有情况，写起来考虑各种边界条件会非常麻烦。

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

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, k; string s;
    cin >> n >> k >> s;
    int sL = k, sR = k, L = k, R = k;
    for (auto c : s) {
        switch (c) {
        case 'L':
            --sL, --L, --R, --sR;
            break;
        case 'R':
            ++sL, ++L, ++R, ++sR;
            break;
        default:
            sL < L ? ++L : --L;
            sR > R ? --R : ++R;
            --sL, ++sR;
            break;
        }
        auto f = [&](int &x) {
            x = min(n, max(1, x));
        };
        if (L < 1 && 1 < R) L = 2;
        if (R > n && n > L) R = n - 1;
        f(sL), f(sR), f(L), f(R);
        if (L > R) L = R;
    }
    string ans(n, '0');
    for (int i = sL; i < L; ++i) ++ans[i - 1];
    for (int i = L; i <= R; i += 2) ++ans[i - 1];
    for (int i = R + 1; i <= sR; ++i) ++ans[i - 1];
    cout << ans << '\n';
    return 0;
}

当然，如果你真的想所有情况 if-else 判断一下，这种代码我也有。

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

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, k; string s;
    cin >> n >> k >> s;
    int L = k, R = k, sL = k, sR = k;
    for (auto c : s) {
        if (c == 'L') {
            if (sL > 1)
                --sL, --L, --R, --sR;
            else if (sL < L)
                --L, --R, --sR;
            else if (L + 1 < R)
                --R, --sR, ++L;
            else if (sR > 1)
                --sR;
        } else if (c == 'R') {
            if (sR < n)
                ++sL, ++L, ++R, ++sR;
            else if (R < sR)
                ++L, ++R, ++sL;
            else if (L + 1 < R)
                ++L, ++sL, --R;
            else if (sL < n)
                ++sL;
        } else {
            if (sL == L && L > 1)
                --L, --sL;
            else if (sL < L)
                sL = max(sL - 1, 1), ++L;
            else if (L < n)
                ++L;
            if (sR == R && R < n)
                ++R, ++sR;
            else if (R < sR)
                sR = min(sR + 1, n), --R;
            else if (R > 1)
                --R;
            L = min(n, max(1, L));
            R = min(n, max(1, R));
            if (L > R)
                L = R;
        }
        // assert(0 <= sL);
        // assert(sL <= L);
        // assert(L <= R);
        // assert(R <= sR);
        // assert(sR < n);
        // printf("%d %d %d %d\n", sL, L, R, sR);
    }
    string ans(n, '0');
    for (int i = sL; i < L; ++i) ans[i - 1] = '1';
    for (int i = L; i <= R; i += 2) ans[i - 1] = '1';
    for (int i = R + 1; i <= sR; ++i) ans[i - 1] = '1';
    cout << ans << '\n';
    return 0;
}

再附赠一个对拍程序。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int N = 1e5 + 5;

string bf(int n, int k, string s) {
    bitset<N> bs;
    bs[k] = 1;

    for (auto c : s) {
        // string ans(n, '0');
        // for (int i = 0; i < n; ++i)
        //     ans[i - 1] = bs[i] + '0';
        // cout << ans << endl;
        int L = bs[1], R = bs[n];
        switch (c) {
        case 'L':
            bs = bs >> 1;
            if (L)
                bs[1] = 1;
            break;
        case 'R':
            bs = bs << 1;
            if (R)
                bs[n] = 1;
            break;
        default:
            bs = (bs << 1) | (bs >> 1);
            if (L)
                bs[1] = 1;
            if (R)
                bs[n] = 1;
            break;
        }
        bs[0] = bs[n + 1] = 0;
    }
    string ans(n, '0');
    for (int i = 1; i <= n; ++i)
        ans[i - 1] += bs[i];
    return ans;
}
string solve1(int n, int k, string s) {
    int L = k, R = k, sL = k, sR = k;
    for (auto c : s) {
        if (c == 'L') {
            if (sL > 1)
                --sL, --L, --R, --sR;
            else if (sL < L)
                --L, --R, --sR;
            else if (L + 1 < R)
                --R, --sR, ++L;
            else if (sR > 1)
                --sR;
        } else if (c == 'R') {
            if (sR < n)
                ++sL, ++L, ++R, ++sR;
            else if (R < sR)
                ++L, ++R, ++sL;
            else if (L + 1 < R)
                ++L, ++sL, --R;
            else if (sL < n)
                ++sL;
        } else {
            if (sL == L && L > 1)
                --L, --sL;
            else if (sL < L)
                sL = max(sL - 1, 1), ++L;
            else if (L < n)
                ++L;
            if (sR == R && R < n)
                ++R, ++sR;
            else if (R < sR)
                sR = min(sR + 1, n), --R;
            else if (R > 1)
                --R;
            L = min(n, max(1, L));
            R = min(n, max(1, R));
            if (L > R)
                L = R;
        }
        // assert(0 <= sL);
        // assert(sL <= L);
        // assert(L <= R);
        // assert(R <= sR);
        // assert(sR < n);
        // printf("%d %d %d %d\n", sL, L, R, sR);
    }
    string ans(n, '0');
    for (int i = sL; i < L; ++i) ans[i - 1] = '1';
    for (int i = L; i <= R; i += 2) ans[i - 1] = '1';
    for (int i = R + 1; i <= sR; ++i) ans[i - 1] = '1';
    return ans;
}
string solve2(int n, int k, string s) {
    // scanf("%d%d%s", &n, &k, s);
    int sL = k, sR = k, L = k, R = k;
    for (auto c : s) {
        switch (c) {
        case 'L':
            --sL, --L, --R, --sR;
            break;
        case 'R':
            ++sL, ++L, ++R, ++sR;
            break;
        default:
            sL < L ? ++L : --L;
            sR > R ? --R : ++R;
            --sL, ++sR;
            break;
        }
        auto f = [&](int &x) { x = min(n, max(1, x)); };
        if (L < 1 && 1 < R) L = 2;
        if (R > n && n > L) R = n - 1;
        f(sL), f(sR), f(L), f(R);
        if (L > R) L = R;
    }
    string ans(n, '0');
    for (int i = sL; i < L; ++i) ++ans[i - 1];
    for (int i = L; i <= R; i += 2) ++ans[i - 1];
    for (int i = R + 1; i <= sR; ++i) ++ans[i - 1];
    return ans;
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    // int n, k;
    // string s;
    // cin >> n >> k >> s;
    // cout << solve2(n, k, s) << endl;
    // return 0;
    // For random number generation
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    // cout << t << endl;
    auto check = [&](int n, int k, string s) {
        static int tc = 0;
        // For verification: compare bf and solve
        string bf_ans = bf(n, k, s);
        string ans1 = solve1(n, k, s);
        string ans2 = solve2(n, k, s);
        cout << "Test case " << ++tc << ": ";
        if (bf_ans != ans1 || bf_ans != ans2) {
            cout << "Mismatch found!" << endl;
            cout << n << " " << k << endl;
            cout << s << endl;
            cout << "bf: " << bf_ans << endl;
            cout << "solve1: " << ans1 << endl;
            cout << "solve2: " << ans1 << endl;
            exit(0);
        } else {
            cout << "OK" << endl;
        }
    };
    // Number of test cases
    // Generate all possible sequences for small inputs
    function<void(int, int, int, string &, int)> generateAllSequences =
        [&](int n, int k, int len, string &s, int pos) {
            if (pos == len) {
                check(n, k, s);
                return;
            }
            // Try all three possible instructions
            s[pos] = 'L';
            generateAllSequences(n, k, len, s, pos + 1);

            s[pos] = 'R';
            generateAllSequences(n, k, len, s, pos + 1);

            s[pos] = '?';
            generateAllSequences(n, k, len, s, pos + 1);
        };

    // For small values, test all possible combinations
    for (int n = 1; n <= 5; ++n) {
        for (int k = 1; k <= n; ++k) {
            for (int len = 1; len <= 5; ++len) {
                string s(len, ' ');
                generateAllSequences(n, k, len, s, 0);
            }
        }
    }
    int tot = 3000; // You can adjust this
    for (int tc = 0; tc < tot; ++tc) {
        // Generate random n, k and length of string
        int n = rng() % N + 1;   // Random n between 1 and 10^6
        int k = rng() % n + 1;   // Random k between 1 and n
        int len = rng() % N + 1; // Random length between 1 and 10^6

        // Generate random instruction sequence
        string s;
        for (int i = 0; i < len; ++i) {
            int cmd = rng() % 3;
            if (cmd == 0)
                s += 'L';
            else if (cmd == 1)
                s += 'R';
            else
                s += '?';
        }
        check(n, k, s);
    }
    return 0;
}

#笔试##牛客创作赏金赛##美团笔试##美团#