本文主要是介绍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;
}
这篇关于uva10706 - Number Sequence（找规律）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
