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 }
题目地址: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;
固然采取的是数组打表的办法在多量测试用例的景象下会快很多,然则累加过程是一样的,耗时差别如此之大,我想,可能就是出在断定语句上了。
他的断定语句是“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 }