首页 > 其他分享 >Count of Integers

Count of Integers

时间:2023-06-04 16:56:58浏览次数:51  
标签:Count Integers num1 min text sum num max

Count of Integers

You are given two numeric strings num1 and num2 and two integers max_sum and min_sum. We denote an integer x to be good if:

  • num1 <= x <= num2
  • min_sum <= digit_sum(x) <= max_sum.

Return the number of good integers. Since the answer may be large, return it modulo 109 + 7.

Note that digit_sum(x) denotes the sum of the digits of x .

Example 1:

Input: num1 = "1", num2 = "12", min_num = 1, max_num = 8
Output: 11
Explanation: There are 11 integers whose sum of digits lies between 1 and 8 are 1,2,3,4,5,6,7,8,10,11, and 12. Thus, we return 11.

Example 2:

Input: num1 = "1", num2 = "5", min_num = 1, max_num = 5
Output: 5
Explanation: The 5 integers whose sum of digits lies between 1 and 5 are 1,2,3,4, and 5. Thus, we return 5.

Constraints:

  • 1 <= num1 <= num2 <= 1022
  • 1 <= min_sum <= max_sum <= 400 

 

解题思路

  很经典的数位dp。现在要求的是在$[\text{num1}, \text{num2}]$范围内的数字中,有多少个数字的各位之和在$[\text{max_sum}, \text{min_sum}]$范围内。为此我们可以先求出$0 \sim \text{num2}$中满足各位之和在$[\text{max_sum}, \text{min_sum}]$范围内的数字个数,记作$b$。再求出$0 \sim \text{num1}-1$中满足各位之和在$[\text{max_sum}, \text{min_sum}]$范围内的数字个数,记作$a$。那么答案就是$b-a$。

  而对于任意数字$x$,如何求出$0 \sim x$中满足各位之和在$[\text{max_sum}, \text{min_sum}]$范围内的数字个数呢?一样用到数位dp。先求出$0 \sim x$中各位之和不超过$\text{max_sum}$的数有多少个,记作$a_2$。再求出$0 \sim x$中各位之和不超过$\text{min_sum} - 1$的数有多少个,记作$a_1$。那么$0 \sim x$中满足各位之和在$[\text{max_sum}, \text{min_sum}]$范围内的数字个数就是$a_2 - a_1$。

  因此最终答案就是$(b_2 - b_1) - (a_2 - a_1)$。

  定义状态$f(i,j,k)$表示所有长度为$i$,且最高位为数字$j$,各位之和不超过$k$的数的集合。根据次高位是哪个数字进行状态划分,因此状态转移方程就是$$f(i,j,k) = \sum\limits_{u=0}^{9}{f(i-1,u,k-j)}$$

  这里用递推的方式来dp。现在求$0 \sim \text{num}$中各位之和不超过$x$的数有多少个。从最高位往底位枚举(从$0$开始),假设当前枚举到第$i$位数字$\text{num}[i]$,并且第$0 \sim i-1$位的数字之和为$s$,那么先累加所有长度为$n-i$,第$i$位是$0 \sim \text{num}[i] - 1$且各位之和为$x - s$的数的个数,即$\sum\limits_{j=0}^{\text{num}[i]-1}{f(n-i,j,x-s)}$。以此类推。当在枚举的过程中发现$s > x$,那么直接返回答案即可。如果枚举完最后的$s \leq x$,那么答案加$1$,因为$\text{num}$也满足要求。

  这样做的计算量为$n \times m \times 10^2$,其中$n$是数字的位数,$m$是各位之和的最大值。如果这样做的话在leetcode会超时,估计卡常了。注意到$n$最大为$23$,因此$m$最大为$23 \times 9 < 400$(所有的数都是$9$的情况),为此我们可以让$m$放小,令$m = \min \{ m, 9 \times n \}$,这样就可以减低计算量了,变成$n^2 \times 10^3$。

  AC代码如下:

 1 class Solution {
 2 public:
 3     int mod = 1e9 + 7;
 4     
 5     int count(string num1, string num2, int min_sum, int max_sum) {
 6         function<int(string, int)> get = [&](string s, int x) {
 7             if (s == "0") return 1; // 特判0的情况
 8             int n = s.size();
 9             x = min(x, 9 * n);
10             vector<vector<vector<int>>> f(n + 1, vector<vector<int>>(10, vector<int>(x + 1)));
11             for (int i = 0; i <= 9; i++) {
12                 for (int j = i; j <= x; j++) {
13                     f[1][i][j]++;
14                 }
15             }
16             for (int i = 2; i <= n; i++) {
17                 for (int j = 0; j <= 9; j++) {
18                     for (int k = j; k <= x; k++) {
19                         for (int u = 0; u <= 9; u++) {
20                             f[i][j][k] = (f[i][j][k] + f[i - 1][u][k - j]) % mod;
21                         }
22                     }
23                 }
24             }
25             int ret = 0, sum = 0;
26             for (int i = 0; i < n; i++) {
27                 int t = s[i] - '0';
28                 for (int j = 0; j < t; j++) {
29                     ret = (ret + f[n - i][j][x - sum]) % mod;
30                 }
31                 sum += t;
32                 if (sum > x) break; // 前面各位之和已经超过x
33             }
34             if (sum <= x) ret++;    // num满足各位之和不超过x
35             return ret;
36         };
37         // 因为要求num1-1,因此对num1进行减1
38         reverse(num1.begin(), num1.end());
39         for (int i = 0; i < num1.size(); i++) {
40             if (num1[i] - 1 >= '0') {   // 不需要借位
41                 num1[i]--;
42                 break;
43             }
44             num1[i] = '9';  // 借位
45         }
46         while (num1.size() > 1 && num1.back() == '0') { // 把前导0删除,同时要至少保留一位数
47             num1.pop_back();
48         }
49         reverse(num1.begin(), num1.end());
50         return ((get(num2, max_sum) - get(num2, min_sum - 1) + mod) % mod - (get(num1, max_sum) - get(num1, min_sum - 1) + mod) % mod + mod) % mod;
51     }
52 };

标签:Count,Integers,num1,min,text,sum,num,max
From: https://www.cnblogs.com/onlyblues/p/17455885.html

相关文章

  • 实验 透视表 计数 len np.count_nonzero 正确与否
    实验透视表计数 len np.count_nonzero正确与否结果:len正确 np.count_nonzero错误结论:除去三行干扰行(原值均为缺失值)以外:未过账中,有1行无业务员名称无业务员名称中,有1行未过账即:未过账且无业务员名称有1行未过账且有业务员名称有57行已过账且无业务员名称有57行最......
  • pandas value_counts() 会忽略统计nan 但是不会忽略 true false
    pandasvalue_counts()会忽略统计nan 但是不会忽略truefalse'''每列包含多少项nan'''foriindf_2:print(df_2.loc[:,i].isna().value_counts())应用'''每列包含多少项nan'''dict_counts={}foriindf_2:......
  • 300iq Contest 2 C Counting Cactus
    这个数据范围显然是要状压的。考虑一个子集\(S\),钦定他的根是\(u\)该如何转移(设为\(f(u,S)\)):\(u\)会在若干个环中,还会有若个用一条边分割的子仙人掌。也就是若干子仙人掌拼起来。自然需要再设一个\(g(u,S)\)表示\(u\)为根,且\(u\)只包含在一个环或一条边中的方案数。......
  • Java多线程三(线程池执行完后再执行主线程)CountDownLatch
      我们在开发多线程的时候,有两种情况一种是我们处理好后,不用管结果。比如我需要查询某些数据然后存在数据库里。还有一种就是查询好数据(通过线程池),然后导出数据。这个就比较麻烦。因为我们要将数据通过多线程处理后,返回一个统一的结果。(由于多线程是在不同的时候执行数据),假如执......
  • D. The BOSS Can Count Pairs
    D.TheBOSSCanCountPairsYouaregiventwoarrays$a$and$b$,bothoflength$n$.Yourtaskistocountthenumberofpairsofintegers$(i,j)$suchthat$1\leqi<j\leqn$and$a_i\cdota_j=b_i+b_j$.InputEachtestcontainsmultipletest......
  • 5.5. Java并发工具类(如CountDownLatch、CyclicBarrier等)
    5.5.1CountDownLatchCountDownLatch是一个同步辅助类,它允许一个或多个线程等待,直到其他线程完成一组操作。CountDownLatch有一个计数器,当计数器减为0时,等待的线程将被唤醒。计数器只能减少,不能增加。示例:使用CountDownLatch等待所有线程完成任务假设我们有一个任务需要三个子......
  • 「题解」ABC292G Count Strictly Increasing Sequences
    没一眼看出来还是拉了。考虑区间dp,\(f_{i,l,r}\)表示\([l,r]\)前\((i-1)\)位都相同,看后面\([i,n]\)位填数使得递增的方案数是多少。这样已经可以做了,但是还不够,要追求一下最简单的写法。想想,发现每次dp是要分为多个儿子乘起来,内部还要搞个dp。但可以改成每次两个儿子......
  • yulong-hids 规则引擎,目前看到就是正则表达式和count技术
    规则项目提供的默认规则太简单和宽泛了,甚至包含一些错误,比如:有些不太精确,比如:另外规则引擎的匹配算法没有做优化,规则或者事件一旦多起来,server的负载会很高有些太宽泛导致误报非常高:agent在测试机才装2天就有近6w条告警,这是无法运营的,当然,规则支持细粒度控制(开关)还是很不错的3、功......
  • ef/efcore/sqlsugar group by字段 orderby count的写法
    ef/efcore:以datatype字段分组后按count倒序:varlist=db.table1.GroupBy(x=>x.DataType).Select(group=>new{group.Key,Count=group.Count()}).OrderByDescending(x=>x.Count).ToList(); sqlsugar:sqlsugargroupBy的返回值不是IQueryable<IGrouping<key,model>......
  • np.bincount方法
    官方文档out=np.bincount(x[,weights,minlength])该函数用于统计输入数组内每个数值出现的次数,输出数组中的索引值对应的是输入数组中的元素值,若输入数组中的某个数值出现了一次,则输出数组对应索引值上的数加一某个数值n在输入数组x中每出现1次,则输出o内的o[n]+=1参数x......