题目链接:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=48&mosmsg=Submission+received+with+ID+10280379
题目类型: 数据结构, 二叉树
加强版样例输入:
22 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))
20 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))
10 (3
(2 (4 () () )
(8 () () ) )
(1 (6 () () )
(4 () () ) ) )
5 ()
0 ()
5 (5 () ())
5 ( 5 () () )
5 (1 (3 () ()) (4 () ()))
5 (18 ( - 13 ( ) ( ))())
0 (1 ()(-2 () (1()()) ) )
2 (1 () (1 () (1 () () ) ) )
10 (5 () (5 () (5 () (5 () (4 () () ) ) ) ) )
10 (5 () (5 () (5 () (5 ( 3 () () ) (4 () () ) ) ) ) )
20 (5 () (5 () (5 () (5 () (4 () () ) ) ) ) )
加强版样例输出:
yes
no
yes
no
no
yes
yes
yes
yes
yes
no
no
no
no
题目大意:
题目要求很简单,意思是要构造一颗二叉树,然后求出所有根结点到叶结点的路径上的数字之和,如果有一个是和题目所给的一样,那么输出yes,否则no
左括号‘(' 表示新建一个子结点, 优先建立左儿子,如果左儿子建立过了,则建立右儿子。 右括号表示退回父结点。如果一对括号内是空的,表示这个结点
也是空的。
解题思路:
这题比较难搞的是输入, 有括号,有数字,又有空格, 而且还会有陷阱,比如负号和数字之间可能也会有空格。于是专门写了个input()函数负责输入,用
getchar()一个一个读, 过滤掉空格,保存到一个数组里。然后再处理。
二叉树建好之后, 进行深搜,得到路径和。
对于空括号, 用一个简单的处理,即把那个结点数据赋值为一个负无穷,而不是空指针, 这样深搜时,如果有个结点数据值是负无穷的,则不处理。
#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstring>
const int END = -214748364;
using namespace std;
class Node{
public:
int data;
Node *parent;
Node *left;
Node *right;
};
bool found;
Node *root, *curRoot; // 根结点指针
Node node[10000]; // 先分配好内存
int nodeIndex;
int sum;
char str[100000];
// 创建一个只有根结点的二叉数,返回根结点指针
inline Node* CreateBTree(){
nodeIndex = 1;
node[0].parent = NULL;
node[0].left = NULL;
node[0].right = NULL;
return &node[0];
}
inline Node* NewNode(Node* parent){
if(nodeIndex>10000-2){
Node *t = new Node;
t->left = NULL;
t->right = NULL;
t->parent = parent;
return t;
}
node[nodeIndex].parent = parent;
node[nodeIndex].left = node[nodeIndex].right = NULL;
return &node[nodeIndex++];
}
void Solve(){
int i, j, ans=0;
Node *temp;
curRoot = NULL;
bool flag = false;
i=0;
while(i<strlen(str)){
// 进入结点并处理数据
if(str[i]=='('){
if(curRoot == NULL){
root = curRoot = CreateBTree();
}
else{
if(curRoot->left == NULL ){
curRoot->left = NewNode(curRoot); //给左儿子开辟空间
curRoot = curRoot->left; // 进入左儿子
}
else{
curRoot->right = NewNode(curRoot); // 先给儿子指明父亲
curRoot = curRoot->right; // 进入右儿子
}
}
// 直接碰到了右括号,说明没有数字,这个结点是终端标志
++i;
if(str[i]==')'){
curRoot->data = END;
Node *parent = curRoot->parent;
--i;
} // 如果是数字
else{
int val;
sscanf(&str[i], "%d", &val);
curRoot->data = val;
}
}
else if(str[i] == ')'){
curRoot = curRoot->parent;
}
++i;
}
}
bool Input(){
char ch;
int cnt1=0, cnt2=0, index=0;
while(ch = getchar()){
if(ch=='(') ++cnt1;
if(ch==')') ++cnt2;
if(ch=='(' || ch==')' || ch=='-' || isdigit(ch))
str[index++] = ch;
if(cnt1 && cnt1==cnt2) break;
}
getchar();
str[index] = '\0';
if(cnt1==1 && cnt2==1) return false; // 如果只有一对括号,那么可以直接判断
return true;
}
void dfs(Node *root, int n){
if(found) return ;
if(root->left->data==END && root->right->data==END ){
if(n+root->data == sum) found = true;
return ;
}
if(root->left && root->left->data!=END) dfs(root->left, n+root->data);
if(root->right && root->right->data!=END) dfs(root->right, n+root->data);
}
int main(){
freopen("input.txt", "r", stdin);
while(~scanf("%d", &sum)){
if(!Input()){
printf("no\n");
}
else{
Solve();
found = false;
dfs(root, 0);
if(found) printf("yes\n");
else printf("no\n");
}
}
return 0;
}
—— 生命的意义,在于赋予它意义。
分享到:
相关推荐
accumulo-column-summing-源码.rar
c代码-summing2.c (while)
4-20mA TO 0-20mA CONVERTER AND CURRENT SUMMING CURRENT-TO-CURREN
对超过 100 万行的单列求和将导致 SummingCombiner 将 100 万个部分和返回给客户端。 使用包含的 SortedKeyValueIterator 将导致发送到客户端的给定表结果的大约分割点数。 实际上,迭代器返回的结果数将取决于在 ...
Graphs - Subgraphs - Connected Graphs - Trees - Separable and Nonseparable Graphs - Tree-Search Algorithms - Flows in Networks - Complexity of Algorithms - Connectivity - Planar Graphs - The Four-...
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 ...
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.
2020_2021学年高中英语Unit2PoemsSectionⅡ_LearningaboutLanguageUsingLanguageSummingUp&LearningTip习题含解析新人教版选修6
Summing Bird—用Scalding 和 Storm进行Streaming MapReduce
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. ...
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...
conditional summing.xlsx:一个演示如何使用单个或多个条件计算进行条件求和的工作簿。 cout unique.xlsx:一个演示如何计算区域内惟一(非复制的)项的工作簿。 counting text in a range.xlsx:一个演示计算...
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 of the second edition: ... Summing Up: Recommended. Computer science collections, upper-division undergraduates and above.” (C. Vickery, Choice, Vol. 50 (6), February, 2013)
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 ...
Chapter 12: Summing Up – A Complete Example Module 2: Python 3 Object-Oriented Programming Chapter 1: Object-oriented Design Chapter 2: Objects in Python Chapter 3: When Objects Are Alike Chapter 4:...
对设计/前面板进行了一些调整,决定在夏季添加Summing Junction输入是一个好主意。 开始一个。 2020-12-08哇,距离我上次在这里更新内容已经很长时间了。 适度的理由:大约一年前,我意识到我同时在进行多个项目...
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 ...