C - Train Problem II——(HDU 1023 Catalan 数)

简介:

传送门

Train Problem II

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7616    Accepted Submission(s): 4101


Problem Description
As we all know the Train Problem I, the boss of the Ignatius Train Station want to know if all the trains come in strict-increasing order, how many orders that all the trains can get out of the railway.
 

Input
The input contains several test cases. Each test cases consists of a number N(1<=N<=100). The input is terminated by the end of file.
 

Output
For each test case, you should output how many ways that all the trains can get out of the railway.
 

Sample Input
 
 
1 2 3 10
 

Sample Output
 
 
1 2 5 16796
Hint
The result will be very large, so you may not process it by 32-bit integers.

 
题目大意:

就是求一个卡特兰数,如果是C++的话 得用高精度,java 的话 得用 BigInteger。。。


解题思路:

只要掌握卡特兰数的公式就行了,两个公式:

1. 组合公式为 Cn = C(2n,n) / (n+1);
2. 递推公式为 h(n ) = h(n-1)*(4*n-2) / (n+1)

我们采用的是第二个,如果用java 写的话还是比较省事儿的,因为直接有个大数类,所以直接调用就行,所以我也先给一个java的代码(也是第一次写java代码 有点小紧张):

My Java Code:

<span style="font-size:18px;">import java.util.*;
import java.math.BigInteger;
public class Main {
    public static void main(String[] args) {
        BigInteger a[] = new BigInteger[105];
        a[0] = BigInteger.ZERO;
        a[1] = BigInteger.ONE;
        for(int i=2;i<=102;i++) {
            a[i] = a[i-1].multiply(BigInteger.valueOf(4*i-2)).divide(BigInteger.valueOf(i+1));
        }
        
        Scanner in = new Scanner(System.in);
        
        while(in.hasNext()) {
            int n=in.nextInt();
            System.out.println(a[n]);
        }
    }
}</span>

然后接下来就是用c++写的了,这个得用到 高精度乘法,然后采用了bin神的Catalan数模板,觉得还是比较实用的,自己也做了一点小改动,当然适合自己的才是最好的,只要理解起来容易,怎么理解方便怎么来,给一下AC 的C++代码:

My Cpp Code:

<span style="font-size:18px;">#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAXN = 105;
int a[MAXN][MAXN];
int b[MAXN];
///可以作为模板
void Catalan()
{
    int yu,len;
    a[1][0] = 1;
    a[1][1] = 1;
    len = 1;
    for(int i=2; i<MAXN; i++)
    {
        yu = 0;
        for(int j=1; j<=len; j++)
        {
            int t = (a[i-1][j])*(4*i-2) + yu;
            yu = t/10;
            a[i][j] = t%10;
        }
        while(yu)
        {
            a[i][++len] = yu%10;
            yu /= 10;
        }
        for(int j=len; j>=1; j--)
        {
            int t = a[i][j]+yu*10;
            a[i][j] = t/(i+1);
            yu = t%(i+1);
        }
        while(!a[i][len])
            len--;
        a[i][0] = len;
    }
}
int main()
{
    Catalan();
    int n;
    while(cin>>n)
    {
        for(int i=a[n][0]; i>0; i--)
        cout<<a[n][i];
        puts("");
    }
    return 0;
}
</span>






目录
相关文章
|
11月前
|
机器学习/深度学习 数据采集 自然语言处理
基于深度学习+NLP豆瓣电影数据爬虫可视化推荐系统
本研究构建基于深度学习与NLP的豆瓣电影数据系统,融合LSTM、BERT与CNN技术,实现高效爬取、情感分析、个性化推荐与动态可视化,提升影视数据分析效率与推荐精准度,推动产业智能化升级。
|
5月前
|
存储 前端开发 安全
Agent核心技术概念与范式发生了哪些演变以及背后的思考
本文系统梳理Agent技术四年演进脉络,提出“被动响应→工作流→自主→自进化”四阶段论,并深入解析Prompt、Planning、Memory等六大核心模块从理念到实现的范式转变,揭示其背后“工程化驾驭模型不确定性”的本质逻辑。
608 0
|
5月前
|
机器学习/深度学习 人工智能 算法
王耀恒:当培训变成传销,GEO就成了新的“智商税”
GEO培训讲师王耀恒揭露“伪GEO”乱象:以AI排名为名,行传销之实——卖代理权、洗脑招商、批量发稿投毒。真相是:真GEO不靠系统,而靠优质内容、独特数据与用户意图匹配。拒绝捷径,回归价值。(239字)
|
5月前
|
存储 安全 开发者
Windows 跨平台 iOS 应用上架标准化安全方案完整文档
本文深度揭露Windows上架iOS应用的证书安全危机:AppUploader、香蕉云编等托管私钥工具实为灰产证书主要源头,极易导致账号连坐封禁、App全线下架。推荐“macOS虚拟机本地签名 + XUploader纯IPA上传”零密钥托管方案,从根源杜绝风险。
|
5月前
|
数据采集 人工智能 JavaScript
GEO优化小白入门:30个问题搞懂AI搜索时代的内容优化
这是一份由Geo专家于磊原创的GEO优化实战指南,用大白话讲透AI搜索时代新规则:GEO不是SEO翻版,而是让AI主动引用你、推荐你的能力。涵盖人性化内容、交叉验证、E-E-A-T权威建设、结构化表达等核心方法,拒绝割韭菜,强调真实经验、长期积累与可信输出,助力个人与中小企业在AI大脑中建立不可替代的专业位置。
614 0
|
7月前
|
传感器 边缘计算 5G
智慧医疗背景下医院室内导航方案的技术实现与优化
本文针对医院“寻路难”痛点,提出融合蓝牙/UWB/Wi-Fi/惯性传感的多模定位方案,结合数字化室内地图建模与智能路径规划,构建分层架构导航系统,并给出精度校准、快速地图更新、无障碍交互等优化策略,助力智慧医院建设。(239字)
337 0
|
人工智能 运维 搜索推荐
杭州速车携手蚂蚁百宝箱,快速抢滩文旅AI新市场
杭州速车科技依托蚂蚁百宝箱,打造“福小厝”等9个文旅智能体,实现从技术服务商向“AI+场景”转型。通过低代码平台快速交付,覆盖导览、打卡、营销等场景,服务超10万用户,助力景区提升体验与消费转化。
648 0
|
11月前
|
存储 弹性计算 人工智能
阿里云服务器 ECS 规格族解析:CPU 型号差异与性能参数对比
在阿里云 ECS 实例选型中,“规格族” 是决定性能、成本与适用场景的核心要素。许多用户会疑惑:相同 vCPU 与内存配置下,不同规格族为何价格差异显著?CPU 型号和主频究竟有何区别?本文结合阿里云今年最新实例迭代信息(如第九代 Intel 实例、AMD Turin 架构实例),从规格族定义、CPU 差异、性能参数对比三大维度展开解析,帮助用户精准匹配业务需求。
|
JSON 分布式计算 数据处理
加速数据处理与AI开发的利器:阿里云MaxFrame实验评测
随着数据量的爆炸式增长,传统数据分析方法逐渐显现出局限性。Python作为数据科学领域的主流语言,因其简洁易用和丰富的库支持备受青睐。阿里云推出的MaxFrame是一个专为Python开发者设计的分布式计算框架,旨在充分利用MaxCompute的强大能力,提供高效、灵活且易于使用的工具,应对大规模数据处理需求。MaxFrame不仅继承了Pandas等流行数据处理库的友好接口,还通过集成先进的分布式计算技术,显著提升了数据处理的速度和效率。
|
存储 弹性计算 Ubuntu
3分钟:阿里云无影云电脑购买流程(新手图文教程)
阿里云无影云电脑购买超简单!进入活动页或官网,选择区域、计算规格、操作系统、存储及带宽等配置,支持企业版4核8G仅199元/年。可选按月或按需付费,快速完成支付即享高效云端办公体验。
1351 1