由于个人原因，这次的训练没有及时的完成，然后也没让大家一起讨论问题，现在赶上五一，终于有一点点属于自己的时间，就把这几道题的题解给写一下。之前也大概写了一下递归的规律，下面总结一下递推的规律。
1.汉诺塔
题目
从前有一座庙，庙里有三个柱子，柱A柱 B柱 C。柱A有64个盘子，从上往下盘子越来越大。要求庙里的老和尚把这64个盘子全部移动到柱子C上。移动的时候始终只能小盘子压着大盘子。而且每次只能移动一个。
现在问题来了，老和尚相知道将柱A上面前n个盘子从柱A搬到柱C搬动方法。要求移动次数最少。
Input
输入有多组，每组输入一个正整数n(0<n<16)
Output
每组测试实例，输出每一步的步骤，输出 “number..a..form..b..to..c”。表示将第a个盘子从柱b搬到柱c.
Sample Input
2
Sample Output
number..1..form..A..to..B
number..2..form..A..to..C
number..1..form..B..to..C
解析：这道题是经典汉诺塔问题，也是递归入门题（拿这道题作为入门实在...）。那这道题是只有三根柱子，我们可以分别称这三根柱子为起始柱、中转柱、目标柱。接着我们开始我们的递归，结束条件是：起始柱上仅有一个塔的时候，这时就可以直接将起始柱上的塔移动到目标柱，也就是一步就可以完成，那假如起始柱上的塔数 > 1 时，我们的思想是先将目标柱作为中转柱，剩下那根柱子作为中转柱，将起始柱中的塔移动到剩下那根柱子，并只剩下一个塔为止。那这时候便是我们递归的结束条件。接着在另一根柱子剩（n - 1）个塔，那这时候这根柱子会作为起始柱，而一开始的起始柱现在变为中转柱，现在又开始重复刚刚上面的操作。
AC代码：
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 7;
const int maxm = 2e5 + 7;
const long long inf = 0x3f3f3f3f;
const long long mod = 1e9 + 7;
void move(int n ,char X, char Y)
{
printf("number..%d..form..%c..to..%c\n", n, X, Y);
}
void Hanio(int n, char one, char two, char three) //起始柱、中转柱、目标柱
{
if(n == 1)
{
move(n, one ,three);
return;
}
Hanio(n - 1, one, three, two);
move(n, one, three);
Hanio(n - 1, two, one, three);
}
int main()
{
int n;
char a = ‘A‘ , b = ‘B‘, c = ‘C‘;
while(~scanf("%d", &n))
{
Hanio(n, a, b, c);
}
return 0;
}
2.盾神与砝码称重
问题描述
有一天，他在宿舍里无意中发现了一个天平！这个天平很奇怪，有n个完好的砝码，但是没有游码。盾神为他的发现兴奋不已！于是他准备去称一称自己的东西。他准备好了m种物品去称。神奇的是，盾神一早就知道这m种物品的重量，他现在是想看看这个天平能不能称出这些物品出来。但是盾神稍微想了1秒钟以后就觉得这个问题太无聊了，于是就丢给了你。
输入格式
第一行为两个数，n和m。
第二行为n个数，表示这n个砝码的重量。
第三行为m个数，表示这m个物品的重量。
输出格式
输出m行，对于第i行，如果第i个物品能被称出，输出YES否则输出NO。
样例输入
4 2
1 2 4 8
15 16
样例输出
YES
NO
样例输入
4 1
10 7 1 19
6
样例输出
YES
数据规模和约定
1<=n<=24, 1<=m<=10.
解析：这道题有点恶，发现n的值最大能到24，不确定dfs行不行，不过试了试剪枝好像可行，一开始一直想用dp解，不过暂时还没想出来。
递归思路：分三种情况
1.将该砝码放在右盘
2.不使用该砝码
3.将该砝码放在左盘
刚开始一直Tle，然后请教了一下大佬，这个dfs先进行那一步也是有一定的讲究的，我们目标是将两盘的重量之差变为0，也就是可以称出目标重物，那么应该先考虑将砝码放在右盘，可以使所需称的物品重量不断变小，接着一种情况就是不放砝码，最后一种才是增钟所需称物品的重量，不过在这里没啥影响。第二个我又加了一个快读试试，发现还是不行（在这道题不用快读也行），然后大佬说试一下后缀和，刚开始我是升序排列，就是选择先使用重量小的砝码，然后发现不行，换了降序还是不行，90分就是不给过，这道题其实必须使用降序的，不排序也过不去，那这个降序其实就是为了可行性剪枝而用，当物品剩余的重量的绝对值大于剩下砝码的重量时，那这时候是不可能称出其重量。
其次这里还要有一个剪枝，就是已经称出该物体重量，那么这时候就不用在进行递归，直接return，这个就是剩下十分没得的原因。
AC代码：
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 7;
const int maxm = 2e5 + 7;
const long long inf = 0x3f3f3f3f;
const long long mod = 1e9 + 7;
int a[30], ad[30];
int flag = 0, n, m;
inline int read()
{
char ch = getchar(); int x = 0, f = 1;
while(ch < ‘0‘ || ch > ‘9‘)
{
if(ch == ‘-‘) f = -1;
ch = getchar();
}
while(‘0‘ <= ch && ch <= ‘9‘)
{
x = x * 10 + ch - ‘0‘;
ch = getchar();
} return x * f;
}
bool cmp(int a, int b)
{
return a > b;
}
void dfs(int w, int q) //需称量物品的重量, 砝码数量
{
if(flag) //剪枝一
return;
if(w == 0)
{
flag = 1;
return;
}
if(abs(w) > ad[q]) //剪枝二
return;
if(q == n + 1) //剪枝三
return;
dfs(w - a[q], q + 1); //放在右盘
dfs(w, q + 1); //不放
dfs(w + a[q], q + 1); //放在左盘
}
int main()
{
n = read();
m = read();
for(int i = 1; i <= n; i++)
a[i] = read();
sort(a + 1, a + 1 + n, cmp); //降序, 将大的砝码放在前面
for(int i = n; i >= 1; i--)
ad[i] = ad[i+1] + a[i]; //后缀和
while(m --)
{
int w = read();
dfs(w, 1);
if(flag)
printf("YES\n");
else
printf("NO\n");
flag = 0;
}
return 0;
}
3.数的划分
题目
一个正整数可以划分为多个正整数的和，比如n=3时：
3；1＋2；1＋1＋1；
共有三种划分方法。
给出一个正整数，问有多少种划分方法。
输入格式
一个正整数n
输出格式
一个正整数，表示划分方案数
样例输入
3
样例输出
3
数据规模和约定
n<=100
解题思路：这道题可以用dp来解，首先就是要找dp方程。这里假设dp[n][m]：n被前m个数划分的方案数（包括第m个）
AC代码：
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long LL;
const int num = 105;
int n;
int dp[num][num]; //dp[n][m]：n被前m个数划分的方案数（包括第m个）
int main()
{
scanf("%d", &n);
dp[0][0] = 1; // 0被0之前的数划分的方案数为1，即：0本身
for(int i = 0; i <= n; i++)
for(int j = 1; j <= n; j++) //j不需要等于0因为dp[i][0] = 0，此外会有越界的危险
j <= i ? dp[i][j] = dp[i][j-1] + dp[i-j][j] : dp[i][j] = dp[i][i];
printf("%d", dp[n][n]);
return 0;
}
4.神、上帝以及老天爷
题目
HDU 2006‘10 ACM contest的颁奖晚会隆重开始了！
为了活跃气氛，组织者举行了一个别开生面、奖品丰厚的抽奖活动，这个活动的具体要求是这样的：
首先，所有参加晚会的人员都将一张写有自己名字的字条放入抽奖箱中；
然后，待所有字条加入完毕，每人从箱中取一个字条；
最后，如果取得的字条上写的就是自己的名字，那么“恭喜你，中奖了！”
大家可以想象一下当时的气氛之热烈，毕竟中奖者的奖品是大家梦寐以求的Twins签名照呀！不过，正如所有试图设计的喜剧往往以悲剧结尾，这次抽奖活动最后竟然没有一个人中奖！
我的神、上帝以及老天爷呀，怎么会这样呢？
不过，先不要激动，现在问题来了，你能计算一下发生这种情况的概率吗？
不会算？难道你也想以悲剧结尾？！
Input
输入数据的第一行是一个整数C,表示测试实例的个数，然后是C 行数据，每行包含一个整数n(1<n<=20),表示参加抽奖的人数。
Output
对于每个测试实例，请输出发生这种情况的百分比，每个实例的输出占一行, 结果保留两位小数(四舍五入)，具体格式请参sample output。
Sample Input
1
2
Sample Output
50.00%
解析：先计算一个全排列，就是把概率的分母算出来，接着在利用错排的递推公式Dn = （n-1）* （Dn-1 + Dn+1）作为分母即可求出概率。贴一个错排递推公式的推导过程：超级详细~点这，然后注意开一个LL就行，杭电的题贼多坑。
AC代码：
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 7;
const int maxm = 2e5 + 7;
const long long inf = 0x3f3f3f3f;
const long long mod = 1e9 + 7;
LL c, n;
LL a[25], b[25];
int main()
{
scanf("%lld", &c);
a[1] = 0, a[2] =1;
b[2] = 2;
while(c --)
{
scanf("%lld", &n);
for(int i = 3; i <= n; i++)
{
a[i] = (i - 1) * (a[i-1] + a[i-2]);
b[i] = i * b[i-1];
}
double ans = a[n] * 1.0 / b[n] * 100;
printf("%.2lf%%\n", ans);
}
return 0;
}
5.考新郎
题目
国庆期间,省城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 = 20, m = 19 可能会溢出, 假如不先对A（n,m）的阶乘进行运算, 再依次除m！假如不这么操作，直接就WA掉，因为long long 也列不出20的阶乘吧，所以我们必须用这个公式：C(n, m) = A(n, m) / m! ，而不能用C（n，m）= n! / （m! * (n - m)! ），此外还有个技巧就是这道题是求多组数据的，可以先对前25个数错排的方案数进行一个计算，这样可以降低一点点时间复杂度。
AC代码：
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 7;
const int maxm = 2e5 + 7;
const int num = 25;
const long long inf = 0x3f3f3f3f;
const long long mod = 1e9 + 7;
LL t, n, m, ans;
LL D[num];
int main()
{
scanf("%lld", &t);
D[1] = 0, D[2] = 1;
for(int i = 3; i <= num; i++)
D[i] = (i - 1) * (D[i-1] + D[i-2]);
while(t --)
{
scanf("%lld%lld", &n, &m);
ans = 0;
LL p = 1;
for(int i = n - m + 1; i <=n ; i++)
p *= i;
for(int i = 1; i <=m ; i++)
p /= i;
ans = D[m] * p;
printf("%lld\n", ans);
}
return 0;
}
附加1：A + B Again
题目
There must be many A + B problems in our HDOJ , now a new one is coming.
Give you two hexadecimal integers , your task is to calculate the sum of them,and print it in hexadecimal too.
Easy ? AC it !
Input
The input contains several test cases, please process to the end of the file.
Each case consists of two hexadecimal integers A and B in a line seperated by a blank.
The length of A and B is less than 15.
Output
For each test case,print the sum of A and B in hexadecimal in one line.
Sample Input
+A -A
+1A 12
1A -9
-1A -12
1A -AA
Sample Output
0
2C
11
-2C
-90
解析：题目大意就是输入两个十六进制数然后让你把他们进行相加并且以十六进制输出。一开始我差点就想直接写一个十六进制和十进制的转换，但发现好像有%x这个好东西，接着就直接用就行。不过这题有三个坑点：第一个是必须开long long ；第二个是输出的二进制数假如有字母必须是大写；第三就是%x的输出是无符号型，必须进行一个转换，也就是当（a + b）< 0 时，先将a + b 变成正的，接着在输出的时候加一个符号即可。
AC代码：
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long LL;
typedef unsigned int ULL;
const int maxn = 1e5 + 7;
const int maxm = 2e5 + 7;
const long long inf = 0x3f3f3f3f;
const long long mod = 1e9 + 7;
LL n, m;
int main()
{
while(~scanf("%llX%llX", &n, &m))
{
if(n + m >= 0)
printf("%llX\n", n + m);
else
printf("-%llX\n", -(n + m));
}
return 0;
}
原文：https://www.cnblogs.com/K2MnO4/p/12814903.html