Description
Input
Output
Sample Input
| input | output |
|---|---|
1 A |
0 |
4 BBBB |
15 |
7 BCCBABC |
95 |
Source
UESTC 2016 Summer Training #17 Div.2
My Solution
汉诺塔， 得到从初始状态到任意给出状态需要的次数的O(n)算法， 记结论吧??
比如要得到 BCCBABC
则对于原始的AAAAAAA
第一次令 res = ‘A‘， 然后对于给出的state从大的往小的开始扫， 当前是C所以第7个A变成C， ans += 2^(7 - 1), 然后res = ‘B‘, 也就是剩余的移到B上，
然后第二个需要到B上，且已经在B上， 所以不用管， 继续访问下一位
然后是A， 这个时候把当期大小的盘在B上， 所以移到A上， ans += 2^(5 - 1), 然后res = ’C‘， 剩余的全都移到第三个柱子’C‘上。
依次这样下去就好了
比较当前盘需要的在哪个柱子上和当前在那个柱子上， 如果恰好在则直接访问下一个盘子， 如果不是则把该盘移过去 ans += 2^i ( 0 <= i < n)， 剩余的盘全移到第三个柱子上
把AAAAAAA.....从右往左， 全部变成state， 就可以得到答案了
此外注意点
用 1<<i得到 2^i次时，如果i很大， 比如50， 这个时候integer 溢出了， 用 (LL)(1<<50)也达不到效果， 还是得到数据丢失的integer大小的数，
然后用了cmath里的那个不大靠谱的pow， ans += (LL)pow(2, i);就可以得到 64位的整数了
复杂度 O(n)
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
const int maxn = 1e2 + 8;
char val[maxn];
int main()
{
#ifdef LOCAL
freopen("a.txt", "r", stdin);
//freopen("b.txt", "w", stdout);
int T = 4;
while(T--){
#endif // LOCAL
LL n, ans = 0;
char res = 'A';
scanf("%I64d", &n);
scanf("%s", val);
for(LL i = n - 1; i >= 0; i--){
if(res != val[i]){
ans += (LL)pow(2, i);
//cout<<ans<<endl;
if(res == 'A'){
if(val[i] == 'B') res = 'C';
else res = 'B';
}
else if(res == 'B'){
if(val[i] == 'A') res = 'C';
else res = 'A';
}
else if(res == 'C'){
if(val[i] == 'A') res = 'B';
else res = 'A';
}
}
if(ans < 0 || ans > 1e18) break;
}
if(ans < 0 || ans > 1e18) printf("-1");
printf("%I64d", ans);
#ifdef LOCAL
printf("\n");
}
#endif // LOCAL
return 0;
}Thank you!
------from ProLights
URAL 2029 Towers of Hanoi Strike Back 汉诺塔,从初始状态到任意给出状态需要的次数
原文：http://blog.csdn.net/prolightsfxjh/article/details/52076323