字节跳动-夏令营笔试-1

字节跳动-夏令营笔试题-2021.05.30

投了个机器人赛道的，错过了一次笔试，来看看题是什么难度吧haha

还没有春招实习生笔试的题难。。。 但是吧 自己做还是不会

01 - 字符串匹配

给定一个订场的字符串，其中包含若干字符，求该字符串中一个连续子串，满足两个条件：

• 子串包含该字符串中的所有不同字符

• 满足上一个条件中最短的一个，如果有多个，则找从左到右第一个出现的字串

可变长度的滑动窗口，力扣应该有原题吧 - Leetcode 70

pair<int, int> findStrMatchLength(string s)
{
    int cnt = 0, suc = 0, res = INT_MAX, si = -1;
    unordered_map<char, int> sset, window;
    // 1. 统计次数
    for(auto c : s)
        if(!sset.count(c))
            sset[c] = 1, cnt++;
    // 2. 维护滑动窗口
    for(int l = 0, r = 0; r < s.size(); r++)
    {
        char c = s[r];
        window[c]++;
        if(window[c] <= sset[c]) suc++;
        while(window[s[l]] > sset[s[l]]) window[s[l++]]--;
        if(suc == cnt)
        {
           if(res > r - l + 1)
                res = r - l + 1, si = l;
            
        }
    }
    return {si, res};
}

02 - 下象棋

小A 和 小B在下象棋，经过激烈的对决，两个人都只剩下了将和一匹马，因此小A提议，如果小B能计算出在小A不移动棋子，且小B的马只能向右上方移动的情况下，小B的马从原点出发能顺利取胜的路径数（吃掉小A的将，且在移动过程中不被小A的马攻击），就算小B赢的对局；

马行动的规则：马走日，一直一斜。即马每次行动需进行两个步骤，首先向右或向上移动一格（一直），再沿原移动方向倾斜45度的对角线跳动一次（一斜）。例如，假设马的位置为( 0, 0)，那么马行动一次可以移动到( 1, 2)或( 2, 1)。但是，马在直线移动后不能落在一个已有棋子的位置上，否则马将无法沿对角线跳跃。即，当马的位置在( 0, 0)，且（ 1, 0）位置有棋子时，马不能到达( 2, 1)，但可到达( 1, 2)。

给定对方的马和将的位置，默认自己的马在原点

---

感觉是经典的动态规划；

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 10010;
int n, m;
int hi, hj, ki, kj;
int f[N][N];

int main()
{
    scanf("%d%d%d%d", &hi, &hj, &ki, &kj);
    f[0][0] = 1;
    set<pair<int, int>> sset = {
        // 1. 可攻击范围
        {hi - 1, hj - 2},
        {hi - 1, hj + 2},
        {hi + 1, hj - 2},
        {hi + 1, hj + 2},
        {hi - 2, hj - 1},
        {hi - 2, hj + 1},
        {hi + 2, hj - 1},
        {hi + 2, hj + 1},
        // 2. 有占着
        {ki + 1, kj + 1},
        {hi + 1, hj + 1},
    };
    f[2][2] = 1;
    for(int i = 2; i <= ki + 1; i++)
        for(int j = 2; j <= kj + 1; j++)
        {
            if(sset.count({i, j})) continue;
            f[i][j] += f[i - 1][j - 2] + f[i - 2][j - 1];
            // 问题就在于什么样是会被攻击的
            // 1. 存在于对面马的日字范围内 会被攻击
            // 2. 对面马的行走路径 or 无法转移etc
        }
    return f[ki + 1][kj + 1];

}

03 - 树上dp

淦 树上dp我真的很会，但是每次都轮不到我考sos

和没有上司的舞会是一样的

某公司想在10月24日为每个人定制一件文化衫。文化衫有D、E、F三种款式。 D[i] 表示编号为 i 的员工收到 D 款式的文化衫时的快乐值。 E[i] 表示编号为 i 的员工收到 E 款式的文化衫时的快乐值。 F[i] 表示编号为 i 的员工收到 F 款式的文化衫时的快乐值。 没有人愿意和自己的直系领导撞衫。 求所有人收到文化衫时的快乐值总和的最大值。

输入描述: 共有 2 N 行。 第 1 行是公司的总人数 N( 2 <= N <= 5000)。 第 2 行到第 N + 1 行描述了员工的快乐值。第 i + 2 行是三个空格分隔的整数： D[i]( 0 <= D[i] <= 100)、 E[i]( 0 <= E[i] <= 100)、 F[i]( 0 <= F[i] <= 100) 表示编号为 i 的员工收到文化衫时的快乐值。最大的领导的编号为 0。 第 N + 2 行到第 2 N 行描述了公司的上下级关系。每行有两个空格分隔的整数：A 和 B，表示 A 是 B 直系领导。除大领导之外，每个员工有且只有一个直系领导。

输出描述: 一个整数，快乐值总和的最大值

#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 5050;
int n, root;
int h[N], e[N], ne[N], idx;
int happy[N][3];
int f[N][3]
bool has_father[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u)
{
    f[u][0] = happy[u][0];
    f[u][1] = happy[u][1];
    f[u][2] = happy[u][2];
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        dfs(j);
        f[u][0] += max(f[j][1], f[j][2]);
        f[u][1] += max(f[j][0], f[j][2]);
        f[u][2] += max(f[j][0], f[j][1]);
    }
}
int main()
{
    scanf("%d", &n);
    // 1. 统计快乐值
    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d%d", &f[i][0], &f[i][1], &f[i][2]);
    }
    for(int i = 1; i < n; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        has_father[b] = true;
    }
    // 2. 找到root
    for(int i = 1; i <= n; i++)
        if(!has_father[i])
        {
            root = i;
            break;
        }
    dfs(root);
    cout << max(max(f[root][1], f[root][1]), f[root][2]) << endl;
    return 0;
}