题解 P1010 【幂次方】
Sweetlemon
2016-12-09 23:50:06
应当注意到,这题数据很小(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;
}
```