9.22腾讯音乐笔试题解

1，题意：给一个数字，每次操作能删一个数位，求最小操作次数使得数字变成5的倍数

思路：从低位删到高位，贪心即可

2，题意：给n棵二叉树，每次操作选树A和树B，把B的根拼到A的某个叶子的左/右儿子上，现在不限操作数，要让最后拼成的树的高度最高，求方案数，模1e9+7，总节点数<=2e5

思路：首先预处理出每颗数的深度最大叶子数量，假设预处理出来数组a，a[i]表示第i棵树的最深叶子数。

先给结论：

怎么思考呢？最后一次操作后，最终在底部的树，它的最深叶子数是对答案是没有贡献的，因为没有东西会继续拼在它下面。

固定住，最底部的树，我们发现，不管上面树拼的顺序是怎么样的（树1+树2+底部树 或者 树2 + 树1 + 底部树），每种顺序的贡献都是

2的幂是因为每次拼接都可以拼在左右儿子，(n-1)!是排列数，S/a[i]是叶子数对方案的贡献。

于是只要枚举底部树就好，也就是

3，题意：给一个长n的目标字符串T ，一开始我们有一个空串S，每次操作可以对S末尾添加任意字符或者S添加一个S的子串，求达成T的操作方案数，模1e9+7，n<=300

思路：设dp[i]表示达成T前i个字符的操作方案数，其中cnt表示j~i子串在S中的数量，对于cnt的计算暴力匹配就行了，长度才300

最后答案dp[n]