简单题,模拟展开即可。O(N)。
其实根据样例就很能看出来的,结点一定是从左到右出现的单词。
关键是怎么确定树的顺序。
想一下括号匹配,其实这基本就是个括号匹配的问题。
遇到 ( 就把当前结点作为公共父节点,如果遇到 ) 就返回上一层的父节点。
特殊情况就是 “),” 和“)))”这种。我是特判了。因为我是记录了一个公共的父亲,如果遇到一个 ) 就用类似并查集,找到父亲的父亲。。。
中间细节部分很繁。。。细心点应该就可以了。
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
#define MID(x,y) ( ( x + y ) >> 1 )
#define L(x) ( x << 1 )
#define R(x) ( x << 1 | 1 )
#define FOR(i,s,t) for(int i=(s); i<(t); i++)
#define BUG puts("here!!!")
#define STOP system("pause")
#define file_r(x) freopen(x, "r", stdin)
#define file_w(x) freopen(x, "w", stdout)
using namespace std;
const int MAX = 1000010;
char s[MAX];
struct NODE{
char s[150];
int pre;
};
NODE a[50010];
vector<pair<int,int> > p;
int main()
{
int ncases;
scanf("%d", &ncases);
while( ncases-- )
{
p.clear();
scanf("%s", s);
int len = strlen(s);
int cnt = 0, l = 0;
int f = 1, now;
a[1].pre = 1;
bool aaa = true;
FOR(i, 0, len)
{
if( isalpha(s[i]) )
{
if( aaa )
{
aaa = false;
cnt++;
a[cnt].pre = f;
p.push_back(make_pair(f, cnt));
}
a[cnt].s[l++] = s[i];
}
else
{
if( l != 0 )
a[cnt].s[l] = '\0';
aaa = true;
a[cnt].pre = f;
l = 0;
if( s[i] == '(' )
{
f = cnt;
}
if( s[i] == ',' )
{
p.push_back(make_pair(cnt, f));
}
if( s[i] == ')' )
{
p.push_back(make_pair(cnt, f));
while( s[i+1] == ')' && i+1 < len)
{
p.push_back(make_pair(f, a[f].pre));
f = a[f].pre;
i++;
}
if( i+1 < len && s[i+1] == ',' )
{
p.push_back(make_pair(f, a[f].pre));
f = a[f].pre;
i++;
}
}
}
}
if( l != 0 )
a[cnt].s[l] = '\0';
printf("%d\n", cnt);
FOR(i, 1, cnt+1)
printf("%s\n", a[i].s);
FOR(i, 1, p.size())
printf("%d %d\n", p[i].first, p[i].second);
printf("\n");
}
return 0;
}
更多推荐
The 36th ACM/ICPC Asia Regional Beijing Site Online Contest - B Eliminate Witche
发布评论