首页 > 其他分享 >[题解]CF55D Beautiful Numbers

[题解]CF55D Beautiful Numbers

时间:2024-04-14 11:22:25浏览次数:22  
标签:Beautiful 2520 int 题解 pos num Numbers 整除 lcm

CF55D Beautiful Numbers

打出暴搜后有些茫然,不知道该怎么优化才好,看了题解才豁然开朗。

简单说下暴搜的思路:参数有\(pos,limit,lcm,num\)。其中\(lcm\)表示到\(pos+1\)位,所有非\(0\)位的\(lcm\)是多少;\(num\)表示填到\(pos+1\)位的整个数是多少。然后在\(pos=0\)时判断\(lcm\)是否整除\(num\),是则返回\(1\),否则返回\(0\),然后一层层累加。

优化思路其实很简单:
显然直接用\(f[pos][num][lcm]\)来记忆化,无论时间还是空间都是过不去的。
但我们知道所有非\(0\)位整除\(num\),就等价于它们的\(lcm\)整除\(num\)。
我们想知道\(num\)是否被\(2\)整除,那么我们关注它\(mod\ 2\)的值是否为\(0\);
我们想知道\(num\)是否被\(6\)整除,那么我们关注它\(mod\ 6\)的值是否为\(0\)。
……
那么我们想知道\(num\)是否被\(a_1,a_2,…,a_k\)整除,那么我们只需要关注它\(mod\ lcm\{a_1,a_2,…,a_k\}\)的值是否为\(0\)。

那么我们只需要记录\(num\ mod\ lcm\{1,2,…,9\}\)的值即\(num\ mod\ 2520\)即可。
\(f[pos][num][lcm]\)空间共\(20*2520*2520\)。而250MB的空间限制还是不允许我们开那么大。怎么继续优化呢?


注意到\(lcm\)中我们能用到的一共就那么几个。我们知道\(2520\)一共有\(48\)个因数。而我们\(1\sim 9\)能凑出的数的个数肯定比\(48\)少了。因此我们把质因数离散化一下,第三维开\(50\)绰绰有余。

我的代码和离散化的意思差不多,大概是现读现存的感觉,用map存下来每个质因数存在哪个位置上。

(不知道为什么用了unsigned long long,其实不需要)

点击查看代码
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int t,l,r,a[30],f[30][2520][50];
bool vis[30][2520][50];
map<int,int> ma;
int val[50],cnt;
int __lcm(int a,int b){
	return a/__gcd(a,b)*b;
}
int dfs(int pos,bool limit,int lcm,int num){
	if(pos==0){
		if(num%lcm==0) return 1;
		return 0;
	}
	if(!limit&&ma.find(lcm)!=ma.end()&&vis[pos][num][ma[lcm]]) return f[pos][num][ma[lcm]];
	int rig=limit?a[pos]:9,ans=0;
	for(int i=0;i<=rig;i++){
		ans+=dfs(pos-1,limit&&i==rig,i?__lcm(lcm,i):lcm,(num*10+i)%2520);
	}
	if(!limit){
		if(ma.find(lcm)==ma.end()) ma[lcm]=++cnt,val[cnt]=lcm;
		f[pos][num][ma[lcm]]=ans,vis[pos][num][ma[lcm]]=1;
	}
	return ans;
}
int solve(int x){
	int len=0;
	while(x){
		a[++len]=x%10;
		x/=10;
	}
	return dfs(len,1,1,0);
}
signed main(){
	cin>>t;
	memset(vis,0,sizeof vis);
	while(t--){
		cin>>l>>r;
		cout<<solve(r)-solve(l-1)<<endl;
	}
	return 0;
}

标签:Beautiful,2520,int,题解,pos,num,Numbers,整除,lcm
From: https://www.cnblogs.com/Sinktank/p/18133886

相关文章

  • [题解]CF1073E Zegment Sum
    CF1073ESegmentSum这道数位dp与其他不同的是,这个求的是满足要求的数的和,这种题型的题我们还没有做过。以前虽然做过一些求和或者求积的题,但都是求每个满足条件的数的数位和、二进制1的个数等等的和。而这道题是对\([L,R]\)中满足条件的数直接求和,这意味着基本不会有两个状态得......
  • [NOIP2018] 旅行 题解
    明显要以\(1\)为起点。原图是树这种情况下,走路不能回头,只能用\(dfs\)的思路走。当然肯定每次都走较小的那棵子树,\(vector\)存图后排序即可达到这种效果。时间复杂度\(O(n\logm)\)。原图是基环树明显可以分别考虑将所有边断掉后的情况,取字典序最小的。时间复杂度\(O(......
  • CF382B Number Busters 题解
    总共就两种情况。当\(b\geqx\)时,\(b\)要减\(x\),\(c\)要减去一。当\(b\ltx\)时,\(a\)和\(c\)都要减一,\(b=w-x\)。如果\(c>a\),退出循环。每一次循环判断\(b\)跟\(x\)的关系,然后秒数加一。代码:#include<bits/stdc++.h>usingnamespacestd;inta,b,c,w,x;in......
  • CF455C Civilization 题解
    思路求树的直径,并存在一个数组里。用并查集来动态合并加维护区域信息(包括同一颗树里的有着相同祖先的点的合并,不同树之间的合并)。假设\(length\)数组:对于每棵树的根节点\(x\),\(length_{x}=\)该树的直径长度接下来对于每个询问(如果给出的两点在同一颗树内则忽略),利用并查......
  • [题解]SP10606 Balanced Numbers
    SP10606BalancedNumbers关于优化方式的说明详见数位dp例题及详解-下。SPOJ注册不上所以暂时无法提交w,但是3份代码与正解对拍没有问题。使用\(vis[0\sim9]\)表示\(0\sim9\)的访问情况,\(sta[0\sim9]\)表示\(0\sim9\)填写个数的奇偶性(奇数为\(1\),偶数为\(0\))。暴搜先打出来,......
  • 第十五届蓝桥杯大赛软件赛省赛C/C++ 大学 B 组题解
    试题A:握手问题本题总分:\(5\)分思路:组合计数,用为\(50\)个人握手的总方案数\(C^{2}_{50}\),减去七个人彼此没有握手握手的方案数\(C^{2}_{7}\)即为答案。A:握手问题#include<bits/stdc++.h>#defineintlonglong#definedblongdouble#defineall(f)f.begin()......
  • CF1923B Monsters Attack! 题解
    题目简述数轴上有$n$个怪兽。最初第$i$个怪兽在$x_i$位置上,且血量为$a_i$。你在位置$0$上。在每秒钟会发生:你给任意怪兽发射总共$k$颗子弹,受到攻击的怪兽血量减一。血量小于等于$0$的怪兽死亡。没有死亡的怪兽向你移动一个单位。当一个怪兽来到你的位置,你就输......
  • CF1165E Two Arrays and Sum of Functions 题解
    题目简述已知两个长度均为$n$的数组$a$和$b$。给定一个函数:$f(l,r)=\sum\limits_{l\lei\ler}a_i\cdotb_i$。你的任务是对数组$b$中的元素以任意的顺序重新排序,使$\sum\limits_{1\lel\ler\len}f(l,r)$的值最小。题目分析我们首先进行化简,发现题......
  • CF107A Dorm Water Supply 题解
    题目简述给出一个$n$个点,$m$条边的有向图,边带权。保证每个点的出度和入度最多为$1$。对于每一个入度为$0$,出度为$1$的点,我们在该点建一个水箱。对于每一个入度为$1$,出度为$0$的点,我们在该点建一个水龙头。可以发现,每一个水箱对应一个唯一的水龙头,我们将每对对应......
  • CF1942B Bessie and MEX 题解
    题目简述给定一个长度为$n$的数组$a$,让你构造一个等长的排列$p$,其中从$0$到$n-1$的每个整数恰好出现一次。满足对于每一个位置$a_i=\texttt{MEX}(p_1,p_2,\ldots,p_i)-p_i$,其中数组的$\texttt{MEX}$是不在该数组中出现的最小非负整数。题目分析我们发现正着做并......