POJ 1001: Exponentiation

这道题是鄙人试图接触竞赛圈的第一个小小的尝试（POJ 1000就不算了哈），所以还是比较有纪念意义的！虽然A了很久，但在自己漫长的一点一点调试的过程中还是总结出了些许心得。

思路非常简单（其实一开始没查题解的时候理解还是不对的，看来还得好好学英语），扼要概括一下就是计算机中自带的浮点类型并不能满足我们这道题对于精度的高要求，这道题需要我们输出的就是实打实的手算结果，所以我们需要做的无非就是把竖式乘法计算（也可以用秦九韶算法）的内容用代码实现，在算出小数位数插入小数点即可。

初步搞定输出结果之后（满足Sample Output），首次提交出现RE，OJ上提醒代码中的to_string部分无法编译，最后老老实实用老办法把数值转成字符。随之而来的是一次又一次的TLE——这让我开始重新审视做这种题是一个什么概念，我开始一遍一遍优化自己的代码，删除不必要的语句，控制循环的次数，精细的做下来之后才发现，第一次编码所呈现的代码无论看起来还是从逻辑上去分析，都是有很多冗余的。优化是一个化繁为简的过程，同样也是让整体思路越来越清晰的过程，很多问题从接手开始都很容易往复杂的方面去想，但最后的道理往往非常简单，但越是这种简单，越不容易去提炼以至于能够一气呵成，所以这种化繁为简的能力非常体现功力，是需要通过不断的练习、总结经验来积淀的。

最后是这道题对于程序健壮性的要求简直变态，需要考虑到各种情况，一般人一次根本不可能考虑全，找到了这位大佬的帖子最后才从 WA变成 AC： http://poj.org/showmessage?message_id=76017。总之在开始运算之前需要先对底数进行预处理，对小数点左侧冗余的 0和右侧冗余的 0都处理掉，还要考虑到整数（例如10.0）参与运算的情况。

附上AC代码:

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

/* 竖式计算两个整数的乘积 */

string string_mutiple(string mutiplied, string mutipler){
   string res(mutipler.length() + mutiplied.length(), '0'); //初始化结果字符串
   for (int i = 0; i < mutipler.length(); i++) {
       int trans = 0;
       for (int j = 0; j < mutiplied.length(); j++) {
           trans = (mutiplied[j] - '0') * (mutipler[i] - '0') + (res[i + j] - '0') + trans / 10;
           res[i + j] = trans % 10 + '0';
           if (j == mutiplied.length() - 1) res[i + j + 1] = trans / 10 + '0';
       }
   }
   if (res.at(mutipler.length() + mutiplied.length() - 1) == '0')
       res.erase(mutipler.length() + mutiplied.length() - 1, 1);
   return res;
}

/* 利用快速幂计算 */

string expo(string mutipler, int time){
   if (time == 1) return mutipler;
   string res = "1", base = mutipler;
   while(time != 0) {
       if ((time & 1) != 0) res = string_mutiple(res, base); //判断幂数的最后一位是否为0
       base = string_mutiple(base, base);
       time >>= 1;
   }
   return res;
}

int main(){
   string base, result;
   int time, pos, len;
   while (cin>>base>>time) {
       if (time == 0) cout << "1" << endl; //处理次数为0的情况
       else {
           int j = 0; //游标
           pos = base.find('.'); //寻找小数点位置
           
           /* 处理小数点之前多余的0 */
           while (j != pos) {
               if (base[j] == '0') base.erase(j, 1);
               else break;
           }
           
           /* 处理小数点末尾多余的0 */
           reverse(base.begin(), base.end());
           bool zero = true;
           for (int a = 0; zero; a++) {
               if(base[0] == '0') base.erase(0, 1);
               else zero = false;
           }
           if (base[0] == '.') zero = true;

           pos = base.find('.'); //重新计算小数点位置
           base.erase(pos, 1); //去除小数点
           result = expo(base, time); //初步计算结果，倒序存放在result字符串中
           
           /* 处理关于0的问题 */
           len = pos * time;
           if (len >= result.length()) {
               int added = len - result.length();
               for (int i = 0;i < added;i++) result = result + '0';
               result = result + '.';
           }
           else result.insert(len, 1, '.'); //插入小数点
           if (zero) result.erase(0, 1);
           reverse(result.begin(), result.end());
           cout << result << endl;
       }
   }
   return 0;
}