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]
三环集团开奖34人在聊
查看7道真题和解析
投递美的集团等公司6个岗位 >