| 记录编号 |
452743 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[NOIP 2007]Hanoi双塔问题 |
最终得分 |
100 |
| 用户昵称 |
 xzcxzc11 |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.004 s |
| 提交时间 |
2017-09-20 10:11:19 |
内存使用 |
0.31 MiB |
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <fstream>
#include <cstring>
using namespace std;
#ifndef _INT
#define _Int
#define MAXN 1100
class Int
{
private:
int data[MAXN];
int length;
bool is_neg;
public:
Int()
{
memset(data, 0, sizeof(data));
length = 1;
is_neg = 0;
}
Int(const char* str)
{
*this = str;
}
Int(int num)
{
*this = num;
}
Int operator=(const char* str)
{
memset(data, 0, sizeof(data));
if (str[0] != '-')
{
is_neg = false;
length = strlen(str);
for (int i = 0; i < length; ++i)
{
data[i] = str[length - 1 - i] - '0';
}
}
else
{
is_neg = true;
length = strlen(str) - 1;
for (int i = 1; i <= length; ++i)
{
data[i - 1] = str[length + 1 - i] - '0';
}
}
return *this;
}
Int operator=(int num)
{
char str[MAXN];
sprintf(str, "%d", num);
*this = str;
return *this;
}
friend ostream & operator << (ostream & out, const Int & x);
bool operator==(const Int & num2)const;
bool operator<(const Int & num2)const;
bool operator>(const Int & num2)const;
bool operator<=(const Int & num2)const;
bool operator>=(const Int & num2)const;
bool operator!=(const Int & num2)const;
Int operator+(const Int & num2)const;
Int operator+=(const Int & num2);
Int operator-(const Int & num2)const;
Int operator-=(const Int & num2);
Int operator*(const Int & num2)const;
Int operator*=(const Int & num2);
Int operator/(const Int & num2)const;
};
istream & operator >> (istream & in, Int & x);
#endif
istream & operator >> (istream & in, Int & x)
{
char str[MAXN];
in >> str;
x = str;
return in;
}
ostream & operator<<(ostream & out, const Int & x)
{
if (x.is_neg)
{
cout << '-';
}
for (int i = x.length - 1; i >= 0; --i)
{
out << x.data[i];
}
return out;
}
bool Int::operator==(const Int & num2) const
{
if (is_neg == num2.is_neg)//如果符号相等
{
if (length != num2.length)
{
return false;
}
else
{
for (int i = 0; i < length; ++i)
{
if (data[i] != num2.data[i])
return false;
}
}
return true;
}
else return false;
}
bool Int::operator<(const Int & num2) const
{
if (is_neg == num2.is_neg)//如果同号
{
if (is_neg == false)//如果都为正数
{
if (length != num2.length)
{
return length < num2.length;
}
for (int i = length - 1; i >= 0; --i)
{
if (data[i] != num2.data[i])
{
return data[i] < num2.data[i];
}
}
return false;
}
else//如果都为负数
{
if (length != num2.length)
{
return length > num2.length;//位数多的绝对值大，其值反而小
}
for (int i = length - 1; i >= 0; --i)
{
if (data[i] != num2.data[i])
{
return data[i] > num2.data[i];//绝对值大的反而小
}
}
return false;//两数相等，"<"亦不成立
}
}
else//如果异号
{
return is_neg == true;//如果操作数1为负数则"<"成立
}
}
bool Int::operator>(const Int & num2) const
{
return num2 < *this;
}
bool Int::operator<=(const Int & num2) const
{
return !(*this > num2);
}
bool Int::operator>=(const Int & num2) const
{
return !(*this < num2);
}
bool Int::operator!=(const Int & num2) const
{
return !(*this == num2);
}
Int Int::operator+(const Int & num2) const
{
Int num;
if (is_neg == num2.is_neg)//如果同号，绝对值相加
{
num.is_neg = is_neg;
int x = 0;
int i;
for (i = 0; i < length || i < num2.length; ++i)
{
num.data[i] = data[i] + num2.data[i] + x;
x = num.data[i] / 10;
num.data[i] %= 10;
}
num.data[i] = x;
if (num.data[i] == 0)
{
num.length = i;
}
else
{
num.length = i + 1;
}
}
else//如果异号
{
//取绝对值
Int a, b;
a = *this;
b = num2;
a.is_neg = b.is_neg = false;
Int* c = &a;
Int* d = &b;
//比较大小
//谁的绝对值大听谁的
if (a > b)
{
num.is_neg = (*this).is_neg;
}
else if (a < b)
{
num.is_neg = num2.is_neg;
c = &b;
d = &a;//交换，把大的放前面
}
else if (a == b)
{
return num;//符号相反，绝对值相等，则返回高精度数 0；
}
//执行正常减法
int i = 0;
for (i = 0; i < c->length || i < d->length; ++i)
{
if (c->data[i] < d->data[i])
{
c->data[i] += 10;
c->data[i + 1]--;
}
num.data[i] = c->data[i] - d->data[i];
}
num.length = i;
while (num.data[num.length - 1] == 0 && num.length > 1)
{
num.length--;
}
}
return num;
}
Int Int::operator+=(const Int & num2)
{
*this = *this + num2;
return *this;
}
Int Int::operator-(const Int & num2) const
{
Int b;
b = num2;
b.is_neg = !num2.is_neg;
return (*this) + b;//减负等于加正
}
Int Int::operator-=(const Int & num2)
{
*this = *this - num2;
return *this;
}
Int Int::operator*(const Int & num2) const
{
Int num;
//同号得正，异号得负
if (is_neg == num2.is_neg)
{
num.is_neg = false;
}
else
{
num.is_neg = true;
}
num.length = length + num2.length;
for (int i = 0; i < length; ++i)
{
for (int j = 0; j < num2.length; ++j)
{
num.data[i + j] += data[i] * num2.data[j];
num.data[i + j + 1] += num.data[i + j] / 10;
num.data[i + j] %= 10;
}
}
while (num.data[num.length - 1] == 0 && num.length > 1)
{
--num.length;
}
return num;
}
Int Int::operator*=(const Int & num2)
{
*this = *this*num2;
return *this;
}
Int Int::operator/(const Int & num2) const
{
Int c;
Int a, b;
a = *this;
b = num2;
a.is_neg = b.is_neg = false;
const Int zero = 0;
const Int one = 1;
if (a < b)
{
return zero;
}
Int level = one;
int len_of_b = b.length;
int delta_length = a.length - b.length;
level.data[level.length - 1] = 0;
level.data[delta_length - 1 + 1] = 1;
level.length = delta_length + 1;
Int tempb = b;
tempb *= level;
while (tempb.length >= len_of_b)
{
while (a - tempb >= zero)
{
a -= tempb;
c += level;
}
if (level.length > 1)
{
level.data[level.length - 1] = 0;
--level.length;
level.data[level.length - 1] = 1;
tempb = b*level;
}
else break;
}
if (is_neg == num2.is_neg || c == zero)
{
c.is_neg = false;
}
else
{
c.is_neg = true;
}
return c;
}
ifstream fin("hanoi.in");
ofstream fout("hanoi.out");
int main()
{
Int two=2;
Int one=1;
int n;
fin>>n;
Int result=1;
for (int i=1;i<=n;++i)
{
result*=two;
}
result-=one;
result*=two;
fout<<result<<endl;
return 0;
}