题目:前n个数字组成串s,利用s的前k个串构成t,求t串的第i个位置的字符。
分析:dp、数学。先构造前n个数字组成的串s,在构造过程中求解以s结束的对应t串的长度。
利用二分确定t中的前k-1个s串的前缀的长度l,那么就是求s(k)的第i-l个字符即可。
说明:又是好久没刷题╮(╯▽╰)╭。
#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> using namespace std; char buf[150000]; long long sum[33000]; char temp[10]; char *itoc(int i) { int t = i,count = 0; while (t) { count ++; t = t/10; } temp[count --] = 0; while (i) { temp[count --] = i%10 + '0'; i /= 10; } return temp; } int bs(long long key) { int l = 0,r = 32000; while (l < r) { int mid = (l+r+1)/2; if (sum[mid] >= key) r = mid-1; else l = mid; } return l; } int main() { memset(buf, 0, sizeof(buf)); sum[0] = 0LL; buf[0] = '0'; int add = 1,len; for (int i = 1 ; i < 32001 ; ++ i) { strcat(&buf[strlen(buf)], itoc(i)); sum[i] = sum[i-1] + strlen(buf)-1; } int t; long long n; while (~scanf("%d",&t)) while (t --) { scanf("%lld",&n); printf("%c\n",buf[n-sum[bs(n)]]); } return 0; }
原文:http://blog.csdn.net/mobius_strip/article/details/44537151