首页 > 其他分享 >Number of Beautiful Integers in the Range

Number of Beautiful Integers in the Range

时间:2023-08-20 16:49:18浏览次数:48  
标签:Beautiful Integers beautiful 10 int even Range odd 数位

Number of Beautiful Integers in the Range

You are given positive integers low, high, and k.

A number is beautiful if it meets both of the following conditions:

  • The count of even digits in the number is equal to the count of odd digits.
  • The number is divisible by k.

Return the number of beautiful integers in the range [low, high].

Example 1:

Input: low = 10, high = 20, k = 3
Output: 2
Explanation: There are 2 beautiful integers in the given range: [12,18]. 
- 12 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 3.
- 18 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 3.
Additionally we can see that:
- 16 is not beautiful because it is not divisible by k = 3.
- 15 is not beautiful because it does not contain equal counts even and odd digits.
It can be shown that there are only 2 beautiful integers in the given range.

Example 2:

Input: low = 1, high = 10, k = 1
Output: 1
Explanation: There is 1 beautiful integer in the given range: [10].
- 10 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 1.
It can be shown that there is only 1 beautiful integer in the given range.

Example 3:

Input: low = 5, high = 5, k = 2
Output: 0
Explanation: There are 0 beautiful integers in the given range.
- 5 is not beautiful because it is not divisible by k = 2 and it does not contain equal even and odd digits.

Constraints:

  • 0 < low <= high <= 109
  • 0 < k <= 20

 

解题思路

  一碰到数位dp就谔谔,昨晚硬是磨了一个多小时都没做出来,然后今天调了一早上才过了,被傻逼lc的评测机制气乐了。

  数位dp我一直都用递推去做的,记忆化搜索一直没学会。当时想状态定义的时候就想了很久,现在的总结就是其实只用关注从最高位往低位递推时会用到哪些特定的数,然后把需要的状态定义出来就好了,比如说最基本的数位的个数,最高位是哪一个数,然后是其他特性比如这题中奇偶数位分别有多少,整个数模$k$是多少。

  定义状态$f(i,j,u,v,w)$表示所有数位大小为$i$,最高位是$j$,奇数数位有$u$个,偶数数位有$v$个,整个数模$k$为$w$的数的个数。很明显数位大小为$i$的数可以转移到数位大小为$i+1$的数,因此当前状态$f(i,j,u,v,w)$可以转移到的状态就有$$\left\{ \begin{array}{c} f \left(i+1, \ x, \ u+1, \ v, \ (x \cdot {10}^i + w) \bmod k \right) \quad x \in \{ 1,3,5,7,9 \}  \\ f \left(i+1, \ x, \ u, \ v+1, \ (x \cdot {10}^i + w) \bmod k \right) \quad x \in \{ 0,2,4,6,8 \} \end{array} \right.$$

  然后递推的时候求的是$1 \sim x$中有多少个数满足条件,先把$x$中的每一个数分离出来,然后从最高位开始往底位枚举。只有$x$的数位大小为偶数时才能递推,因为要求奇偶数位相同,并且在递推时要保证没有前导$0$(前导$0$会印象奇偶数位的数目),最后再把那些含前导$0$的数补上即可。递推时需要开变量分别记录前面已确认的数的奇数数位和偶数数位有多少,以及组成的数在十进制中模$k$是多少。

  最后因为lc的逆天评测机制,如果对于每个样例都跑dp预处理那么肯定会TLE,因此需要把预处理的结果记录到全局变量中,这样只用跑一次即可,不过需要把$1 \leq k \leq 20$所有情况都跑一遍,预处理的计算量大概是$20 \times 10 \times 10 \times 6 \times 6 \times 20 \times 10 \approx {10}^7$。

  AC代码如下:

 1 vector<vector<vector<vector<vector<vector<int>>>>>> f;
 2 
 3 class Solution {
 4 public:
 5     void init() {
 6         f = vector<vector<vector<vector<vector<vector<int>>>>>>(21, vector<vector<vector<vector<vector<int>>>>>(11, vector<vector<vector<vector<int>>>>(10, vector<vector<vector<int>>>(6, vector<vector<int>>(6, vector<int>(20))))));
 7         for (int k = 1; k <= 20; k++) {
 8             vector<int> p(10);
 9             p[0] = 1 % k;
10             for (int i = 1; i < 10; i++) {
11                 p[i] = p[i - 1] * 10 % k;
12             }
13             for (int i = 0; i <= 9; i++) {
14                 if (i & 1) f[k][1][i][1][0][i % k] = 1;
15                 else f[k][1][i][0][1][i % k] = 1;
16             }
17             for (int i = 1; i < 10; i++) {
18                 for (int j = 0; j <= 9; j++) {
19                     for (int u = 0; u <= 5; u++) {
20                         for (int v = 0; v <= 5; v++) {
21                             for (int w = 0; w < k; w++) {
22                                 for (int x = 0; x <= 9; x++) {
23                                     if (x % 2 && u + 1 <= 5) f[k][i + 1][x][u + 1][v][(x * p[i] + w) % k] += f[k][i][j][u][v][w];
24                                     else if (x % 2 == 0 && v + 1 <= 5) f[k][i + 1][x][u][v + 1][(x * p[i] + w) % k] += f[k][i][j][u][v][w];
25                                 }
26                             }
27                         }
28                     }
29                 }
30             }
31         }
32     }
33     
34     int numberOfBeautifulIntegers(int low, int high, int k) {
35         if (f.empty()) init();
36         vector<int> p(10);
37         p[0] = 1 % k;
38         for (int i = 1; i < 10; i++) {
39             p[i] = p[i - 1] * 10 % k;
40         }
41         function<int(int)> get = [&](int x) {
42             if (!x) return 0;
43             vector<int> q;
44             while (x) {
45                 q.push_back(x % 10);
46                 x /= 10;
47             }
48             int ret = 0, odd = 0, even = 0, s = 0;
49             if (~q.size() & 1) {
50                 int t = q.size() >> 1;
51                 for (int i = q.size() - 1; i >= 0; i--) {
52                     for (int j = i == q.size() - 1; j < q[i]; j++) {
53                         ret += f[k][i + 1][j][t - odd][t - even][(k - s) % k];
54                     }
55                     if (q[i] & 1) odd++;
56                     else even++;
57                     if (odd > t || even > t) break;
58                     s = (s + q[i] * p[i]) % k;
59                     if (!i && odd == even && !s) ret++;
60                 }
61             }
62             for (int i = 1; i < q.size(); i++) {
63                 if (~i & 1) {
64                     for (int j = 1; j <= 9; j++) {
65                         ret += f[k][i][j][i >> 1][i >> 1][0];
66                     }
67                 }
68             }
69             return ret;
70         };
71         return get(high) - get(low - 1);
72     }
73 };

  这题还可以用暴搜,可以发现只有数位大小为偶数的数才能满足奇数数位和偶数数位的数目相同,因此可以暴搜出来这些数,实际上大概有$2 \times {10}^7$个左右。然后在暴搜的时候要保证搜到的数有序,对于$\text{low}$和$\text{high}$二分出可选数的区间,然后再逐个枚举是否模$k$为$0$即可。详细见参考资料,这里就不写了,比赛很少会这样做,一般都直接数位dp。

 

参考资料

  久违的力扣周赛讲解来啦~第111场双周赛:https://www.bilibili.com/video/BV1P44y1F7EG/

标签:Beautiful,Integers,beautiful,10,int,even,Range,odd,数位
From: https://www.cnblogs.com/onlyblues/p/17644193.html

相关文章

  • orange pi 5 plus开发板使用
    系统镜像烧写参考网址:http://www.orangepi.cn/orangepiwiki/index.php/Orange_Pi_5_Plus烧写方法:使用RKDevTool烧录Linux镜像到eMMC中的方法烧写镜像:选择Orangepi5plus_1.0.6_ubuntu_jammy_desktop_gnome_linux5.10.110.img驱动:DriverAssitant_v5.12烧写工具:RKDe......
  • Go 语言范围(Range)
    range关键字用于for循环中迭代数组(array)、切片(slice)、通道(channel)或集合(map)的元素。packagemainimport"fmt"funcmain(){//这是我们使用range去求一个slice的和。使用数组跟这个很类似nums:=[]int{2,3,4}sum:=0for_,num:=rangenums{......
  • 13用BeautifulSoup爬取网站
     代码如下frombs4importBeautifulSoupimportrequests'''本例子通过BeautifulSoup的常用方法find_all查询出所有包含电影名字的a标签的父节点h4,再通过父节点遍历得到a标签中的文本。find_all里面的参数一般是class_、id、name等html属性值,批量爬取数据时往往使用的......
  • k8s 准入控制器之LimitRanger
    LimitRanger概述尽管用户可以为容器或Pod资源指定资源需求及资源限制,但这并非强制性要求,那些未明确定义资源限制的容器应用很可能会因程序Bug或真实需求而吞掉本地工作节点上的所有可用计算资源。因此妥当的做法是,使用LimitRange资源在每个名称空间中限制每个容器的最小及最大计算......
  • mysql Error 1264: Out of range value for column 'balance' at row 1
    报错原因:值超出列的范围可能原因:原因1:值超出其可输入的范围。解决方法:设置的为INT,可以把列的值改为BIGINT,或者改成其他数据类型。原因2:新版本的MySQL对字段的严格检查。解决方法:修改my.ini,将sql-mode="STRICT_TRANS_TABLES,NO_AUTO_CREATE_USER,NO_ENGINE_SUBSTITUTION"......
  • Stata广义矩量法GMM面板向量自回归PVAR模型选择、估计、Granger因果检验分析投资、收
    原文链接:http://tecdat.cn/?p=24016原文出处:拓端数据部落公众号摘要最近我们被要求撰写关于广义矩量法GMM的研究报告,包括一些图形和统计输出。面板向量自回归(VAR)模型在应用研究中的应用越来越多。虽然专门用于估计时间序列VAR模型的程序通常作为标准功能包含在大多数统计软件......
  • BeautifulSoup 使用多条件查询
        最近开始学习python的爬虫,开始的时候单纯的用requests.get(url)取得源代码后,用正则表达后来取得相关的数据,效率不高,接触到BeautifulSoup,发现确实方便.    正好遇到一个问题,需要取的数据在两个div中,是两个class名,最开始的时候是取得两次来得到数据,就想精简一下......
  • python 使用BeautifulSoup的 html5lib爬取网站内容
    1、使用BeautifulSoup的'html5lib'能像网页工具一样渲染内容。缺点:运行比较慢2、安装包pipinstallhtml5lib3、直接获取网页的所有有效内容importrequests#数据请求模块第三方模块pipinstallrequestsfrombs4importBeautifulSoupheads={'User-Agen......
  • Beautifulsoup4
    目录一爬取新闻1.1直接爬取新闻1.2新闻数据保存到mysql中二bs4介绍遍历文档树三bs4搜索文档树3.2其他用法四css选择器一爬取新闻#1爬取网页---requests#2解析xml包含html格式 ---xml格式,用了re匹配的 ---html,bs4,lxml...---json: -python:内置的 -......
  • ranges介绍
    range概念介绍ranges为C++20引入的新特性,是对迭代器和算法库的扩展,C++stl中的容器都可以视作一个range。那什么是range?range是一个concept,其中concept概念可参考博文【3】中的Constraitsandconcepts介绍。namespacestd::ranges{template<classT>conceptrange=......