HDU100题 2040-2049

2040：

#include <cstdio>

using namespace std;

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int num1, num2;
        scanf("%d %d", &num1, &num2);
        int sum1, sum2;
        sum1 = sum2 = 0;
        int n1 = num1/2;
        for(int i=1; i<=n1; i++)
        {
            if(num1 % i == 0)
            {
                sum1 += i;
            }
                
        }
        int n2 = num2/2;
        for(int i=1; i<=n2; i++)
        {
            if(num2 % i == 0)
                sum2 += i;
        }
        // printf("%d %d\n", sum1, sum2);
        if(sum1 == num2 && sum2 == num1)
            printf("YES\n");
        else
            printf("NO\n");
    }


    return 0;
}

2041：

// 看到这个题的第一眼想法是这道题是个dp
// 然后尝试用DFS找一下数据
// 发现竟然是个斐波那契额
// 没注意开始时第一级楼梯WA了一发

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

LL dp[40+7];
// LL dfs(int i, int n)
// {
//     if(i == n) return 1;
//     if(i > n) return 0;
//     LL res = 0;
//     res += dfs(i+1, n);
//     res += dfs(i+2, n);
//     return dp[i] = res;

// }

int main()
{
    memset(dp, 0, sizeof(dp));
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int num;
        scanf("%d", &num);
        // printf("%d\n", dfs(0, num));
        dp[0] = 0;
        dp[1] = 0;
        dp[2] = 1;
        dp[3] = 2;
        for(int i=4; i<=40; i++)
        {
            dp[i] = dp[i-1] + dp[i-2];
        }
        printf("%d\n", dp[num]);
    }



    return 0;
}

2042：

// 类似猴子吃桃问题
#include <cstdio>

using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    while(n--)
    {
        int a;
        scanf("%d", &a);
        int ans = 3;
        for(int i=0; i<a; i++)
        {
            ans -= 1;
            ans = ans * 2;
        }
        printf("%d\n", ans);


    }


    return 0;
}

2043：

#include <cstdio>
#include <iostream>
#include <string>
#include <set>

using namespace std;

set<char> s1, s2, s3, s4;

int main()
{
    ios::sync_with_stdio(0);
    s1.clear(); s2.clear(); s3.clear(); s4.clear();
    for(int i='a'; i<='z'; i++)
        s1.insert(i);
    for(int i='A'; i<='Z'; i++)
        s2.insert(i);
    for(int i='0'; i<='9'; i++)
        s3.insert(i);
    s4.insert('~'); s4.insert('!'); s4.insert('@');
    s4.insert('#'); s4.insert('$'); s4.insert('%');
    s4.insert('^');

    int m; 
    string str;
    cin >> m;
    while(m--)
    {
        cin >> str;
        int cnt = 0;
        bool f1, f2, f3, f4;
        f1 = f2 =f3 = f4 = 1;
        int len = str.size();
        for(int i=0; i<len; i++)
        {
             if(f1 && s1.count(str[i]))
             {
                 f1 = false;
                 cnt ++;
             }
             if(f2 && s2.count(str[i]))
             {
                 f2 = false;
                 cnt ++;
             }
             if(f3 && s3.count(str[i]))
             {
                 f3 = false;
                 cnt ++;
             }
             if(f4 && s4.count(str[i]))
             {
                 f4 = false;
                 cnt ++;
             }
        }
        if(cnt >= 3 && len >= 8 && len <= 16)
           cout << "YES" << endl;
        else
        {
            cout << "NO" << endl;
        }
        
    }



    return 0;
}

2044：

// 斐波那契数列，本以为只有50大小不会爆int，结果还是爆了

#include <cstdio>

using namespace std;

long long a[50+7];
int main()
{
    a[1] = 1;
    a[2] = 1;
    for(int i=3; i<50+7; i++)
        a[i] = a[i-1] + a[i-2];
    int n;
    scanf("%d", &n);
    while(n--)
    {
        int b1, b2;
        scanf("%d%d", &b1, &b2);
        int ans = b2 - b1;
        if(ans == 0)
            printf("0\n");
        else
            printf("%lld\n", a[ans+1]);
    }



    return 0;
}

2045：

#include <cstdio>

using namespace std;
typedef long long LL;

LL a[50+7];
LL s[50+7];

void init()
{
    for(int i=0; i<57; i++)
        s[i] = a[i] = 0;
}
LL pow2(int n)
{
    LL res = 1;
    for(int i=0; i<n; i++)
        res = res * 2;
    return res;
}

int main()
{
    init();
    a[0] = 0;
    s[0] = 3;

    for(int i=1; i<51; i++)
    {
        a[i] = pow2(i) - a[i-1];
        // printf("%lld ", a[i]);
    }
    // printf("\n");
    for(int i=1; i<51; i++)
    {
        s[i] = 3*pow2(i) - 3*a[i-1];
        // printf("%lld ", s[i]);
    }
    // printf("\n");

    int n;
    while(scanf("%d", &n) != EOF)
    {
        printf("%lld\n", s[n-1]);
    }



    return 0;
}

2046：

// 类似Fibonacci数列

#include <cstdio>
using namespace std;
typedef long long LL;

LL s[50+7];

int main()
{
    s[0] = 0;
    s[1] = 1;
    s[2] = 2;
    for(int i=3; i<=50; i++)
        s[i] = s[i-1] + s[i-2];
    int n;
    while(scanf("%d", &n) != EOF)
    {
        printf("%lld\n", s[n]);



    }

    return 0;
}

2047：

#include <cstdio>

using namespace std;
typedef long long LL;

LL s[40+7];
int main()
{
    s[1] = 3;
    s[2] = 8;
    for(int i=3; i<41; i++)
    {
        s[i] = s[i-1] * 2 + s[i-2] * 2;
    }
    int n;
    while(scanf("%d", &n) != EOF)
    {
        printf("%lld\n", s[n]);
    }


    return 0;
}

2048：

// https://blog.csdn.net/synapse7/article/details/14642937
// 解析看上面这篇博客，写的很好

#include <cstdio>

using namespace std;
typedef long long LL;

LL func(int n)  // 计算阶乘
{
    LL res = 1;
    for(int i=1; i<=n; i++)
        res = res * i;
    return res;
}

LL a[21];

int main()
{
     int c;
     scanf("%d", &c);
     a[1] = 0;
     a[2] = 1;
     for(int i=3; i<=20; i++)
     {
         a[i] = (i-1) * a[i-1] + (i-1) * a[i-2];
     }
     while(c--)
     {
         int n;
         scanf("%d", &n);
         LL total = func(n);
         printf("%.2lf%%\n", 1.0 * a[n] / total * 100);


     }



    return 0;
}

2049：

// 与2048一样计算错排数，不同得是计算得是m个错排得错排方案数
// 此外因为n个人中m个错排所以需要先选出这个人，组合数
#include <cstdio>

using namespace std;
typedef long long LL;

LL a[20+7];

LL func(int n, int m)   // 计算组合数
{  
    LL res = 1;
    for(int i=1; i<=n; i++)
        res = res * i;
    for(int i=1; i<=n-m; i++)
        res /= i;
    for(int i=1; i<=m; i++)
        res /= i;
    return res;
}
int main()
{
    a[1] = 0;
    a[2] = 1;
    for(int i=3; i<=20; i++)
    {
        a[i] = (i-1) * a[i-1] + (i-1) * a[i-2];
    }
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n, m;
        scanf("%d%d", &n, &m);
        printf("%lld\n", func(n, m) * a[m]);
    }


    return 0;
}