P1473 零的数列 Zero Sum

admin

https://www.luogu.org/problemnew/show/P1473

题目描述
请考虑一个由1到N（N=3, 4, 5 ... 9）的数字组成的递增数列：1 2 3 ... N。 现在请在数列中插入“+”表示加，或者“-”表示减，“ ”表示空白(例如1-2 3就等于1-23)，来将每一对数字组合在一起（请不要在第一个数字前插入符号）。 计算该表达式的结果并判断其值是否为0。 请你写一个程序找出所有产生和为零的长度为N的数列。

输入输出格式
输入格式：
单独的一行表示整数N (3 <= N <= 9)。

输出格式：
按照ASCII码的顺序，输出所有在每对数字间插入“+”, “-”, 或 “ ”后能得到结果为零的数列。

输入输出样例
输入样例#1：
7
输出样例#1：
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
说明
翻译来自NOCOW

USACO 2.3

张笑宇

思路:在1前面加一个”+“

1. #include<iostream>
   
2. using namespace std;
   
3. int n,f[10];///f为每个空填的字符
   
4. string s[4];///1是“ ” 2是“+” 3是“-”
   
5. void pp()
   
6. {
   
7.     for (int i=2; i<=n; i++)
   
8.         cout<<i-1<<s[f[i]];
   
9.     cout<<n<<endl;
   
10. }
    
11. bool check()
    
12. {
    
13.     int s,sum=0,bb=1;
    
14.     for (int i=1; i<=n; i++)
    
15.     {
    
16.         if (f[i]==1) continue;///' '就跳过
    
17.         s=i;
    
18.         for (int j=i+1; j<=n; j++)
    
19.         {
    
20.             if (f[j]!=1) break;
    
21.             s=10*s+j;
    
22.         }
    
23.         if (f[i]==2) sum=sum+s,bb=0;
    
24.         else sum=sum-s,bb=0;
    
25.     }
    
26.     if (sum==0&&bb==0) return true;
    
27.     else return false;
    
28. }
    
29. void dfs(int x)///搜索到第x个空
    
30. {
    
31.     if (x==n+1)///一共(n-1)个空 1前加了一个+
    
32.     {
    
33.         if (check()) pp();
    
34.     }
    
35.     else for (int i=1; i<=3; i++)
    
36.         {
    
37.             f[x]=i;
    
38.             dfs(x+1);
    
39.             f[x]=0;
    
40.         }
    
41. }
    
42. int main()
    
43. {
    
44.     cin>>n;
    
45.     s[1]=' ',s[2]='+',s[3]='-';
    
46.     f[1]=2;///在1前加一个‘+’
    
47.     dfs(2);///从第二个开始找
    
48.     return 0;
    
49. }
    

复制代码

YTC

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. int n;
   
4. char c[15];
   
5. int sum;
   
6. void dfs(int k,int ans,int p)//1+ 2-
   
7. {
   
8.     if(k==n)
   
9.     {
   
10.         if(p==1)  sum+=ans;
    
11.         if(p==2)  sum-=ans;
    
12.         //cout<<sum<<endl;
    
13.         if(sum==0)
    
14.             {for(int i=1;i<n;i++) cout<<i<<c[i];
    
15.         cout<<n<<endl;}
    
16.         if(p==1)  sum-=ans;
    
17.         if(p==2)  sum+=ans;
    
18.         return;
    
19.     }
    
20.     else
    
21.     {
    
22.     if(p==1) {
    
23.         c[k]=' ';
    
24.         dfs(k+1,ans*10+k+1,1);
    
25.         sum+=ans;
    
26.         c[k]='+';
    
27.         dfs(k+1,k+1,1);
    
28.         c[k]='-';
    
29.         dfs(k+1,k+1,2);
    
30.         sum-=ans;
    
31.     }
    
32.     if(p==2)
    
33.     {
    
34.         c[k]=' ';
    
35.         dfs(k+1,ans*10+k+1,2);
    
36.         sum-=ans;
    
37.         c[k]='+';
    
38.         dfs(k+1,k+1,1);
    
39.         c[k]='-';
    
40.         dfs(k+1,k+1,2);
    
41.         sum+=ans;
    
42.     }
    
43.     }
    
44. }
    
45. int main()
    
46. {
    
47.     cin>>n;
    
48.     dfs(1,1,1);
    
49.     return 0;
    
50. }
    

复制代码