日常写点奇奇怪怪的乱搞做法 awa
这题跟前面几道数位 DP 的区别在于让求第 \(n\) 小的数。
虽然我不会求也不想学这个,但我们可以 binary search!
问题就转换为求 \([1,mid]\) 中的幸运数个数,这样就和前面那些题做法一样了/xyx
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=40;
int a[N],vis[N][5];
int dfs(int pos,int op,bool limit,bool lead)
{
if(pos<1) return (op==3);
if((!limit)&&lead&&vis[pos][op]!=-1) return vis[pos][op];
int up=9,ans=0;
if(limit) up=a[pos];
for(int i=0;i<=up;i++)
{
if(op==3) ans+=dfs(pos-1,3,limit&&(i==up),lead||i);
else ans+=dfs(pos-1,(i==6?op+1:0),limit&&(i==up),lead||i);
}
if(!limit&&lead) vis[pos][op]=ans;
return ans;
}
int work(int x)
{
memset(vis,-1,sizeof(vis));
int len=0;
while(x)
{
a[++len]=x%10;
x/=10;
}
return dfs(len,0,1,0);
}
int T;
signed main()
{
scanf("%lld",&T);
while(T--)
{
int x;
scanf("%lld",&x);
int l=666,r=1e10;
while(l<r)
{
int mid=(l+r)>>1;
if(work(mid)<x) l=mid+1;
else r=mid;
}
cout<<l<<endl;
}
return 0;
}
原文地址:http://www.cnblogs.com/ying-xue/p/16792411.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性