POJ 1019-Number Sequence Number Sequence Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 34278 Accepted: 9835 Description A single positive integer i is given. Write a program to find the digit located in the position i in the sequence of number groups S1S2…Sk. Each group Sk consists of a sequence of positive integer numbers ranging from 1 to k, written one after another. For example, the first 80 digits of the sequence are as follows: 11212312341234512345612345671234567812345678912345678910123456789101112345678910 Input The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by one line for each test case. The line for a test case contains the single integer i (1 ≤ i ≤ 2147483647) Output There should be one output line per test case containing the digit located in the position i. Sample Input 2 8 3 Sample Output 2 2 Source Tehran 2002, First Iran Nationwide Internet Programming Contest
做这一题需要细心，我们先分析一下题意。给出一串数字，问你这个数字串中第i个位置的数字是什么。其中数字串是形如112123123412345123456123456712345678123456789123456789101234567891011123456789101112这样的。 仔细分析一下就是1、12、123、1234，…，123456789、12345678910、1234567891011，… 串联起来的。我们定义单个数字串1234…i的长度为single_len[i]，总的数字串1,12,123,…,123…i.的长度为total_len[i]。因为1,12,123,…,123…i.=1,12,123,…,123…(i-1).+123…i.所以我们可以得出一个等式：total_len[i]=total_len[i-1]+single_len[i]。那么怎么来求解single_len[i]呢？ single_len[0]=0; single_len[1]=1; single_len[2]=2; single_len[10]=11. 因为single_len[i]为123…(i-1)i的长度，single_len[i-1]为123…(i-1)的长度。很显然，single_len[i]=single_len[i-1]+数字i的长度。这有点类似动态规划的状态转移方程。求数字i的长度可以用下面的函数求解： [cpp] //求数字i的位数 int get_digits_num(int i) { int rs=1; while(i>=10) { rs++; i/=10; } return rs; } [/cpp] 当然也可以用stringstream先将int转换为string再求string.size()，但是这种方法更慢。 当我们求到了single_len和total_len，就可以分两步求解总的数字串中第i个位置的数字了。首先在total_len中找到位置i在哪一个内部串中，然后再在内部串中找到位置i的确切位置。这就有点像信号调节中的粗调和微调，首先找到大致的位置，然后在某个局部找细节的位置。 比如给定数字串112123123412345123456123456712345678123456789123456789101234567891011123456789101112。问i=18位置处的数字是什么。我们已经求到total_len[0]=0; total_len[1]=1; total_len[2]=3; total_len[3]=6; total_len[4]=10; total_len[5]=15; total_len[6]=21; 。18正好在total_len[5]和total_len[6]之间。因为total_len[5]=15表示以5结束的总的数字串的长度为15<18，所以我们取total_len[6]，也就是i=18必定在以6结尾的总的数字串中，即在112123123412345123456中，且在以6结尾的单个数字串中的第i-total_len[6-1]=18-15=3个位置，也就是在123456的第3个位置即3，所以最终结果就是3。 所以总结一下求解的步骤就是： 1. 计算single_len和total_len。 2. 在total_len中二分查找位置i在以last_num为末尾数字的总的串中。 3. 计算出在以last_num为末尾数字的单个内部串中位置i所在的相对位置inner_index。 4. 在以last_num为末尾数字的单个内部串中二分查找出相对位置为inner_index的数字。 其中要数第4步最难，其二分搜索函数如下： [cpp] //（单组数字串）内部二分搜索 char bin_search_inner(int i) { int s=1,t=MAX_N,mid; while(s<t) { mid=(s+t)/2; if(single_len[mid]<i) s=mid+1; else if(single_len[mid]==i) { string s=int2string(mid); return s[s.size()-1]; } else t=mid-1; } if(single_len[t]<i) t++; string rs=int2string(t); return rs[rs.size()-(single_len[t]-i)-1]; } [/cpp] 其中的single_len[mid]==i分支：比如single_len[12]=15; single_len[13]=17;如果mid==12; i==15.结果是多少呢？single_len[12]=15表示以12结尾的数字串的长度为15，而i正好为15，所以结果应该为123456789101112的最后一个数字2。 假设single_len[1234]=9843; i=9841; 这时t=1234，结果又是多少呢？假设我们到了rs[rs.size()-(single_len[t]-i)-1];这一步。通过直观观察，i=9841的位置是2，因为single_len[1234]=9843表示1234末尾的数字4的i=9843，往前推自然得到i=9841时数字为2；怎样写成一个公式呢？single_len[t]-i=2表示位置i离末尾数字的距离为2，那么它离开头的距离为多少呢？很显然用t（也就是rs=int2string(t)）的总长度减去离末尾的距离再减1就行了。也就是rs[rs.size()-(single_len[t]-i)-1];，所以我们是从这个数字的末尾往前推的。 还要注意一下i最大为2147483647，2147483647刚好是int的正整数最大极限值，所以total_len要用unsigned int。其他的就没有太多要解释的了。具体看代码： [cpp] #include<iostream> #include<string> #include<sstream> #include<cstdlib> using namespace std; const static int MAX_N=31269;//数字串中最大的数 int single_len[MAX_N]={0};//single_len[i]表示1,2,3,…,i.这个数字串中总的数字位数 unsigned int total_len[MAX_N]={0};//total_len[i]表示1,12,123,…,123…i.这个数字串中总的数字位数 //将int转换为string string int2string(int i) { stringstream ss; string s; ss<<i; ss>>s; return s; } //求数字i的位数 int get_digits_num(int i) { int rs=1; while(i>=10) { rs++; i/=10; } return rs; } //初始化单组数字串 void init_single_len() { for(int i=1;i<MAX_N;i++) { single_len[i]=single_len[i-1]+get_digits_num(i); } } //初始化总体数字串 void init_total_len() { for(int i=1;i<MAX_N;i++) { total_len[i]=total_len[i-1]+single_len[i]; } } //外部（总体）二分搜索 int bin_search_outer(int i) { int s=1,t=MAX_N-1,mid; while(s<t) { mid=(s+t)/2; if(total_len[mid]<i) s=mid+1; else if(total_len[mid]==i) return mid; else t=mid-1; } if(total_len[t]<i) return t+1; else return t; } //（单组数字串）内部二分搜索 char bin_search_inner(int i) { int s=1,t=MAX_N,mid; while(s<t) { mid=(s+t)/2; if(single_len[mid]<i) s=mid+1; else if(single_len[mid]==i) { string s=int2string(mid); return s[s.size()-1]; } else t=mid-1; } if(single_len[t]<i) t++; string rs=int2string(t); return rs[rs.size()-(single_len[t]-i)-1]; } int main() { int t,i; cin>>t; init_single_len(); init_total_len(); //cout<<total_len[31268]<<endl; while(t–) { cin>>i; int last_num=bin_search_outer(i); int inner_index=i-total_len[last_num-1]; cout<<bin_search_inner(inner_index)<<endl; } return 0; } [/cpp] 本代码提交AC，用时16MS，内存464K。]]>