咕咕东的奇妙序列
有一个序列11212312341234512345612345671234567812345678912345678910······
特点为由若干部分组成 每一部分si为1~i所有数字
给出q(q<=500)次查询 每次查询给出一个数字ki(ki<=1018) 请给出序列中第ki个数字
例如 第1项是1,第3项是2,第20项是 5,第38项是2,第56项是0
Input
第一行给出q
接下来2~q+1行 每行一个数字ki
Output
输出包含q行
第i行输出对询问 的输出结果。
Sample Input
5
1
3
20
38
56
Sample Output
1
2
5
2
0
我的思路:
对于题目的序列分析,可以发现,这个序列满足在特定区间的特定等差数列。即在10的i次方到10的(i+1)次方-1的过程中每次都是增加i+1.知道这个特点之后,就可以利用等差数列的公式,进行求解。在找数字的过程中,整体的思路是先判断这一项数字在哪一个部分,然后再在这个部分中用类似的方法找到对应的数字。在查找的问题上,可以利用二分法进行优化,避免超时。通过计算序列某部分之前所有部分的长度,来和k进行比较,找到k所在的部分。然后,通过对于这个部分中每个数的长度来判断第k项在哪个数字中,然后再用k减去这个数字之前的长度确定k在这个数字中的位置,最后将z这个数字变成字符串,找到对应位置的数字即可。
我的总结:
这道题困扰我很久,最开始是想到了通过枚举的方式列出所有的序列,test4到最后的test都超时。。。然后又想到了通过的等差性质来朴素求解,test7到最后的test都超时。。。最后,通过二分法进行优化才AC。
我的代码:
#include<cstdio>
#include<iostream>
using namespace std;
long long q,k,l,r,mid,an;
long long compute(long long x,int opr){
long long cnt=1,sa=0,a=0,n=0,d=0;
while(true){
cnt*=10;
d++;
if(x>cnt-1)
{
n=cnt-cnt/10;
sa+=(a+d)*n+n*(n-1)/2*d;
a+=n*d;
}
else
{
n=x-cnt/10+1;
sa+=(a+d)*n+n*(n-1)/2*d;
a+=n*d;
break;
}
}
return opr?sa:a;
}
int main(){
scanf("%lld",&q);
for(int r1=0;r1<q;r1++)
{
scanf("%lld",&k);
l=0,r=1000000000;
while(l<=r){
mid=(l+r)/2;
if(compute(mid,1)<k) an=mid,l=mid+1 ;
else r=mid-1;
}
k-=compute(an,1);
l=0,r=an+1;
while(l<=r){
mid=(l+r)/2;
if(compute(mid,0)<k) an=mid,l=mid+1;
else r=mid-1;
}
k-=compute(an,0);
an++;
string ans=to_string(an);
printf("%d\n",ans[k-1]-'0');
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)