126 条题解

  • 3
    @ 2017-05-08 12:36:01
    /*
    这一题我用的是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+ (9n-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 位了
    #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;
    }*/
    /*
    数学解法害怕
    但是数据不大直接枚举暴力也是可以得
    直接暴力枚举1-i,每次n减去i的位数,直到n<=i的位数
    */
    #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;
    }
    
  • 2
    @ 2018-10-30 16:22:56

    首先可以发现,1位的数有9个,2位的数有90个,m位的数有9 * 10^(m-1)个
    由此因此可以先枚举出最后的数的位数
    之后可以用剩下的数字个数除位数即可以卡出确定的数
    然后取出相应的位数就可以了

    #include<iostream>
    using namespace std;
    int main()
    {
        int n,i,j,jie=1,num,h;
        cin>>n;
        for(i=1;;i++)
        {
            if(n-9*i*jie>0)
             {
                n-=9*i*jie;
                jie*=10;
                continue;
             }
            num=jie+n/i;
            h=n-n/i*i;
            if(h==0)
            {
                num--;
                h=i;
            }
            for(j=1;j<=i-h;j++)
            {
                num/=10;
            }
            break;
        }
        cout<<num%10;
        return 0;
    }
    
  • 0
    @ 2016-10-14 20:35:18
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    int lena;
    long long n,ans,temp1,temp2;
    int b[15],a[100]={0,1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000},t;
    char c[15];
    int main()
    {
        cin>>n;
        for(int i=1;i<=9;i++)
        {
        if(n-9*a[i]*i>0){n=n-9*a[i]*i;
        ans+=9*a[i];}
        else {t=i;break;}
        }   
        temp1=n%t;
        temp2=n/t;
    if(temp1==0)
        ans=ans+temp2;
        else
        ans=ans+temp2+1;
    itoa(ans,c,10);
    lena=strlen(c);
    if(temp1==0)
    cout<<c[lena-1];
    else
    cout<<c[temp1-1];
    return 0;
    }
    
  • 0
    @ 2016-08-20 11:26:56

    var n, a, b, c, x, y, z, i, w : longint;
    s : string;
    begin
    readln(n);
    a:=1; b:=9; c:=0;
    while c<=n do begin
    inc(c, a*b);
    inc(a);
    b:=b*10;
    end;
    c:=c-(a-1)*(b div 10);
    x:=n-c;
    if x=0 then
    writeln(0)
    else begin
    y:=1;
    for i:=1 to a-2 do y:=y*10;
    w:=0; s:='';
    repeat
    inc(w, a-1);
    if w>=x then begin
    str(y, s);
    writeln(s[a-1-(w-x+1)+1]);
    exit;
    end;
    inc(y);
    until false;
    end;
    end.

  • 0
    @ 2013-11-20 00:18:42

    水翻了。。。
    var n,m,i,j,k:longint;
    s:string;
    begin
    read(n);
    i:=0;j:=1;k:=1;
    while k*9+i<n do
    begin
    i:=i+k*9;
    n:=n-j*k*9;
    j:=j+1;k:=k*10;
    end;
    i:=i+(n div j);
    if n mod j=0 then write(i mod 10)
    else begin i:=i+1;
    str(i,s);
    write(s[n mod j]);
    end;
    end.

  • 0
    @ 2013-10-29 21:34:41

    坑人的程序,自己领悟吧...
    评测结果
    编译成功

    测试数据 #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
    代码
    const
    d:array[1..8] of longint=(9,189,2889,38889,488889,5888889,68888889,788888889);

    f:array[1..8] of longint=(10,100,1000,10000,100000,1000000,10000000,100000000);
    var
    n,a,b,i:longint;
    m:ansistring;
    begin
    readln(n);
    for i:=8 downto 1 do
    if n>d[i] then
    begin
    n:=n-d[i];
    a:=n div (i+1)+f[i]-1;
    b:=(n-1) mod (i+1)+1;
    str(a,m);
    write(m[b]);
    break;
    end;
    end.

  • 0
    @ 2013-08-27 14:34:47

    为毛我的暴力没过,暴力只拿了80
    害得我重写了一遍。。。
    0s了。。
    program encryption;
    var a:array[0..10] of int64;
    n,i,j,k:longint;
    num:string;
    begin
    readln(n);
    a[1]:=9;
    for i:=2 to 10 do a[i]:=trunc(a[i-1]*10);
    i:=1;
    while a[i]*i<n do
    begin
    n:=n-trunc(a[i]*i);
    inc(i);
    end;
    k:=1;
    for j:=1 to i-1 do k:=trunc(k*10);
    if n mod i=0 then writeln((k+(n div i)-1) mod 10)
    else
    begin
    j:=k+(n div i);
    str(j,num);
    writeln(num[n mod i]);
    end;
    end.

  • 0
    @ 2012-10-15 18:45:29

    编译通过... 

    ├ 测试数据 01:答案正确... (0ms, 580KB) 

    ├ 测试数据 02:答案正确... (0ms, 580KB) 

    ├ 测试数据 03:答案正确... (0ms, 580KB) 

    ├ 测试数据 04:答案正确... (0ms, 580KB) 

    ├ 测试数据 05:答案正确... (0ms, 580KB) 

    program _1181;

    var

      n,m,i,j,k:longint;

    function e(a:longint):longint;

    var

      s:longint;

    begin

      s:=1;

      while a>0 do

        begin

          dec(a);

          s:=s*10;

        end;

      exit(s);

    end;

    begin

      read(n);

      m:=n;

      i:=1;

      j:=1;

      while m-i*j*9>=0 do

        begin

          m:=m-i*j*9;

          inc(i);

          j:=j*10;

        end;

      while m>i do

        begin

          inc(j);

          dec(m,i);

        end;

      writeln(j mod e(i-m+1) div e(i-m));

    end.

    以为会很麻烦的,所以写的很麻烦。。。。。。。。。。

  • 0
    @ 2012-09-27 08:34:10

    范围太小了10的8次估计也就是上百万次运算,不会超时,直接模拟可过,我的做法是m每一次等于i的时候乘以10,然后用n-,这样就不会多算,也不用保存到字符串里

  • 0
    @ 2012-08-20 10:03:38

    编译通过...

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

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

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

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

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

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

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

    现在评测机不办事了,所以没办法暴力枚举了。。。

    program p1181;

    const count:array[1..8] of longint=(9,90,900,9000,90000,900000,9000000,90000000);

    orz:array[1..8] of longint=(1,10,100,1000,10000,100000,1000000,10000000);

    var n,ans,sum,i,j,k,aa,l:longint;

    a:array[1..100000000] of char;

    s:string;

    begin

    readln(n);

    ans:=0;

    for i:=1 to 8 do

    begin

    ans:=ans+i*count[i];

    if ans>n then begin aa:=i-1; break; end;

    end;

    sum:=0;

    for i:=1 to aa do

    sum:=sum+count[i]*i;

    k:=0;

    while sum

  • 0
    @ 2012-08-12 21:25:31

    编译通过...

    ├ 测试数据 01:答案正确... (36ms, 580KB)

    ├ 测试数据 02:答案正确... (75ms, 580KB)

    ├ 测试数据 03:答案正确... (60ms, 580KB)

    ├ 测试数据 04:答案正确... (134ms, 580KB)

    ├ 测试数据 05:答案正确... (837ms, 580KB)

    朴素算法就可以了。。膜拜评测机的CPU

  • 0
    @ 2012-08-02 15:35:20

    编译通过...

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

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

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

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

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

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

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

    点击查看代码

  • 0
    @ 2009-10-24 14:44:31

    var

    n,i,t,l:longint;

    s:string;

    begin

    readln(n);

    i:=1;l:=1;

    while n>l do begin

    n:=n-l;

    inc(i);

    l:=trunc(ln(i)/ln(10))+1;

    end;

    str(i,s);

    writeln(s[n]);

    end.

  • 0
    @ 2009-10-29 16:36:43

    var

    n,i:longint;

    s:string;

    begin

    readln(n);

    i:=1;

    while n>1 do

    begin

    n:=n-1;

    inc(i);

    str(l,i);

    end;

    str(i,s);

    writeln(s[n]);

    end.

  • 0
    @ 2009-10-21 13:19:11

    ...

    简单题。。

    直接+可得答案。。

  • 0
    @ 2009-10-15 14:56:35

    编译通过...

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

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

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

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

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

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

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

    直接算。。。

  • 0
    @ 2009-10-13 23:50:30

    不能用ansistring模拟

    用数字模拟

    还是很慢

    sunny会超时

    编译通过...

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

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

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

    ├ 测试数据 04:答案正确... 9ms

    ├ 测试数据 05:答案正确... 806ms

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

    Accepted 有效得分:100 有效耗时:815ms

  • 0
    @ 2009-10-13 23:26:30

    一次秒杀,纯粹是数论的题。

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

    编译通过...

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

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

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

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

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

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

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

    var n,i:longint;

    procedure init;

    begin

    readln(n);

    end;

    procedure find(n:longint);

    var z,t,k,i,j,m:longint;

    s:string;

    begin

    m:=n;

    i:=1;

    j:=9;

    t:=1;

    while m>j*i do

    begin

    m:=m-j*i;

    j:=j*10;

    inc(i);

    t:=t*10;

    end;

    k:=m div i;

    t:=t+k-1;

    z:=m mod i;

    if z=0 then

    begin

    writeln(t mod 10);

    end

    else

    begin

    str(t+1,s);

    writeln(s[z]);

    end;

    end;

    begin

    init;find(n);

    end.

  • 0
    @ 2009-10-12 19:53:07



    第一次常量大错!!!

  • 0
    @ 2009-10-11 21:41:15

    var p,n,s,d,i,j:longint;

    a:array[1..100]of integer;

    begin

    readln(n);

    s:=0;d:=9;i:=1;

    while s+d*i

信息

ID
1181
难度
5
分类
模拟 点击显示
标签
递交数
1835
已通过
682
通过率
37%
被复制
6
上传者