综合
1S
100Kb
给定一个表示序列长度的整数 n n n ( 3 ≤ n ≤ 9 3\le n\le 9 3≤n≤9)。在序列 1 2 3 … n 1\ 2\ 3\dots n 123…n 中插入 ' ' ，'-' ，' ' 结构表达式，插入 ' ' 例如，前后两个数字构成一个整数 1 2-3-4-5 = 0 。
在输出结构的所有表达式中，结果是 0 0 0 例如，表达式的数量， n = 3 n=3 n=3 只有表达式 1 2-3=0 ，输出结果为 1 1 1 。
输入数据是一个整数 n n n ( n < 10 n<10 n<10)，表示序列长度，同时表示输入序列为 1 2 3 … n 1\ 2\ 3\dots n 123…
对于每一组数据，输出一个整数，表示构造的表达式中结果为 0 0 0 的表达式数量。
3
1
解法 DFS+模拟
经典类型的DFS题目：
#include <bits/stdc++.h>
using namespace std;
int n, cnt = 0; // count计数结果为0的所有表达式
int a[9] = {
1, 2, 3, 4, 5, 6, 7, 8, 9};
/* idx 0 1 2 3 4 5 6 7 8 ** a 1 2 3 4 5 6 7 8 9 ** b 1 b[1] b[2] b[3] b[4] b[5] b[6] b[7] b[8] ** b = ops */
int ops[10] = {
0}; // 记录命令 b[i]记录i+1和i+2之间空格的命令,即a[i-1]和a[i]之间空格的命令
void dfs(int space, int op) {
// space记录在哪一空格之间插入命令
ops[space] = op; // 记录每个空格中的命令选择
if (space == n - 1) {
// 例如,4个数字1 2 3 4,最多有3个格子
int sum = 0; // 记录表达式的最终结果
for (int j = 0; j <= space; ) {
// j遍历命令数组ops[]
int tmp = a[j], op = ops[j++]; // op记录此处的命令
for (; ops[j] == 3; ++j) tmp = tmp * 10 + a[j];
if (op == 1) sum += tmp; // 加法,表示a[...:i-1]前面的数加上a[j:...]的数
else if (op == 2) sum -= tmp; // 减法,表示a[...:i-1]前面的数减去a[j:...]的数
}
// cout << sum << endl;
if (sum == 0) ++cnt;
return;
}
for (int i = 1; i <= 3; ++i) dfs(space + 1, i); // 命令1: +, 2: -, 3: ' '
}
int main() {
cin >> n;
dfs(0, 1); // b[0]命令为1,即加法
cout << cnt;
return 0;
}
