题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=48
主要思路:这道题目的难点在于如何把题目所给的输入数据转换成一棵树。首先定义一个字符型的变量c,再定义一个整型的变量num。因为开始一定是'(',所以先输入c(cin>>c;),然后判断,如果是'(',那么再输入num(cin>>num;),这里加一个判断,如果说cin>>num输入正常,那么输入的是一个数;如果说输入异常,那么输入的是')'。这样就可以把括号的输入和数字的输入分开了。然后就是入栈、出栈,转换成二叉树,然后再dfs。
具体代码:
主要思路:这道题目的难点在于如何把题目所给的输入数据转换成一棵树。首先定义一个字符型的变量c,再定义一个整型的变量num。因为开始一定是'(',所以先输入c(cin>>c;),然后判断,如果是'(',那么再输入num(cin>>num;),这里加一个判断,如果说cin>>num输入正常,那么输入的是一个数;如果说输入异常,那么输入的是')'。这样就可以把括号的输入和数字的输入分开了。然后就是入栈、出栈,转换成二叉树,然后再dfs。
具体代码:
#include<iostream> #include<cstdlib> #include<stack> using namespace std; struct Node { int value; Node *left,*right; }; int I; bool dfs(Node *n,int sum) { sum+=n->value; if(!n->left&&!n->right&&sum==I) return 1; if(n->left&&dfs(n->left,sum)) return 1; if(n->right&&dfs(n->right,sum)) return 1; return 0; } int main() { //freopen("in.txt","r",stdin); int num; char c; stack<Node *> s_Node; while(cin>>I) { while(!s_Node.empty()) s_Node.pop(); int left_num=0,right_num=0;//左右括号的数目 do { cin>>c; if(c=='(') { if(!(cin>>num))//如果输入异常,说明是')' { cin.clear(); cin>>c; Node *tmp=NULL; s_Node.push(tmp); } else { left_num++; Node *tmp=(Node *)malloc(sizeof(Node)); tmp->value=num; tmp->left=tmp->right=NULL; s_Node.push(tmp); } } else { right_num++; Node *tmp,*left,*right; right=s_Node.top(); s_Node.pop(); left=s_Node.top(); s_Node.pop(); tmp=s_Node.top(); tmp->left=left; tmp->right=right; } }while(left_num>right_num); Node *root=s_Node.top(); s_Node.pop(); if(root) { if(dfs(root,0)) cout<<"yes"<<endl; else cout<<"no"<<endl; } else cout<<"no"<<endl; } return 0; }
发表评论
-
UVa 10422 Knights in FEN
2012-09-07 08:40 903题目:http://uva.onlinejudge.org/i ... -
UVa 539 The Settlers of Catan
2012-08-31 22:22 28题目:http://uva.onlinejudge.org/i ... -
UVa 301 Transportation
2012-08-31 22:10 34题目:http://uva.onlinejudge.org/i ... -
UVa 639 Don't Get Rooked
2012-08-30 23:01 815题目:http://uva.onlinejudge.org/i ... -
UVa 216 Getting in Line
2012-08-29 20:48 724题目:http://uva.onlinejudge.org/i ... -
UVa 10474 Where is the Marble?
2012-08-28 13:45 851题目:http://uva.onlinejudge.org/i ... -
UVa 592 Island of Logic
2012-08-27 11:05 1644题目:http://uva.onlinejudge ... -
UVa 11205 The broken pedometer
2012-08-25 17:28 1051题目:http://uva.onlinejudge.org/i ... -
UVa 131 The Psychic Poker Player
2012-08-24 22:28 876题目:http://uva.onlinejudge.org/i ... -
UVa 729 The Hamming Distance Problem
2012-08-24 12:18 696题目:http://uva.onlinejudge.org/i ... -
Uva 10098 Generating Fast
2012-08-23 15:28 660题目:http://uva.onlinejudge.org/i ... -
UVa 146 ID Codes
2012-08-20 18:46 765题目:http://uva.onlinejudge.org/i ... -
UVa 10167 Birthday Cake
2012-08-16 20:57 606题目:http://uva.onlinejudge.org/i ... -
UVa 10129 Play on Words
2012-08-15 22:49 1128题目:http://uva.onlinejudge.org/i ... -
UVa 10596 Morning Walk
2012-08-14 22:05 882题目:http://uva.onlinejudge.org/i ... -
Uva 10305 Ordering Tasks
2012-08-13 23:40 660题目:http://uva.onlinejudge.org/i ... -
Uva 10004 Bicoloring
2012-08-13 23:34 877题目:http://uva.onlinejudge.org/i ... -
Uva 532 Dungeon Master
2012-08-13 23:29 790题目:http://uva.onlinejudge ... -
Uva 439 Knight Moves
2012-08-11 22:24 656题目:http://uva.onlinejudge.org/i ... -
UVa 784 Maze Exploration
2012-08-11 14:09 828题目:http://uva.onlinejudge.org/i ...
相关推荐
accumulo-column-summing-源码.rar
c代码-summing2.c (while)
4-20mA TO 0-20mA CONVERTER AND CURRENT SUMMING CURRENT-TO-CURREN
2020_2021学年高中英语Unit2PoemsSectionⅡ_LearningaboutLanguageUsingLanguageSummingUp&LearningTip习题含解析新人教版选修6
累加列求和 Accumulo 迭代器将在一组列族上执行服务器端求和。 这是对 SummingCombiner 的改进,以代码复杂性为代价,因为它减少了发送回客户端的数据量,还减少了最终客户端求和的大小。 虽然这在单机设置中通常...
Neutron stimulated emission computed tomography (NSECT) is a new approach for biological spectroscopy and imaging. Since the<BR>gamma-ray photons emitted from stimulated element have energies from 100...
Summing Bird—用Scalding 和 Storm进行Streaming MapReduce
From the reviews of the second edition: ... Summing Up: Recommended. Computer science collections, upper-division undergraduates and above.” (C. Vickery, Choice, Vol. 50 (6), February, 2013)
Summing Up 33 Other Linkages 33 Manager’s Checklist for Chapter 237 3. Understanding Performance—Good and Bad 38 What Do We Mean by “Performance”? 39 The Stuff of Performance—Good and Poor 42 ...
From the reviews: ... presented in the text … Summing Up: Highly recommended Upper division undergraduate through professional collections " J Y Cheung Choice Vol 47 2 October 2009 ...
DGCNN features a propagation-based graph convolution layer to extract vertex features, as well as a novel SortPooling layer which sorts vertex representations instead of summing them up.
Summing Durations of Songs Recipe 3.5. Calculating the Number of Weekdays Between Two Dates Recipe 3.6. Looking up Holidays Automatically Recipe 3.7. Fuzzy Parsing of Dates Recipe 3.8. ...
Combine two geo-referenced arrays in one plot by differencing, summing or averaging. Plot lon-lat data on a global or regional map using any of over 100 map projections or make a zonal average line ...
Graphs - Subgraphs - Connected Graphs - Trees - Separable and Nonseparable Graphs - Tree-Search Algorithms - Flows in Networks - Complexity of Algorithms - Connectivity - Planar Graphs - The Four-...
对设计/前面板进行了一些调整,决定在夏季添加Summing Junction输入是一个好主意。 开始一个。 2020-12-08哇,距离我上次在这里更新内容已经很长时间了。 适度的理由:大约一年前,我意识到我同时在进行多个项目...
Summing Up Continuous Delivery .................................................................................. 22 Puppet Enterprise: Automate and Make Your Life Better. ...............................
Multi-kernel classifiers, however, are capable of integrating spectral features with spatial or structural features using multiple kernels and summing them for final outputs. Using a support vector ...
Considering the extremely wide bandwidth, we use 20-μm-thick BBO crystal as the nonlinear medium, and correct the spectral response with the frequency summing efficiency. Spatial splitting is ...