AcWing 1370. 零和序列
原题链接
简单
作者:
Lacy
,
2024-09-26 17:29:42
,
所有人可见
,
阅读 1
#include<iostream>
using namespace std;
// oprea[i] 存储数i与i+1之间的操作
// 存储1表示"+",2表示"-",3表示" "
int opera[10];
int n;
int get_num(int x)
{
int tmp=x;
//得到第x次操作下的数值
//如果oprea[x]为3则开始合并操作, 直至遇到下一次操作不为3
while(opera[x]==3)
{
tmp=tmp*10+x+1;
x++;
}
return tmp;
}
void print()
{
printf("1");
for(int i=1;i<n;i++)
{
if(opera[i]==1)
printf("+");
else if(opera[i]==2)
printf("-");
else printf(" ");
printf("%d",i+1);
}
cout<<endl;
}
void dfs(int cnt)
{
//递归终止条件
if(cnt==n)
{
// s定义为前i项和, 初始s = a[1] = get_num(1)
int s=get_num(1);
for(int i=1;i<n;i++)
{
if(opera[i]==1)
s+=get_num(i+1);//得到需要加的数
else if(opera[i]==2)
s-=get_num(i+1);//得到需要减的数
}
if(s==0) print();//如果序列总和为0,则输出
return;
}
// 按字典序输出, 则以" "."+"."-"的顺序进行dfs
opera[cnt]=3;
dfs(cnt+1);
// 因为顺序执行,恢复现场会被二次覆盖,所以无需显示化恢复现场的过程
// oprea[x] = 0;
opera[cnt]=1;
dfs(cnt+1);
// oprea[x] = 0;
opera[cnt]=2;
dfs(cnt+1);
// oprea[x] = 0;
}
int main()
{
cin>>n;
// 从第一个操作数开始dfs
dfs(1);
return 0;
}