题解：CF1216E1 Numerical Sequence (easy version)

l_do_Cpp · 2026-11-07 14:32:23 · 题解

本篇题解只完成了可以解决简单版本的做法，显然比困难版本的解法更易懂。若想知道简单和困难版本通用解法，请参考我的困难版本题解。

博客观看效果更佳。

前置知识

二分、前缀和。

题目解析

慢慢定位位置，先定位到块。

利用前缀和 s 表示第 i 块的长度。

    s[1]=1;
    l[1]=1;//l 即第 i 块的长度。注意分辨字母 l 与 数字 1。
    for(int i=1;i<=1e5;i++) l[i]=l[i-1]+lenth(i),s[i]=s[i-1]+l[i];//lenth() 即求长度

然后二分定位。

        int l=0,r=1e5,qwq=0;
        while(l<=r)
        {
            int mid=l+r>>1;
            if(s[mid]<k) l=mid+1,qwq=mid;
            else r=mid-1;
        }

:::info[关于困难版本] 困难版本和简单版本的区别的区别即修改 s 数组，改为其他处理方式。读者可自行思考。

:::

之后找到对应块后，先枚举这个数字的位数。

int pwp=9,len=1,oh=1; 
while(pwp<k)
{
  len++;
  oh*=10;
  pwp=oh*len*9+pwp;//pwp即比自己位数小的数字总长度
}
pwp-=oh*len*9;//减去长度和自己位数一样的
k-=pwp;//减去长度比自己小的

然后计算这个数字是几、要这个数字的第几位。

  int ans=(k-1)/len+oh;
  for(int j=1;j<=(len-k%len)%len;j++)
  {
    ans/=10;
  }
  cout<<ans%10<<"\n";

正解代码

https://codeforces.com/contest/1216/submission/397682438