这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
题目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=2064
感觉这题算不错吧。 (在ambition大牛的指点下才发现哪错了,orz) 考虑了几点。
一个是找规律,另外一个就是大数的处理。
大家看看这个图。
怎么找规律。
假设f[n]表示把n层从1移到3的次数,则f[n] = f[n-1]*3+2
考虑为何,因为f[n-1]表示把n-1层从1移到3的次数,这时在底部再添一层时,首先1~n-1层要从1移到3,这就是f[n-1]次了,然后最后一层n从1移到2,为1次,1~n层肯定还得从3移到1(这样最后一层n才能在第3环的最后),这又是f[n-1]次了,最后第n层由2移到3,为1次,1~n-1层由1再到3是f[n-1]次。所以总共就是f[n] = f[n-1]*3+2次
另外,网上好多人写了这个代码:
// 注意这是错误的版本
#include
#include
using namespace std;
int main()
{
int n;
while(scanf("%d", &n;) != EOF)
{
printf("%I64d\n", __int64(pow(3.0, n)) -1);
}
return 0;
}
大家测试就会发现在n=34和n=35时会和标准答案有出入,这是因为pow和double型都会精度丢失。 他们应该是很早做的。杭电的数据肯定很弱,发现BUG后改过来了。
正确的方法,用数组保存即可,注意用64为整型__int64保存。
// Tanky Woo
// HDOJ 2064
#include
#include
using namespace std;
__int64 num[36];
int main()
{
int n;
num[0] = 1;
num[1] = 2;
for(int i=2; i<36; ++i)
num[i] = num[i-1]*3+2;
while(scanf("%d", &n;) != EOF)
printf("%I64d\n", num[n]);
return 0;
}
当然,你测试就会发现只当n=34和35时会有标准有出入,所以你也可以这么写:
// Tanky Woo
#include
#include
using namespace std;
int main()
{
int n;
while(scanf("%d", &n;) != EOF)
{
if(n == 34)
printf("16677181699666568\n");
else if(n == 35)
printf("50031545098999706\n");
else
printf("%I64d\n", __int64(pow(3.0, n)) -__int64(1));
}
return 0;
}