大数 Astar-Round1 Problem B
发布时间:2021-03-15 12:05:10 所属栏目:大数据 来源:网络整理
导读:题目 2016"百度之星" - 资格赛(Astar Round1) http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=690pid=1002 Problem Description 度熊面前有一个全是由1构成的字符串,被称为全1序列。你可以合并任意相邻的两个1,从而形成一个新的序列
题目 2016"百度之星" - 资格赛(Astar Round1) http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=690&pid=1002 Problem Description 度熊面前有一个全是由1构成的字符串,被称为全1序列。你可以合并任意相邻的两个1,从而形成一个新的序列。对于给定的一个全1序列,请计算根据以上方法,可以构成多少种不同的序列。Input 这里包括多组测试数据,每组测试数据包含一个正整数N,代表全1序列的长度。 1≤N≤200 Output 对于每组测试数据,输出一个整数,代表由题目中所给定的全1序列所能形成的新序列的数量。 Sample Input 1 3 5 Sample Output 1 3 8 Hint 如果序列是:(111)。可以构造出如下三个新序列:(111),(21),(12)。 分析 n-i个位置中放置i个2。要计算组合,由于N较大,最后结果远超long long能存储范围,所以涉及大数加法、乘法、除法。 (这个代码运行时间相对较长,不是很有参考性) (比赛还没结束,但这篇文章能被搜索引擎收录时应该结束了吧) 代码 #include <iostream> using namespace std; const int SZ=50; int ans[SZ]; int c[SZ]; void mul(int a[],int m) { for(int i=0;i<SZ-2;i++){ a[i]*=m; } for(int i=1;i<SZ-2;i++){ a[i]+=a[i-1]/10; a[i-1]%=10; } } void div(int a[],int m) { int i,c; for(i=SZ-2,c=0;i>=0;i--){ c=c*10+a[i]; a[i]=c/m; c%=m; } } void add(int a[],const int b[]) { int i; for(i=0;i<SZ-2;i++){ a[i]+=b[i]; a[i+1]+=a[i]/10; a[i]%=10; } if(a[SZ-1]) cout<<"spill"<<endl; } void zero(int a[]) { for(int i=0;i<SZ;i++) a[i]=0; } void print(int a[]) { int i,j; for(i=SZ-1;i>=0;i--) if(a[i]) break; for(j=i;j>=0;j--) cout<<a[j]; cout<<endl; } int main() { int i,j; int n; while(cin>>n){ zero(ans); ans[0]=1; for(i=1;2*i<=n;i++){ zero(c); c[0]=1; for(j=1;j<=min(i,n-2*i);j++){ mul(c,n-i-j+1); div(c,j); } add(ans,c); } print(ans); } return 0; } (编辑:威海站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |