加入收藏 | 设为首页 | 会员中心 | 我要投稿 威海站长网 (https://www.0631zz.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 大数据 > 正文

大数 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;
}

(编辑:威海站长网)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    热点阅读