落絮飞雁的个人网站

顺流而下,把梦做完

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 (1<=n<=1000) Output For each test case, there is only one integer means the number of queue satisfied the headmaster’s needs. Sample Input 1 2 3 Sample Output 1 2 4 设:F(n)表示n个人的合法队列,则:按照最后一个人的性别分析,他要么是男,要么是女,所以可以分两大类讨论:

  • 1、如果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的大小。所以要用大数运算来做。但是大数运算至今没搞懂,就直接从网上找了大数的模板了……

    代码:

    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。不要问我怎么知道的……

    代码:

    HDOJ2050:折线分割平面

    折线分割平面

    Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

    Total Submission(s): 14929 Accepted Submission(s): 10324

    Problem Description

    我们看到过很多直线分割平面的题目,今天的这个题目稍微有些变化,我们要求的是n条折线分割平面的最大数目。比如,一条折线可以将平面分成两部分,两条折线最多可以将平面分成7部分,具体如下所示。

    Input 输入数据的第一行是一个整数C,表示测试实例的个数,然后是C 行数据,每行包含一个整数n(0<n<=10000),表示折线的数量。

    Output 对于每个测试实例,请输出平面的最大分割数,每个实例的输出占一行。

    Sample Input

    2

    1

    2

    Sample Output

    2

    7

    递推求解的问题,其实是在考数学……
    感谢@chuancqc 指正