201 条题解

  • 2
    @ 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
    @ 2018-10-25 12:18:55

    为什么难度是1

  • 1
    @ 2017-09-07 13:05:20

    用折线法,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
    @ 2018-01-13 22:01:52

    如果把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
    @ 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
    @ 2013-10-15 21:38:45

    #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
    @ 2013-10-04 20:59:00

    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
    @ 2013-09-13 00:25:15

    最懒的办法
    #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
    @ 2013-08-16 13:13:39

    50题纪念

  • 0
    @ 2013-07-24 22:03:01

    目测是格路问题,结果等于C(N+N-1,N)-C(N+N-1,N+1)

    • @ 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.

    • @ 2013-07-24 22:07:14

      评测结果
      编译成功

      测试数据 #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
    @ 2013-04-04 11:31:21

    深搜2种情况:出(so(i-1,j+1,t));进:(so(i+1,j,t+1));也可以用卡特兰数做

  • 0
    @ 2012-11-03 22:23:47

    Catalan数。。。问度受前15项打表即可- -!

    其实我们做过一道加强版,1

  • 0
    @ 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
    @ 2012-08-02 15:10:23

    编译通过...

    ├ 测试数据 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)

    点击查看代码

  • 0
    @ 2009-11-04 22:27:49

    数学题

  • 0
    @ 2009-11-04 10:23:16

    Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2009-11-03 08:45:53

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    catalan...

  • 0
    @ 2009-11-02 16:51:02

    #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
    @ 2009-10-31 16:34:02

    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 有效耗时:0ms

    catlan递推

  • 0
    @ 2009-10-30 22:13:00

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    H2O题一道~~

    卡特兰可以~

    递归可以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.

信息

ID
1122
难度
1
分类
组合数学 | Catalan数列 点击显示
标签
递交数
3981
已通过
2452
通过率
62%
上传者