字节跳动秋招 2023.08.27 机试题目与题解

发表于 2023-08-27 更新于 2023-09-07 分类于笔试阅读次数：本文字数： 4.5k 阅读时长 ≈ 4 分钟

1、小红的字符串相似度

假设字符串\(s\)和\(t\)的最长相同前缀的长度是\(a\)，最长相同后缀的长度是\(b\)。

小红认为字符串\(s\)和\(t\)的相似度是\(a \times b\)。

现在小红想进行最多一次修改，\(s\)的一个小写字母改成另一个小写字母，使得相似度尽量大。

问相似度最大是多少?

输入

第一行输入一个仅包含小写字母的字符串\(s\)。

第二行输入一个仅包含小写字母的字符串\(t\)。

\(1 \le \text{len}(s),\text{len}(t) \le 10^5\)

输出

输出一个整数。

样例

输入：
abc
abba

输出：
4

提示：
将s串的第三个字符改成'a'，s串变成"aba"。最长相同前经和后缀分别是"ab"和"ba"。

解答

首先一个候选答案就是不进行操作。

假设现在字符串\(s,t\)的最长公共前缀长度为\(a\)，最长公共后缀的长度为\(b\)。如果想要通过一次操作使得结果更优，那么要么让\(a\)变大，要么让\(b\)变大。

如果\(a<\min\{\text{len}(s),\text{len}(t)\}\)，怎么才能够让\(a\)继续变大呢？把\(s\)的第\(a+1\)个字符\(s_{a+1}\)变成\(t_{a+1}\)就能让\(a\)继续变大。如果对\(s\)的前\(a\)个字符进行，那么只会让\(a\)值更小（因为它们已经相等）；如果对\(s\)的后面\(\text{len}(s)-a-1\)个字符进行操作，那么\(a\)值不会变化。

类似的，如果\(b<\min\{\text{len}(s),\text{len}(t)\}\)，操作和上面的情况相似。

最终在这\(3\)个答案中取最优即可。

代码

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

const int N=100004;
char s[N],t[N];
int n,m;
ll cal(){
    int p,q;
    for(p=0;1+p<=n&&1+p<=m&&s[1+p]==t[1+p];++p);
    for(q=0;n-q>0&&m-q>0&&s[n-q]==t[m-q];++q);
    return 1ll*p*q;
}
int main(){
    scanf("%s %s",s+1,t+1);
    n=strlen(s+1),m=strlen(t+1);
    ll ans=cal();
    int p,q;
    for(p=0;1+p<=n&&1+p<=m&&s[1+p]==t[1+p];++p);
    if(1+p<=n&&1+p<=m){
        char ch=s[1+p];
        s[1+p]=t[1+p];
        ans=max(ans,cal());
        s[1+p]=ch;
    }
    for(q=0;n-q>0&&m-q>0&&s[n-q]==t[m-q];++q);
    if(n-q>0&&m-q>0){
        char ch=s[n-q];
        s[n-q]=t[m-q];
        ans=max(ans,cal());
        s[n-q]=ch;
    }
    printf("%lld\n",ans);
}

2、小红的颜色矩阵

小红拿到了一个矩阵，矩阵中格子的颜色为红色、绿色或者蓝色。现在小红有\(q\)次询问，每次询问一个子矩阵，希望你输出这个子矩阵的颜色种类数。

输入

第一行输入两个正整数\(n,m\)，代表矩阵的行数和列数。

接下来的\(n\)行，每行输入\(m\)个字符串 (字符串一定是"red"、"green"、"blue"中的一种，代表格子的颜色）

接下来的一行，输入一个正整数\(q\)，代表小红的询问次数。

接下来的\(q\)行，每行输入四个正整数\(x_1,y_1,x_2,y_2\)代表询问的子矩阵左上角为第\(x_1\)行第\(y_1\)列，右下角为第\(x_2\)行第\(y_2\)列。

\(1 \le n,m \le 500\)
\(1 \le q \le 50000\)
\(1 \le x_i \le x_2\le n\)
\(1 \le y_i \le y_2\le m\)

输出

输出\(q\)行，每行输出一个整数，代表颜色的数量。

样例

输入：
3 3
red blue blue
red blue blue
green green green
2
1 2 2 3
2 1 3 2

输出：
1
3

解答

可以发现，这道题的颜色数只有\(3\)种。因此大致思路是：对于每种颜色\(c\in\{r,g,b\}\)，需要以很短的时间内判断\(c\)是否在一个子矩阵中，然后再按照判断结果统计颜色数即可。

因此，这题使用二维前缀和就可以完成了。

可以构造出三个矩阵\(v_r,v_g,v_b\)。如果格子\((x,y)\)填充的是颜色\(c\)，那么\(v_c[x,y]=1\)，否则\(v_c[x,y]=0\)。

接下来构造\(v_c\)的二维前缀和\(s_c\)，它被定义成\(\displaystyle{s_{c}[x,y]=\sum_{i=1}^x\sum_{j=1}^y v_c[i,j]}\)，其中\(v_c[0,\cdot]=v_c[\cdot,0]=0\)，对于\(i\in [1,n],j\in [1,n]\)，\(s_c[x,y]\)可以通过下列递推式进行求出：

\[s_c[x,y]=s_c[x-1,y]+s_c[x,y-1]-s_c[x-1,y-1]+v_c[x,y]\]

通过画图（或使用容斥原理）能够发现，上面的式子\(s_c[x,y]\)确实不重不漏地（正确地）求出\(s_c[x,y]\)的值。

对于左上角为第\(x_1\)行第\(y_1\)列，右下角为第\(x_2\)行第\(y_2\)列的子矩阵，同样画图（或使用容斥原理）可以发现，下面式子可以正确地计算出这个子矩阵中所有元素的和：

\[t_c(x_1,y_1,x_2,y_2)=s_c[x_2,y_2]-s_c[x_1-1,y_2]-s_c[x_2,y_1-1]+s_c[x_1-1,y_-1]\]

因此如果\(t_c(x_1,y_1,x_2,y_2)>0\)，意味着\(c\)在这个子矩阵中。最终由此我们可以以\(O(1)\)的时间处理每个询问。

代码

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

const int N=504;
int s[3][N][N],n,m;
int main(){
    cin>>n>>m;
    string t;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>t;
            int f=(t[0]=='r'?0:t[0]=='g'?1:2);
            s[f][i][j]=1;
        }
    }
    for(int c=0;c<3;c++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                s[c][i][j]+=s[c][i-1][j]+s[c][i][j-1]-s[c][i-1][j-1];
            }
        }
    }
    int xa,ya,xb,yb,q;
    cin>>q;
    while(q--){
        cin>>xa>>ya>>xb>>yb;
        --xa;--ya;
        int cnt=0;
        for(int c=0;c<3;c++){
            if(s[c][xb][yb]-s[c][xa][yb]-s[c][xb][ya]+s[c][xa][ya]>0){
                ++cnt;
            }
        }
        printf("%d\n",cnt);
    }
}

3、小红的数字串权值

小红定义一个数字串的权值为: 奇数位的和乘以偶数位的和。

奇数位指下标是奇数的位置，偶数位指下标是偶数的位置，下标从\(1\)开始。

例如数字串"114514"，奇数位的和\(1+4+1=6\)，偶数位的和\(1+5+4=10\)。

现在小红想知道所有长度为\(n\)的数字串（可以有前导零），它们的权值和是多少？

输入

第一行输入一个整数

\(2\le n \le 10^9\)

输出

输出一个非负整数，表示权值和。答案可能太大，请对\(10^9+7\)取模后再输出。

样例

输入：
3

输出：
40500

解答

需要注意的是，偶数位所有数字的取法和奇数位的所有数字的取法都是相互独立的。

因此，令\(f(n)\)表示所有带前导\(0\)的\(n\)为整数的数字之和。如果一个数有\(n\)位，那么奇数位有\(\lfloor n/2\rfloor\)位，偶数位有\(\lceil n/2\rceil\)位。可见偶数位的每一种取法和奇数位的每一种取法进行组合后，数位和再计算乘积，就得到了这\(n\)位整数中的每一个。因此最终答案为\(f(\lfloor n/2\rfloor)\cdot f(\lceil n/2\rceil)\)。

接下来计算\(f(n)\)。可见，这\(n\)位数字的地位都是平等的，因此考虑其中一个数字的贡献，再将它的贡献复制\(n\)份即可。不失一般性，考虑最高位的取法，可见，有\(10^{n-1}\)个\(n\)位数，其最高位为\(0\)，因为剩下的\(n-1\)位数都可以随意取值；类似的，有\(10^{n-1}\)个\(n\)位数，其最高位为\(1\)……有\(10^{n-1}\)个\(n\)位数，其最高位为\(9\)。因此，最终最高位贡献的答案值是\((0+1+\dots+9)\cdot 10^{n-1}=45\cdot 10^{n-1}\)。

因此有\(f(n)=45n\cdot 10^{n-1}\)。

那么，原题目的答案为

\(\begin{aligned} &f(\lfloor n/2\rfloor)\cdot f(\lceil n/2\rceil)\\ =&45\cdot \lfloor n/2\rfloor\cdot 10^{\lfloor n/2\rfloor-1}\cdot 45\cdot \lceil n/2\rceil\cdot 10^{\lceil n/2\rceil-1}\\ =&45^2\cdot \lfloor n/2\rfloor\cdot\lceil n/2\rceil\cdot 10^{n-2} \end{aligned}\)

代码

n = int(input())
mod = 10 ** 9 + 7
ans = (n // 2) * (n - n // 2) * 45 ** 2 * pow(10, n - 2, mod) % mod
print(ans)

4、小红的最大数位

小红定义\(f(x)\)为最大数位的值。

例如:

\(f(5271) = \max(5,2,7,1) = 7\)

\(f(115414) = \max(1,1, 4, 5, 1, 4) = 5\)

小红想求出\(\displaystyle{\sum_{i=l}^r f(i)}\)。对\(10^9+7\)取模再输出。

输入

输入两个整数\(l,r\)。

\(1 \le l\le r \le 10^{18}\)

输出

输出一个非负整数，表示答案。

样例

输入：
9 10

输出：
10

提示：
f(9) + f(10) = 10

输入：
1 101

输出：
617

解答

这道题是一道数位动态规划题目。可见这里求的是一个区间内所有元素的\(f\)函数之和。为了方便，我们将它们转化成是两个前缀和的相减\(s(r)-s(l-1)\)，其中\(\displaystyle{s(n)=\sum_{i=1}^n f(i)}\)。

我们把这个问题简单化了一步，接下来是求解\(s(n)\)。一种最为简单的思路是：统计\(1\sim n\)中有多少个数的数位最大值是\(d\)，然后对它们的所有值进行统计求和即可。更形式化的说，令\(c(n,d)\)表示\(1\sim n\)中有多少个数的数位最大值是\(d\)，那么就可以得到\(\displaystyle{s(n)=\sum_{i=0}^9 c(n,i)\cdot i}\)。

接下来需要求解\(c(n,i)\)，其中\(i=0,1,\dots,9\)。这个时候就需要使用数位动态规划上场来进行求解。

将十进制数\(n\)看作是一个长度为\(m\)的数位字符串\(d_0d_1\dots,d_{m-1}\)，其中\(d_0\)为最高位，\(d_{m-1}\)为最低位。我们考虑从高位到低位填充每个数字。需要注意的是，由于前导\(0\)的存在不会影响这个数的数位最大值，因此为了方便我们将所有数包含了前导\(0\)后在进行计算。

令状态\(f(i,j,0)(0\le i<m,0\le j\le 10)\)表示对一个\(m\)位数\(b\)填充了这些位\(b_0,b_1,\dots ,b_i\)后，满足如下条件的填法数量：

十进制数\(b_0b_1\dots b_i\)严格小于十进制数\(d_0d_1\dots d_i\)。
并且\(b\)的这第\(0\sim i\)的最大数位为\(j\)。

状态\(f(i,j,1)\)的定义和上面的类似，只是从严格小于转换成了等于。

可见，对于状态\(f(i,j,1)\)，如果\(\displaystyle{j=\max_{k=0}^i\{ d_k\}}\)，那么\(f(i,j,1)=1\)，否则\(f(i,j,1)=0\)。

因此对于初值，有：

如果\(k<d_0\)，那么有\(f(0,k,0)=1\)；如果\(k=d_0\)，那么有\(f(0,k,1)=1\)。

对于状态\(f(i,j,0)\)，由于这里表示的所有填法中，已经小于\(d_0d_1\dots d_i\)，因此\(b_{i+1}\)可以随意填充。因此填充\(d=0,1\dots,9\)后，它将转移到如下状态：

\(f(i,j,0)\rightarrow f(i,\max\{j,d\},0)\)

对于状态\(f(i,j,1)\)，此时\(b_{i+1}\)不能随意填充，因为\(b_{i+1}\)不能填入超过\(a_{i+1}\)的数，因此如果填充\(d=0,1\dots,a_{i+1}-1\)后，它将转移到如下状态：

\(f(i,j,1)\rightarrow f(i,\max\{j,d\},0)\)

而如果填充\(d=a_{i+1}\)，它仍然是紧逼的，因此它将转移到如下状态：

\(f(i,j,1)\rightarrow f(i,\max\{j,a_{i+1}\},1)\)

最终，我们可以得到\(c(n,d)=f(m-1,d,0)+f(m-1,d,1)\)。然后按照上面的式子计算出\(s(n)\)即可。

代码

l, r = map(int, input().split())
mod = 10 ** 9 + 7


def solve(n):
    if n == 0:
        return [0] * 10
    a = list(map(int, str(n)))
    m = len(a)
    f = [[[0, 0] for _ in range(10)] for _ in range(m)]
    for d in range(a[0]):
        f[0][d][0] += 1
    f[0][a[0]][1] += 1
    for i in range(m - 1):
        digit = a[i + 1]
        for j in range(10):
            for d in range(10):
                f[i + 1][max(d, j)][0] += f[i][j][0]
            for d in range(digit):
                f[i + 1][max(d, j)][0] += f[i][j][1]
            f[i + 1][max(digit, j)][1] += f[i][j][1]
    return [u[0] + u[1] for u in f[-1]]


fl, fr = solve(l - 1), solve(r)
ans = sum(i * (fr[i] - fl[i]) for i in range(10)) % mod
print(ans)