腾讯音乐 秋招 2023.09.06 机试题目与题解

1、小红的完美数

小红定义一个数为“完美数”,当且仅当该数仅有一个非零数字。例如\(5000,4,1,10,200\)都是完美数。

小红拿到了一个大小为\(n\)的数组,她希望选择两个元素,满足它们的乘积为完美数。

小红想知道,共有多少种不同的取法?

数据范围:

  • \(1 \le n \le 2000\)
  • \(1 \le a_i \le 10^9\)

样例

1
2
3
4
5
输入:
[25, 2, 1, 16]

输出:
3

解答

暴力地取出每一对组合,然后将它们相乘后并连续除\(10\),直到不能再除\(10\)为止,判断剩下的数是否小于\(10\)即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# include <bits/stdc++.h>
typedef long long ll;
using namespace std;

class Solution{
public:
ll check(ll x){
for(;x>=10&&x%10==0;x/=10);
return x<10;
}
int solve(vector<int> &a){
int ans=0;
for(int i=0;i<a.size();i++){
for(int j=0;j<i;j++){
if(check(1ll*a[i]*a[j])){
++ans;
}
}
}
return ans;
}
};

2、小红的red子序列

小红定义一个字符串是可爱串,当且仅当该字符串包含子序列"red",且不包含子串"red"

我们定义子序列为字符串中可以不连续的一段,而子串则必须连续。例如rderd包含子序列"red",且不包含子串"red",因此该字符串为可爱串。

小红想知道,长度为\(n\)的、仅由'r', 'e', 'd'三种字母组成的字符串中,有多少是可爱串?答案请对\(10^9+7\)取模。

数据范围:\(1\le n\le 10^5\)

样例

1
2
3
4
5
6
7
8
输入:
4

输出:
3

提示:
"reed"、"rerd"、"rded"

解答

本题也是一道动态规划题目。按假设字符串\(t=\texttt{red}\)下标从\(0\)开始。照题目所给定的要求,我们能够设计如下状态:令\(f(i,j,k)(0\le i\le n,0\le j\le 3,0\le k\le 2)\)表示有多少个仅由'r', 'e', 'd'三种字母组成的字符串\(s\),满足以下条件:

  • \(s\)的长度为\(i\)
  • \(t\)的最长前缀是\(s\)的一个子序列,该最长前缀的长度为\(j\)
  • \(t\)的最长前缀是\(s\)的一个后缀,该最长前缀的长度为\(k\)

注意,当\(k=3\)时,这是一个非法状态,因此我们不考虑这个状态,因为这个字符串已经存在一个子串\(t\)了,我们不从这些状态进行转移。

考虑当前状态\(f(i,j,k)\)。我们有\(3\)种不同的策略进行转移:也就是在\(f(i,j,k)\)中的所有字符串添加\(3\)个不同的字母。我们考虑如下具体转移过程:

  • 对于\(j\),我们现在需要添加一个字母\(t_0,t_1\)或者是\(t_2\),假设我们选择字母\(t_d\)进行转移。如果\(d=j\),那么说明原本的字符串\(s\)可以进一步匹配\(t\)的前缀,从而从\(j\)转移到\(j'=j+1\),否则不会有任何变化,从\(j\)转移到\(j'=j\)

  • 对于\(k\),我们现在需要添加一个字母\(t_0,t_1\)或者是\(t_2\),假设我们选择字母\(t_d\)进行转移。如果\(d=k\),那么说明填充了这个字符后,\(s\)的后缀可以匹配多\(t\)的后一个字母,此时从\(k\)转移到\(k'=k+1\),需要注意的是,这个转移只有在\(k<2\)的时候才成立;否则,那么这个子串的匹配过程就被破坏,如果\(d=0\),那么说明目前还能匹配到第\(1\)个字母,此时从状态\(k\)转移到状态\(k'=1\),不然这个匹配过程彻底被破坏,需要从头开始匹配,因此此时从\(k\)转移到\(k'=0\)

因此,对于所有\(f(i,j,k)\)和对应的\(d\),都有:

\(f(i,j,k)\rightarrow f(i+1,j',k')\)

更具体的,以下是计算\(j'=J(j,d),k'=K(k,d)\)的两个矩阵:

\(\begin{array}{cc} &d\\ j&\begin{bmatrix} 1&0&0\\ 1&2&1\\ 2&2&3\\ 3&3&3\\ \end{bmatrix} \end{array} \begin{array}{cc} &d\\ \qquad k&\begin{bmatrix} 1&0&0\\ 0&2&0\\ 0&0&-\\ \end{bmatrix} \end{array}\)

因此按照题目的要求,最终答案为\(\displaystyle{\sum_{k=0}^2 f(n,3,k)}\)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# include <bits/stdc++.h>
typedef long long ll;
using namespace std;

class Solution{
public:
int mod=1e9+7;
void add(int &x,int y){
x+=y;
if(x>=mod) x-=mod;
}
int f[100004][4][3];
int solve(int n){
f[0][0][0]=1;
for(int i=0;i<n;i++){
for(int j=0;j<=3;j++){
for(int k=0;k<=2;k++){
for(int d=0;d<=2;d++){
int nj=(j==d?j+1:j);
int nk=(k==d?k+1:0);
if(nk==0&&d==0) nk=1;
add(f[i+1][nj][nk],f[i][j][k]);
}
}
}
}
int ans=0;
for(int k=0;k<=2;k++)
add(ans,f[n][3][k]);
return ans;
}
};

3、小红的好二叉树

小红定义一个二叉树为“好二叉树”,当且仅当该二叉树所有节点的孩子数量为偶数(\(0\)或者\(2\))。

小红想知道,\(n\)个节点组成的好二叉树,共有多少种不同的形态?答案请对\(10^9+7\)取模。

  • \(1\le n\le 3000\)

样例

1
2
3
4
5
6
7
8
9
10
11
输入:
5

输出:
2

输入:
7

输出:
5

第一个样例两种形态的树如下:

graph TD
  1((" "));2((" "));3((" "));4((" "));5((" "));
  A((" "));B((" "));C((" "));D((" "));E((" "));
  1---2;1---3;
  2---4;2---5;
  A---B;A---C;
  C---D;C---E;

解答

不难发现这道题使用动态规划即可简单求出。令\(f(n)\)表示\(n\)个节点的满二叉树个数。那么可以写出\(f(n)\)的状态转移方程为:

\(f(n)= \left \{\begin{aligned} &1 & & \text{if}\quad n=1 \\ &\sum_{i=1}^{i-2} f(i)\cdot f(n-1-i) & & \text{if}\quad n>1 \\ \end{aligned}\right.\)

其中按照定义,仍然可以知道这棵树的左子树和右子树仍然是满二叉树,因此它们之间的形状是独立的,可以随意取出。如果左子树有\(i\)个节点,那么右子树就有\(n-1-i\)个节点。其中,\(1\le i<n-1\),因为需要确保右子树非空。

可以发现,当\(n\)为偶数的时候,\(f(n)=0\)。因为\(f(2)=0\),按照上面的状态转移方程可以得知,如果\(n\)为偶数,那么其中一棵子树的节点数必定为偶数,因此按照归纳法可以知道\(f(n)=0\)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# include <bits/stdc++.h>
typedef long long ll;
using namespace std;

class Solution{
public:
int mod=1e9+7;
int solve(int n){
vector<ll>f(n+1);
f[1]=1;
for(int i=2;i<=n;i++){
for(int j=1;j+1<i;j++){
f[i]=(f[j]*f[i-j-1]+f[i])%mod;
}
}
return f[n];
}
};
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
Ujimatsu Chiya 微信 微信
Ujimatsu Chiya 支付宝 支付宝