首页 > 代码库 > HDU 4041 Eliminate Witches! --模拟
HDU 4041 Eliminate Witches! --模拟
题意： 给一个字符串，表示一颗树，要求你把它整理出来，节点从1开始编号，还要输出树边。
解法： 模拟即可。因为由括号，所以可以递归地求，用map存对应关系，np存ind->name的映射，每进入一层括号，使father = now， 遇到右括号‘)‘，则father = fa[father]，用vector存每个节点的子节点，然后最后dfs输出即可。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#include <string>#include <vector>#include <map>using namespace std;#define N 50017string ss,tmp,S;string np[N];map<string,int> mp;int fa[N],father,ind;vector<int> G[N];void Go(int u,int v,int father){ tmp = ""; int j; for(int i=u;i<v;i++) { if(ss[i] >= ‘a‘ && ss[i] <= ‘z‘) tmp += ss[i]; else if(ss[i] == ‘(‘ || ss[i] == ‘,‘ || ss[i] == ‘)‘) { if(tmp == "") continue; mp[tmp] = ++ind; np[ind] = tmp; tmp = ""; fa[ind] = father; G[father].push_back(ind); if(ss[i] == ‘(‘) { int cnt = 1; for(j=i+1;j<v;j++) { if(ss[j] == ‘(‘) cnt++; else if(ss[j] == ‘)‘) { cnt--; if(cnt == 0) break; } } Go(i+1,j,ind); i = j; } else if(ss[i] == ‘)‘) father = fa[father]; } } if(tmp != "") { mp[tmp] = ++ind; np[ind] = tmp; tmp = ""; fa[ind] = father; G[father].push_back(ind); }}void dfs(int u){ for(int i=0;i<G[u].size();i++) { int v = G[u][i]; printf("%d %d\n",u,v); dfs(v); printf("%d %d\n",v,u); }}int main(){ int t,i,j,len; scanf("%d",&t); while(t--) { mp.clear(); for(i=0;i<=50000;i++) G[i].clear(); cin>>ss; len = ss.length(); father = 0; ind = 0; Go(0,len,0); printf("%d\n",ind); for(i=1;i<=ind;i++) cout<<np[i]<<endl; dfs(1); puts(""); } return 0;}
HDU 4041 Eliminate Witches! --模拟
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。