落絮飞雁的个人网站

顺流而下,把梦做完

HDOJ2045:不容易系列之(3)—— LELE的RPG难题——递推求解

Problem Description
人称“AC女之杀手”的超级偶像LELE最近忽然玩起了深沉,这可急坏了众多“Cole”(LELE的粉丝,即”可乐”),经过多方打探,某资深Cole终于知道了原因,原来,LELE最近研究起了著名的RPG难题:

有排成一行的n个方格,用红(Red)、粉(Pink)、绿(Green)三色涂每个格子,每格涂一色,要求任何相邻的方格不能同色,且首尾两格也不同色.求全部的满足要求的涂法.

以上就是著名的RPG难题.

如果你是Cole,我想你一定会想尽办法帮助LELE解决这个问题的;如果不是,看在众多漂亮的痛不欲生的Cole女的面子上,你也不会袖手旁观吧?

Input
输入数据包含多个测试实例,每个测试实例占一行,由一个整数N组成,(0=4是才能用。
f[1]=k; f[2]=k*(k-1); f[3]=k*(k-1)*(k-2);
如果n很大的会话,可以利用矩阵乘法快速幂进行加速。
可以参考Matrix67的博客

代码:

#include
int main()
{
	_int64 i, t = 1, j, n[52];
	n[1] = 3;
	n[2] = n[3] = 1;
	for (i = 4; i<51; i++)
	{
		if (i % 2 == 0)  n[i] = 2 * t + 1;
		else        n[i] = 2 * t - 1;
		t = n[i];
	}
	while (~scanf("%lld", &j))
	{
		if (j == 1)  printf("%dn", n[1]);
		else
			printf("%lldn", 6 * n[j]);
	}
	return 0;
}

HDOJ:阶乘取余

一道关于递推的题目,题目链接在这里
READ MORE →

HDOJ2044:一只小蜜蜂…——递推求解

Problem Description
有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房,不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。
其中,蜂房的结构如下所示。

Input
输入数据的第一行是一个整数N,表示测试实例的个数,然后是N 行数据,每行包含两个整数a和b(0<a<b<50)。

Output
对于每个测试实例,请输出蜜蜂从蜂房a爬到蜂房b的可能路线数,每个实例的输出占一行。

Sample Input
2
1 2
3 6

Sample Output
1
3

递推求解,注意_int64。

代码:

#include
int main()
{
    int a, b, n, i;
    _int64 cell[52] = { 1, 1, 2 };
    for (i = 3; i<51; i++)
        cell[i] = cell[i - 1] + cell[i - 2];
    while (~scanf("%d", &n))
    {
        while (n--)
        {
            scanf("%d%d", &a, &b);
            printf("%lld\n", cell[b - a]);
        }
    }
    return 0;
}

HDOJ1465:不容易系列之一——递推求解

Problem Description
大家常常感慨,要做好一件事情真的不容易,确实,失败比成功容易多了!
做好“一件”事情尚且不易,若想永远成功而总从不失败,那更是难上加难了,就像花钱总是比挣钱容易的道理一样。
话虽这样说,我还是要告诉大家,要想失败到一定程度也是不容易的。比如,我高中的时候,就有一个神奇的女生,在英语考试的时候,竟然把40个单项选择题全部做错了!大家都学过概率论,应该知道出现这种情况的概率,所以至今我都觉得这是一件神奇的事情。如果套用一句经典的评语,我们可以这样总结:一个人做错一道选择题并不难,难的是全部做错,一个不对。

不幸的是,这种小概率事件又发生了,而且就在我们身边:
事情是这样的——HDU有个网名叫做8006的男性同学,结交网友无数,最近该同学玩起了浪漫,同时给n个网友每人写了一封信,这都没什么,要命的是,他竟然把所有的信都装错了信封!注意了,是全部装错哟!

现在的问题是:请大家帮可怜的8006同学计算一下,一共有多少种可能的错误方式呢?

Input
输入数据包含多个多个测试实例,每个测试实例占用一行,每行包含一个正整数n(1<n<=20),n表示8006的网友的人数。

Output
对于每行输入请输出可能的错误方式的数量,每个实例的输出占用一行。

Sample Input
2
3

Sample Output
1
2

思路:
错排序列问题。难点在于找到递归式;初始状态F(1)=0,F(2)=1和状态转移式F(n)=(n-1)*F(n-2)

代码:

#include
int main()
{
    __int64 n, i, a[21] = { 1, 2 };
    for (i = 2; i<19; i++)
    {
        a[i] = (i + 1)*(a[i - 1] + a[i - 2]);
    }
    while (~scanf("%I64d", &n))
    {
        printf("%I64d\n", a[n - 2]);
    }
    return 0;
}

HDOJ2018母牛的故事

Problem Description
  有一头母牛,它每年年初生一头小母牛。每头小母牛从第四个年头开始,每年年初也生一头小母牛。请编程实现在第n年的时候,共有多少头母牛?
Input
  输入数据由多个测试实例组成,每个测试实例占一行,包括一个整数n(0<n<55),n的含义如题目中描述。

n=0表示输入数据的结束,不做处理。

Output
  对于每个测试实例,输出在第n年的时候母牛的数量。

每个输出占一行。

Sample Input
  2

4

5

0

Sample Output
  2

4

6


>#include
int sum[55]={1,2,3,4,6,9,13};
int main()
{
    int n,i;
    while(~scanf("%d",&n)&&n>0&&n<55)
    {
        for(i=7;i<55;i++)
        {
            sum[i]=sum[i-1]+sum[i-3];//此时三年的前的牛已经全部可育
        }
    printf("%dn",sum[n-1]);
    }
}