题目地址:
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次
另外,网上好多人写了这个代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | // 注意这是错误的版本 #include <iostream> #include <cmath> 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保存。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | // Tanky Woo // HDOJ 2064 #include <iostream> #include <cmath> 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时会有标准有出入,所以你也可以这么写:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | // Tanky Woo #include <iostream> #include <cmath> 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; } |
我刚刚用你的代码试了,通不过,很可惜了
我刚又去提交了,AC。
不知道是你用的是第一个错误的代码?还是你的编译器选择错了?
@人生如梦
[s:33]
好文章
[s:4]