admin管理员组文章数量:1596345
Kaname Madoka is a Magical Girl(Mahou Shoujo/Puella Magi). The duty of a Magical Girl is to eliminate Witches(Majo). Though sounds horrific, it is not a hard job for her as a powerful magical girl.
One day Madoka is eliminating Witches as usual. This time she is facing a maze full of Witches. The maze consists of rooms, each lives exactly one Witch. And there is exactly one path from one room to another. So you see, the maze can be represented as a tree, with rooms regarded as nodes on the tree.
Madoka eliminates Witches according to the following rules:
1. At first, Madoka enters the root node room of the maze.
2. If the room Madoka enters lives a Witch, Madoka will eliminate it at once, and the Witch disappear.
3. If the room has child node rooms with Witches, Madoka will choose the leftmost one and enter it.
4. Madoka won't go back to the parent node room of a room X until Witches living in child node rooms of X are all eliminated.
See the figure below for details about a sample maze. The numbers inside nodes indicate the order of elimination of the corresponding Witches, the strings below nodes are names of Witches, and the arrow shows the tracks Madoka travels:
After finishes her task, Madoka just make a brief log like this:
"walpurgis(charlotte(patricia,gertrud),elly,gisela)"
which represents the tree-like maze identifying rooms by the names of Witches living in them.
Akemi Homura, a classmate of Madoka, also a Magical Girl, is a mad fan of her. She wants to take detailed notes of everything Madoka do! Apparently the log Madoka made is hard to read, so Homura decide to make a new one of her own.
The new log should contain the following information:
1. The number of rooms of the maze
2. Names of Witches in all rooms.
3. The tracks Madoka travels. (represented by the number identifying the node)
So the new log should be like this:
6
walpurgis
charlotte
patricia
gertrud
elly
gisela
1 2
2 3
3 2
2 4
4 2
2 1
1 5
5 1
1 6
6 1
However, the maze may be very large, so Homura nees a program to help her.
Input
The first line contains an integer T(T<=20), indicating the number of test cases.For each case there is only one string on a line, Madoka's log.
It is guaranteed that the maze consists of at most 50000 rooms, and the names of Witches is a string consists of at most 10 lowercase characters, while the string of Madoka's log consists of at most 1000000 characters, which are lowercase characters, '(', ')' or ','.
Output
For each case, you should output the detailed log.The first line an integer N, the number of rooms of the maze.
The following N lines, each line a string, the name of the Witches, in the order of elimination.
The following 2(N-1) lines, each line two integers, the number of two nodes indicating the path Madoka passes.
Output a blank line after each case.
Sample Input
3 walpurgis(charlotte(patricia,gertrud),elly,gisela) wuzetian nanoha(fate(hayate))
Sample Output
6 walpurgis charlotte patricia gertrud elly gisela 1 2 2 3 3 2 2 4 4 2 2 1 1 5 5 1 1 6 6 1 1 wuzetian 3 nanoha fate hayate
这题呢,题意就是将所有的老巫婆消灭,也就是无重复遍历一遍,根据“,”、“)”,“(”来判断入栈出栈进出队列操作 借鉴大神的代码,才a了··
#include<iostream>
#include<string.h>
#include<stack>
#include<queue>
using namespace std;
stack<int> fstack;
queue<int> Q;
char s[1000010];
struct name
{
char str[11];
}na[50001];
int main()
{
int cas,n,num;
char str1[11]; //定义数组遍历名字
scanf("%d",&cas);
while(cas--)
{
while(!fstack.empty()) //检查是否为栈空
fstack.pop();
while(!Q.empty()) //检查队列是否为空
Q.pop();
scanf("%s",s); //输入
int len=strlen(s);
num=0;
int j=0;
for(int i=0;i<len;i++)
{
if(s[i]>='a'&&s[i]<='z') //如果是名字 就存入str1数组
str1[j++]=s[i];
else
{
if(j!=0) //将一个名字结尾
{
str1[j]='\0';
j=0;
strcpy(na[++num].str,str1); //名字放入结构体数组中
}
if(s[i]=='(') //如果是( 就分别入栈和 入队列
{
fstack.push(num);
Q.push(num);
}
else if(s[i]==',')
{
if(s[i-1]!=')') //如果, 且前一个非) 就入队列,且将栈顶元素入队列
Q.push(num);
Q.push(fstack.top());
}
else {
if(s[i-1]!=')') //如果是 ) 且前一个不是) 就入队列 且将栈的首个入队列并弹出
Q.push(num);
Q.push(fstack.top());
fstack.pop();
}
}
}
if(num==0)
{
str1[j]='\0';
printf("1\n%s\n\n",str1);
continue;
}
printf("%d\n",num);
for(int i=1;i<=num;i++)
printf("%s\n",na[i].str);
while(!Q.empty())
{
if(Q.front()==1&&Q.size()==1)//所有子节点已经遍历,只剩根节点
break;
printf("%d ",Q.front()); //输出队列的元素
Q.pop();
printf("%d\n",Q.front());
}
puts("");
}
return 0;
}
版权声明:本文标题:Eliminate Witches!2011年北京网络赛 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1728255915a1151010.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论