当前位置：首页 > news >正文

P1473 [USACO2.3] 零的数列 Zero Sum(DFS 回溯 + 状态维护+ 空格合并数字)

news 2026/6/6 6:33:01

题目描述

请考虑一个由 1 到 N 的数字组成的递增数列：1,2,3,…,N。

现在请在数列中插入 + 表示加，或者 - 表示减，（空格）表示空白（例如 1-2 3 就等于 1-23），来将每一对数字组合在一起（请不要在第一个数字前插入符号）。

计算该表达式的结果并判断其值是否为 0。请你写一个程序找出所有产生和为零的长度为N的数列。

输入格式

单独的一行表示整数 N（3≤N≤9）。

输出格式

按照 ASCI I码的顺序，输出所有在每对数字间插入 +，-，（空格）后能得到结果为零的数列。

输入输出样例

输入 #1复制运行

输出 #1复制运行

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

说明/提示

翻译来自NOCOW

USACO 2.3

// 考点：DFS 回溯 + 状态维护（current_val/last_num/op）+ 空格合并数字#include<bits/stdc++.h>
using namespace std;// 存储所有结果为0的合法表达式
vector<string> result;
// 存储当前拼接的表达式路径（直接用string）
string path;
// 题目输入的N（保持long long，贴合你的变量类型）
long long N;// DFS枚举符号并计算表达式
// pos：当前处理到的数字（1~N）
// current_val：当前表达式计算结果
// last_num：上一个参与运算的数（处理空格合并用）
// op：上一个符号类型（0=初始/空格，1=+，2=-）
void dfs(long long pos, long long current_val, long long last_num, int op) {// 递归终止：处理完所有数字，结果为0则存入resultif (pos > N) {if (current_val == 0) {result.push_back(path);}return;}// 处理第一个数字（无前置符号）if (pos == 1) {path += to_string(pos); // 将数列中的数转换为字符后拼接数字dfs(pos + 1, pos, pos, 0);path.pop_back(); // 回溯return;}// 按ASCII顺序遍历3种符号：空格 → + → -（直接分支判断，无多余数组）// 1. 处理空格int len = path.size();path += ' ';path += to_string(pos);long long new_last = last_num * 10 + pos;if (op == 1) {dfs(pos + 1, current_val - last_num + new_last, new_last, op);} else if (op == 2) {dfs(pos + 1, current_val + last_num - new_last, new_last, op);} else {dfs(pos + 1, new_last, new_last, op);}path.erase(len); // 回溯// 2. 处理+len = path.size();path += '+';path += to_string(pos);dfs(pos + 1, current_val + pos, pos, 1);path.erase(len); // 回溯// 3. 处理-len = path.size();path += '-';path += to_string(pos);dfs(pos + 1, current_val - pos, pos, 2);path.erase(len); // 回溯
}int main(void) {cin >> N;// 初始调用：pos=1，初始值0，上一个数0，初始符号0dfs(1, 0, 0, 0);// 输出所有合法表达式（已按ASCII顺序存储）for (string expr : result) {cout << expr << endl;}return 0;
}