腾讯音乐 秋招 2023.09.06 机试题目与题解
1、小红的完美数
小红定义一个数为“完美数”,当且仅当该数仅有一个非零数字。例如\(5000,4,1,10,200\)都是完美数。
小红拿到了一个大小为\(n\)的数组,她希望选择两个元素,满足它们的乘积为完美数。
小红想知道,共有多少种不同的取法?
数据范围:
- \(1 \le n \le 2000\)
- \(1 \le a_i \le 10^9\)
样例
1 | 输入: |
解答
暴力地取出每一对组合,然后将它们相乘后并连续除\(10\),直到不能再除\(10\)为止,判断剩下的数是否小于\(10\)即可。
代码
1 |
|
2、小红的red
子序列
小红定义一个字符串是可爱串,当且仅当该字符串包含子序列"red"
,且不包含子串"red"
。
我们定义子序列为字符串中可以不连续的一段,而子串则必须连续。例如rderd
包含子序列"red"
,且不包含子串"red"
,因此该字符串为可爱串。
小红想知道,长度为\(n\)的、仅由'r', 'e', 'd'
三种字母组成的字符串中,有多少是可爱串?答案请对\(10^9+7\)取模。
数据范围:\(1\le n\le 10^5\)
样例
1 | 输入: |
解答
本题也是一道动态规划题目。按假设字符串\(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 |
|
3、小红的好二叉树
小红定义一个二叉树为“好二叉树”,当且仅当该二叉树所有节点的孩子数量为偶数(\(0\)或者\(2\))。
小红想知道,\(n\)个节点组成的好二叉树,共有多少种不同的形态?答案请对\(10^9+7\)取模。
- \(1\le n\le 3000\)
样例
1 | 输入: |
第一个样例两种形态的树如下:
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 |
|