杭电 OJ2040-2049

写在前面

本文记录了刷杭电 OJ2040-2049 的过程和一些想法，代码仅供参考！

2040 亲和数

Problem Description

古希腊数学家毕达哥拉斯在自然数研究中发现，220 的所有真约数 (即不是自身的约数) 之和为：
1+2+4+5+10+11+20+22+44+55+110 ＝ 284。
而 284 的所有真约数为 1、2、4、71、 142，加起来恰好为 220。人们对这样的数感到很惊奇，并称之为亲和数。
一般地讲，如果两个数中任何一个数都是另一个数的真约数之和，则这两个数就是亲和数。
你的任务就编写一个程序，判断给定的两个数是否是亲和数

Input

输入数据第一行包含一个数 M，接下有 M 行，每行一个实例，包含两个整数 A,B； 其中 0 <= A,B <= 600000 ;

Output

对于每个测试实例，如果 A 和 B 是亲和数的话输出 YES，否则输出 NO。

Sample Input

2
220 284
100 200

Sample Output

YES
NO

解题思路

求所有公约数之和并相加，判断是否为亲和数

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
int sum(int a) {
    int ans = 0;
    for (int i = 1; i <= a / 2; i++)  //遍历一半
        if (a % i == 0) ans += i;     //所有真约数之和
    return ans;
}
int main() {
    int n, a, b;
    cin >> n;
    while (n--) {
        cin >> a >> b;
        if (sum(a) == b && sum(b) == a)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

2041 超级楼梯

Problem Description

有一楼梯共 M 级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第 M 级，共有多少种走法？

Input

输入数据首先包含一个整数
N，表示测试实例的个数，然后是 N 行数据，每行包含一个整数 M（1<=M<=40）,
表示楼梯的级数。

Output

对于每个测试实例，请输出不同走法的数量

Sample Input

2
2
3

Sample Output

1
2

解题思路

递推题，简单写几项之后发现时斐波那契数列，之后就好办了
走上第 n 级，可以从第 n-1 级走一步上来，也可以从第 n-2 级走两步上来
f(1) = 1,f(2) = 1,f(3) = 2
f(n) = f(n - 1) + f(n - 2)

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;
int main() {
    __int64 n, m, f[41] = {1, 1, 2};  //用int可能溢出，可以用long long 或者 __int64
    cin >> n;
    while (n--) {
        cin >> m;
        for (int i = 3; i < 41; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        cout << f[m - 1] << endl;
    }
    return 0;
}

2042 不容易系列之二

Problem Description

你活的不容易，我活的不容易，他活的也不容易。不过，如果你看了下面的故事，就会知道，有位老汉比你还不容易。重庆市郊黄泥板村的徐老汉（大号徐东海，简称 XDH）这两年辛辛苦苦养了不少羊，到了今年夏天，由于众所周知的高温干旱，实在没办法解决牲畜的饮水问题，就决定把这些羊都赶到集市去卖。从黄泥板村到交易地点要经过 N 个收费站，按说这收费站和徐老汉没什么关系，但是事实却令徐老汉欲哭无泪：
（镜头回放） 近景：老汉，一群羊 远景：公路，收费站
…
收费员（彬彬有礼 + 职业微笑）：“老同志，请交过路费！”
徐老汉（愕然，反应迟钝状）：“锅，锅，锅，锅 - 炉 - 费？我家不烧锅炉呀？”
收费员（职业微笑依然）：“老同志，我说的是过 - 路 -费，就是你的羊要过这个路口必须交费，understand?”
徐老汉（近镜头 10 秒，嘴巴张开）：“我 - 我 - 我知道汽车过路要收费，这羊也要收费呀？”
收费员（居高临下 +不解状）：“老同志，你怎么就不明白呢，那么我问你，汽车几个轮子？”
徐老汉（稍放松）：“这个我知道，今天在家里我孙子还问我这个问题，4 个！”
收费员（生气，站起）：“嘿！老头，你还骂人不带脏字，既然知道汽车四个轮子，难道就不知道这羊有几条腿吗？！”
徐老汉（尴尬，依然不解状）：“也，也，也是 4 个呀，这有关系吗？”
收费员（生气，站起）：“怎么没关系！我们头说了，只要是 4 条腿的都要收费！”
…
(画外音)
由于徐老汉没钱，收费员就将他的羊拿走一半，看到老汉泪水涟涟，犹豫了一下，又还给老汉一只。
巧合的是，后面每过一个收费站，都是拿走当时羊的一半，然后退还一只，等到老汉到达市场，就只剩下 3 只羊了。
你，当代有良知的青年，能帮忙算一下老汉最初有多少只羊吗？

Input

输入数据第一行是一个整数 N，下面由 N
行组成，每行包含一个整数 a(0<a<=30),表示收费站的数量。

Output

对于每个测试实例，请输出最初的羊的数量，每个测试实例的输出占一行。

Sample Input

2
1
2

Sample Output

4
6

解题思路

简单题，可以直接 for 循环 sum = (sum - 1) * 2
同样可以用递推式： f(0) = 3，f(1) = 4 ，f(n) = [f(n-1) - 1] × 2
另外通过递推式也可以得到公式 f(n) = 2^n + 2

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
int main() {
    int n, a;
    cin >> n;
    while (n--) {
        int sum = 3;
        cin >> a;
        for (int i = 0; i < a; i++) {
            sum = (sum - 1) * 2;
        }
        cout << sum << endl;
    }
    return 0;
}

2043 密码

Problem Description

网上流传一句话:“常在网上飘啊，哪能不挨刀啊～”。其实要想能安安心心地上网其实也不难，学点安全知识就可以。
首先，我们就要设置一个安全的密码。那什么样的密码才叫安全的呢？一般来说一个比较安全的密码至少应该满足下面两个条件：
(1). 密码长度大于等于 8，且不要超过 16。
(2). 密码中的字符应该来自下面 “字符类别” 中四组中的至少三组。
这四个字符类别分别为：

  1. 大写字母：A,B,C…Z;
  2. 小写字母：a,b,c…z;
  3. 数字：0,1,2…9;
  4. 特殊符号：~,!,@,#,$,%,^;

给你一个密码，你的任务就是判断它是不是一个安全的密码。

Input

输入数据第一行包含一个数 M，接下有 M 行，每行一个密码（长度最大可能为 50），密码仅包括上面的四类字符。

Output

对于每个测试实例，判断这个密码是不是一个安全的密码，是的话输出 YES，否则输出 NO。

Sample Input

3
a1b2c3d4
Linle@ACM
^~^@^@!%

Sample Output

NO
YES
NO

解题思路

根据要求判断即可，若满足条件，则设置 flag=1

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <cstring>
#include <iostream>
using namespace std;
int main() {
    int n, f1, f2, f3, f4;
    string s;
    cin >> n;
    getchar();  //吃掉回车
    while (n--) {
        cin >> s;
        int len = s.length();
        if (len < 8 || len > 16) {  //密码长度大于等于 8，且不要超过 16
            cout << "NO" << endl;
            continue;
        }
        f1 = f2 = f3 = f4 = 0;
        for (int i = 0; i < len; i++) {
            if (isupper(s[i]))  //如果是大写字母
                f1 = 1;
            else if (islower(s[i]))  //如果是小写字母
                f2 = 1;
            else if (isdigit(s[i]))  //如果是数字
                f3 = 1;
            else  //特殊符号
                f4 = 1;
        }
        if ((f1 + f2 + f3 + f4) >= 3)  //至少三种
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

2044 一只小蜜蜂…

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

解题思路

通过观察图片，蜜蜂只能爬向右侧相邻的蜂房，比如:蜜蜂在 1 格里，它可以往 2、3 两格里爬
所以第 n 格的蜜蜂，可以往第 n+1 格或者第 n+2 格移动
之后就可以写出递推式 f(n) = f(n - 1) + f(n - 2)

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
int main() {
    __int64 n, a, b, s[51] = {1, 1, 2};  //用int可能溢出，可以用long long 或者 __int64
    cin >> n;
    for (int i = 3; i < 51; i++) {
        s[i] = s[i - 1] + s[i - 2];
    }
    while (n--) {
        cin >> a;
        cin >> b;
        if (a > b)
            cout << "0" << endl;  //不能向左爬
        else
            cout << s[b - a] << endl;
    }
    return 0;
}

2045 不容易系列之(3)——LELE 的 RPG 难题

Problem Description

人称 “AC 女之杀手” 的超级偶像 LELE 最近忽然玩起了深沉，这可急坏了众多“Cole”（LELE 的粉丝，即 “可乐”）, 经过多方打探，某资深 Cole
终于知道了原因，原来，LELE 最近研究起了著名的 RPG 难题:
有排成一行的ｎ个方格，用红 (Red)、粉 (Pink)、绿 (Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色．求全部的满足要求的涂法.以上就是著名的 RPG 难题.
如果你是 Cole, 我想你一定会想尽办法帮助 LELE 解决这个问题的；如果不是，看在众多漂亮的痛不欲生的 Cole 女的面子上，你也不会袖手旁观吧？

Input

输入数据包含多个测试实例，每个测试实例占一行，由一个整数 N 组成，(0<n<=50)。

Output

对于每个测试实例，请输出全部的满足要求的涂法，每个实例的输出占一行。

Sample Input

1
2

Sample Output

3
6

解题思路

同样的也是递推问题，试着写几项
f(1) = 3, f(2) = 6, f(3) = 6
f(n) = f(n - 1) + 2 * f(n - 2)

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
using namespace std;
int main() {
    __int64 n, f[51] = {3, 6, 6};  //用int可能溢出，可以用long long 或者 __int64
    for (int i = 3; i < 51; i++) {
        f[i] = f[i - 1] + 2 * f[i - 2];
    }
    while (cin >> n) {
        cout << f[n - 1] << endl;
    }
    return 0;
}

2046 骨牌铺方格

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

解题思路

第 N 张牌的排列可以在 N-1 张牌的排列再在末尾加上一张竖的牌
也可以在 N-2 张合法排列的牌后面加上两张横着放的牌
f(1) = 1, f(2) = 2, f(3) = 3
f(n) = f(n - 1) + f(n - 2)

参考源码

1
2
3
4
5
6
7
8
9
10
#include <iostream>
using namespace std;
int main() {
    __int64 n, f[51] = {1, 2, 3};  //用int可能溢出，可以用long long 或者 __int64
    for (int i = 3; i < 51; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }
    while (cin >> n) cout << f[n - 1] << endl;
    return 0;
}

2047 阿牛的 EOF 牛肉串

Problem Description

今年的 ACM 暑期集训队一共有 18 人，分为 6 支队伍。其中有一个叫做 EOF 的队伍，由 04 级的阿牛、XC 以及 05 级的 COY 组成。在共同的集训生活中，大家建立了深厚的友谊，阿牛准备做点什么来纪念这段激情燃烧的岁月，想了一想，阿牛从家里拿来了一块上等的牛肉干，准备在上面刻下一个长度为 n 的只由 “E” “O” “F”
三种字符组成 的字符串（可以只有其中一种或两种字符，但绝对不能有其他字符）, 阿牛同时禁止在串中出现 O 相邻的情况，他认为，“OO” 看起来就像发怒的眼睛，效果不好。 你，NEW ACMer,EOF 的崇拜者，能帮阿牛算一下一共有多少种满足要求的不同的字符串吗？
PS:阿牛还有一个小秘密，就是准备把这个刻有 EOF 的牛肉干，作为神秘礼物献给杭电五十周年校庆，可以想象，当校长接过这块牛肉干的时候该有多高兴！这里，请允许我代表杭电的 ACMer 向阿牛表示感谢！再次感谢！

Input

输入数据包含多个测试实例，每个测试实例占一行，由一个整数 n 组成，(0<n<40)。

Output

对于每个测试实例，请输出全部的满足要求的涂法，每个实例的输出占一行。

Sample Input

1
2

Sample Output

3
8

解题思路

f[n][0]表示以 O 结尾的合法字符串，f[n][1]表示不以 O 结尾的合法字符串
以 O 结尾的合法字符串之后可以跟 E 或者 F
不以 O 结尾的合法字符串之后可以跟 E、O、F
f[n][0] = f[n - 1][1];
f[n][1] = 2 * (f[n - 1][0] + f[n - 1][1])

参考源码

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
using namespace std;
int main() {
    __int64 n, f[40][2] = {{0, 0}, {1, 2}};
    for (int i = 2; i < 40; i++) {
        f[i][0] = f[i - 1][1];
        f[i][1] = 2 * (f[i - 1][0] + f[i - 1][1]);
    }
    while (cin >> n) cout << f[n][0] + f[n][1] << endl;
    return 0;
}

2048 神、上帝以及老天爷

Problem Description

HDU 2006’10 ACM contest 的颁奖晚会隆重开始了！
为了活跃气氛，组织者举行了一个别开生面、奖品丰厚的抽奖活动，这个活动的具体要求是这样的：
首先，所有参加晚会的人员都将一张写有自己名字的字条放入抽奖箱中；
然后，待所有字条加入完毕，每人从箱中取一个字条；
最后，如果取得的字条上写的就是自己的名字，那么 “恭喜你，中奖了！”
大家可以想象一下当时的气氛之热烈，毕竟中奖者的奖品是大家梦寐以求的 Twins 签名照呀！不过，正如所有试图设计的喜剧往往以悲剧结尾，这次抽奖活动最后竟然没有一个人中奖！我的神、上帝以及老天爷呀，怎么会这样呢？不过，先不要激动，现在问题来了，你能计算一下发生这种情况的概率吗？不会算？难道你也想以悲剧结尾？！

Input

输入数据的第一行是一个整数 C, 表示测试实例的个数，然后是 C 行数据，每行包含一个整数 n (1<n<=20),表示参加抽奖的人数。

Output

对于每个测试实例，请输出发生这种情况的百分比，每个实例的输出占一行，结果保留两位小数(四舍五入)，具体格式请参照 sample output。

Sample Input

1
2

Sample Output

50.00%

解题思路

全错排问题
若前 n-1 个人拿到的都不是自己的名字，第 n 个人拿到的是自己的名字，只需要与前 n-1 个人中的任意一个交换即可满足，有 n-1 种可能
若前 N-1 个人不满足错排，第 n 个人只要与第 i 个人交换即可满足，这时 n-2 个人完全错排，有 f(n-2)种可能，若第 i 个人不与第 n 个人交换，则 n-1 个元素错排，有 f(n-1)种可能
递推公式：f[n]=(n-1)*(f[n-1]+f[n-2])

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
long long jc(int a) {  //阶乘
    if (a == 1)
        return 1;
    else
        return jc(a - 1) * a;
}
int main() {
    int c, n;
    long long f[21] = {0, 0, 1, 2};
    for (int i = 4; i < 21; i++) {
        f[i] = (i - 1) * (f[i - 1] + f[i - 2]);
    }
    cin >> c;
    while (c--) {
        cin >> n;
        printf("%.2f%%\n", 100.0 * f[n] / jc(n));
    }
    return 0;
}

2049 不容易系列之(4)——考新郎

Problem Description

国庆期间，省城 HZ
刚刚举行了一场盛大的集体婚礼，为了使婚礼进行的丰富一些，司仪临时想出了有一个有意思的节目，叫做"考新郎", 具体的操作是这样的: 首先，给每位新娘打扮得几乎一模一样，并盖上大大的红盖头随机坐成一排；然后，让各位新郎寻找自己的新娘。每人只准找一个，并且不允许多人找一个.最后，揭开盖头，如果找错了对象就要当众跪搓衣板…看来做新郎也不是容易的事情…
假设一共有 N 对新婚夫妇，其中有 M 个新郎找错了新娘，求发生这种情况一共有多少种可能.

Input

输入数据的第一行是一个整数 C, 表示测试实例的个数，然后是 C 行数据，每行包含两个整数 N 和 M(1<M<=N<=20)。

Output

对于每个测试实例，请输出一共有多少种发生这种情况的可能，每个实例的输出占一行。

Sample Input

2
2 2
3 2

Sample Output

1
3

解题思路

先是排列组合，从 N 个新郎中选出 M 个，之后是 M 的全错排
计算 C(n,m)，可以通过定义计算，即：

Cnm=n!m!(n−m)!\text{C}_{\text{n}}^{\text{m}}=\frac{\text{n!}}{\text{m!}\left( \text{n}-\text{m} \right) !}

我这里用了递推公式计算：

Cnm=Cn−1m+Cn−1m−1\text{C}_{\text{n}}^{\text{m}}=\text{C}_{\text{n}-1}^{\text{m}}+\text{C}_{\text{n}-1}^{\text{m}-1}

计算 m 的全错排，参见 oj2048
递推公式：f[n] = (n - 1) * (f[n - 1] + f[n - 2])

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
long long res[21][21] = {0};
long long C(int n, int m) {
    if (n == m || m == 0) return 1;
    if (res[n][m] != 0)  //避免重复计算
        return res[n][m];
    else
        return C(n - 1, m) + C(n - 1, m - 1);  //按递推公式计算
}
int main() {
    int c, n, m;
    long long f[21] = {0, 0, 1, 2};
    for (int i = 4; i < 21; i++) {
        f[i] = (i - 1) * (f[i - 1] + f[i - 2]);  //全错排
    }
    cin >> c;
    while (c--) {
        cin >> n >> m;
        cout << C(n, m) * f[m] << endl;
    }
    return 0;
}

相关内容