咕咕东 正在上可怕的复变函数，但对于稳拿A Plus的 咕咕东 来说，她早已不再听课，此时她在睡梦中 突然想到了一个奇怪的无限序列：112123123412345 …这个序列由连续正整数组成的若干部分构成，其 中第一部分包含1至1之间的所有数字，第二部分包含1至2之间的所有数字，第三部分包含1至3之间的所 有数字，第i部分总是包含1至i之间的所有数字。所以，这个序列的前56项会是 11212312341234512345612345671234567812345678912345678910，其中第1项是1，第3项是2，第20项是 5，第38项是2，第56项是0。咕咕东 现在想知道第 k 项数字是多少。
即对于s1s2s3s4…其中s1=12345…i，这样的序列，给出一个k，输出这个k项的数字是多少。
对于给定的每个k，输出数字。
例如：
输入：
5 1 3 20 38 56输出：
1 2 5 2 0一开始没什么思路的，然后前3个数据点很小，直接贴到string上，骗了30分。
主要考虑数据点特别大，1e18，直接顺序暴力来得算，只能过前六组。后来观察规律。首先数据点是一组一组的，并且每个大组里面还能分出来小的组。比如对前9个s，即s1到s9。可以看出是等差数列，公差为1。从s10到s99，公差为2，s100到s999公差为3。通过计算可以得到当s中最大数为9位数的时候即总位数超过1e18。故可以先按照这样的位数计算出当最大数为1位数，2位数等等的时候的总的位数。在这里有数组ret，记录每个小组的前n位数的位数，如ret[1]，即为123456789，故ret[1]=9，ret[2]，12345678910111213…99，故ret[2]=189。
依次类推。
另有数组记录前n位数的数据大组的位数a。如a[1]即位112123123412345123456123456712345678…12345678910
即a[1]=45，a[2]即为123456…9899，故a[2]=9045。通过观察规律，以及等差数列可以计算出来。
自此后每次得到一个k，便与之比较，可以直接得到k所在的那个大组，即最大数为（设为n位的范围)。如k=45刚好到9，即为一位数，k=9045时为99，即为两位数，若k=46，即在最大数为10的组，故k减去a[1]，即减去前面的最大组的位数，可以得到在当前最大组中的位数。同时得到该数据所处大组中的上下界，即pow(10,n)-1和pow(10,n-1)。在这上下界中可以通过二分查找每一个小组的位数，并与k，比较，找到k所在的那个小组的，如k在最大数为21的小组，则k可以减去前20个小组。得到在这个小组中位数。在当前小组中可以继续分组，即12345678910111213…
可以依次查找数字为n位的位数，即记录在ret数组中，如若k在12上，可以减去前面的ret[1]，即减去所有的1位数，即得到在当前的位数，并且在当前的数字中，所有数字的位数都相同，可以直接除法得到是第几个数字，求余得到在第几位。最后输出。
因为数据非常大，ll百度的为9e19，当时记录了a[9]的，大概是4e19，觉得没问题。后来本地跑没问题，vj上总是出错，也能过前3组。就总找不到错，然后问了学长，给的数据大概是爆了，本地也re了。然后对a[9]的数据处理了下，设为1e18，因为只要大于数据的最大数就可以了，然后换了个编译器就过了。。。。。整了一两天时间。其中还重写了两三次。。。。。 还有一个要注意的，二分的时候，因为二分的是每组中的数据，而不是准确的位数，然后最后的出来的数据可能不准。就取了得到的数据的左边和右边，一共三个数，重新进行判断，看这个位数是在哪个数据中。。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
long long q, k;
long long a[10]; //a里面装的如：1-9是45位 1-99是9045位 1-999是1395495位 的组的名次数
long long l, r, mid;
long long ret[10]; //记录如：123456789是9位 1-99是189位 等等的单个组的位数
long long t; //记录位数
long long f(long long tmp1) { //求一组中数据直到t的位数，如10的位数是11
long long tmp2 = tmp1;
long long r1 = 0; //这个数的位数
while (tmp2 > 0) {
r1++;
tmp2 = tmp2 / 10;
}
long long ret = 0;
for (long long i = 1; i < r1; i++) {
ret = ret + (pow(10, i) - pow(10, i - 1)) * i;
}
ret = ret + (tmp1 - pow(10, r1 - 1) + 1) * r1;
return ret;
}
int main() {
ios::sync_with_stdio(0);
memset(ret, 0, sizeof(ret));
for (int i = 1; i <= 9; i++) {
ret[i] = ret[i - 1] + (pow(10, i) - pow(10, i - 1)) * i;
}
memset(a, 0, sizeof(ret));
long long sum = 1;
for (long long i = 1; i <= 8; i++) {
sum = sum * 10;
long long n = sum - sum / 10;
a[i] = n * i + n * (n - 1) * i / 2 + n * ret[i - 1] + a[i - 1];
}
a[9]=1e18;
cin >> q;
for (int i = 0; i < q; i++) {
cin >> k;
for (int j = 1; j <= 9; j++) {
if (a[j] >= k) {
k -= a[j - 1]; t = j; break; //找到在几位数的分组中, j位数
}
}
l = 1;
r = pow(10, t) - pow(10, t - 1); //共有多少个j位数
long long qi = f(pow(10, t - 1)); //这大组中第一个组的位数
long long tt = 0; //记录mid的名次数
while (l <= r) {
mid = (l + r) / 2;
tt = mid * qi + mid * (mid - 1) * t / 2;
if (tt >= k) r = mid - 1;
else l = mid + 1;
}
//可能在mid的左右位置 即可能在 mid-1 mid 或者 mid+1组中
long long tt1=(mid-2)*qi+(mid-2)*(mid-3)*t/2; //mid-1前面的位数
long long tt2 = (mid - 1) * qi + (mid - 1) * (mid - 2) * t / 2; //mid前面的位数
long long tt3 = mid * qi + (mid - 1) * mid * t / 2; //mid+1前面的位数
if(k<=tt2){
k-=tt1; mid=mid-1; //在mid-1组中
}else{
if(k<=tt3){ //在mid组中
k-=tt2;
}else{
k-=tt3; mid=mid+1;
}
}
for (int j = 1; j <= 9; j++) {
if (ret[j] >= k) {
k -= ret[j - 1]; //在相同位数之间中找 比如在数字125中 减去1-99的
t = j;
break;
}
}
long long m1 = k / t; //有几个整数
long long m2 = k % t; //剩余几位
if (m2 == 0) {
mid = pow(10, t - 1) + m1 - 1;
cout << mid % 10<<endl;
}
else {
mid = pow(10, t - 1) + m1;
long long x = t - m2;
mid = mid / pow(10, x);
cout << mid % 10<<endl;
}
}
return 0;
}