题意

求区间 \([L,R]\) 中数位包含 \(x\) 个 \(4\) 和 \(y\) 个 \(7\) 的第 \(k\) 大的数。

分析

第 \(k\) 大的数,考虑二分。

如果每次都是暴力跑数位dp的话,复杂度是 \(O(T*n*18*x*y)\) ,最坏情况下会 TLE 。

所以需要预处理 \(f[i][j][k]\) ,表示 \(i\) 位数包含 \(x\) 个 \(4\) 和 \(y\) 个 \(7\) 的个数。

然后对于每一个数,直接利用 dfs 逼近一下就好了,这样的时间复杂度是 \(O(T*n*18*18+18*x*y)\) 。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注