HDOJ 1023 | HDOJ 1130 | HDOJ 1134 | BUCT OJ 1222 大数的卡特兰数

HDOJ 1023 Train Problem II http://acm.hdu.edu.cn/showproblem.php?pid=1023

HDOJ  1130 How Many Trees? http://acm.hdu.edu.cn/showproblem.php?pid=1130

HDOJ 1134  Game of Connections  http://acm.hdu.edu.cn/showproblem.php?pid=1134

BUCT OJ 1222  连线游戏  http://coder.buct.edu.cn/oj/Problem.aspx?pid=1222

这四题都是大数的卡特兰数,并且基本上可以说这四题的代码通用,唯一的区别就已在输入控制时可能不一样。

这里给出代码,注意在输出时要变通下:

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
using namespace std;
const int MAX = 105;
int catalan[105][MAX];
int temp[MAX];
 
int main()
{
	memset(catalan, 0, sizeof(catalan));
	catalan[1][0] = 1;
	int i, j;
	for(i = 2; i <= 100; ++i)
	{
		int mode = 4*i-2;
		for(j=0; j<MAX-1; ++j)
		{
			catalan[i][j] += catalan[i-1][j]*mode;
			if(catalan[i][j] >= 10)
			{
				catalan[i][j+1] += catalan[i][j]/10;
				catalan[i][j] %= 10;
			}
		}
		memset(temp, 0, sizeof(temp));
		int res = 0;
		mode = i+1;
		for(j=MAX-1; j>=0; --j)
		{
			temp[j] = (10*res + catalan[i][j])/mode;
			res = (10*res + catalan[i][j])%mode;
		}
		for(j=0; j<MAX; ++j)
			catalan[i][j] = temp[j];
 
	}
	int N;
	while(scanf("%d", &N) && N!=-1)
	{
		i = MAX-1;
		while(catalan[N][i] == 0)
		{
			--i;
		}
		printf("%d", catalan[N][i]);
		while(i--)
			printf("%d", catalan[N][i]);
		printf("\n");
	}
	return 0;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDOJ 1023 | HDOJ 1130 | HDOJ 1134 | BUCT OJ 1222 大数的卡特兰数》有4个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注