USACO2.3.3Zero Sum

Zero Sum

Consider the sequence of digits from 1 through N (where N=9) in increasing order: 1 2 3 ... N.

Now insert either a `+' for addition or a `-' for subtraction or a ` ' [blank] to run the digits together between each pair of digits (not in front of the first digit). Calculate the result that of the expression and see if you get zero.

Write a program that will find all sequences of length N that produce a zero sum.

PROGRAM NAME: zerosum

INPUT FORMAT

A single line with the integer N (3 <= N <= 9).

SAMPLE INPUT (file zerosum.in)

OUTPUT FORMAT

In ASCII order, show each sequence that can create 0 sum with a `+', `-', or ` ' between each pair of numbers.

SAMPLE OUTPUT (file zerosum.out)

1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2 3+4+5+6+7
1-2 3-4 5+6 7
1-2+3+4-5+6-7
1-2-3-4-5+6+7
题解：先对每个数字之间添加'+'或者'-'或者空格。这个可以用深搜实现。然后再对表达式求值，如果表达式的和为零，那么就是符合要求的，输出即可。
丑陋的代码o(╯□╰)o

View Code

  1 /*
  2 ID:spcjv51
  3 PROG:zerosum
  4 LANG:C
  5 */
  6 #include<stdio.h>
  7 #include<string.h>
  8 int n;
  9 char ss[50];
 10 void print()
 11 {
 12     char s[50];
 13     int i,len,lr,j,ans;
 14     ans=0;
 15     strcpy(s,ss);
 16     len=strlen(s);
 17     i=1;
 18     lr=1;
 19     if(s[i]==' ')
 20         {
 21             lr=lr*10+s[i+1]-'0';
 22             j=i+2;
 23             while(s[j]==' ')
 24             {
 25                 lr=lr*10+s[j+1]-'0';
 26                 j+=2;
 27 
 28             }
 29             i=j;
 30         }
 31     ans+=lr;
 32 
 33     while(i<len)
 34     {
 35 
 36 
 37         if(s[i]=='-')
 38         {
 39             j=i+2;
 40             lr=s[i+1]-'0';
 41             while(s[j]==' ')
 42             {
 43                 lr=lr*10+s[j+1]-'0';
 44                 j+=2;
 45 
 46             }
 47             i=j;
 48             ans-=lr;
 49 
 50         }
 51         if(s[i]=='+')
 52         {
 53             j=i+2;
 54             lr=s[i+1]-'0';
 55             while(s[j]==' ')
 56             {
 57                 lr=lr*10+s[j+1]-'0';
 58                 j+=2;
 59 
 60             }
 61             i=j;
 62             ans+=lr;
 63         }
 64 
 65     }
 66     if(ans==0)
 67     printf("%s\n",ss);
 68 }
 69 void dfs(int step,int last)
 70 {
 71     char str[3],ssr[50];
 72     if(step==n)
 73     {
 74         print();
 75         return;
 76     }
 77     sprintf(str,"%d",step+1);
 78     last=last*10+step+1;
 79     strcpy(ssr,ss);
 80     strcat(ss," ");
 81     strcat(ss,str);
 82     dfs(step+1,last);
 83     strcpy(ss,ssr);
 84     strcat(ss,"+");
 85     strcat(ss,str);
 86     last=step+1;
 87     dfs(step+1,last);
 88     strcpy(ss,ssr);
 89     strcat(ss,"-");
 90     strcat(ss,str);
 91     last=-(step+1);
 92     dfs(step+1,last);
 93     strcpy(ss,ssr);
 94 }
 95 
 96 int main(void)
 97 {
 98     freopen("zerosum.in","r",stdin);
 99     freopen("zerosum.out","w",stdout);
100     scanf("%d",&n);
101     strcpy(ss,"1");
102     dfs(1,1);
103     return 0;
104 }