基础测试

汉诺塔

描述

汉诺塔问题经常作为一个递归的经典例题存在。 汉诺塔来源于印度传说的一个故事，上帝创造世界时作了三根金刚石柱子，在一根柱子上从下往上按大小顺序摞着64片黄金圆盘。 上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上，并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。 我们知道最少需要移动2^64-1次。 在移动过程中发现，有的圆盘移动次数多，有的少。 用1,2,…… ,n表示n个盘子的编号，已知盘子总数和某个盘子的编号，计算该盘子的移动次数。

输入

可能包含多组数据，首先输入(1 < T <=1000)表示有T组数据，每个数据一行，是盘子的总数N(1<=N<=100)和盘号k(1<=k<=N)。

输出

对于每组数据，输出一个数，表示完成汉诺塔时k号盘需要的最少移动步数。

输入样例 1

2
63 1
3 1

输出样例 1

4611686018427387904
4

代码

#include <bits/stdc++.h>
using namespace std;
int t, n, k;
int num[100];
void gjd(int x) {
    memset(num, 0, sizeof(num));
    int jishu = 1;
    num[0] = 2;
    for (int i = 0; i < x - 1; i++) {
        for (int j = 0; j < jishu; j++) {
            num[j] *= 2;
        }
        for (int j = 0; j < jishu; j++) {
            if (num[j] >= 10) {
                if (j == jishu - 1) jishu++;
                num[j + 1] = num[j + 1] + num[j] / 10;
                num[j] = num[j] % 10;
            }
        }
    }
    for (int i = jishu - 1; i >= 0; i--) cout << num[i];
    cout << endl;
}
int main() {
    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> n >> k;
        gjd(n - k);
    }
    return 0;
}

线性表合并

描述

给定两个有序的数列 L1，L2，要求输出将两个有序数列合并成一个新的有序数列。

输入

总共3行。

第一行两个数，第一个数表示 L1 数列的元素个数 N1，第二个数表示 L2 数列的元素个数 N2

第二行 N1 个数，对应L1数列的各个元素

第三行 N2 个数，对应L2数列的各个元素

输出

合并后的线性表，合并后线性表必须有序。

输入样例 1

4 5
1 4 7 8
2 4 6 9 10

输出样例 1

1 2 4 4 6 7 8 9 10

提示

对于100%数据 1 ≤ n,m ≤ 100000

代码

#include <bits/stdc++.h>
using namespace std;
int n, m, num[210000], b[110000], a[110000];
int main() {
    cin >> n >> m;
    memset(a, 0x3f, sizeof(a));
    memset(b, 0x3f, sizeof(b));
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> b[i];
    }
    int jishu1 = 0, jishu2 = 0, jishu = 0;
    int q = n + m;
    while (q--) {
        if (a[jishu1] <= b[jishu2]) {
            num[jishu] = a[jishu1];
            jishu1++;
            jishu++;
        } else if (a[jishu1] > b[jishu2]) {
            num[jishu] = b[jishu2];
            jishu2++;
            jishu++;
        }
    }
    for (int i = 0; i < n + m; i++) {
        cout << num[i] << " ";
    }
    return 0;
}

猫吃鱼

描述

明明家从 1 号站点出发，开车去旅游，一共要经过 n 个站点，依次为 2、3…… n。

由于明明带上了心爱的小猫，在每个站点都要为小猫提供一条鱼用做美餐（包括 1 号站点）。

除了 1 号站点只能吃 1 号站点买的鱼，其他站点既可以吃当地买的鱼，也可吃之前经过的站点买了存入车载冰箱中的鱼。

但车载冰箱消耗的电能来自汽油，所以每条鱼用冰箱保存到下一站的费用与各个站点的汽油价格有关。

为使问题简化，我们约定：

（1）车从某站开出时油箱中都是此站点刚加的汽油。

（2）车载冰箱能容纳一路上需要的所有鱼。

即：每条鱼的费用既包括购买时的费用，也包括用冰箱保存鱼的费用。

编程实现：

为了降低小猫吃鱼的总代价，明明预先上网查到了这 n 个站点的鱼价和汽油价格。 并据此算出每个站点买一条鱼的费用以及从该站点到下一站用冰箱保存一条鱼的费用。 你能帮

明明算出这一路上小猫吃鱼的最小总费用吗？

输入

第一行：站点数 n，1 < n < 100。

接下来的 n 行：每行两个以空格分隔的正整数，表示：这一站买一条鱼的费用，以及从这一站把每条

鱼保存到下一站的费用，两个费用均为小于 10000 的正整数。

输出

最小总费用，是一个正整数。

输入样例 1

5
6 3
7 1
3 2
8 3
9 5

输出样例 1

29

代码

#include <bits/stdc++.h>
using namespace std;
int n, a[110], b[110];
int mi, jishu;
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }
    mi = a[0];
    jishu = a[0];
    for (int i = 1; i < n; i++) {
        mi += b[i - 1];
        mi = min(mi, a[i]);
        jishu += mi;
    }
    cout << jishu;
    return 0;
}

阿短的背包

描述

阿短在放暑假的时候带着他能装M（M≤10000）公斤的背包去旅行。 旅行结束他想给亲友们带些纪念品，摆在阿短眼前的有N（N≤100）件想买的纪念品，第i件纪念品的重量为一个我一个**我（一个我一个**我≤1000）公斤。 问在装满背包的情况下，阿短有多少种选择纪念品的方案。

输入

第一行是两个数字，表示N和 M。

第二行起N 个正数 一个我一个**我（可以有相同的数字，每个数字均在1000以内）。

输出

一个正整数，表示选纪念品方案数结果对10000789取余。

输入样例 1

4 4
1 1 2 2 

输出样例 1

3

代码

#include <bits/stdc++.h>
using namespace std;
long long n, m, a[11000], dp[110000];
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    dp[0] = 1;
    for (int j = 0; j < n; j++) {
        int w = a[j];
        for (int i = m; i >= w; i--) {
            dp[i] = (dp[i] + dp[i - w]) % 10000789;
        }
    }
    cout << dp[m];
    return 0;
}