编码-百度之星资格赛Problem B-2016.05.15

2016-05-15 11:25:00

Problem B

Accepts: 1884 Submissions: 7016
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

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)。

代码

其中的大数类来自网络，冗余的功能并未删减。

include

using namespace std;

define MAXN 9999

define MAXSIZE 10

define DLEN 4

class BigNum
{
private:
int a[500]; //可以控制大数的位数
int len; //大数长度
public:
BigNum() { len = 1;memset(a, 0, sizeof(a)); } //构造函数
BigNum(const int); //将一个int类型的变量转化为大数
BigNum(const char*); //将一个字符串类型的变量转化为大数
BigNum(const BigNum &); //拷贝构造函数
BigNum &operator=(const BigNum &); //重载赋值运算符，大数之间进行赋值运算

friend istream& operator >> (istream&, BigNum&);   //重载输入运算符friend ostream& operator(const BigNum & T)const;   //大数和另一个大数的大小比较bool   operator>(const int & t)const;      //大数和一个int类型的变量的大小比较void print();       //输出大数

};
BigNum::BigNum(const int b) //将一个int类型的变量转化为大数
{
int c, d = b;
len = 0;
memset(a, 0, sizeof(a));
while (d > MAXN)
{
c = d - (d / (MAXN + 1)) (MAXN + 1);
d = d / (MAXN + 1);
a[len++] = c;
}
a[len++] = d;
}
BigNum::BigNum(const chars) //将一个字符串类型的变量转化为大数
{
int t, k, index, l, i;
memset(a, 0, sizeof(a));
l = strlen(s);
len = l / DLEN;
if (l%DLEN)
len++;
index = 0;
for (i = l - 1;i >= 0;i -= DLEN)
{
t = 0;
k = i - DLEN + 1;
if (k> (istream & in, BigNum & b) //重载输入运算符
{
char ch[MAXSIZE 4];
int i = -1;
in >> ch;
int l = strlen(ch);
int count = 0, sum = 0;
for (i = l - 1;i >= 0;)
{
sum = 0;
int t = 1;
for (int j = 0;j= 0;j++, i--, t = 10)
{
sum += (ch[i] - '0')*t;
}
b.a[count] = sum;
count++;
}
b.len = count++;
return in;

}
ostream& operator= 0; i--)
{
cout.width(DLEN);
cout.fill('0');
cout len ? T.len : len;
for (i = 0; i MAXN)
{
t.a[i + 1]++;
t.a[i] -= MAXN + 1;
}
}
if (t.a[big] != 0)
t.len = big + 1;
else
t.len = big;
return t;
}
BigNum BigNum::operator-(const BigNum & T) const //两个大数之间的相减运算
{
int i, j, big;
bool flag;
BigNum t1, t2;
if (this>T)
{
t1 = this;
t2 = T;
flag = 0;
}
else
{
t1 = T;
t2 = *this;
flag = 1;
}
big = t1.len;
for (i = 0; i i)
t1.a[j--] += MAXN;
t1.a[i] += MAXN + 1 - t2.a[i];
}
else
t1.a[i] -= t2.a[i];
}
t1.len = big;
while (t1.a[len - 1] == 0 && t1.len > 1)
{
t1.len--;
big--;
}
if (flag)
t1.a[big - 1] = 0 - t1.a[big - 1];
return t1;
}

BigNum BigNum::operator(const BigNum & T) const //两个大数之间的相乘运算
{
BigNum ret;
int i, j, up;
int temp, temp1;
for (i = 0; i MAXN)
{
temp1 = temp - temp / (MAXN + 1) (MAXN + 1);
up = temp / (MAXN + 1);
ret.a[i + j] = temp1;
}
else
{
up = 0;
ret.a[i + j] = temp;
}
}
if (up != 0)
ret.a[i + j] = up;
}
ret.len = i + j;
while (ret.a[ret.len - 1] == 0 && ret.len > 1)
ret.len--;
return ret;
}
BigNum BigNum::operator/(const int & b) const //大数对一个整数进行相除运算
{
BigNum ret;
int i, down = 0;
for (i = len - 1; i >= 0; i--)
{
ret.a[i] = (a[i] + down (MAXN + 1)) / b;
down = a[i] + down (MAXN + 1) - ret.a[i] b;
}
ret.len = len;
while (ret.a[ret.len - 1] == 0 && ret.len > 1)
ret.len--;
return ret;
}
int BigNum::operator %(const int & b) const //大数对一个int类型的变量进行取模运算
{
int i, d = 0;
for (i = len - 1; i >= 0; i--)
{
d = ((d (MAXN + 1)) % b + a[i]) % b;
}
return d;
}
BigNum BigNum::operator^(const int & n) const //大数的n次方运算
{
BigNum t, ret(1);
int i;
if (n1)
{
t = this;
for (i = 1;i (const BigNum & T) const //大数和另一个大数的大小比较
{
int ln;
if (len > T.len)
return true;
else if (len == T.len)
{
ln = len - 1;
while (a[ln] == T.a[ln] && ln >= 0)
ln--;
if (ln >= 0 && a[ln] > T.a[ln])
return true;
else
return false;
}
else
return false;
}
bool BigNum::operator >(const int & t) const //大数和一个int类型的变量的大小比较
{
BigNum b(t);
return this>b;
}

void BigNum::print() //输出大数
{
int i;
cout = 0; i--)
{
cout.width(DLEN);
cout.fill('0');
cout > N) {
if (N 200)
cout

心得

1.求出递推公式。本题的就是菲波那切数列。本项的值等于前两项之和。
2.求通项的方法不可以用递归。
因为递归消耗资源太多，比如时间限制为1000ms.一开始我是这么写的（代码在下方），结果总是超时。
考虑到只需要1到200的通项，可以把1到200的通项都存起来，用空间换取时间。
BigNum fun(int n) {
if (n == 0)return 1;
else if (n == 1)return 1;
else if (n == 2)return 2;
BigNum count = fun(n - 1) + fun(n - 2);
return count;
}

int main() {
int N;
while (cin >> N) {
if (N 200)
cout
3.由于序数N最大为200，所对应的数列的已经超出unsigned long long，必须要用自定义的高精度的大数类存储。