首页 > 代码库 > uva10706 - Number Sequence(找规律)

uva10706 - Number Sequence(找规律)

题目:uva10706 - Number Sequence(找规律)


题目大意:有这样一串序列11212312341234512345612345671234567812345678912345678910123456789101112345678910...,问第i个位置数的值。

                                                  1  2     3       4          5            6              7               ... 

解题思路:这题需要发现规律。我一开始还看错题意了。规律是看了别人的题解才明白的。

                    这里定义s【i】代表第i个序列的位置。例如上面那串序列下面标的数字就代表属于哪个序列。(1序列的位置1,3序列的位置6...)

                    num【i】代表第i个序列的长度。注意数字10长度位2.

                    递推公式: s【i】 =  s【i - 1】  + s【i - 1】 - s【i - 2】 + Wi(i的位数)。

                    求第i序列的位置,那么就要从第i - 1序列的位置开始+序列i的长度。 s【i-1】 - s【i - 2】 :i- 1序列的位置,减去i - 2序列的位置,就是i - 1序列的长度,也就是num【i - 1】。  那么只要在i - 1序列的位置加上i - 1的长度,最后i序列的长度和i - 1序列的长度差的就是 i的位数。

                  这里需要预处理数组s和num,之后的查找就是遍历这两个数组,找到相应的值。数组的大小开到1e5就可以了,已经超过2147483647了。

                  求第i个位置的值,那么就要先找到位于哪个序列。遍历s数组,找到s【k - 1】 <= i, 将i 减去s【k - 1】(k - 1序列的位置)就是i位置在k序列中的长度。

                   然后每个序列的长度也是由规律的: 序列3 :123 长度3

                                                                                       序列4:1234 长度4

                                                                                       序列i和序列i - 1相差的长度其实就是i的位数,而且又是递增的。

                   在num数组里面找到num【k - 1】 >= i <=num[k],那么意味着i的值就是k位数里的其中一个。


代码:

#include <stdio.h>
#include <math.h>

typedef long long ll;
const ll N = 2147483647;
const int w[] = {0, 10, 100, 1000, 10000, 100000};    //(0位1位2位...)位数分界值
const int M = 100000;
ll s[M];
ll num[M];
//预处理
void init () {

	s[0] = num[0] = 0;
	s[1] = num[1] = 1;
	int cur = 1;
	for (int i = 2; s[i - 1] < N; i++) {

		if (i >= w[cur]) cur++;
		s[i] = 2 * s[i - 1] - s[i - 2] + cur;
		num[i] = s[i] - s[i - 1];
	}
}

int main () {

	init();
	int t;
	ll n;
	scanf ("%d", &t);
	char str[10];
	while (t--) {

		scanf ("%lld", &n);
		int i;

		for (i = 1; i < M ; i++)
			if (s[i] >= n)
				break;
		n -= s[i - 1];

		for (i = 1; i < M; i++)
			if (num[i] >= n)
				break;
		n -= num[i - 1];	

		sprintf (str, "%d", i);
		printf ("%c\n", str[n - 1]);
	}
	return 0;
}