P11605 题解

Luogu_916767 · 2025-01-25 20:22:53 · 题解

In Luogu

题目大意

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

• 不存在两个相邻的 1；
• 表达式运算结果为 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";
    }
}