8.27 字节跳动笔试

第3题有如下规律： 从0到(10**k)-1（即所有k位数字）的和为：45*k*10**(k-1)。 对于位数n，分为奇数位a和偶数位b（n=a+b），分别用上面式子求一下在相乘即可 10**k用二分求解，基本题型了。

第四题用小于r+1的减去小于l的，对于小于n的，通过计算最大为1到9的数字的数量去算权重，数字数量就用容斥原理和dp了

最后一题同来不及，感觉应该是下面这样。 先打表 dp[n][i] 表示从0到 10**n-1 的数里答案为i的数量。 然后对于数字num进行dfs 令a为num的首位，b为去掉首位的剩余值（例如num=201, a=2, b=1），l为数字长度， dfs中分两部分： def dfs(num): count = [0] * 10 count2 = dfs(b) for digit in range(10): for i in range(a): count[max(digit, i)] += dp[l-1][digit] count[max(digit, a)] += count2[digit] return count 最后把首尾区间相减算总和。

第三题： 你考虑因式分解，就变成了奇数的所有权值和 * 偶数的所有权值和。 然后对于奇数的所有权值和你考虑每一位的贡献是(1+2...+9) * 10^{len - 1} * len 第四题： 可以通过[1...r] - [1..l-1]得到[l,r]，然后对于[1...r]，你枚举所有数的最大值x从1到9，这就变成了问你1到r里面所有数<=x有多少方案，最大值=x，就是<=x减去<=x-1，用数位dp计算就可以了。代码如下： https://pastebin.ubuntu.com/p/VTW4fkggKG/

第四题有AC的吗？我记得题目中数字会到10**18那么大，这样的话O（n）的复杂度会超时吧。

第四题同有思路来不及写

有思路运行不出来

四题90 25 25 25 😅