编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

好象不能用power哦..

仔细想一想,很简单的奥数题目

虽然用了20分钟

...................

说到const,我是

const

lim:array[1..9] of longint=

(0,9,189,2889,38889,488889,5888889,68888889,100000000);

思路是很简单的

但是编起来很容易错

本来编出来就10来分钟 可是调试却用了半个小时才AC

就是错在1位数，2位数，3位数。。。。的个数上

我把他们重复加了

呵呵~~

希望你注意点呀

这样就可以了:

const data:array[1..8,1..4] of longint=

((1,9,9,1),(10,99,180,2),(100,999,2700,3),(1000,9999,36000,4),

(10000,99999,450000,5),(100000,999999,5400000,6),(1000000,9999999,63000000,7),(10000000,99999999,720000000,8));

将1位数，2位数，3位数...逐个去掉

然后计算,不过要小心点！

我也是那样做的……楼上有什么高见？

好主意，HOHO

不过麻烦点而已。

PS一句,Vijos的机器暴快,字符串其实也可以过.

将1位数，2位数，3位数...逐个去掉

然后计算

冷静下来后。。。简化一波代码 应该是逻辑比较清晰的 供后来人参考
```c++
#include<cstdio>
#include<cmath>
#include<cstring>
int main()
{
int n,pre_sum,sum=0,c = 1;
scanf("%d",&n);
int num ;
char sh[10];
for(int i=9;; i *= 10,c++)
{
pre_sum = sum;
sum += i*c;
if(sum > n)
{
//求该位的数
if((n-pre_sum)/c==0)
num =(int)pow(10,c-1);
else
num = (int)pow(10,c-1)+(n-pre_sum)/c-1;

//转换为字符数组
for(int j=c-1; j >= 0; j--)
{
sh[j] = num%10;
num = num/10;
}

//输出
if((n - pre_sum)%c == 0) printf("%d\n",sh[c-1]);
else printf("%d\n",sh[((n - pre_sum)%c)-1]);
break;
}
}
return 0;
}

哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈。。。。。。

哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈 。。。。。。

哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈。。。。。。

什么复杂度。。。。不用管就是。。。。直接找到这个数就好了 然后输出啊
c
#include<cstdio>
#include<cmath>
#include<cstring>
int main()
{
int n,pre_sum,sum=0,c = 1,m,d,e,f,len,pum=1;
scanf("%d",&n);
int num ;
char sh[10];
for(int i=9;; i *= 10,c++)
{
pre_sum = sum;
sum += i*c;
if(sum > n)
{
//求该位的数
d = (n-pre_sum)/c;
if(d==0)
{
for(int k=1;k <= c-1;k++)
pum *= 10;
e = pum;
}
else
{
for(int k=1;k <= c-1;k++)
pum *= 10;
e = pum+d-1;
}
num = e;
//转换为字符数组
for(int j=c-1; j >= 0; j--)
{
sh[j] = num%10;
num = num/10;
}
//输出
if((n - pre_sum)%c == 0) printf("%d\n",sh[c-1]);
else printf("%d\n",sh[((n - pre_sum)%c)-1]);
break;
}
}
return 0;
}


这一题我用了一个数学计算方法，时间复杂度为lgn
1-n位数共有(10^n)-1个数
因此第n位数共有((10^n)-1)-((10^(n-1))-1)个数
因此第n位数总长度为(((10^n)-1)-((10^(n-1))-1))*n
由此可知，若要求x位上的数
只需要首先取得x对应的从第n位开始的位数m
x所在的数为d=c^(n-1)-1+ceil(x/n)
从左往右数位数（从1开始）为：
若x%n==0，为n，否则为x%n
然后对d不断的除以10，直到取到所需要的位数为止
输出即可
测试数据 #0: Accepted, time = 0 ms, mem = 524 KiB, score = 20
测试数据 #1: Accepted, time = 0 ms, mem = 520 KiB, score = 20
测试数据 #2: Accepted, time = 0 ms, mem = 520 KiB, score = 20
测试数据 #3: Accepted, time = 15 ms, mem = 524 KiB, score = 20
测试数据 #4: Accepted, time = 0 ms, mem = 524 KiB, score = 20
Accepted, time = 15 ms, mem = 524 KiB, score = 100
代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <string.h>
using namespace std;
int main()
{
int i, j, n;
int c;
int d;
int e;
int len;
cin >> n;
i = 0;
c = 1;
len = 0;
if (n == 0)
{
cout << 0 << endl;
}
else
{
while (1)
{
i++;
c *= 10;
len += ((c - 1) - (c / 10 - 1))*i;
if (n <= len)
{
n -= len - ((c - 1) - (c / 10 - 1))*i;
d = c / 10 - 1 + n / i;
if (n%i > 0)
{
d++;
}
e = n%i;
if (e == 0)
{
e = i;
}
for (j = i; j >= 1; j--)
{
if (j == e)
{
cout << d % 10 << endl;
break;
}
d /= 10;
}
break;
}
}
}
return 0;
}

这一题我用的是O(logn)的算法，理论上来说假设数据类型允许高精度的话，n=10^10000000 以内都可以在半秒出解。
说说思路：主要用了等差比数列求和（错位相减+等比求和），然后后期处理一下。
根据常识我们有：

1位数(1~9) 共有9个
2位数(10~99) 共有90个
3位数(100~999) 共有900个
...
n位数 共有 9*10^(n-1) 个

而一个n位数有n位，故所有n位数有 9n*10^(n-1) 位。令

a(n) = 9n*10^(n-1)

通过数学方法对 a(n) 求前n项和( 记作 f(n) )，得

f(n) = (1+ (9*n-1) * 10^n ) / 9

f(n) 代表的意义是 所有1位数，2位数，... ，n位数 的位数总和
例如 f(2) 代表1位数和2位数的位数总和，=189
因此我们只需要枚举并找到最小的 i ，使得 f(i)>=n (n是题目中给出的位数)，我们就可以判断出题目要输出的那一位来自一个 i 位数
根据本题数据范围，i 一定小于8 (可以用几何画板验证一下)

在程序中，
k 代表这一个 i 位数到底是所有 i位数中的第几个 (从0编号)
j 代表究竟要输出这个 i 位数的第几位 (从0编号)
s 还原出这个 i 位数
接着的循环就是提取 s 的左起第 j 位了

//vijos 1181
#include <stdio.h>
int pow10[10];
int tmp[10];
int f(int n){
return (1+(9*n-1)*pow10[n])/9;
}
int main(){
int n, i, j, k, s;
scanf("%d", &n);
pow10[0] = 1;
for(i=1; i<10; i++)
pow10[i] = pow10[i-1]*10;
for(i=1; i<8; i++){
if(f(i) >= n)
break;
}
k = (n-f(i-1)-1)/i;
j = (n-f(i-1)-1)%i;
s = pow10[i-1]+k;
for(i=0; s>0; i++, s/=10)
tmp[i] = s%10;
printf("%d\n", tmp[i-j-1]);
return 0;
}

很简单很简单
#include<iostream>
#include<sstream>
#include<string>
using namespace std;

int tj(int a)
{
int ans=0;
while (a>0) ans++,a/=10;
return ans;
}

int main()
{
ios::sync_with_stdio(0);
int n,m=0,i=0;
cin>>n;
while (m<n) { ++i; m+=tj(i); }
string s;
stringstream ss;
ss<<i; ss>>s;
cout<<s[tj(i)-(m-n)-1];
return 0;
}

重新发一下，直接暴力枚举1-i,每次n减去i的位数，直到n<=i的位数
foo.cpp: In function 'int len(int)':
foo.cpp:16:1: warning: control reaches end of non-void function [-Wreturn-type]

测试数据 #0: Accepted, time = 0 ms, mem = 440 KiB, score = 20

测试数据 #1: Accepted, time = 0 ms, mem = 440 KiB, score = 20

测试数据 #2: Accepted, time = 0 ms, mem = 436 KiB, score = 20

测试数据 #3: Accepted, time = 0 ms, mem = 436 KiB, score = 20

测试数据 #4: Accepted, time = 78 ms, mem = 444 KiB, score = 20

Accepted, time = 78 ms, mem = 444 KiB, score = 100

代码

#include <cstdio>
#include <cstdlib>
using namespace std;
char t[11]="",ans;
int len(int x)
{
if(x<10) return 1;
else if(x<100) return 2;
else if(x<1000) return 3;
else if(x<10000) return 4;
else if(x<100000) return 5;
else if(x<1000000) return 6;
else if(x<10000000) return 7;
else if(x<100000000) return 8;
else if(x<1000000000) return 9;
}
int main()
{
int n,i=1;
scanf("%d",&n);
int tmp=len(1);
while(1){
if(n<=tmp) break;
n-=tmp;
i++;
tmp=len(i);
}
sprintf(t,"%d",i);
printf("%c",t[n-1]);
return 0;
}

直接暴力枚举1-i,每次n减去i的位数，直到n<=i的位数
编译成功

foo.cpp: In function 'int len(int)':
foo.cpp:16:1: warning: control reaches end of non-void function [-Wreturn-type]

测试数据 #0: Accepted, time = 0 ms, mem = 440 KiB, score = 20

测试数据 #1: Accepted, time = 0 ms, mem = 440 KiB, score = 20

测试数据 #2: Accepted, time = 0 ms, mem = 436 KiB, score = 20

测试数据 #3: Accepted, time = 0 ms, mem = 436 KiB, score = 20

测试数据 #4: Accepted, time = 78 ms, mem = 444 KiB, score = 20

Accepted, time = 78 ms, mem = 444 KiB, score = 100
#include <cstdio>
#include <cstdlib>
using namespace std;
char t[11]="",ans;
int len(int x)
{
if(x<10) return 1;
else if(x<100) return 2;
else if(x<1000) return 3;
else if(x<10000) return 4;
else if(x<100000) return 5;
else if(x<1000000) return 6;
else if(x<10000000) return 7;
else if(x<100000000) return 8;
else if(x<1000000000) return 9;
}
int main()
{
int n,i=1;
scanf("%d",&n);
int tmp=len(1);
while(1){
if(n<=tmp) break;
n-=tmp;
i++;
tmp=len(i);
}
sprintf(t,"%d",i);
printf("%c",t[n-1]);
return 0;
}

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 464 KiB, score = 20
测试数据 #1: Accepted, time = 0 ms, mem = 464 KiB, score = 20
测试数据 #2: Accepted, time = 0 ms, mem = 468 KiB, score = 20
测试数据 #3: Accepted, time = 15 ms, mem = 468 KiB, score = 20
测试数据 #4: Accepted, time = 0 ms, mem = 464 KiB, score = 20
Accepted, time = 15 ms, mem = 468 KiB, score = 100

终于过了~~~
原来是pow没考虑0次方！

#include <iostream>
#include <cstdio>

using namespace std;

int pow(int ds, int zs)
{
int jg = 0;
int idx = 0;
jg = ds;
if (zs == 0) return 1;
for (idx = 1; idx < zs; idx++)
{
jg *= ds;
}
return jg;
}

int main()
{
int n = 0, already = 0, i = 0;
int shang = 0, yu = 0;
char c[10];

cin >> n;
i = 1;
while(n > i * pow(10, i - 1) * 9)
{
n -= i * pow(10, i - 1) * 9;
already += 9 * pow(10, i - 1);
i++;
}
shang = n / i;
yu = n % i;
if (0 == yu)
{
already += shang;
cout << already % 10 << endl;
return 0;
}
already += shang + 1;
sprintf(c, "%d", already);
cout << c[yu - 1] << endl;
return 0;
}

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 856 KiB, score = 20
测试数据 #1: Accepted, time = 15 ms, mem = 860 KiB, score = 20
测试数据 #2: Accepted, time = 0 ms, mem = 860 KiB, score = 20
测试数据 #3: Accepted, time = 0 ms, mem = 856 KiB, score = 20
测试数据 #4: Accepted, time = 0 ms, mem = 860 KiB, score = 20
Accepted, time = 15 ms, mem = 860 KiB, score = 100
用很坑的方法ac了 哈哈...

猥琐的数学办法
#include <iostream>
using namespace std;

int base[]={0,0/*1位*/,10/*2位*/,100/*3位*/,1000/*4位*/,10000/*5位*/,100000/*6位*/,1000000/*7位*/,10000000/*8位*/};
int digit[]={0,9/*1位*/,189/*2位*/,2889/*3位*/,38889/*4位*/,488889/*5位*/,5888889/*6位*/,68888889/*7位*/,788888889/*8位*/};

int pow(int n);
int pos(int where,int mod,int length);

int main(){
int n,i,rest=0,length;
cin>>n;

if (n<10){
cout<<n<<endl;
return 0;
}

///找位数
for (i=1;;i++){
rest=n-digit[i];
if (rest<=0){
length=i;
n-=digit[length-1];
break;
}

}

//是从左到右第几位数
int mod=n%length;
//是哪个数
int div=(n+mod)/length;
int where=base[length]+div-1;

cout<<pos(where,mod,length)%10;
return 0;

}

//求where第mod位数
int pos(int where,int mod,int length){
if (length==2){
if (mod==1)
return where/10;
return where%10;

}
if (mod==1)
return where/base[length];
if (mod==0)
return where%10;
return ( where % pow(length-mod+1) ) / pow(length-mod);
}

//10^n
int pow(int n){
long long int ans=1;
for (int i=1;i<=n;i++)
ans*=10;
return ans;
}