Eliminate Witches!
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 511 Accepted Submission(s): 216
Problem Description
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
1 2
2 3
3 2
2 1
题目大意:水题!模拟题!英语题!不解释,直接代码。遇到这些题就是要小心啊!不要粗心大意!
链接:http://acm.hdu.edu.cn/showproblem.php?pid=4041
代码:
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <string>
#include <stack>
using namespace std;
char str[1000005], ss[1000005];
char sh[105];
char ch[50005][105];
int main()
{
int i, k, len, t, ans, num;
bool tar;
scanf("%d", &t);
while(t--)
{
stack<int> ST;
scanf("%s", str);
len = strlen(str);
tar = true;
num = 0;
ans = 0;
for(i = 0; i < len; i++)
{
if(str[i]>='a' && str[i]<='z')
{
sh[ans++] = str[i];
tar = false;
}
else
{
if(tar) continue;
sh[ans] = 0;
strcpy(ch[num], sh);
num++;
ans = 0;
tar = true;
}
}
if(!tar)
{
sh[ans] = 0;
strcpy(ch[num], sh);
num++;
}
printf("%d\n", num);
for(i = 0; i < num; i++)
{
printf("%s\n", ch[i]);
}
k = 1;
for (i = 0; i < len; i++)
{
if(str[i] == '(') continue;
if(str[i] >= 'a' && str[i] <= 'z' && (i+1 >= len || str[i+1] < 'a' || str[i+1] > 'z'))
{
if(ST.size() > 0)
printf ("%d %d\n", ST.top(), k);
ST.push(k++);
}
if(str[i] == ',' || str[i] == ')')
{
printf("%d ", ST.top());
ST.pop();
printf("%d\n", ST.top());
}
}
printf ("\n");
}
return 0;
}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU最全ac代码
hdu 1166线段树代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类
HDU图论题目分类
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
Hdu 1237 解题代码