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]