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
	

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
	

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
	

HDOJ1297:Children’s Queue——递推求解、大数运算

Problem Description
There are many students in PHT School. One day, the headmaster whose name is PigHeader wanted all students stand in a line. He prescribed that girl can not be in single. In other words, either no girl in the queue or more than one girl stands side by side. The case n=4 (n is the number of children) is like
FFFF, FFFM, MFFF, FFMM, MFFM, MMFF, MMMM
Here F stands for a girl and M stands for a boy. The total number of queue satisfied the headmaster’s needs is 7. Can you make a program to find the total number of queue with n children?

Input
There are multiple cases in this problem and ended by the EOF. In each case, there is only one integer n means the number of children (11、如果n个人的合法队列的最后一个人是男,则对前面n-1个人的队列没有任何限制,他只要站在最后即可,所以,这种情况一共有F(n-1);

  • 2、如果n个人的合法队列的最后一个人是女,则要求队列的第n-1个人务必也是女生,这就是说,限定了最后两个人必须都是女生,这又可以分两种情况:
  • 2.1、如果队列的前n-2个人是合法的队列,则显然后面再加两个女生,也一定是合法的,这种情况有F(n-2);
  • 2.2、但是,难点在于,即使前面n-2个人不是合法的队列,加上两个女生也有可能是合法的,当然,这种长度为n-2的不合法队列,不合法的地方必须是尾巴,就是说,这里说的长度是n-2的不合法串的形式必须是“F(n-4)+男+女”,这种情况一共有F(n-4).
  • 所以F(n)=F(n-1)+F(n-2)+F(n-4)。因为题目要求n取值在1000以内,超过了_int64的大小。所以要用大数运算来做。但是大数运算至今没搞懂,就直接从网上找了大数的模板了……

    代码:

    #include
    #include
    #include
    using namespace std;
    long long s[1010][1005];
    int main()
    {
        int i,j,n;
        memset(s,0,sizeof(s));
        s[1][0]=1;s[2][0]=2;s[3][0]=4;s[4][0]=7;
        for(i=5;i=10){
                    s[i][j+1]+=s[i][j]/10;
                    s[i][j]%=10;
                }
           }
        }
    
        while(cin>>n){
            i=1000;
            while(i--){
                if(s[n][i]!=0)
                    break;
            }
            cout=0;i--)
                printf("%d",s[n][i]);
            cout
    	

    HDOJ2046:骨牌铺方格——递推问题

    Problem Description
    在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数.
    例如n=3时,为2× 3方格,骨牌的铺放方案有三种,如下图:

    Input
    输入数据由多行组成,每行包含一个整数n,表示该测试实例的长方形方格的规格是2×n (0<n<=50)。

    Output
    对于每个测试实例,请输出铺放方案的总数,每个实例的输出占一行。

    Sample Input
    1
    3
    2

    Sample Output
    1
    3
    2

    斐波那契数列解决,注意输出要用int64才行,否则WA。不要问我怎么知道的……

    代码:

    #include
    #include
    using namespace std;
    int main()
    {
    	_int64 fibn[51] = {1,2,3};
    	int i,j;
    	while (~scanf("%d", &i))
    	{
    		for (j = 3; j 
    	

    HDOJ1274:展开字符串——字符串处理

    Problem Description
    在纺织CAD系统开发过程中,经常会遇到纱线排列的问题。
    该问题的描述是这样的:常用纱线的品种一般不会超过25种,所以分别可以用小写字母表示不同的纱线,例如:abc表示三根纱线的排列;重复可以用数字和括号表示,例如:2(abc)表示abcabc;1(a)=1a表示a;2ab表示aab;如果括号前面没有表示重复的数字出现,则就可认为是1被省略了,如:cd(abc)=cd1(abc)=cdabc;这种表示方法非常简单紧凑,也易于理解;但是计算机却不能理解。为了使计算机接受,就必须将简单紧凑的表达方式展开。某ACM队接受了此项任务。现在你就是该ACM队的一员,请你把这个程序编写完成。
    已知条件:输入的简单紧凑表达方式的长度不超过250个字符;括号前表示重复的数不超过1000;不会出现除了数字、括号、小写字母以外的任何其他字符;不会出现括号不配对等错误的情况(错误处理已由ACM其他队员完成了)。

    Input
    本题有多个测试数据组,第一行输入的就是数据组数N,接着就是N行表达式,表达式是按照前面介绍的意义书写的。

    Output
    输出时含有N行,每行对应一个输入的表达式。

    Sample Input
    2
    1(1a2b1(ab)1c)
    3(ab2(4ab))

    Sample Output
    abbabc
    abaaaabaaaababaaaabaaaababaaaabaaaab

    栈问题。
    代码:

    #include
    #include
    #include
    using namespace std;
    string process(string s)
    {
    	string ans;
    	stack x;
    	for(int i=0;i='0'&&s[i]='a'&&s[i]='0')
    			{
    				int num=x.top()-'0';
    				x.pop();
    				while(num--)
    					x.push(s[i]);
    			}
    			else
    				x.push(s[i]);
    		}
    		else if(s[i]==')')
    		{
    			string temp;
    			while(x.top()!='(')
    			{
    				temp.insert(temp.begin(),x.top());
    				x.pop();
    			}
    			x.pop();
    			int num;
    			if(x.empty()||!(x.top()>='0'&&x.top()>test;
    	while(test--)
    	{
    		cin>>s;
    		cout