A-幼儿数学 三叉树结构 DFS深搜题解

题目描述

Problem Description

给你一个只包含数字[0,9]的字符串。 你可以在字符之间加上’ + ‘或’ - '，使得字符串成为一个带加减法的式子。 例如对于“12345”，你可以将他变成"123+4-5”。 现在给你一个整数N，计算有多少种方法可以使式子的结果等于N。 你只能在两个相邻字符中选择最多一个符号。

Input

多组数据，每组数据给出数字串S和一个整数n，（ |S|tspan{fill:#000;stroke:none}#mermaid-svg-Sc1haK1OaY5G8HMC .loopText,#mermaid-svg-Sc1haK1OaY5G8HMC .loopText>tspan{fill:#000;stroke:none}#mermaid-svg-Sc1haK1OaY5G8HMC .loopLine{stroke-width:2px;stroke-dasharray:2, 2;stroke:#ccf;fill:#ccf}#mermaid-svg-Sc1haK1OaY5G8HMC .note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-Sc1haK1OaY5G8HMC .noteText,#mermaid-svg-Sc1haK1OaY5G8HMC .noteText>tspan{fill:#000;stroke:none}#mermaid-svg-Sc1haK1OaY5G8HMC .activation0{fill:#f4f4f4;stroke:#666}#mermaid-svg-Sc1haK1OaY5G8HMC .activation1{fill:#f4f4f4;stroke:#666}#mermaid-svg-Sc1haK1OaY5G8HMC .activation2{fill:#f4f4f4;stroke:#666}#mermaid-svg-Sc1haK1OaY5G8HMC .mermaid-main-font{font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Sc1haK1OaY5G8HMC .section{stroke:none;opacity:0.2}#mermaid-svg-Sc1haK1OaY5G8HMC .section0{fill:rgba(102,102,255,0.49)}#mermaid-svg-Sc1haK1OaY5G8HMC .section2{fill:#fff400}#mermaid-svg-Sc1haK1OaY5G8HMC .section1,#mermaid-svg-Sc1haK1OaY5G8HMC .section3{fill:#fff;opacity:0.2}#mermaid-svg-Sc1haK1OaY5G8HMC .sectionTitle0{fill:#333}#mermaid-svg-Sc1haK1OaY5G8HMC .sectionTitle1{fill:#333}#mermaid-svg-Sc1haK1OaY5G8HMC .sectionTitle2{fill:#333}#mermaid-svg-Sc1haK1OaY5G8HMC .sectionTitle3{fill:#333}#mermaid-svg-Sc1haK1OaY5G8HMC .sectionTitle{text-anchor:start;font-size:11px;text-height:14px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Sc1haK1OaY5G8HMC .grid .tick{stroke:#d3d3d3;opacity:0.8;shape-rendering:crispEdges}#mermaid-svg-Sc1haK1OaY5G8HMC .grid .tick text{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Sc1haK1OaY5G8HMC .grid path{stroke-width:0}#mermaid-svg-Sc1haK1OaY5G8HMC .today{fill:none;stroke:red;stroke-width:2px}#mermaid-svg-Sc1haK1OaY5G8HMC .task{stroke-width:2}#mermaid-svg-Sc1haK1OaY5G8HMC .taskText{text-anchor:middle;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Sc1haK1OaY5G8HMC .taskText:not([font-size]){font-size:11px}#mermaid-svg-Sc1haK1OaY5G8HMC .taskTextOutsideRight{fill:#000;text-anchor:start;font-size:11px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Sc1haK1OaY5G8HMC .taskTextOutsideLeft{fill:#000;text-anchor:end;font-size:11px}#mermaid-svg-Sc1haK1OaY5G8HMC .task.clickable{cursor:pointer}#mermaid-svg-Sc1haK1OaY5G8HMC .taskText.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-Sc1haK1OaY5G8HMC .taskTextOutsideLeft.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-Sc1haK1OaY5G8HMC .taskTextOutsideRight.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-Sc1haK1OaY5G8HMC .taskText0,#mermaid-svg-Sc1haK1OaY5G8HMC .taskText1,#mermaid-svg-Sc1haK1OaY5G8HMC .taskText2,#mermaid-svg-Sc1haK1OaY5G8HMC .taskText3{fill:#fff}#mermaid-svg-Sc1haK1OaY5G8HMC .task0,#mermaid-svg-Sc1haK1OaY5G8HMC .task1,#mermaid-svg-Sc1haK1OaY5G8HMC .task2,#mermaid-svg-Sc1haK1OaY5G8HMC .task3{fill:#8a90dd;stroke:#534fbc}#mermaid-svg-Sc1haK1OaY5G8HMC .taskTextOutside0,#mermaid-svg-Sc1haK1OaY5G8HMC .taskTextOutside2{fill:#000}#mermaid-svg-Sc1haK1OaY5G8HMC .taskTextOutside1,#mermaid-svg-Sc1haK1OaY5G8HMC .taskTextOutside3{fill:#000}#mermaid-svg-Sc1haK1OaY5G8HMC .active0,#mermaid-svg-Sc1haK1OaY5G8HMC .active1,#mermaid-svg-Sc1haK1OaY5G8HMC .active2,#mermaid-svg-Sc1haK1OaY5G8HMC .active3{fill:#bfc7ff;stroke:#534fbc}#mermaid-svg-Sc1haK1OaY5G8HMC .activeText0,#mermaid-svg-Sc1haK1OaY5G8HMC .activeText1,#mermaid-svg-Sc1haK1OaY5G8HMC .activeText2,#mermaid-svg-Sc1haK1OaY5G8HMC .activeText3{fill:#000 !important}#mermaid-svg-Sc1haK1OaY5G8HMC .done0,#mermaid-svg-Sc1haK1OaY5G8HMC .done1,#mermaid-svg-Sc1haK1OaY5G8HMC .done2,#mermaid-svg-Sc1haK1OaY5G8HMC .done3{stroke:grey;fill:#d3d3d3;stroke-width:2}#mermaid-svg-Sc1haK1OaY5G8HMC .doneText0,#mermaid-svg-Sc1haK1OaY5G8HMC .doneText1,#mermaid-svg-Sc1haK1OaY5G8HMC .doneText2,#mermaid-svg-Sc1haK1OaY5G8HMC .doneText3{fill:#000 !important}#mermaid-svg-Sc1haK1OaY5G8HMC .crit0,#mermaid-svg-Sc1haK1OaY5G8HMC .crit1,#mermaid-svg-Sc1haK1OaY5G8HMC .crit2,#mermaid-svg-Sc1haK1OaY5G8HMC .crit3{stroke:#f88;fill:red;stroke-width:2}#mermaid-svg-Sc1haK1OaY5G8HMC .activeCrit0,#mermaid-svg-Sc1haK1OaY5G8HMC .activeCrit1,#mermaid-svg-Sc1haK1OaY5G8HMC .activeCrit2,#mermaid-svg-Sc1haK1OaY5G8HMC .activeCrit3{stroke:#f88;fill:#bfc7ff;stroke-width:2}#mermaid-svg-Sc1haK1OaY5G8HMC .doneCrit0,#mermaid-svg-Sc1haK1OaY5G8HMC .doneCrit1,#mermaid-svg-Sc1haK1OaY5G8HMC .doneCrit2,#mermaid-svg-Sc1haK1OaY5G8HMC .doneCrit3{stroke:#f88;fill:#d3d3d3;stroke-width:2;cursor:pointer;shape-rendering:crispEdges}#mermaid-svg-Sc1haK1OaY5G8HMC .milestone{transform:rotate(45deg) scale(0.8, 0.8)}#mermaid-svg-Sc1haK1OaY5G8HMC .milestoneText{font-style:italic}#mermaid-svg-Sc1haK1OaY5G8HMC .doneCritText0,#mermaid-svg-Sc1haK1OaY5G8HMC .doneCritText1,#mermaid-svg-Sc1haK1OaY5G8HMC .doneCritText2,#mermaid-svg-Sc1haK1OaY5G8HMC .doneCritText3{fill:#000 !important}#mermaid-svg-Sc1haK1OaY5G8HMC .activeCritText0,#mermaid-svg-Sc1haK1OaY5G8HMC .activeCritText1,#mermaid-svg-Sc1haK1OaY5G8HMC .activeCritText2,#mermaid-svg-Sc1haK1OaY5G8HMC .activeCritText3{fill:#000 !important}#mermaid-svg-Sc1haK1OaY5G8HMC .titleText{text-anchor:middle;font-size:18px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Sc1haK1OaY5G8HMC g.classGroup text{fill:#9370db;stroke:none;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:10px}#mermaid-svg-Sc1haK1OaY5G8HMC g.classGroup text .title{font-weight:bolder}#mermaid-svg-Sc1haK1OaY5G8HMC g.clickable{cursor:pointer}#mermaid-svg-Sc1haK1OaY5G8HMC g.classGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-Sc1haK1OaY5G8HMC g.classGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-Sc1haK1OaY5G8HMC .classLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.5}#mermaid-svg-Sc1haK1OaY5G8HMC .classLabel .label{fill:#9370db;font-size:10px}#mermaid-svg-Sc1haK1OaY5G8HMC .relation{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-Sc1haK1OaY5G8HMC .dashed-line{stroke-dasharray:3}#mermaid-svg-Sc1haK1OaY5G8HMC #compositionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-Sc1haK1OaY5G8HMC #compositionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-Sc1haK1OaY5G8HMC #aggregationStart{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-Sc1haK1OaY5G8HMC #aggregationEnd{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-Sc1haK1OaY5G8HMC #dependencyStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-Sc1haK1OaY5G8HMC #dependencyEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-Sc1haK1OaY5G8HMC #extensionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-Sc1haK1OaY5G8HMC #extensionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-Sc1haK1OaY5G8HMC .commit-id,#mermaid-svg-Sc1haK1OaY5G8HMC .commit-msg,#mermaid-svg-Sc1haK1OaY5G8HMC .branch-label{fill:lightgrey;color:lightgrey;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Sc1haK1OaY5G8HMC .pieTitleText{text-anchor:middle;font-size:25px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Sc1haK1OaY5G8HMC .slice{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Sc1haK1OaY5G8HMC g.stateGroup text{fill:#9370db;stroke:none;font-size:10px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Sc1haK1OaY5G8HMC g.stateGroup text{fill:#9370db;fill:#333;stroke:none;font-size:10px}#mermaid-svg-Sc1haK1OaY5G8HMC g.statediagram-cluster .cluster-label text{fill:#333}#mermaid-svg-Sc1haK1OaY5G8HMC g.stateGroup .state-title{font-weight:bolder;fill:#000}#mermaid-svg-Sc1haK1OaY5G8HMC g.stateGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-Sc1haK1OaY5G8HMC g.stateGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-Sc1haK1OaY5G8HMC .transition{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-Sc1haK1OaY5G8HMC .stateGroup .composit{fill:white;border-bottom:1px}#mermaid-svg-Sc1haK1OaY5G8HMC .stateGroup .alt-composit{fill:#e0e0e0;border-bottom:1px}#mermaid-svg-Sc1haK1OaY5G8HMC .state-note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-Sc1haK1OaY5G8HMC .state-note text{fill:black;stroke:none;font-size:10px}#mermaid-svg-Sc1haK1OaY5G8HMC .stateLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.7}#mermaid-svg-Sc1haK1OaY5G8HMC .edgeLabel text{fill:#333}#mermaid-svg-Sc1haK1OaY5G8HMC .stateLabel text{fill:#000;font-size:10px;font-weight:bold;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Sc1haK1OaY5G8HMC .node circle.state-start{fill:black;stroke:black}#mermaid-svg-Sc1haK1OaY5G8HMC .node circle.state-end{fill:black;stroke:white;stroke-width:1.5}#mermaid-svg-Sc1haK1OaY5G8HMC #statediagram-barbEnd{fill:#9370db}#mermaid-svg-Sc1haK1OaY5G8HMC .statediagram-cluster rect{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-Sc1haK1OaY5G8HMC .statediagram-cluster rect.outer{rx:5px;ry:5px}#mermaid-svg-Sc1haK1OaY5G8HMC .statediagram-state .divider{stroke:#9370db}#mermaid-svg-Sc1haK1OaY5G8HMC .statediagram-state .title-state{rx:5px;ry:5px}#mermaid-svg-Sc1haK1OaY5G8HMC .statediagram-cluster.statediagram-cluster .inner{fill:white}#mermaid-svg-Sc1haK1OaY5G8HMC .statediagram-cluster.statediagram-cluster-alt .inner{fill:#e0e0e0}#mermaid-svg-Sc1haK1OaY5G8HMC .statediagram-cluster .inner{rx:0;ry:0}#mermaid-svg-Sc1haK1OaY5G8HMC .statediagram-state rect.basic{rx:5px;ry:5px}#mermaid-svg-Sc1haK1OaY5G8HMC .statediagram-state rect.divider{stroke-dasharray:10,10;fill:#efefef}#mermaid-svg-Sc1haK1OaY5G8HMC .note-edge{stroke-dasharray:5}#mermaid-svg-Sc1haK1OaY5G8HMC .statediagram-note rect{fill:#fff5ad;stroke:#aa3;stroke-width:1px;rx:0;ry:0}:root{--mermaid-font-family: '"trebuchet ms", verdana, arial';--mermaid-font-family: "Comic Sans MS", "Comic Sans", cursive}#mermaid-svg-Sc1haK1OaY5G8HMC .error-icon{fill:#522}#mermaid-svg-Sc1haK1OaY5G8HMC .error-text{fill:#522;stroke:#522}#mermaid-svg-Sc1haK1OaY5G8HMC .edge-thickness-normal{stroke-width:2px}#mermaid-svg-Sc1haK1OaY5G8HMC .edge-thickness-thick{stroke-width:3.5px}#mermaid-svg-Sc1haK1OaY5G8HMC .edge-pattern-solid{stroke-dasharray:0}#mermaid-svg-Sc1haK1OaY5G8HMC .edge-pattern-dashed{stroke-dasharray:3}#mermaid-svg-Sc1haK1OaY5G8HMC .edge-pattern-dotted{stroke-dasharray:2}#mermaid-svg-Sc1haK1OaY5G8HMC .marker{fill:#333}#mermaid-svg-Sc1haK1OaY5G8HMC .marker.cross{stroke:#333} :root { --mermaid-font-family: "trebuchet ms", verdana, arial;} #mermaid-svg-Sc1haK1OaY5G8HMC { color: rgba(0, 0, 0, 0.75); font: ; }

#include 
#define ll long long
using namespace std;
char s[100];
ll n;
int len, ans;
void dfs(ll sum, ll num, int pos, int op){
    if (pos == len){
        if (n == sum + num * op) ans++;
        return;
    }
    dfs(sum, num * 10 + s[pos] - '0', pos + 1, op); //无符号
    dfs(sum + num * op, s[pos] - '0', pos + 1, 1);  //加号
    dfs(sum + num * op, s[pos] - '0', pos + 1, -1); //减号
}

int main(){
    while (cin >> s >> n){
        ans = 0;
        len = strlen(s);
        dfs(0, s[0] - '0', 1, 1);
        cout