牛客寒假训练营(三)——G——用dfs找“6"的基本算法思想是什么？
求各位大佬帮忙解答一下
#include <bits/stdc++.h>
usingnamespacestd;
intnu[18];
longlongpox(intx,intn)
{
longlongg=1;
for(inti=0;i<n;i++)g*=x;
returng;
}
longlongdfs(intx,intn)
{
if(n==0)
{
if(x>=6&&x<10)returnx;
elsereturnx+1;
}
if(x<10&&x>6)return(x-1)*pox(9,n)+dfs(nu[n-1],n-1);
elseif(x==6)return(x)*pox(9,n);
elsereturn(x)*pox(9,n)+dfs(nu[n-1],n-1);
}
longlongans(longlongx)
{
intnx=0;
longlongx1=x;
for(inti=0;i<=18;i++)
{
if(x1<10)break;
elsenu[i]=x1%10;
x1=x1/10,nx++;
}
//cout << x1 << ' '<< nx <<' '<<pox(9,2) << ' ' << dfs(nu[nx-1],nx-1) << endl ;
longlongg;
if(nx==0&&x<6) g=0;
elseif(nx==0)g=1;
elseif(x1>6) g=x-(pox(9,nx)*(x1-1))-dfs(nu[nx-1],nx-1)+1;
elseif(x1==6)g=x-(pox(9,nx)*(x1))+1;
elseg=x-(pox(9,nx)*(x1))-dfs(nu[nx-1],nx-1)+1;
//cout << x << ' ' << (pox(9,nx)*(x1)) << ' ' << dfs(nu[nx-1],nx-1) << endl;
returng;
}
intmain()
{
longlongl,r;
cin >> l >> r;
cout << ans(r)-ans(l-1) << endl;
return0;
}
hy why？
全部评论
(0) 回帖