做完（看完）发现，这套题都是组合数学的多，可是几乎都没学过啊！ 所以只做出了三题，接下来的题目，先学算法，再补上吧。
晚上的CF，到底能不能脱离灰名呢， 呃， 还得看晚上报不报名， 报了， 还得看 会不会做、、、、 - -#
A - 过山车
Problem Description
RPG girls今天和大家一起去游乐场玩，终于可以坐上梦寐以求的过山车了。可是，过山车的每一排只有两个座位，而且还有条不成文的规矩，就是每个女生必须找个个男生做partner和她同坐。但是，每个女孩都有各自的想法，举个例子把，Rabbit只愿意和XHD或PQK做partner，Grass只愿意和linle或LL做partner，PrincessSnow愿意和水域浪子或伪酷儿做partner。考虑到经费问题，boss刘决定只让找到partner的人去坐过山车，其他的人，嘿嘿，就站在下面看着吧。聪明的Acmer，你可以帮忙算算最多有多少对组合可以坐上过山车吗？
Input
输入数据的第一行是三个整数K , M , N，分别表示可能的组合数目，女生的人数，男生的人数。0<K<=1000
1<=N 和M<=500.接下来的K行，每行有两个数，分别表示女生Ai愿意和男生Bj做partner。最后一个0结束输入。
1<=N 和M<=500.接下来的K行，每行有两个数，分别表示女生Ai愿意和男生Bj做partner。最后一个0结束输入。
Output
对于每组数据，输出一个整数，表示可以坐上过山车的最多组合数。
Sample Input
6 3 3 1 1 1 2 1 3 2 1 2 3 3 1 0
Sample Output
3
简单的 二分图最大匹配，没想那么多，取值的时候，我是直接去n m 里面大的那个数，AC了， 也就没管了、、
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define N 520
vector<int> mpt[N];
int linker[N];
bool vis[N];
void init(int n)
{
for(int i = 1; i <= n; i ++)
{
mpt[i].clear();
}
}
bool dfs(int n)
{
for(int i = 0; i < mpt[n].size(); i ++)
{
if(!vis[ mpt[n][i] ])
{
vis[ mpt[n][i] ] = true;
if(!linker[ mpt[n][i] ] || dfs( linker[ mpt[n][i] ]))
{
linker[ mpt[n][i] ] = n;
return true;
}
}
}
return false;
}
int getsum(int n)
{
int cnt = 0;
memset(linker, 0, sizeof(linker));
for(int i = 1; i <= n; i ++)
{
memset(vis, false, sizeof(vis));
if(dfs(i))
cnt ++;
}
return cnt;
}
int main()
{
int t, m, n, tt;
int a, b;
while(~scanf("%d",&t))
{
if(t == 0)
break;
scanf("%d%d",&n, &m);
tt = max(n, m);
init(tt);
for(int i = 0; i < t; i ++)
{
scanf("%d%d",&a, &b);
mpt[a].push_back(b);
}
printf("%d\n",getsum(tt));
}
return 0;
}
B - 汉诺塔III
Problem Description
约19世纪末，在欧州的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到右边的杆上，条件是一次只能移动一个盘，且不允许大盘放在小盘的上面。
现在我们改变游戏的玩法，不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出)，也不允许大盘放到下盘的上面。
Daisy已经做过原来的汉诺塔问题和汉诺塔II，但碰到这个问题时，她想了很久都不能解决，现在请你帮助她。现在有N个圆盘，她至少多少次移动才能把这些圆盘从最左边移到最右边？
现在我们改变游戏的玩法，不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出)，也不允许大盘放到下盘的上面。
Daisy已经做过原来的汉诺塔问题和汉诺塔II，但碰到这个问题时，她想了很久都不能解决，现在请你帮助她。现在有N个圆盘，她至少多少次移动才能把这些圆盘从最左边移到最右边？
Input
包含多组数据，每次输入一个N值(1<=N=35)。
Output
对于每组数据，输出移动最小的次数。
Sample Input
1 3 12
Sample Output
2 26 531440
画了满满两面的 试卷大的草稿纸， 结果公式还搞错了， 差一点！ 我想知道，稍微数据大一点的，或者复杂的递推题要怎么搞- -||
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
__int64 f[40];
int main()
{
int n;
f[1] = 2;
f[2] = 8;
for(int i = 3; i <= 36; i ++)
{
f[i] = f[i - 1] * 3 + 2;
}
while(~scanf("%d", &n))
{
printf("%I64d\n", f[n]);
}
}
E - 小兔的棋盘
Problem Description
小兔的叔叔从外面旅游回来给她带来了一个礼物，小兔高兴地跑回自己的房间，拆开一看是一个棋盘，小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(0，0)走到终点(n,n)的最短路径数是C(2n,n),现在小兔又想如果不穿越对角线(但可接触对角线上的格点)，这样的路径数有多少?小兔想了很长时间都没想出来，现在想请你帮助小兔解决这个问题，对于你来说应该不难吧!
Input
每次输入一个数n(1<=n<=35)，当n等于－1时结束输入。
Output
对于每个输入数据输出路径数，具体格式看Sample。
Sample Input
1 3 12 -1
Sample Output
1 1 2 2 3 10 3 12 416024
简单的DP， 突然感觉，自己又水了一场比赛， 看来、、、、、好吧、、。 这场比赛就这样吧、、、
#include<stdio.h>
#include<math.h>
#include<string.h>
typedef long long ll;
ll dp[40][40];
void init()
{
for(int i = 1; i < 40 ; i ++)
dp[1][i] = 1;
for(int i = 2; i <40; i ++)
{
dp[i][i] = dp[i-1][i];
for(int j = i + 1; j < 40; j ++)
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
int main()
{
int n,t = 1;
init();
while(~scanf("%d",&n))
{
if(n == -1)
break;
printf("%d %d %I64d\n",t++,n,2*dp[n+1][n+1]);
}
return 0;
}
F - RPG的错排
Problem Description
今年暑假杭电ACM集训队第一次组成女生队,其中有一队叫RPG,但做为集训队成员之一的野骆驼竟然不知道RPG三个人具体是谁谁。RPG给他机会让他猜猜，第一次猜：R是公主，P是草儿，G是月野兔；第二次猜：R是草儿，P是月野兔，G是公主；第三次猜：R是草儿，P是公主，G是月野兔；......可怜的野骆驼第六次终于把RPG分清楚了。由于RPG的带动，做ACM的女生越来越多，我们的野骆驼想都知道她们，可现在有N多人，他要猜的次数可就多了，为了不为难野骆驼，女生们只要求他答对一半或以上就算过关，请问有多少组答案能使他顺利过关。
Input
输入的数据里有多个case,每个case包括一个n，代表有几个女生，（n<=25）, n = 0输入结束。
Sample Input
1 2 0
Sample Output
1 1
很容易找出公式，当然， 你还要知道一个错排（一个有n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排）公式，就更简单了。 错排公式: D(n) = (n - 1) * （ D (n - 2) + D (n - 1) ）
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
__int64 c(int n,int m)
{
__int64 a = 1;
if(m == 0)
return 1;
for(int i = 1; i <= m; i ++)
{
a = a* (n - i + 1);
a = a / i;
}
return a;
}
int main()
{
int n;
__int64 tt[30];
tt[1] = 0;
tt[2] = 1;
for(int i = 3; i <= 13; i ++)
{
tt[i] = (i - 1) * (tt[i - 1] + tt[i - 2]);
}
while(~scanf("%d",&n), n)
{
__int64 sum = 1;
for(int i = 1; i <= n/2 ; i ++)
{
sum += c(n, i)* tt[i];
}
printf("%I64d\n", sum);
}
}