uva 10706 - Number Sequence

点击打开链接uva 10706

题目意思:    有一个数组 s[1] = 1 , s[2] = 1 2 , .......s[k] = 1....k,要求给定一个n表示数组的第几位,要求这个第几位是什么数。例如 n为1 时候是1 n为 2 时候是1 ,n 为3 时候为2

解题思路:    1:思路:预处理打表+查找
                     2:题目给的数据可以发现一些规律
                        s[1]:1                                   总位数1
                        s[2]:1 2                                总位数1+2 = 3
                        s[3]:1 2 3                             总位数1+2 +3 = 6
                        .
                        .
                        .
                        s[9]:1 2 3 4 5 6 7 8 9          总位数1+2 +3+...+9 = 45
                        s[10]:  1 2 3 4 5 6 7 8 9 10    总位数45+1+2 +3+...+9 +1+0 = 56
                        s[K]:1 2 3 4 . . . . . . k           总位数 num[k-1]+1+2+......
                                               用num[k]保存当值为k时候总的位数.
                      所以我们要是能够预先把所有的数据全部求出弄成一张表,然后输入的时候直接查找位于那个位置,然后在去查找这个位置 ,由于上面的递增趋势,我么可以推断当k到100000时候就会超过int,所以开个这么大的数组就可以了。
                     3:打表过程:我么采用枚举当前值的位数,例如位数为1,那么就有1-9共9位数,如果位数为2就有10-99公共90个.......假设当前的数值为n,那么根据上面的规律求出num[n],一次这样求出所以数据
                     4:查找,O(n)的时间复杂度,只要找到num[i-1] < n, num[i]>=n , 那么我们可以知道这个数存在s[n]中,把n减去num[i-1],可以知道要求的数在s[n]中第几位,然后再去一一判断。注意这里n可能为1234等多位数,那么要把他拆开,这时候是先拆前面即最大位。
                     5注意事项:由于这一题的n最大为2147483647,那么我们开得num数组要为long long,中间的一些处理也要为long long不然会有精度缺失

代码:

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
using namespace std;
#define MAXN 100000

int  t , n;
long long  num[MAXN];//保存某一个值的总数

//打表初始化
void init(){
    long long i , j , k , tmp;//long long注意
    memset(num , 0 , sizeof(num));//初始化
    for(i = 1 ; i <= 5 ; i++){//枚举位数,最大到5位即可
        for(j = pow(10,i-1) ; j < pow(10,i) ; j++){
            num[j] = num[j-1] ; tmp = (j-pow(10,i-1)+1)*i;
            for(k = 1 ; k < i ; k++)
                tmp +=(pow(10,k)-pow(10,k-1))*k;
            num[j] += tmp;
        }
    }
}

void solve(){
    int i , j , k , pos , ans;
    //找到pos位置
    for(i = 1 ; i < MAXN ; i++){
        if(n > num[i-1] && n <= num[i]){
            pos = i ; break;
        }
    }
    //查找
    int cnt = n-num[pos-1] ; int sum = 0;
    int len , tmp , tmp_j;
    for(j = 1 ; j <= pos ; j++){
        tmp_j = j;
        for(i = tmp_j , len = 0 ; i != 0 ; i/=10) len++;
        for(k = len-1; k >= 0 ;k--){
            ans = tmp_j/pow(10,k) ; sum++;
            if(sum == cnt){
                printf("%d\n" , ans);
                return;
            }
            tmp = pow(10,k) ; tmp_j %= tmp;
        }
    }
}

int main(){
    //freopen("input.txt" , "r" , stdin);
    init() ; scanf("%d" , &t);
    while(t--){
        scanf("%d" , &n) ; solve();
    }
    return 0;
}
时间: 2024-11-08 22:31:04

uva 10706 - Number Sequence的相关文章

UVa 10706:Number Sequence

链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=1647 原题: A single positive integer i is given. Write a program to find the digit located in the position i in the sequence of n

UVa 10706 / POJ 1019 Number Sequence:打表及O(1)算法

10706 - Number Sequence Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=19&page=show_problem&problem=1647 http://poj.org/problem?id=1019 Description A single positive integer i is giv

acm-杭电ACM OJ 1005 Number Sequence

问题描述 杭电ACM OJ 1005 Number Sequence A number sequence is defined as follows: f(1) = 1 f(2) = 1 f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7. Given A B and n you are to calculate the value of f(n). 超过49个数之后一定会出现和之前的数组合相同的情况,这个我可以了解,但是 为什么最多经过49个数之后一定会出现周

[ACMcoder] Number Sequence

Problem Description A number sequence is defined as follows: f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7. Given A, B, and n, you are to calculate the value of f(n). Input The input consists of multiple test cases. Each test case co

HDOJ 1005 Number Sequence

Problem Description A number sequence is defined as follows: f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7. Given A, B, and n, you are to calculate the value of f(n). Input The input consists of multiple test cases. Each test case co

UVa 10049 Self-describing Sequence:自描述序列&amp;amp;二分递推

10049 - Self-describing Sequence Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=34&page=show_problem&problem=990 Solomon Golomb's self­describing sequence is the only non­decreasing

UVa 11371 Number Theory for Newbies (water ver.)

11371 - Number Theory for Newbies Time limit: 1.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2366 Given any positive integer, if we permute its digits, the differenc

算法题:UVA 10534 Wavio Sequence(dp + LIS)

Wavio is a sequence of integers. It has some interesting properties. ·  Wavio is of odd length i.e. L = 2*n + 1. ·  The first (n+1) integers of Wavio sequence makes a strictly increasing sequence. ·  The last (n+1) integers of Wavio sequence makes a

hdu 1711 Number Sequence

点击打开链接hdu1711 思路:KMP kmp算法: 1 kmp是用来匹配字符串,只能够匹配单一的字符串 2 kmp的算法的过程:   1:假设文本串的长度为n,模式串的长度为m:   2:先例用O(m)的时间去预处理next数组,next数组的意思指的是当前的字符串匹配失败后要转到的下一个状态:   3:利用o(n)的时间去完成匹配: 3 时间复杂度为o(n+m)即o(n): 代码: #include<algorithm> #include<iostream> #include