P1473 [USACO2.3] 零的数列 Zero Sum

题目描述

请考虑一个由 $1$ 到 $N$ 的数字组成的递增数列：$1,2,3,\dots ,N$。

现在请在数列中插入 + 表示加，或者 - 表示减， （空格） 表示空白（例如 1-2 3 就等于 1-23），来将每一对数字组合在一起（请不要在第一个数字前插入符号）。

计算该表达式的结果并判断其值是否为 $0$。 请你写一个程序找出所有产生和为零的长度为N的数列。

输入格式

单独的一行表示整数 $N$（$3\le N\le 9$）。

输出格式

按照 ASCI I码的顺序，输出所有在每对数字间插入 +，-， （空格） 后能得到结果为零的数列。

输入输出样例 #1

输入 #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

C++实现

#include<bits/stdc++.h>//john.c_Tae Yeon
#define sea 1000500
using namespace std;
int n,sz[20],ss;
char symbol[20];
void sear(int k,int s,int q,char c){
if(kn){
if(c’+‘){
s=s+q;
}
else{
s=s-q;
}
if(s0){
ss++;
cout<<“1”;
for(int i=1;i<n;i++){
cout<<symbol[i]<<sz[i];
}
cout<<" "<<ss<<endl;
}
}
else{
symbol[k]=’ ‘;
sear(k+1,s,q*10+sz[k],c);
symbol[k]=’+';
if(c’+‘){
sear(k+1,s+q,sz[k],’+‘);
}
else{
sear(k+1,s-q,sz[k],’+‘);
}
symbol[k]=’-‘;
if(c==’+‘){
sear(k+1,s+q,sz[k],’-‘);
}
else{
sear(k+1,s-q,sz[k],’-‘);
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
sz[i]=i+1;
}
sear(1,0,1,’+');
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容