HDU Page11(2041～2050)递推

//f[i]表示到达台阶i的方案数，由于只能从i-1或者i-2到达台阶 i 因此f[i]=f[i-1]+f[i-2] 。

#include <stdio.h>

int main(int argc, const char * argv[]) {
    // insert code here...
    
    int n, m, steps[105], maxM = 2;
    steps[1] = 1;
    steps[2] = 1;
//    steps[3] = 2;
    
    scanf("%d", &n);
    
    while (n--) {
        scanf("%d", &m);
        
        if (maxM < m) {
            for (int i=3; i<=m; i++) {
                steps[i] = steps[i-1] + steps[i-2];
            }
            maxM = m;
        }
        
        printf("%d\n", steps[m]);
    }
    
    return 0;
}

#include <stdio.h>
#include <string.h>

int main(int argc, const char * argv[]) {
    // insert code here...
    
    int n;
    char s[105];
    
    scanf("%d", &n);
    
    while (n--) {
        int check[4] = {0, 0, 0, 0};
        scanf("%s", s);
        if (strlen(s) >= 8 && strlen(s) <= 16) {
            for (int i=0; i<strlen(s); i++) {
                if (s[i] >= 'A' && s[i] <= 'Z')
                    check[0] = 1;
                else if (s[i] >= 'a' && s[i] <= 'z')
                    check[1] = 1;
                else if (s[i] >= '0' && s[i] <= '9')
                    check[2] = 1;
                else if (s[i] == '~' || s[i] == '!' || s[i] == '@' || s[i] == '#' || s[i] == '$' || s[i] == '%' || s[i] == '^')
                    check[3] = 1;
            }
            
            if ((check[0] + check[1] + check[2] + check[3]) >= 3)
                printf("YES\n");
            else
                printf("NO\n");
        } else
            printf("NO\n");
        
        
    }
    
    return 0;
}

#include <stdio.h>
#include <string.h>

int main(int argc, const char * argv[]) {
    // insert code here...

    int n, a, b;
    //注意这个1-50就会很长，用long int都是错误的
    long long int f[105];

    scanf("%d", &n);

    while (n--) {
        scanf("%d %d", &a, &b);

        f[a] = 1;
        f[a+1] = 1;

        for (int i=a+2; i<=b; i++) {
            f[i] = f[i-1] + f[i-2];
        }

        printf("%lld\n", f[b]);
    }

    return 0;
}

//#include <stdio.h>
//int main(){
//    long long dp[51];
//    int a, b, z, i;
//    scanf("%d", &z);
//    dp[1] = 1;
//    dp[2] = 2;
//    for ( i=3; i<=50; ++i ){
//        dp[i] = dp[i-2]+dp[i-1];
//    }
//    while (z--){
//        scanf("%d%d", &a, &b);
//        printf("%lld\n", dp[b-a]);
//    }
//    return 0;
//}

//注意题目要求，首尾也不相同
//有排成一行的ｎ个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色
/*
  n个格子合乎题目要求的涂色时（即称之为合法）对应一个映射f  使f（n）即为所求值。那么接下来分析，当涂
 第n个格子的时候，即要求f（n）时，受到第n-1个格子是否与第一个格子相同的制约。那么接下来的问题是对第
 n-1个格子分两种情况：假定其和第一个格子不同颜色，那么也就是说前n-1个格子是合法的涂法可以写为f（n-1），
 再涂最后一个格子只有一种涂法。第二种第n-1个格子和第一个相同，那么前n-1不合法，且此时第n-2个格子一定和
 第一个不同，那么此时前n-2个格子必定又是合法的,且第n个格子2种涂法。那么对f（n）的贡献为f(n-2)*2，那么
 f(n)来源于前两种情况的和，由加法原理。f（n）=f（n-1）+f(n-2)*2;
 n>3(注意是如何确定的)
 前面的1， 2， 3要自己考虑
 */

#include <stdio.h>

int main(int argc, const char * argv[]) {
    // insert code here...

    int n;
    //注意递归的其实数字马上很大的，要long long
    long long res[105] = {3, 6, 6};
    
    while (scanf("%d", &n) != EOF) {
        for (int i=3; i<n; i++) {
            res[i] = res[i-1] + res[i-2] * 2;
        }
        printf("%lld\n", res[n-1]);
    }

    return 0;
}

#include <stdio.h>

int main(int argc, const char * argv[]) {
    // insert code here...

    int n, maxN = 2;
    long long int f[60];
    f[1] = 1;
    f[2] = 2;
    
    while(scanf("%d", &n) != EOF) {
        if (maxN < n) {
            for (int i=maxN+1; i<=n; i++) {
                f[i] = f[i-1] + f[i-2];
            }
            maxN = n;
        }
        printf("%lld\n", f[n]);
    }

    return 0;
}

/*
 关于这道题我们直接考虑n为‘o’时候的情况，因为题目说只要‘oo’不相邻就算一组题解，当n为‘o’的时候，n-1只能是‘e’或者‘f’，n-2则是每组‘e’，‘o’，‘f’都可以取，
 能够得到f(n)=2f(n-2);
 然后考虑n不为‘0’,n为‘e’或者‘f’，则n-1对于‘e’，‘o’，‘f’都可选取，择有f(n)=2*f(n-1)，
 然后换位思考，站在‘e’‘f’的角度看问题你会发现‘e’关于‘f’是对称的，即f(n)=2*(f(n-1)+f(n))
 */

#include <stdio.h>

int main(int argc, const char * argv[]) {
    // insert code here...

    int n, maxN = 2;
    long long int f[60];
    f[1] = 3;
    f[2] = 8;
    
    while(scanf("%d", &n) != EOF) {
        if (maxN < n) {
            for (int i=maxN+1; i<=n; i++) {
                f[i] = 2*(f[i-1] + f[i-2]);
            }
            maxN = n;
        }
        printf("%lld\n", f[n]);
    }

    return 0;
}

/*
题意是给出抽奖的人数，抽中自己的名字算中奖，计算没有一个人中奖的概率
可以用错排+递推
分析：
全错的概率 = 全错数 / 全部情况。
全部情况就是N的阶乘。
全错数：
 1.将第N个数放在k位置，有n-1种。
2.将第k个位置的数拿出来考虑，如果第k个数放在第N个位置，则剩下就是n-2个数全部排错情况；
如果第k个数不是放在第N个位置，则就是n-1个数全部排错情况（这是对的，可把k看成n，n不会放到N位置，所以算错排?）
因此全错数就是a(n) = (n-1)*(a(n-1) + a(n-2))
 */

#include <stdio.h>

long long int jieceng(int n) {
    long long sum = 1;
    while (n) {
        sum *= n;
        n--;
    }
//    printf("%lld\n", sum);
    return sum;
}

int main(int argc, const char * argv[]) {
    // insert code here...

    int n, m, maxN = 2;
    double f[60];
    f[1] = 0;
    f[2] = 1;
    
    scanf("%d", &m);
    while (m--) {
        scanf("%d", &n);
        if (maxN < n) {
            for (int i=maxN+1; i<=n; i++) {
                f[i] = (i-1)*(f[i-1] + f[i-2]);
            }
            maxN = n;
        }
//        printf("%.2lf\n", f[n]);
        printf("%.2lf%%\n", f[n]*100.0/jieceng(n));
    }

    return 0;
}

/*
 这道题是n个人，错了m个，那我们就转化为m个人全错排好了，那n-m个人坐对了，m个人全错排，
 n-m个人坐对的方式有c(m,n-m)（组合数）种，那n个人m个人坐对的种数就是c(m,n-m)*f(m)，
 当然，有几个特殊情况需要另外讨论。比如说n=m时，组合数计算需要返回一个1，结果就是f(m)，
 还有m=1时，f(1)=0，计算结果是0，而事实上计算结果是c(n,1)种，所以我们在计算完f(i)的
 值以后可以把f(1)赋为1，（因为1<m<=n<=20，所以不用考虑用到f（1）计算结果不正确）
 */

#include <stdio.h>

long long int jieceng(int n) {
    long long sum = 1;
    while (n) {
        sum *= n;
        n--;
    }
    return sum;
}

long long CMethod(int n, int a) {
    long long int sum = 1;
    
    for (int i=n; i>n-a; i--) {
        sum *= i;
    }
    
    for (int i=1; i<=a; i++) {
        sum /= i;
    }
    
    return sum;
}

int main(int argc, const char * argv[]) {
    // insert code here...

    int c, n, m, maxN = 2;
    long long int f[60];
    
    scanf("%d", &c);
    
    while (c--) {
        f[1] = 0;
        f[2] = 1;
        scanf("%d %d", &n, &m);
        
        if (maxN < m) {
            for (int i=maxN+1; i<=m; i++) {
                f[i] = (i-1)*(f[i-1] + f[i-2]);
            }
            maxN = m;
        }
        
        f[1] = 1;
        printf("%lld\n", CMethod(n, n-m) *f[m]);
    }

    return 0;
}

/*
 先看N条相交的直线最多能把平面分割成多少块
 当添加第N条只显示，为了使平面最多， 则第N条直线要与前面的N-1条直线都相交，且没有任何三条直线教育一个点。
 则第N条直线有N-1个交点。由于每增加N个交点，就增加N+1个平面，所以用N条直线来分隔平面，
 最多的数是1+1+2+3+…+n=1+n*(n+1)/2, 第一个1是原先就有一个平面
 */

/*
 再看每次增加两条相互平行的直线
 当第N次添加时，前面已经有2N-2条直线了，所以第N次添加时，第2N-1条直线和第2N条直线都各能增加2*（n-1）+1 个平面。
 所以第N次添加增加的面数是2[2(n-1) + 1] = 4n - 2 个。因此，总面数应该是
 1 + 4n(n+1)/2 - 2n = 2n2 + 1
 */

/*
 如果把每次加进来的平行边让它们一头相交
 则平面1、3已经合为一个面，因此，每一组平行线相交后，就会较少一个面，
 所以所求就是平行线分割平面数减去N，为2n2 -n + 1
 利用上述总结公式f(n)=2n2 - n + 1
 */


#include <stdio.h>

int main(int argc, const char * argv[]) {
    // insert code here...

    int c, n;

    scanf("%d", &c);
    
    while (c--) {
        scanf("%d", &n);
        
        printf("%d\n", 2 * n * n - n + 1);
    }

    return 0;
}