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

发表于 2023-09-07 更新于 2023-09-12 分类于笔试阅读次数：本文字数： 2.5k 阅读时长 ≈ 2 分钟

1、小红的完美数

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

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

小红想知道，共有多少种不同的取法？

数据范围：

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

样例

输入：
[25, 2, 1, 16]

输出：
3

解答

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

代码

# 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\)

样例

输入：
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)}\)。

代码

# 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\)

样例

输入：
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\)。

代码

# 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];
    }
};

1、小红的完美数

样例

解答

代码

2、小红的red子序列

样例

解答

代码

3、小红的好二叉树

样例

解答

代码

2、小红的`red`子序列