|
|
Posted on 2010-08-08 17:08 MiYu 阅读(896) 评论(1) 编辑 收藏 引用 所属分类: ACM ( 数论 ) 、 ACM ( 组合 )
MiYu原创, 转帖请注明 : 转载自 ______________白白の屋
卡特兰数专题
更多卡特兰数资料 请看 卡特兰数
HDU 1023 1130 1134 2067 都是标准的卡特兰数, 具体说明请见 卡特兰数 , 只是有一点需要注意, 在35以下的catalan数
可以直接使用 long long 或 __int64 提交的, 但是当 N 超过35 之后, 这就需要大数了.
下面是 2067 的 long long 代码 ,详细请见 ( 2067 小兔的棋盘 解题报告 ) 没有使用递归式 , 直接用的catalan 的 迭代式. :
//MiYu原创, 转帖请注明 : 转载自 ______________白白の屋
#include<iostream>
using namespace std;
typedef long long int64;
int64 f[37][37];
int main()
{
int ca=0;
int N;
while ( cin >> N , N + 1 )
{
++ ca;
for ( int i = 1;i <= N; ++ i )
{
f[0][i] = 1;
}
for ( int i = 1; i < N; ++ i )
{
for ( int j = i; j <= N; ++ j )
{
if ( i == j )
{
f[i][j] = f[i-1][j];
}
else
{
f[i][j] = f[i-1][j] + f[i][j-1];
}
}
}
printf("%d %d %I64d\n", ca, N, 2 * f[N-1][N] );
}
return 0;
}
除了 2067 外, 其他的题目均是大数的类型, 在这里, 各位 ACMer , 请出你们的大数模板吧 .
或者某些代码牛人可以自己手打 <-------0rz
写好代码后 只需按题目要求格式做相应的改变, 便能直接AC. 1133 稍微有点不同. 会在
最后给出它的解题报告.
1023 1130 1134 直接使用 catalan数 的递归式 ,代码如下, 使用的是高精度乘法 ( 需要在输入结束控制方面根据各题做相应变化 ) :
//MiYu原创, 转帖请注明 : 转载自 ______________白白の屋
#include<iostream>
using namespace std;
#define MAX 105
#define BASE 10000
typedef int myType[MAX+10];
void multiply ( int a[], int Max, int b ) //大数乘小数
{
int i,array=0;
for (i=Max-1; i>=0; i--)
{
array+=b*a[i];
a[i] = array%BASE;
array /= BASE;
}
}
void divide ( int a[], int Max, int b ) //大数除小数
{
int i,div=0;
for (i=0;i<Max; i++)
{
div = div*BASE + a[i];
a[i] = div / b;
div %= b;
}
}
void outPut ( myType ctl[MAX] ,int N )
{
int i = 0;
while ( i < MAX && ctl[N][i] == 0 )
{
i ++ ; //去前导0
}
cout << ctl[N][i++];
while ( i < MAX )
{
printf ( "%04d", ctl[N][i++] );
}
cout << endl;
}
void setNum ( myType ctl[MAX] )
{
memset ( ctl[1], 0, MAX * sizeof ( int ) );
ctl[1][MAX-1] = 1;
for ( int i = 2; i < 101; i ++ )
{
memcpy ( ctl[i], ctl[i-1], MAX * sizeof ( int ) );
multiply ( ctl[i], MAX, 4 * i - 2 );
divide ( ctl[i], MAX, i + 1 );
}
}
myType ctl[MAX];
int main()
{
setNum ( ctl );
int N;
while ( cin >> N ) // 这里根据各题要求需要做相应变化
{
outPut ( ctl, N );
}
return 0;
}
1133 公式推导如下 :
//MiYu原创, 转帖请注明 : 转载自 ______________白白の屋
( C(m+n, n) - C(m+n, m+1) ) * m! * n! 化简即 (m+n)! * (m-n+1) / (m+1)
推导过程如下 :
m个人拿50，n个人拿100
1: 所以如果 n > m，那么排序方法数为 0 这一点很容易想清楚
2: 现在我们假设 拿50的人用 ‘0’表示， 拿100的人用 1 表示。
如果有这么一个序列 0101101001001111.
当第K个位置出现1的个数多余0的个数时就是一个不合法序列了
假设m=4 n=3的一个序列是：0110100 显然，它不合法， 现在我们把它稍微变化一下：
把第二个1（这个1前面的都是合法的）后面的所有位0变成1，1变成0
就得到 0111011 这个序列1的数量多于0的数量， 显然不合法， 但现在的关键不是看这个序列是不是合法的
关键是：它和我们的不合法序列 0110100 成一一对应的关系
也就是说任意一个不合法序列(m个0，n个1)， 都可以由另外一个序列(n-1个0和m+1个1)得到
另外我们知道，一个序列要么是合法的，要么是不合法的
所以，合法序列数量 = 序列总数量 - 不合法序列的总量
序列总数可以这样计算m+n 个位置中， 选择 n 个位置出来填上 1， 所以是 C(m+n, n)
不合法序列的数量就是： m+n 个位置中， 选择 m+1 个位置出来填上 1 所以是 C(m+n, m+1)
然后每个人都是不一样的，所以需要全排列 m! * n!
所以最后的公式为 : ( C(m+n, n) - C(m+n, m+1) ) * m! * n! 化简即 (m+n)! * (m-n+1) / (m+1)
推广:
如果原来有p张50元的话,那么不合法的序列的数量应该是:任意一个不合法序列(m个0，n个1)，
都可以由另外一个序列(n-1个0和m+1+p个1)得到,所以是m+n 个位置中， 选择 m+1+p 个位置
出来填上 1 所以是 C(m+n, m+1+p) 接下来的化简就不推了.
代码如下 :
//MiYu原创, 转帖请注明 : 转载自 ______________白白の屋
#include <iostream>
#include <string>
using namespace std;
#define MAX 100
#define BASE 10000
void multiply(int a[],int Max,int b) //大数乘小数
{
int i,array=0;
for (i=Max-1; i>=0; i--)
{
array+=b*a[i];
a[i] = array%BASE;
array /= BASE;
}
}
void divide(int a[], int Max, int b) //大数除小数
{
int i,div=0;
for (i=0;i<Max; i++)
{
div = div*BASE + a[i];
a[i] = div / b;
div %= b;
}
}
int fact[205][MAX];
void setFact ()
{
fact[0][MAX-1] = fact[1][MAX-1] = 1;
for ( int i = 2; i <= 200; ++ i )
{
memcpy ( fact[i] , fact[i-1] , MAX * sizeof ( int ) );
multiply ( fact[i] , MAX , i );
}
}
void outPut ( int ctl[MAX] )
{
int i = 0;
while ( i < MAX && ctl[i] == 0 )
{
i ++ ; //去前导0
}
printf ( "%d", ctl[i++] );
while ( i < MAX )
{
printf ( "%04d", ctl[i++] );
}
putchar ( '\n' );
}
int res[MAX];
int main ()
{
int M,N;
int ca = 1;
setFact();
while ( cin >> M >> N , M + N )
{
printf ( "Test #%d:\n",ca++ );
if ( N > M )
{
puts ( "0" );
continue;
}
memcpy ( res , fact[M+N] , MAX * sizeof ( int ) ); //阶乘 ( m + n )!
multiply ( res, MAX, M - N + 1 ); //( m + n )! * ( m-n+1 )
divide ( res, MAX, M + 1 ); //( m + n )! * ( m-n+1 ) / ( m+ 1 )
outPut ( res );
}
return 0;
}
Feedback
# re: HDOJ HDU 1023 1130 1133 1134 2067 ACM 1023 1130 1133 1134 2067 IN HDU ( 卡特兰数 专题 catalan ) 回复 更多评论
2010-08-08 17:34 by
有空再来！！
|