-
POJ 1019 解题呈报
添加时间:2013-7-17 点击量:题目地址：http://poj.org/problem？id=1019
一道通俗的ACM题，然则从中可以看出一些题目。题很简单，就是给你一串数字串，其规律为：
1 12 123 1234 12345 123456 1234567 12345678 123456789 12345678910 1234567891011 123456789101112······
输入地位i，策画这一串数字第i位是什么数字，重视是数字，不是数。例如12345678910的第10位是1，而不是10，第11位是0，也不是10。
然后就很好说了，策画一个数字k的长度用：int（log10（double（num））） + 1，然后变量sk每次加上k的长度，再定一个和变量sum，它每次加上sk的值，直到sum比index大。然后再按照残剩的长度在sk内部找那个数字，很简单。
这里有个题目就是，题中说“The line for a test case contains the single integer i （1 ≤ i ≤ 2147483647）”，遵守OJ的常规，测试用例必然会有极端景象，极大的或极小的，所以i = 2147483647是必然要推敲的。这里若是处理惩罚不好或许会呈现超时的景象。很不幸我就超时了。
有一点很是诡异，在代码第48行，注释说：若是sum < index 则超时。因为我开端时while里用的就是sum < index，每次剖断当前数到的长度是否比题中给的长度index小。然则很遗憾如许对于极大的景象：i = 2147483647会很慢，插装了策画时候的代码后发明这一步须要策画60秒阁下。
而后我在网上搜刮到了别人的代码，根蒂根基都是应用累加的办法，比如：http://blog.csdn.net/lyy289065406/article/details/6648504中是如许累加的：
const int size=31269;
void play_table（void）{a[1]=s[1]=1;for（int i=2;i<size;i++）{a[i]=a[i-1]+（int）log10（（double）i）+1; //log10（i）+1 默示第i组数字列的长度 比 第i-1组 长的位数s[i]=s[i-1]+a[i]; //前i组的长度s[i] 便是 前i-1组的长度s[i-1] + 第i组的长度a[i]} //log（）是重载函数，必须对int的i强迫类型转换，以断定参数类型return;}固然采取的是数组打表的办法在多量测试用例的景象下会快很多，然则累加过程是一样的，耗时差别如此之大，我想，可能就是出在断定语句上了。
他的断定语句是“i<31269”，而我的是“sum < 2147483647”，题目或许就出在这里，我的小于号两端用来斗劲的数字都太大。事实证实是如许的，我采取了与他类似的断定前提来累加后，耗时变成了0s，然后我将while的剖断前提从sum < index改为了index - sum > 0，耗时也是0s。
为什么只是一个小小的批改，耗时却变更这么大呢？或许我们要到底层去推敲，int型的变量占4个字节，也就是32bit，两个斗劲大32bit的数字彼此斗劲天然比两个斗劲小的彼此斗劲要耗时很多。或许再连络汇编里的常识会懂得地更透辟一些，然则很遗憾我已经忘了。。。
下面是完全的代码，在POJ上经由过程，268K 16MS。（若是打表的话，占用内存会增长，然则时候会削减，以空间换时候罢了，既然如许能过就不打表了）
1 ＃include <iostream>
2 ＃include <cmath>
3 ＃include <fstream>
4 ＃include <time.h>
5 using namespace std;
6
7 int size（int num）
8 {
9 return int（log10（double（num））） + 1;//数字num的长度
10 }
11
12 int digit（int num， int length）
13 {
14 length = size（num） - length;
15 while（length--）
16 {
17 num /= 10;
18 }
19 num ％= 10;
20 return num; //返回数字num的第length个数字
21 }
22
23 int main（）
24 {
25 //ifstream in（in.txt）;//重定向cin和cout，使法度从文本读入数据，避免一遍遍输入
26 //cin.rdbuf（in.rdbuf（））;
27
28 //ofstream out（out.txt）;
29 //cout.rdbuf（out.rdbuf（））;
30
31 //time_t start，stop; //用于查看耗时
32
33 int t，k;
34 long index， sk， sum;
35 cin >>t;
36 while（t--）
37 {
38 cin >>index;
39
40 //cout <<endl <<endl <<index = <<index <<endl;
41
42 sum = 1;
43 k = 1;
44 sk = 1;
45
46 //time（&start）; //返回当前时候到start
47
48 while（index - sum > 0） //若是sum < index 则超时
49 {
50 k++;
51 sk += size（k）;
52 sum += sk;
53 }
54
55 //time（&stop）; //返回当前时候到stop
56 //cout <<time_cost= <<stop - start <<endl;
57
58 sum = index - sum + sk;
59
60 //cout << sk残剩长度 << sum <<endl;
61
62 int num = 1;
63 int length = 1;
64 while（length < sum）
65 {
66 num++;
67 length += size（num）;
68 }
69
70 length = sum - length + size（num）;
71
72 //cout << num残剩长度 <<length <<endl;
73 //cout << 数字num是 <<num <<endl;
74
75 cout <<digit（num， length） <<endl;
76 }
77 return 0;
78 }
