207 条题解
-
2
852741 LV 10 @ 2018-08-16 15:59:57
#include<bits/stdc++.h>
using namespace std;
long long a[50];
int main()
{
long long n;
cin>>n;
a[0]=1;
a[1]=1;
a[2]=2;
a[3]=5;
for(int i=4;i<=n;i++)
for(int j=0;j<=i-1;j++)
a[i]=a[i]+a[j]*a[i-1-j];
cout<<a[n];
return 0;
}
用递推写的，不要在意，已经AC了 -
1
不会用卡特兰数列。。。
如果进栈次数和出栈次数都等于n，整个操作就结束了。如果进栈次数大于出栈次数，说明栈非空，执行出栈。如果进栈次数小于n，执行出栈#include<bits/stdc++.h> using namespace std; int n,ans = 0; void dfs(int jz,int cz) { if(jz == n&&cz == n) { ans++; return; } if(jz < n) dfs(jz + 1, cz); if(cz < jz) dfs(jz,cz + 1); } int main() { scanf("%d",&n); dfs(0,0); printf("%d",ans); return 0; } -
1
***用折线法，x表示进行第几次操作，y表示进栈元素个数-出栈元素个数，从(1,1)到(2n-1,1)，与x轴下方无公共点.
所以将坐标轴向下移一个单位长度，就是从(1,2)到(2n-1,2),与x轴无公共点，直接套公式.
则答案=C(2n-1,n-1)-C(2n-1,n+1).***
代码如下******如果把catalan数放到走地图这种情景下，不妨将出栈入栈看作两种方式：
（假设从左下向右上走）即向右（出栈）或者向上（入栈）走，因为要出栈n次，入栈n次，所以可以看成是从（0，0）到（n，n）点的走法数。
同时由于栈结构要求在出栈之前必须栈中需要有数，故我们走的路线必须不经过形如(x,x-1)的点，即路线一直在y=x-1这条直线的上面。
可以看出，如果我们从(1,-1)点出发必定会经过y=x-1直线才能到达(n,n)点，且这些路线恰巧和从(0,0)点出发但是通过y=x-1直线再到达(n,n)点的路径一一对应（即我们需要剔除的路线)
所以最终从(0,0)出发到达且不接触y=x-1直线的方式有C(2n,n)-C(2n,n-1)种。
#include<cstdio> #define MAX_N 20 #define ll long long using namespace std; int n; ll f[MAX_N][MAX_N]; int main() { scanf("%d",&n); for(int i=0;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][j-1]+f[i-1][j]; } } printf("%lld",f[n][n]); return 0; } -
1
aph。 (chenqianrong) LV 10 @ 2021-08-26 12:15:26
#include <bits/stdc++.h> using namespace std; int n, f[30]; int main() { scanf("%d", &n); f[0] = 1, f[1] = 1; for(int i=2; i<=n; i++) for(int j=0; j<i; j++) f[i] += f[j] * f[i-j-1]; printf("%d", f[n]); return 0; } -
1
用折线法，x表示进行第几次操作，y表示进栈元素个数-出栈元素个数，从(1,1)到(2n-1,1)，与x轴下方无公共点.
所以将坐标轴向下移一个单位长度，就是从(1,2)到(2n-1,2),与x轴无公共点，直接套公式.
则答案=C(2n-1,n-1)-C(2n-1,n+1).
代码如下:
#include<cstdio> #include<iostream> using namespace std; int n; int c(int n,int m){ long long s=1,d=1; for(int i=n;i>=n-m+1;i--) s*=i; for(int i=m;i;i--) d*=i; return s/d; } int main(){ scanf("%d",&n); printf("%d",c(2*n-1,n-1)-c(2*n-1,n+1)); } -
0
/* 简单的递推 通过第一个元素的出栈位置划分 dp[n] = dp[0] * dp[n - 1] + dp[1] * dp[n - 2] + ... + dp[n - 2] * dp[1] + dp[n - 1] * dp[0]; */ #include <iostream> #include <algorithm> using namespace std; int n; int dp[20]; int main() { cin >> n; dp[0] = dp[1] = 1; for (int i = 2; i <= n; i++) for (int k = 0; k < i; k++) dp[i] += dp[k] * dp[i - k - 1]; cout << dp[n] << endl; return 0; } -
0
如果把catalan数放到走地图这种情景下，不妨将出栈入栈看作两种方式：
（假设从左下向右上走）即向右（出栈）或者向上（入栈）走，因为要出栈n次，入栈n次，所以可以看成是从（0，0）到（n，n）点的走法数。
同时由于栈结构要求在出栈之前必须栈中需要有数，故我们走的路线必须不经过形如(x,x-1)的点，即路线一直在y=x-1这条直线的上面。
可以看出，如果我们从(1,-1)点出发必定会经过y=x-1直线才能到达(n,n)点，且这些路线恰巧和从(0,0)点出发但是通过y=x-1直线再到达(n,n)点的路径一一对应（即我们需要剔除的路线)
所以最终从(0,0)出发到达且不接触y=x-1直线的方式有C(2n,n)-C(2n,n-1)种。 -
0
feidaoluoye LV 9 @ 2017-11-21 19:45:36
#include <iostream> #include<cstdlib> #include<cstdio> #include<map> #include<vector> #include<cstring> #include<algorithm> #define mod 7654321 #define FOR(i,x,y) for(i=x;i<=y;++i) #define maxa 10000+100 using namespace std; int c(int n,int m){ long long s=1,d=1; for(int i=n;i>=n-m+1;i--) s*=i; for(int i=m;i;i--) d*=i; return s/d; } int main(){ int n; scanf("%d",&n); printf("%d",c(2*n,n)-c(2*n,n-1)); } -
0
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>using namespace std;
long long gcd(long long a,long long b)
{
if(a%b==0)return b;
return gcd(b,a%b);
}long long C(long long n)
{
long long cnt1=1,cnt2=1;
for(int i=1;i<=n;i++){
cnt2*=i;
cnt1*=i+n;
long long h=gcd(cnt2,cnt1);
if(h!=1){
cnt2/=h;
cnt1/=h;
}
}
return cnt1/cnt2;
}int main()
{
long long n;
cin>>n;
cout<<C(n)/(n+1)<<endl;
return 0;
} -
0
var tab:array[0..20,0..20] of longint;
n,z1,z2:longint;
Function go(s,x:longint):longint;
var tot:longint;
begin
If x>n then begin tab[s,x]:=1; go:=1; exit; end;
If tab[s,x]<>-1 then begin go:=tab[s,x]; exit; end;
tot:=0;
If s>0 then tot:=tot+go(s-1,x);
tot:=tot+go(s+1,x+1);
tab[s,x]:=tot;
go:=tot;
end;begin
readln(n);
fillchar(tab,sizeof(tab),$FF);
writeln(go(0,1));
end. -
0
最懒的办法
#include <iostream>
using namespace std;
int main()
{
char* Catalanwords[]={"1","1","2","5","14","42","132","429","1430","4862","16796","58786","208012","742900","2674440","9694845","35357670","129644790","477638700","1767263190","6564120420","24466267020","91482563640","343059613650"};
int i;
cin>>i;
cout<<Catalanwords[i]<<endl;
return 0;
} -
0
xiaoyu9964 LV 9 @ 2013-08-16 13:13:39
50题纪念
-
0
目测是格路问题，结果等于C(N+N-1,N)-C(N+N-1,N+1)
-
huangxin @ 2013-07-24 22:05:48
var
t1,t2,t3,t4,t5,ans:int64;
i,n:integer;
begin
readln(n); if n=1 then begin writeln(1); halt; end;
t1:=1; t2:=1; t3:=1; t4:=1; t5:=1;
for i:=n+1 to 2*n-1 do
t1:=t1*i;
for i:=1 to n-1 do
t2:=t2*i;
t3:=t1 div (n+1);
t4:=t2 div (n-1);
ans:=t1 div t2-t3 div t4;
writeln(ans);
end. -
评测结果
编译成功测试数据 #0: Accepted, time = 0 ms, mem = 772 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 772 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 768 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 768 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 768 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 772 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 772 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 772 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 768 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 772 KiB, score = 10
Accepted, time = 0 ms, mem = 772 KiB, score = 100可以参考《组合数学》第一章》...
-
-
0
zhumingjie10 LV 8 @ 2012-11-03 22:23:47
Catalan数。。。问度受前15项打表即可- -！
其实我们做过一道加强版，1 -
0
ChinaLover LV 8 @ 2012-07-29 09:16:35
const catalan:array[0..23] of string=('1','1','2','5','14','42','132','429','1430','4862','16796','58786','208012','742900','2674440','9694845','35357670','129644790','477638700','1767263190','6564120420','24466267020','91482563640','343059613650');
var n:integer;
begin
readln(n);
writeln(catalan[n]);
end.
这是最坑爹的做法。。楼下的公式我还没学到。。
852741
LV 10
@ 2018-08-16 15:59:57
