201 条题解
-
1
小胖666 LV 6 @ 2018-10-25 12:18:55
为什么难度是1
-
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
如果把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 8 @ 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 7 @ 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.
这是最坑爹的做法。。楼下的公式我还没学到。。 -
0
#include
int number;
int account=0;int pop(int point,int n)
{
point--;
if( point==0)
push(point+1,n+1);
else
{
push(point+1,n+1);
pop(point,n);
}}
int push( int point,int n)
{
if(n==number) account++;else
{
push(point+1,n+1);
pop(point,n);
}
}int main()
{
int point=1;
scanf("%d",&number);
push(point,1);
printf("%d",account);return 0;
}
-
0
program E1_2;
var
n1,i,n:integer;
a:array[0..20] of longint;
cha1,cha2:longint;
begin
//init
readln(n1);
//main---|DiTui---|Catalan
a[2]:=1;n:=2;
repeat
inc(n);
for i:=2 to n-1 do
a[n]:=a[n]+a[i]*a[n-i+1];
until n>=n1+2;
//print
writeln(a[n1+2]);
end.
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0mscatlan递推
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0msH2O题一道~~
卡特兰可以~
递归可以0ms~晒晒程序
Var
n:Longint;Function try(w,z:Longint):Longint;
Begin
If (w=0) and (z=0) Then Exit(1);
If w=0 Then Exit(try(w,z-1));
If z=0 Then Exit(try(w-1,z+1));
Exit(try(w,z-1)+try(w-1,z+1));
End;Begin
Readln(n);
Writeln(try(n,0));
End.
小胖666
LV 6
@ 2018-10-25 12:18:55
