题解 P1010 【幂次方】

Sweetlemon

2016-12-09 23:50:06

Solution

应当注意到,这题数据很小(n<=20000)!由14<log(2) 20000<15得,我们只要把2的0到14次方用“零二表示法”表示出来,再根据这个数的二进制输出相应的位就好啦!20行AC,靠的就是这种奇怪的方法…… 当然,还是希望大家能练习更好、更通用的方法,这只是作为一个“思维拓展”啦! 下面上代码: ```cpp #include <iostream> #include <string> using namespace std; int main(void){ int n; int i; bool first=true; string t[15]={"2(0)","2","2(2)","2(2+2(0))","2(2(2))","2(2(2)+2(0))","2(2(2)+2)", "2(2(2)+2+2(0))","2(2(2+2(0)))","2(2(2+2(0))+2(0))","2(2(2+2(0))+2)", "2(2(2+2(0))+2+2(0))","2(2(2+2(0))+2(2))","2(2(2+2(0))+2(2)+2(0))", "2(2(2+2(0))+2(2)+2)"};//此为“零二表示法”的表 cin >> n; for (i=14;i>=0;i--){ //由于这题要求降幂排列,因此从高位到低位迭代 if ((n>>i)&1){ //意思是“如果n的二进制形式从右往左数第i位是1”,不理解的同学请补习位运算 cout << (first? (first=false,"") :"+"); //如果不是第一项,就输出"+"号 cout << t[i]; } } return 0; } ```