http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2609
数位DP 以前没怎么做过,自己憋了半天,还是看了标程,标程写的就是好呀。
相关注释见代码:
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<set>
#include<map> #define ll long long
#define ull unsigned long long
using namespace std;
const int INF=0x3f3f3f3f;
ll dp[22][10][2];
int a[22];//把这一个数按位分解
ll dfs(int n,int x,int flag,int limit)
//这里表示的意思应该是 到第n位的时候,前面构成的数的余数是x
//flag代表是否有 7 limit代表是否限制大小
{
if(n==-1)//边界
return (flag||x==0);
if(!limit&&dp[n][x][flag]!=-1)
return dp[n][x][flag];
ll ans=0;
int up=(limit)?a[n]:9;
for(int i=0;i<=up;++i)//枚举当前位的取值
{
ans+=dfs(n-1,(x*10+i)%7,(flag||i==7),(limit&&i==a[n]));
}
if(!limit)//当没有限制的时候 就是记忆化搜索 有限制就是普通的dfs
dp[n][x][flag]=ans;
return ans;
}
ll solve(ull x)
{
int len=0;
while(x)
{
a[len++]=x%10;
x=x/10;
}
return dfs(len-1,0,0,1)-1;
}
ll fNum(ull x)
{
ull tmp=solve(x);
return tmp-solve(tmp);
}
int main()
{
//freopen("data.in","r",stdin);
memset(dp,-1,sizeof(dp));
ll k;
while(cin>>k)
{
ull l=1,r=(ull)(pow(2.0,63)-1.0);
while(l<=r)//由于没有思路,根本没想到二分
{
ull mid=(l+r)>>1;
if(fNum(mid)>=k)
r=mid-1;
else
l=mid+1;
}
cout<<l<<endl;
}
return 0;
}