自动搬运

查看原文

来自洛谷，原作者为

	Luogu_916767 Florr.io

搬运于2025-08-24 23:08:47，当前版本为作者最后更新于2025-01-25 20:22:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

In Luogu

题目大意

多组数据，每组数据一个 $k$ 要求构造一个只包含 $\texttt{1},\texttt{+},\texttt{*},\texttt{(},\texttt{)}$ 的合法表达式，满足：

• 不存在两个相邻的 $1$；
• $1$ 的数量最多为 $100$；
• 表达式运算结果为 $k$。

思路分析

很容易想到用类似十进制转二进制的方法来构造。

若 $k$ 是奇数，则将 $k$ 变成 $(1+(1+1)*(\left \lfloor \frac{k}{2} \right \rfloor ))$ 的形式。

若 $k$ 是偶数，则将 $k$ 变成 $((1+1)*(\frac{k}{2}))$ 的形式。

按照这种方法，直到将 $k$ 变成 $1$ 为止。

这种方式构造的表达式中 $1$ 的个数大约为 $2 \times \log_{2}{k}$，针对题目的数据来说是绝对不会超过 $100$ 的，所以不用特判。

Code

#include<iostream>

using namespace std;

int t;
int n;
string ans;

void work(int n){
    if(n == 1){
        ans += "1";
        return ;
    }
    if(n % 2 == 0){
        ans += "((1+1)*";
        work(n/2);
        ans += ")";
    }else{
        ans += "(1+(1+1)*";
        work(n/2);
        ans += ")";
    }
}

int main(){
    cin>>t;
    while(t -- ){
        cin>>n;
        ans = "";
        work(n);
        cout<<ans<<"\n";
    }
}