P1010 [NOIP1998 普及组] 幂次方 题解

题目描述

任何一个正整数都可以用 2 的幂次方表示。例如 137 = 2 7 + 2 3 + 2 0 。 137=2^7+2^3+2^0。 137=27+23+20。

同时约定方次用括号来表示，即 a b a^b ab 可表示为 a ( b ) a(b) a(b)。

由此可知，137 可表示为 2(7)+2(3)+2(0)

进一步：

7 = 2 2 + 2 + 2 0 7= 2^2+2+2^0 7=22+2+20 ( 2 1 2^1 21 用 2 表示)，并且 3 = 2 + 2 0 3=2+2^0 3=2+20。

所以最后 137 可表示为 2(2(2)+2+2(0))+2(2+2(0))+2(0)2(2(2)+2+2(0))+2(2+2(0))+2(0)。

又如 1315 = 2 10 + 2 8 + 2 5 + 2 + 1 1315=2^{10} +2^8 +2^5 +2+1 1315=210+28+25+2+1

所以 1315 最后可表示为 2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)。

输入格式

一行一个正整数 n。

输出格式

符合约定的 n 的 0, 2 表示（在表示中不能有空格）。

输入输出样例

输入 #1复制

1315

输出 #1复制

2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

说明/提示

【数据范围】

对于 100% 的数据， 1 ≤ n ≤ 2 × 10 4 1 \le n \le 2 \times {10}^4 1≤n≤2×104。

题解思路：

记得这道题当初是做过的，好像是准备蓝桥杯的期间做的，由于当时的基础很薄弱，c++只学会了基本语法，所以是用纯模拟来做的。

现在又在洛谷上跳题跳到这个上了，一看题：2的n次方balabala，就想到了二进制，所以这次就用位运算来做。

这是道入门递归的好题，同时也是入门位运算的好题。

步骤如下：

1.对输入数字的二进制数逐位扫描，若为1则记录下当前的位数，因为若二进制下当前位为1的话，是可以用2的位数次方来表示的。

2.对录入的位数反序扫描（步骤1是从低位到高位记录的位数，而要保证为高位到低位输出，所以要反序），然后处理三种情况：

（一）位数为0，实际输出格式为 2(0)

（二）位数为1，实际输出格式为 2

（三）位数为其他，则按题目要求转化为（一）（二）的情况，即对该位数进行同样的拆解，实际操作上就是再调用该处理函数进行处理（即递归）。

这样就顺利解决了。

最后附上代码:

#include<bits/stdc++.h>//STL的催肥机
using namespace std;

#define ll long long
#define INF 0x3f3f3f3f

void produce(int n){
    vector<int> bit;//用于存储位数
    int i = 0;
    while(n > 0){//对数字进行位移扫描，如果为1则存储位数
        if(n & 1) bit.emplace_back(i);//n & 1表示，n的第一位如果，是1则会返回1，为0则会返回0
        n >>= 1;//向右位移一位
        i++;
    }
    //输出
    for(i = bit.size() - 1;i >= 0;i--){
        if(bit[i] != 1){//如果位数不为一
            cout << "2(";
            if(bit[i] == 0) cout << "0";     //如果位数为零，则输出格式 2(0)
            else produce(bit[i]);//其他位数则继续调用produce转化为位数为零或者一为止
            cout << ")";
        }
        else cout << "2";//如果为一，则输出格式 2
        cout << (i == 0 ? "" : "+");
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    produce(n);

    return 0;
}