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

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=\mathtt{\text{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^{\prime }=j+1$，否则不会有任何变化，从 $j$ 转移到 $j^{\prime }=j$。

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

因此，对于所有 $f(i,j,k)$ 和对应的 $d$，都有：

$f(i,j,k)\to f(i+1,j^{\prime },k^{\prime })$

更具体的，以下是计算 $j^{\prime }=J(j,d),k^{\prime }=K(k,d)$ 的两个矩阵：

$\begin{array}{cc}& d\\ j& \left[\begin{array}{ccc}1& 0& 0\\ 1& 2& 1\\ 2& 2& 3\\ 3& 3& 3\end{array}\right]\end{array}\begin{array}{cc}& d\\ k& \left[\begin{array}{ccc}1& 0& 0\\ 0& 2& 0\\ 0& 0& -\end{array}\right]\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

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

解答

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

$f(n)=\{\begin{array}{rlrl}& 1& & \text{if}n=1\\ & \sum _{i=1}^{i-2}f(i)\cdot f(n-1-i)& & \text{if}n>1\end{array}$

其中按照定义，仍然可以知道这棵树的左子树和右子树仍然是满二叉树，因此它们之间的形状是独立的，可以随意取出。如果左子树有 $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];
    }
};