字节跳动秋招 2023.09.17 编程题目与题解

发表于 2023-09-20 更新于 2023-09-25 分类于笔试阅读次数：本文字数： 3.3k 阅读时长 ≈ 3 分钟

1、小红查单词

小红拿到了一个仅由英文字母组成的字符串。她想知道某单词在该字符串中出现了多少次，你能帮帮她吗？

请注意，小红会询问多次。

输入

第一行输入两个正整数\(n\)和\(q\)，代表字符串长度和询问次数。

第二行输入一行长度为\(n\)的，仅由小写英文字母组成的字符串。代表小红拿到的字符串。

接下来的\(q\)行，每行输入一个仅由小写英文字母组成的字符串，代表小红的每次查询。

\(1 \le n,q \le 10^5\)

每次查询的字符串长度不超过\(10\)。

输出

输出\(q\)行，每行输出一个整数，代表该次查询的结果。

样例

输入：
10 3
bobobalice
bob
alice
red

输出：
2
1
0

解答

需要注意的是，本题中每个询问串的长度都不超过\(10\)，我们可以从这里入手。

我们可以提前将\(s\)中的每个长度不超过\(10\)的所有子串全部取出来，并使用哈希值来表示这些子串，使用\(10\)个哈希表来统计这些哈希值出现的次数。也就是说，一个子串\(t\)的哈希值统计到第\(|t|\)个哈希表中。

最终，对于每个询问串\(t\)，我们只需要求出它的哈希值是\(h\)，并查看第\(|t|\)个字典出现了多少次哈希值\(h\)即可。

代码

# include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
unordered_map<ull,int>mp[12];
ull B=131;
int main(){
    int n,q;
    string s;
    cin>>n>>q>>s;
    for(int i=0;i<n;i++){
        ull h=0;
        for(int j=0;j<10&&i+j<n;j++){
            h=h*B+s[i+j];
            ++mp[j+1][h];
        }
    }
    while(q--){
        cin>>s;
        ull h=0;
        for(char ch:s)
            h=h*B+ch;
        printf("%d\n",mp[s.size()][h]);
    }
}

2、小红的魔法数组

小红有两个长度为\(n\)的数组，分别为\(a\)和\(b\)。她可以施展魔法，先选择—个实数\(mul\)，获得\(c\)数组，其中\(c_i = mul \times a_i+b_i\)，小红想知道，她能获得的数组\(c\)，最多有几个\(0\)。

输入

一行一个整数\(n\)，表示数组的长度。

一行\(n\)个整数\(a_i\)，表示数组\(a\)。

一行\(n\)个整数\(b_i\)，表示数组\(b\)。

\(1\le n\le 10^5\)
\(-10^9\le a_i,b_i\le 10^9\)

输出

输出个正整数，表示最多有几个\(0\)。

样例

输入：
4
2 4 6 7
1 2 3 4

输出：
3

提示：
选择mul=-0.5，得到c=[0,0,0,0.5]，有3个0。

解答

这道题分两种情况进行讨论。

如果\(a_i=0\)，那么是否\(c_i=0\)已经不需要考虑\(mul\)的值，它取决于是否\(b_i=0\)。因此，这种情况下，只需要统计\(b_i=0\)的个数即可。
如果\(b_i\neq 0\)，那么要令\(c_i=0\)，就必须有\(mul=-\dfrac{b_i}{a_i}\)。因此我们统计输入中有多少个相同的\(-\dfrac{b_i}{a_i}\)，并取出现次数最多的那个作为答案即可。需要注意的是，\(-\dfrac{b_i}{a_i}\)必须使用最简分数来表示，并且\(b_i>0\)，这样才能够确保将相同的\(-\dfrac{b_i}{a_i}\)统计起来；其次还要进行约分。

最终，只需要将上面的两种情况分别所求结果进行合并即可。

代码

from fractions import Fraction

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
z = []
cnt = 0
mp = {}
for i in range(n):
    if a[i] == 0:
        if b[i] == 0:
            cnt += 1
    else:
        f = Fraction(b[i], a[i])
        mp[f] = mp.get(f, 0) + 1
ans = max([0] + list(mp.values()))
print(ans + cnt)

3、小红的数组前缀或

小红拿到了\(3\)个数组，她准备各取一个前缀（前缀的长度可以是\(0\)），总共取\(k\)个数。小红希望最终这\(k\)个数的按位或尽可能大。请你帮帮小红。

注：按位或指二进制上每一位取或运算，例如\(3\)的二进制表示是\((0011)_2\)，\(9\)的二进制表示是\((1001)_2\)，那么\(3\text{ or }9=(1011)_2=11\)

输入

第一行输入两个正整数\(n\)和\(k\)。

接下来的三行，每行输入\(n\)个整数\(a_i\)，分别代表一个数组。

\(1\le n\le 10^5\)
\(1\le k\le 3\cdot n\)
\(0\le a_i \le 10^9\)

输出

一个整数，代表最终的最大答案。

样例

输入：
4 2
1 2 3 4
2 2 3 4
4 2 3 4

输出：
6

提示：
第一个数组取的前缀长度是0，第二个数组取的前缀长度是1，第三个数组取的前缀长度是1，最终的或运算的答案是2 or 4 = 6。

输入：
4 4
1 2 3 4
2 2 3 4
4 2 3 4

输出：
7

提示：
第一个数组取的前缀长度是3，第二个数组取的前缀长度是0，第三个数组取的前缀长度是1，最终的或运算的答案是3 or 4 = 7。

解答

令\(\displaystyle{s_{m,i}=\text{or}_{j=1}^i a_{m,j},s_{m,0}=0}\)表示第\(m\)个数组\(a_k\)的前缀或。

对于每一个数组，虽然它有\(n\)个数，也就是说有\(n+1\)个决策，我们考虑对这些决策进行压缩。

我们可以发现这个决策\(s_{m,i}\)是非常有趣的。观察序列\(s_m=[s_{m,0},s_{m,1},\dots,s_{m,n}]\)，可以发现它是单调递增的。并且，按照或运算的性质，在这个计算\(s_{m,i}\)过程中，这些数中的每一个二进制位都会从\(0\)置成\(1\)，而不会从\(1\)置成\(0\)。由于\(10^9<2^{30}\)，因此这个序列是由最多\(31\)个不同的数（包括\(0\)）重复多次，一段段连续的数组成的。

由于我们希望效果最优化，因此在相同的结果的基础上，我们选择最少的那个数即可。按照上面的结论，我们对每个决策压缩成一个二元组决策数组\((c_{m,j},f_{m,j})\)，表示选择数组\(m\)的前\(c_{m,j}\)个数才能有前缀或\(f_{m,j}\)。这些决策数组的长度不会超过\(31\)。

我们将这些决策一个个枚举进行组合，只需要满足条件的就进行组合，并取最大值。因此，这题的时间复杂度为\(O(n+\log^3 M)\)，其中\(M\)是这\(3\)个数组中所有数的最大值。

代码

# include <bits/stdc++.h>
# define pi pair<int,int>
using namespace std;
const int N=100004;
int s[4][N],n,c;
vector<pi>pa[4];
int main(){
    scanf("%d %d",&n,&c);
    for(int i=1;i<=3;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&s[i][j]);
            s[i][j]|=s[i][j-1];
        }
        int pre=-1;
        for(int j=0;j<=n;j++){
            if(s[i][j]!=pre){
                pre=s[i][j];
                pa[i].push_back(pi(j,s[i][j]));
            }
        }
    }
    int ans=0;
    for(auto &[c1,v1]:pa[1])
        for(auto &[c2,v2]:pa[2])
            for(auto &[c3,v3]:pa[3])
                if(c1+c2+c3<=c)
                    ans=max(ans,v1|v2|v3);
    printf("%d\n",ans);
}

4、小红的字符串拼接

小红有两个字符串\(s\)和\(t\)，每次可以对\(s\)分割成\(s_1+s_2\)，然后拼接成新的字符串\(s_2+s_1\)。

例如字符串"abcd"可以分割成"ab"和"cd"，然后拼接成"cdab"。

小红想知道恰好进行\(k\)次操作，将\(s\)变成\(t\)的方案数，输出方案数模\(10^9+7\)的结果。

注意，分割的两个字符串都不能是空串。

输入

第一行一个仅包含小写字母的字符串s，第二行一个仅包含小写字母的字符串\(t\)，第三行一个正整数\(k\)。

\(1\le |s|,|t| \le 1000,1 \le k \le 1000\)。

输出

输出一行一个整数表示答案。

样例

输入：
abcde
cdeab
2

输出：
3

解答

令\(n\)表示字符串\(s\)的长度。

注：这道题是Leetcode 2851的原题，其题解提供了一种时间复杂度能达到\(O(n\log k)\)的做法，这里不讲述这种方法，因为需要两个模板才能完成。这里介绍的是一种更为直观的\(O(n^2+nk)\)的做法，同样足以通过本题。

我们可以发现，本质上每次删除和拼接是选择一个非空真后缀将其放到其余字符的前面。如果是一个一个字符这样操作，那么进行\(n\)次操作后，整个字符串就变成了原来的样子。

整个过程中，字符串最多只有\(n\)个不同的样子，我们用一个数\(j\)来表示当前字符串是将\(s\)经过若干操作后的样子，但其实，他只是将\(s\)的最后\(j\)个字符移动到前面\((0\le j<n)\)。

那么，我们令状态\(f(i,j)\)表示经过了\(i\)次操作后，字符串变成\(j\)的样子的操作的方案数是多少。那么我们可以写出\(f(i,j)\)的状态转移方程为：

\(f(i,j)= \left \{\begin{aligned} &1 & & \text{if}\quad i=0\land j=0 \\ &0 & & \text{if}\quad i=0\land j\neq 0 \\ &\sum_{h=0}^{n-1} f(i-1,h) -f(i-1,j) & & \text{if}\quad i>1 \\ \end{aligned}\right.\)

其中第三行的方程意思表示如下：由于我们每一次操作的选择都是令\(s_1,s_2\)均为非空的字符串，这意味着样子为\(j\)的字符串可以从\(0,1,2,\dots,j-1,j+1,j+2,\dots,n-1\)的样子转换而来，唯独除了\(j\)，因此后面需要减去\(f(i-1,j)\)的值。

在计算\(f(i,j)\)的时候，在同一行我们可以先预处理出\(\displaystyle{s=\sum_{h=0}^{n-1} f(i-1,h)}\)的值，再进行后续的计算，从而使转移达到了\(O(nk)\)的时间。

那么接下来开始判断\(s\)的哪些样子和字符串\(t\)相同，并将和\(t\)相同的那些样子添加到集合\(J\)中。我们可以暴力求出集合\(J\)，因此这道题的答案为\(\displaystyle{\sum_{j\in J}f(k,j)}\)。

代码

# include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N=1004;
ll f[N][N],mod=1e9+7;
int vis[N];
int main(){
    string s,t;
    int k;
    cin>>s>>t>>k;
    int n=s.size();
    for(int i=0;i<n;i++){
        if(s==t) vis[i]=1;
        s=s.substr(n-1)+s.substr(0,n-1);
    }
    f[0][0]=1;
    for(int i=1;i<=k;i++){
        ll w=0;
        for(int j=0;j<n;j++)
            w=(w+f[i-1][j])%mod;
        for(int j=0;j<n;j++){
            f[i][j]=(w-f[i-1][j]+mod)%mod;
        }
    }
    ll ans=0;
    for(int j=0;j<n;j++)
        if(vis[j])
            ans=(ans+f[k][j])%mod;
    printf("%lld\n",ans);
}