HDOJ 1005 Number Sequence

题目地址:

http://acm.hdu.edu.cn/showproblem.php?pid=1005

曾经失败过,今天怀着论坛挂了的沉重心情再做了一次,先准备用上hash表的。

后来一想,数据很小的,必然会再前50次里碰到开始循环的局面。

为何?

思路:

因为循环的条件就是有2个数m和n

f[m-1] = f[n-1], f[m] = f[n]

这样就会开始循环了。

即f[n-1], f[n]与之前的[m-1],f[m]分别对应

而 0 <= f[n-1],f[n] < 7

所以f[n-1]f[n]连着的情况有7*7的情况。

只需每次求出一个f[n],然后比较f[n-1]f[n]与前面数的情况即可。

代码:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 // Author: Tanky Woo
// HDOJ 1005
// Accepted 1005 0MS 276K 815B G++ Tanky Woo 
#include <iostream>
int f[60];
 
int a, b, c;  // 分别代表f[i-2], f[i-1], f[i];
 
int A, B, n;
 
int main()
{
	while(scanf("%d %d %d", &A, &B, &n) && (A||B||n))
	{
		memset(f, 0, sizeof(f));
		f[1] = 1;
		f[2] = 1;
		// f[n] = A*f[n-1]+B*f[n-2] = A*b+B*a;
		a = 1;  // f[n-2]
		b = 1;  // f[n-1]
		c = (A+B)%7;
		int cnt = 0, loop = 0;
		for(int i = 3; i < 60; ++i)
		{
			f[i] = c;
			a = b;
			b = c;
			c = (A*b+B*a)%7;
			for(int j = 2; j < i; ++j)
				if(f[j-1] == f[i-1] && f[j] == f[i])
				{
					cnt = j;   //从cnt开始循环
					loop = i-j;  // 循环数
					break;
				}
		}
		if(n < cnt)
			printf("%d\n", f[n]);
		else
			printf("%d\n", f[cnt+(n-cnt)%loop]);
	}
	return 0;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDOJ 1005 Number Sequence》有419个想法

  1. 同受益匪浅!以下是我仿照你的代码写的:

    #include

    int main()
    {
    int a,b,n,i,j,len,pos;
    int ans[51];
    scanf(“%d%d%d”,&a,&b,&n);
    while(a+b+n)
    {
    ans[0] = 1;
    ans[1] = 1;
    for(i = 2; i < 51; ++i)
    {
    ans[i] = (a*ans[i-1] + b*ans[i-2]) % 7;
    for(j = 0; j + 1 < i; ++j)
    {
    if(ans[j] == ans[i-1] && ans[j+1] == ans[i])
    {
    pos = j; //循环开头位置
    len = i – j – 1; //循环长度
    break;
    }
    }
    }
    printf("%d\n",ans[(n-pos) % len]);
    scanf("%d%d%d",&a,&b,&n);
    }
    return 0;
    }

    把f[n]f[n+1]作为一对,最多连续出现49种不同的配对,也就是说循环节最长是50,第50对一定会跟前面某一对相同,大多数情况下是第1对。

发表评论

电子邮件地址不会被公开。 必填项已用*标注