207 条题解
-
2
852741 LV 10 @ 6 年前
#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了 -
12 年前@
不会用卡特兰数列。。。
如果进栈次数和出栈次数都等于n,整个操作就结束了。如果进栈次数大于出栈次数,说明栈非空,执行出栈。如果进栈次数小于n,执行出栈 -
12 年前@
***用折线法,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)种。
-
13 年前@
-
13 年前@
-
16 年前@
为什么难度是1
-
17 年前@
用折线法,x表示进行第几次操作,y表示进栈元素个数-出栈元素个数,从(1,1)到(2n-1,1),与x轴下方无公共点.
所以将坐标轴向下移一个单位长度,就是从(1,2)到(2n-1,2),与x轴无公共点,直接套公式.
则答案=C(2n-1,n-1)-C(2n-1,n+1).
代码如下:
-
05 年前@
-
05 年前@
-
07 年前@
如果把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)种。 -
07 年前@
-
011 年前@
#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;
} -
011 年前@
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. -
011 年前@
最懒的办法
#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;
} -
011 年前@
50题纪念
-
011 年前@
目测是格路问题,结果等于C(N+N-1,N)-C(N+N-1,N+1)
-
012 年前@
深搜2种情况:出(so(i-1,j+1,t));进:(so(i+1,j,t+1));也可以用卡特兰数做
-
012 年前@
Catalan数。。。问度受前15项打表即可- -!
其实我们做过一道加强版,1 -
012 年前@
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.
这是最坑爹的做法。。楼下的公式我还没学到。。 -
012 年前@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms用公式,m:=C(2n{在右下角},n)/(n+1)
点击查看代码