题目1498：寻找表达式

缺乏、安全感 2022-01-12 11:53 164阅读 0赞

题目1498：寻找表达式

**时间限制：**1 秒

**内存限制：**128 兆

**特殊判题：**否

**题目描述：**

现在有一个序列123......N，其中N介于3和15之间，要求在序列之间加入+、-或者空格，使得该序列组成的数学表达式的运算结果为0。

**输入：**

输入可能包含多个测试样例。 对于每个测试案例，输入整数N(3<=N<=15)，代表这个序列的长度。

**输出：**

对应每个测试案例，输出所有使得表达式结果为0的组合，当有多个组合时，按字典序进行排序输出。

**样例输入：**

3
    6

**样例输出：**

1+2-3
    1 2+3-4-5-6

**提示：**

1\_2+3-4-5-6相当于12+3-4-5-6(‘\_’代表空格)

**来源：**

[*微策略2013年校园招聘笔试题* ][2013_]

思路：暴力，可以比较其他写法。

#include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <string>
    #include <map>
    #include <vector>
    #include <set>
    #include <algorithm>
    #include <vector>
    #include <stack>
    #include <math.h>
    #include <stdlib.h>
    #define Max(a,b) ((a)>(b)?(a):(b))
    #define Min(a,b) ((a)<(b)?(a):(b))
    using namespace std;
    typedef long long LL ;
    const int size=18 ;
    struct Me{
        int N ;
        int choose[size] ;
        Me(){} ;
        Me(int n):N(n){};
        LL ans(){
            // 1 ' '
            // 2 '+'
            // 3 '-'
             LL sum ,now ;
             int type=2 ;
             sum=0 ;
             now=1 ;
             choose[N]=2 ;
             for(int i=1;i<=N;i++){
                if(choose[i]==2||choose[i]==3){
                    if(type==2)
                        sum+=now ;
                    else
                        sum-=now ;
                    type=choose[i] ;
                    now=i+1 ;
                }
                else{
                    if(i+1<=9)
                      now=now*10+i+1 ;
                    else
                      now=now*100+i+1 ;
                }
             }
             return sum ;
        }
        void dfs(int id){
           if(id==N){
             if(ans()==0){
                 printf("%d",1) ;
                 for(int i=1;i<N;i++){
                    if(choose[i]==1)
                        putchar(' ') ;
                    else if(choose[i]==2)
                        putchar('+') ;
                    else
                        putchar('-') ;
                    printf("%d",i+1) ;
                 }
                 puts("") ;
              }
              return  ;
           }
           for(int i=1;i<=3;i++){
              choose[id]=i ;
              dfs(id+1) ;
           }
        }
    };
    int main(){
       int n ;
       while(scanf("%d",&n)!=EOF){
          Me me(n) ;
          me.dfs(1) ;
       }
       return 0 ;
    }

转载于:https://www.cnblogs.com/liyangtianmen/p/3301032.html

[2013_]: http://ac.jobdu.com/problemset.php?search=%E5%BE%AE%E7%AD%96%E7%95%A52013%E5%B9%B4%E6%A0%A1%E5%9B%AD%E6%8B%9B%E8%81%98%E7%AC%94%E8%AF%95%E9%A2%98