题目描述
其实这个题本来应该是那道撼烁古今的A+B签到题，但LCC小王子一看不乐意了，说：“这么经典的题怎么能让别人做，我们要留着自己做，马上把这道题给我换了。”于是把原本经典的A+B签到题改成了现在这道题。哎。。。啥都不说了，你们还是自己看题吧。
给你一个正整数n,找出位于序列组S1S2S3...Sk中第n个位置的数字。序列Sk就是一个从1到k的正整数序列。例如，一个80位的序列组为：11212312341234512345612345671234567812345678912345678910123456789101112345678910
输入
多实例测试。每行输入一个整数n(1<=n<=2147483647)
输出
每个测试实例输出一个整数，占一行，表示序列组第n个位置上的数字。
样例输入
8
3样例输出
2
2两次预处理，预处理 两个数组：
a[N] , b[N] 。 b[i]：1,2,3, .. i 的长度； a[i] ： S1S2S3...Sk k = i 时字符串的长度。
两次二分：
第一次 二分 从 a[N] 中找到 长度 小于等于 n 最大的 i , 如果 a[i] == n, 输出 i%10 结束，a[i] != n 进行下一步 。
第二次二分 从 b[N] 中找到 长度 小于等于 n-a[i] 最大的 j, 如果 b[j] == n-a[i], 输出 j%10 结束，b[j] != n-a[i] 进行下一步 。
输出 j+1 这个数字 的 n-a[i]-b[j] 位。
#include <iostream>
#include <cmath>
using namespace std;long long a[1000100];
long long b[1000100];long long find1(int left, int right, long long e)
{int mid;while(left < right){mid = (left+right)/2;(e < a[mid]) ? right = mid : left = mid + 1;}return --left;
}
long long find2(int left, int right, long long e)
{int mid;while(left < right){mid = (left+right)/2;(e < b[mid]) ? right = mid : left = mid + 1;}return --left;
}int main()
{a[0] = 0;b[0] = 0;for(int i=1; i<=9; i++){b[i] = i;a[i] = a[i-1] + b[i];}
// for(int i=1; i<=9; i++)
// cout << a[i] << endl;for(int i=10; i<=99; i++){b[i] = b[i-1] + 2;a[i] = a[i-1] + b[i];}for(int i=100; i<=999; i++){b[i] = b[i-1]+3;a[i] = a[i-1] + b[i];}for(int i=1000; i<=9999; i++){b[i] =b[i-1]+4;a[i] = a[i-1] + b[i];}for(int i=10000; i<=99999; i++){b[i] = b[i-1]+5;a[i] = a[i-1] + b[i];}long long n;while(cin >> n){
// for(int i=a[999]; i<=a[1000]; i++) {// n = i;int cnt;cnt = find1(0, 99998, n);n -= a[cnt];//cout << cnt << " " << n << endl;if(n == 0){cout << cnt%10 << endl;continue;}cnt = find2(0, 99998, n);// cout << n << " " << cnt << endl;n -= b[cnt];if(n == 0){cout << cnt%10 << endl; // " ";continue;}// cout << n << " " << cnt << endl;cnt ++;while(cnt >= pow(10, n)){cnt /= 10;}cout << cnt%10 << endl; // " ";}return 0;
}