hdu 1133 卡特兰 高精度
Buy the Ticket
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5566 Accepted Submission(s): 2326
Suppose the cinema only has one ticket-office and the price for per-ticket is 50 dollars. The queue for buying the tickets is consisted of m + n persons (m persons each only has the 50-dollar bill and n persons each only has the 100-dollar bill).
Now the problem for you is to calculate the number of different ways of the queue that the buying process won't be stopped from the first person till the last person.
Note: initially the ticket-office has no money.
The buying process will be stopped on the occasion that the ticket-office has no 50-dollar bill but the first person of the queue only has the 100-dollar bill.
3 0
3 1
3 3
0 0
Test #1:
6
Test #2:
18
Test #3:
180
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define base 10000
int a[101];
void multiply(int x)
{
a[100]=1;
for(int i=1;i<=x;i++)
for(int j=100,temp=0;j>=0;j--)
{
temp+=a[j]*i;
a[j]=temp%base;
temp=temp/base;
}
}
void chen(int x)
{
int temp=0;
for(int i=100;i>=0;i--)
{
temp+=a[i]*x;
a[i]=temp%base;
temp=temp/base;
}
}
void output()
{
int i=1;
while(!a[i])
i++;
printf("%d",a[i]);//********假如第一位a[1]=34,a[2]=2039,则只能输出343029,而不能输出00342039,所以a[1]需 // 要单独列出来输出
for(i++;i<=100;i++)
printf("%04d",a[i]);//右对齐,左边不足的位数补0,例如假设,a[19]=1234,a[20]=34,a{21]=789则这一段的输出
//就为123400340789;
printf("\n");
}
void chu(int x)
{
int i=1,temp=0;
while(!a[i])
i++;
for(;i<=100;i++)
{
temp=a[i]+temp*base;
a[i]=temp/x;
temp%=x;
}
}
int main()
{
int m,n,cas=0;
while(~scanf("%d %d",&m,&n)&&(m||n))
{
cas++;
printf("Test #%d:\n",cas);
if(n>m) {cout<<"0"<<endl;}
else{
memset(a,0,sizeof(a));
multiply(m+n);
chen(m-n+1);
chu(m+1);
output();
}
}
return 0;
}
/*****受益匪浅的一道题,这道题综合性还是有点强的,首先卡特兰数推出公示后(公式我推了出来),但是因为数字实在太大(毕竟100的阶乘),所以必需对大数进行处理,也就是高精度,很有技巧性的是,可以让数组一个单元存储一万,而不是以前习惯的十(毕竟数太大),最后还有一个非常关键的地方,就是最终的输出(我个人觉得输出才是本题高潮,最有戏剧性的一部分),具体输出可见代码上的注释,最后,悲催的是发现自己很多题目没有把握都是因为不会时间复杂度以及内存存储大小的分析,是时候好好看看这两个知识点了****/
最新文章
- 利用SHELL脚本实现文件完整性检测程序(1.2版更新)
- angularjs的resource实例对象
- android权限使用
- css3 border-image 学习随笔
- Http请求和响应应用
- MVC3.0,路由设置实现伪静态IIS中404错误
- cocos2d-x 制作资源下载页面
- Multi-Objective Data Placement for Multi-Cloud Socially Aware Services---INFOCOM 2014
- mac下安装nginx问题解决
- 上传图片转为base64格式预览并压缩图片(不兼容IE9以下浏览器,兼容移动端ios,android)
- Tomcat集群搭建
- Git创建本地分支并推送到远程github仓库
- jquery切换
- java之简单工厂模式详解
- hdu5634 BestCoder Round #73 (div.1)
- ajax 请求问题
- Redis和Memcache的区别是什么
- 运算类实现 及 GNU Makefile基本结构
- idea打包 - 可执行jar包
- Linux系统日志分析与管理(14)
热门文章
- 剑指offer16:输入两个单调递增的链表,合成后的链表满足单调不减规则。
- dos(cmd)命令大全(本文摘至于网络)
- Pytorch报错:cuda runtime error (59) : device-side assert triggered at /pytorch/aten/src/THC/generic/THCTensorMath.cu:26
- 关于工作单元模式——工作单元模式与EF结合的使用
- JavaScript特点有哪些
- requests模块高级操作之cookie
- Qt 中配置 c99的问题
- bootsctrap4 datepicker时间选择插件
- Notepad++快捷键及使用技巧
- Java 读取 .properties 文件的几种方式