USACO 2.3 Zero Sum 题解

xiaoxiao2021-02-28  114

Zero Sum

DESCRIPTION

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)

7

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

THOUGHTS:

注意n<=9,对于如此小的数据范围,我们第一反应便是暴力(DFS),复杂度3^n,完全可以通过。 所以这道题非常简单,只需要Dfs到最后判定一下是否式子的结果为0即可。 至于字典序输出,我们观察样例,可以发现’ ’ < ‘+’ < ‘-‘,那么只需要分别让012代表’ ‘, ‘+’, ‘-‘即可。

DIFFICULTIES: pj-

AC PROGRAM:

/* ID: kongse_1 PROG: zerosum LANG: C++ */ // Skq_Liao #include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for (register int i = (a), i##_end_ = (b); i < i##_end_; ++i) #define ROF(i, a, b) for (register int i = (a), i##_end_ = (b); i > i##_end_; --i) #define debug(...) fprintf(stderr, __VA_ARGS__) const char Fin[] = "zerosum.in"; const char Fout[] = "zerosum.out"; void In() { freopen(Fin, "r", stdin); freopen(Fout, "w", stdout); return ; } const int MAXN = 15; int n; int A[MAXN]; int B[MAXN]; void Print() { FOR(i, 1, n) { printf("%d", i); switch (A[i]) { case 0: printf(" "); break; case 1: printf("+"); break; default: printf("-"); } } printf("%d\n", n); return ; } void Check() { int last(1), num(0), ans(0); memset(B, 0, sizeof B); A[n] = 1; FOR(i, 1, n + 1) { B[num] = B[num] * 10 + i; if(A[i]) { if(last == 2) B[num] = -B[num]; last = A[i]; ++num; } } FOR(i, 0, num) ans += B[i]; if(!ans) Print(); return ; } void Dfs(int cur) { if(cur == n) Check(); else { FOR(i, 0, 3) { A[cur] = i; Dfs(cur + 1); } } return ; } int main() { In(); scanf("%d", &n); Dfs(1); return 0; }

Skq_Liao 2017/07/11 9:40 于 AB213

转载请注明原文地址: https://www.6miu.com/read-52399.html

最新回复(0)