首页 > 代码库 > poj1019
poj1019
给定数列:1121231234...
求:某一位对应的数值
打表+二分
******************************
#include<cstdio> #include<cstring> #include<cmath> #define MAXN 111111 #define P 31268 #define N 2147483647 using namespace std; int a[10]; long long s[MAXN],sum[MAXN]; int cal(int x) { return (int)log10(x)+1; } void init() { int i=1; long long cur=0; while(cur<N) { s[i]=s[i-1]+cal(i); cur=sum[i]=sum[i-1]+s[i]; i++; } } int find(long long x) { int l=1,r=P; while(l<=r) { int m=(l+r)>>1; if(sum[m]>x)r=m-1; else if(sum[m]==x)return m-1; else l=m+1; } return l-1; } int find1(long long x) { int l=1,r=P; while(l<=r) { int m=(l+r)>>1; if(s[m]>x)r=m-1; else if(s[m]==x)return m-1; else l=m+1; } return l-1; } int main() { //freopen("in.txt","r",stdin); init(); int t; scanf("%d",&t); while(t--) { long long n; scanf("%lld",&n); int p=find(n); n-=sum[p]; p=find1(n); n-=s[p]; p++; int tot=0; while(p) { a[++tot]=p%10; p/=10; } int ans=a[tot+1-n]; printf("%d\n",ans); } return 0; }
******************************
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。