字节春招笔试后端第四场

先说情况，纯菜鸡，100 0 0 0，应该是寄了，后面没心情做了

为啥字节这么难啊，狠狠地裁员字节佬，以后有机会面试字节的出走员工必须整hard

------------------------

1.

小红拿到了一个数组，她希望选择一个区间，将区间内所有的元素各自翻转。小红希望最终所有元素之和尽可能大。你能帮帮她吗?

所谓元素翻转，指元素正着读变成倒着读，例如”1234"变成”4321”"1430"变成”341”(去掉了前导零)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;

int reverse(int& num) {
    vector<int>tmp;
    while (num > 0) {
        tmp.push_back(num % 10);
        num /= 10;
    }
    int sum = 0;
    for (auto bit : tmp) {
        sum *= 10;
        sum += bit;
    }
    return sum;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n); 
    vector<int> rev;
    LL sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    for (auto x : a) {
        rev.push_back(reverse(x));
    }

    vector<int> c(n);
    for (int i = 0; i < n; i++) {
        c[i] = rev[i] - a[i];
    }

    LL pre = 0;
    LL res = c[0];
    for (auto num : c) {
        pre = max((LL)pre + num, (LL)num);
        res = max(res, pre);
    }
    cout << res + sum;

}

2.

小红拿到一个字符矩阵。她希望选定一个字符作为起点，然后通过“跳马步”的方式跳3步得

到"byte"字符串。小红想知道，共有多少种方式?

定义“跳马步”的方式如下: 如果当前的坐标是(x0, y0)，那么落点的坐标(x,y)必须满足

|x - x0| +|y-y0|= 3且 x ≠ x0, y ≠ y0

3.

小红在一个长度为n的数组上，初始在第一个元素，她准备前往最后一个元素。

小红有一个弹力鞋，她每次可以利用弹力鞋向右弹跳，初始弹力鞋只能跳 1的距离，每跳一次弹

力鞋能跳的距离翻倍。例如，第一次跳的距离恰好是1，第二次跳的距离恰好是2，第三次跳的距

离恰好是4，以此类推。

另外小红可以随时将弹力鞋弹跳的距离重置为 1。

现在数组上有若干个单向传送阵，小红可以随时使用这些传送阵向右传送 (传送后弹力鞋的距离

强制重置为 1)。

小红想知道，自己需要至少弹跳多少次可以到达最后一个元素?

这个应该是二维dp

4.

小红拿到了一个仅由"red"三种字符组成的串，她有若干次询问，每次查询一个子串，小红希望你

回答: 重排该子串可以生成多少种不同的回文串。你能帮帮她吗?

所谓回文串，指正着读和倒着读都相同的字符串，例如”ded”是回文串。