P1473 零的数列 Zero Sum网页链接P1473 零的数列 Zero Sum题目描述请考虑一个由1 11到N NN的数字组成的递增数列1 , 2 , 3 , … , N 1, 2, 3, \ldots, N1,2,3,…,N。现在请在数列中插入表示加或者-表示减空格 表示空白例如1-2 3就等于1-23来将每一对数字组合在一起请不要在第一个数字前插入符号。计算该表达式的结果并判断其值是否为0 00。 请你写一个程序找出所有产生和为零的长度为N的数列。输入格式单独的一行表示整数N NN3 ≤ N ≤ 9 3 \leq N \leq 93≤N≤9。输出格式按照 ASCI I码的顺序输出所有在每对数字间插入-空格 后能得到结果为零的数列。输入输出样例 #1输入 #17输出 #112-34-5-67 12-3-456-7 1-2 34567 1-2 3-4 56 7 1-234-56-7 1-2-3-4-567说明/提示翻译来自NOCOWUSACO 2.3解题思路·本题是DFS全枚举 表达式求值的暴力搜索题利用N ≤ 9 N \le 9N≤9的小规模特性递归枚举所有符号插入方案逐一计算表达式结果按字典序筛选出值为0的合法序列。1. 枚举策略DFS生成所有符号组合1到N之间共有N − 1 N-1N−1个间隔每个间隔可插入空格、、-三种符号总共有3 N − 1 3^{N-1}3N−1种组合。N9时仅6561种情况完全可以暴力枚举。为了满足ASCII升序的输出要求按空格 → → -的顺序递归尝试每个位置的符号空格ASCII码32 43 -45生成的表达式天然符合字典序无需额外排序。2. 表达式求值逻辑由于空格会将相邻数字拼接为多位数求值时需特殊处理维护总和x、当前累积数字y、上一个运算符p初始为隐式的。遍历表达式字符串遇到空格直接跳过不参与运算。遇到数字则累加到当前数y y * 10 当前数字。遇到或-时根据上一个运算符将当前数y合并到总和x中随后重置y并更新运算符。遍历结束后将最后一个数字按运算符合并到总和判断总和是否为0。3. 递归边界与输出当递归处理完所有间隔到达第N个数字时对当前表达式执行求值若结果为0则直接输出。由于枚举顺序严格遵循ASCII升序输出顺序天然符合题目要求。算法总时间复杂度为O ( N ⋅ 3 N ) O(N \cdot 3^N)O(N⋅3N)N9时运算量极小远低于时间限制。总结核心逻辑通过DFS按字典序枚举所有符号插入方案对每个表达式跳过空格拼接数字、逐运算符计算总和筛选出结果为0的序列直接输出。关键操作三分支DFS枚举、空格数字拼接求值、按ASCII顺序枚举保证输出有序。效率保障N≤9时总组合数仅数千级暴力枚举无任何性能压力。代码简要说明chk求值函数接收表达式字符串通过一次遍历计算表达式值。跳过空格累积连续数字遇到运算符时按前序符号合并到总和最终判断结果是否为0。dfs递归函数参数k表示当前处理第k个间隔s为当前表达式字符串。递归边界k n时所有间隔处理完毕调用chk校验合法则输出。递归分支先保持当前空格符号递归再将该位置改为递归最后改为-递归保证枚举顺序符合ASCII升序。字符串初始化初始构造每个数字后带空格的字符串再删除末尾多余空格使所有间隔初始为空格状态作为DFS的起点。主函数逻辑读入整数n构造初始字符串启动DFS枚举所有方案。输入优化关闭流同步并解绑tie提升输入输出效率。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll n;boolchk(string s){charp;ll l(ll)s.size();ll x0,y0;for(ll i0;il;i){if(s[i] )continue;if(s[i]0s[i]9)yy*10(ll)(s[i]-0);if(s[i]){if(p)xxy;if(p-)xx-y;y0;p;}if(s[i]-){if(p)xxy;if(p-)xx-y;y0;p-;}}if(p)xxy;if(p-)xx-y;if(x0)returntrue;returnfalse;}voiddfs(ll k,string s){if(kn){if(chk(s))coutsendl;return;}ll p2*k-1;dfs(k1,s);s[p];dfs(k1,s);s[p]-;dfs(k1,s);}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinn;string s;for(ll i1;in;i)ss(char)(i0) ;s.erase(2*n-1,1);dfs(1,s);return0;}