【Week8CSP模拟II-C】咕咕东的奇妙序列 Gym - 270737E

算法

模拟数学

题目描述

给出一个序列，该序列由若干部分组成，其中第i部分由1到i组成。例如，第一部分为1，第二部分为12，第10部分为12345678910（注意，10为两个字符）。现给出一个数字，要求计算在该位置上的字符是什么。

解题思路

对于60分来说，直接逐位计算每一个字符是什么即可。计算完毕之后根据询问返回该位即可。
对于满分来说，因为数据量过大，将通过数学计算来算出该位的字符。具体为，将序列根据该部分数字的位数分段，分段后每一段由于数字位数相同，即为等差数列，再推导公式即可。
由于等差数列公式中存在未知量的二次方，故应使用二分计算。

代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const long long maxn=10;
long long cnt[maxn];    //位数为i的最多有多少个字符
long long sum[maxn];    //位数为i的共有多少个字符
//char anss[]="011212312341234512345612345671234567812345678912345678910";
long long findn(long long x,long long wei){
    long long l=0,r=1;
    for(long long i=1;i<=wei;i++){
        r*=10;
    }
    long long ans=0;
    while (l <= r) {
        long long mid = (l + r) / 2;
        long long n=mid;
        long long sum = (cnt[wei-1]+wei+cnt[wei-1]+wei*n)*(n)/2;
        if (sum < x) {
            ans = mid;
            l = mid + 1;//向大找
        }
        else {
            r = mid - 1;//向小找
        }
    }
    long long n=ans;
    long long sum = (cnt[wei-1]+wei+cnt[wei-1]+wei*n)*(n)/2;
    return sum;
}
long long c[maxn];
int print(long long x){
    long long wei;
    long long lst=1;
    for(long long i=1;i<maxn;i++){
        if(x<cnt[i]){
            x-=cnt[i-1];
            wei=i;
            break;
        }
        lst*=10;
    }
    lst+=x/wei;//当前数值
    c[0]=(lst-1)%10;
    for(long long i=wei;i>0;i--){
        c[i]=lst%10;
        lst/=10;
    }
    return c[x%wei];
}
int find(long long x){
    /*if(x<=56){
        return anss[x];
    }*/
    long long wei=0;
    for(long long i=0;i<maxn;i++){
        if(x<=sum[i]){
            x-=sum[i-1];
            wei=i;
            break;
        }
    }
    if(wei==0){
        x-=sum[maxn];
        wei=maxn;
    }
    x-=findn(x,wei);
    //if(x>cnt[wei-1])    x-=cnt[wei-1];
    return print(x);
}
int main(){
    
    long long cntx=1;
    long long lstx=0;
    for(long long i=0;i<maxn;i++){
        cnt[i]=cntx*i;
        cnt[i]-=lstx;
        lstx+=cntx;
        cntx*=10;
    }
    cntx=10;
    lstx=1;
    for(long long i=1;i<maxn;i++){
        sum[i]=(cnt[i-1]+i+cnt[i])*(cntx-lstx)/2;
        lstx=cntx;
        cntx*=10;
    }
    for(long long i=1;i<=maxn;i++){
        sum[i]+=sum[i-1];
    }
    //for(long long i=0;i<maxn;i++) cout<<cnt[i]<<endl;
    //for(long long i=0;i<maxn;i++) cout<<sum[i]<<endl;

//  cout<<find(1000000000000000000);
/*  freopen("c.txt","w",stdout);
    for(long long i=1;i<=1000000;i++){
        printf("%d:%d\n",i,find(i));
    }
*/

    long long q;
    cin>>q;
    long long x;
    for(long long i=1;i<=q;i++){
        cin>>x;
        printf("%d\n",find(x));
    }

    return 0;
}

题目总结

由于此题目较为复杂，尤其是公式的推导以及计算，导致在场上的时间内基本难以写出满分解法。此时要做的就是，保证自己的60分解法没有问题，并在再三确定后提交60解法。如果场上写出了满分解法也不要贸然提交，应和60解法对拍，并将程序分段，以尽可能获得更多的分数。

题目原文

题目描述

咕咕东正在上可怕的复变函数，但对于稳拿APlus的咕咕东来说，她早已不再听课，此时她在睡梦中突然想到了一个奇怪的无限序列：112123123412345......这个序列由连续正整数组成的若干部分构成，其中第一部分包含1至1之间的所有数字，第二部分包含1至2之间的所有数字，第三部分包含1至3之间的所有数字，第i部分总是包含1至i之间的所有数字。所以，这个序列的前56项会是11212312341234512345612345671234567812345678912345678910，其中第1项是1，第3项是2，第20项是5，第38项是2，第56项是0。咕咕东现在想知道第k项数字是多少！但是她睡醒之后发现老师讲的东西已经听不懂了，因此她把这个任务交给了你。

输入格式

输入由多行组成。
第一行一个整数q表示有q组询问（1 <= q <= 500）。
接下来第i+1行表示第i个输入，表示询问第项数字（1 <= ki <= 10¹⁸）。

输出格式

输出包含q行
第i行输出对ki询问的输出结果。

样例输入

样例输出

数据点	q（上限）	k（上限）
1，2	500	55
3，4，5	100	10⁶
6，7，8，9，10	500	10¹⁸