首页 > 代码库 > 洛谷P1473 零的数列 Zero Sum

洛谷P1473 零的数列 Zero Sum

2024-08-15 14:35:37   214人阅读

P1473 零的数列 Zero Sum

    • 134通过
    • 170提交
  • 题目提供者该用户不存在
  • 标签USACO
  • 难度普及/提高-

  讨论  题解  

最新讨论

  • 路过的一定帮我看错了我死了…

题目描述

请考虑一个由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+71+2-3-4+5+6-71-2 3+4+5+6+71-2 3-4 5+6 71-2+3+4-5+6-71-2-3-4-5+6+7

说明

翻译来自NOCOW

USACO 2.3

分析：数据很小，似乎不管怎么样做都可以过，甚至可以打表......很显然，可以爆搜，因为数字都是确定了，那么只需要搜索运算符和空格,空格的处理有些麻烦，模拟一下就能知道规律.

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;int n,ans;char c[9];void dfs(int step, int num, int id){    if (step == n)    {        int temp = ans;        if (id == 1)            temp += num;        else            temp -= num;        if (temp == 0)        {            for (int i = 1; i < n; i++)                printf("%d%c", i, c[i]);            printf("%d\n", n);        }        return;    }    c[step] = ‘ ‘;    if (id == 1)        dfs(step + 1, num * 10 + step + 1, 1);    else        dfs(step + 1, num * 10 + step + 1, 2);    c[step] = ‘+‘;    if (id == 1)    {        ans += num;        dfs(step + 1,step + 1, 1);        ans -= num;    }    else    {        ans -= num;        dfs(step + 1, step + 1, 1);        ans += num;    }    c[step] = ‘-‘;    if (id == 2)    {        ans -= num;        dfs(step + 1, step + 1, 2);        ans += num;    }    else    {        ans += num;        dfs(step + 1, step + 1, 2);        ans -= num;    }    return;}int main(){    scanf("%d", &n);    dfs(1, 1, 1);    //while (1);    return 0;}

 

洛谷P1473 零的数列 Zero Sum


联系
我们