USACO 2.3.3: Zero Sum(暴搜)


题意

洛谷 P1473 零的数列 Zero Sum

对于数列1 2 3 ... N3 <= N <= 9),在除了1之外的每个数前面插入+-,如果得到的和为0,就把这个数列输出。

分析

这道题明摆着是要直接搜索。搜索空间总共只有3^8 = 6561,所以应该还挺快的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/*
ID: zhanghu15
TASK: zerosum
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long int LL;

ofstream fout("zerosum.out");
ifstream fin("zerosum.in");

int N;
char signs[10];

void dfs(int depth) {
if (depth == N - 1) {
LL sum = 0, cur = 1;
int s = 1; // sign
for (int i = 0; i < depth; i++) {
if (signs[i] == ' ') cur = cur * 10 + (i + 2);
else if (signs[i] == '+') {
sum += cur * s;
s = 1;
cur = i + 2;
}
else {
sum += cur * s;
s = -1;
cur = i + 2;
}
}
sum += cur * s;
if (sum == 0) {
fout << 1;
for (int i = 0; i < depth; i++)
fout << signs[i] << (i + 2);
fout << endl;
}
return;
}
signs[depth] = ' ';
dfs(depth + 1);
signs[depth] = '+';
dfs(depth + 1);
signs[depth] = '-';
dfs(depth + 1);
}

int main() {
fin >> N;
dfs(0);
return 0;
}

 评论