第31届ICPC北京赛区网络试题(A,B)
１０月７号的ＩＣＰＣ（国际大学生程序设计大赛）北京赛区网络预赛试题．Syntax Highlight(A)
Time Limit:10S Memory Limit:32768K
Description
Syntax Highlight is a useful function, but the efficiency to implement this function is often ignored, as it is unusual for a large area of text to change color at the same time. Now, you have implemented a highly efficient Syntax Highlight system. In order to prove the weakness of the original system, you hope the text of the whole screen changes color all the time. You are given a segment of text and can only change one character.
Syntax Highlight system is described by a Deterministic Finite Automaton (DFA). This DFA has n states, each with one color. At the beginning, DFA is in State 0. Each character input makes a state switch. The color of a certain character in the text is the color of the state that DFA reaches when this character and its former texts are inputted.
Given a DFA and a text, you shall change one character at most, such that maximum number of characters changes color accordingly.
Input
Input consists of several test cases. (10 cases at most)
Each case begins with a line containing n (n <= 32), the number of states of the DFA, followed by n lines, specifying the description of each state.
Each description consists of an integer c (0<=c<16), the color of this state; and s0 (0<=s0
The next line contains the text, which ends with a single character '~'. The text will contain no more than 131072 characters, and the ASCII of each character in text will be between 32 to 125 (inclusive).
The last case is followed by a line containing the integer zero.
Output
For each case, output the maximum number of characters which change color when changing only one character in the text.
Note: the blank character has color too.
Sample Input
5
0 0 @ 1
0 1 & 2
0 2 # 3
0 3 % 4
1 4 ! 0
@&%!%%!%%%!%%%%!~
3
0 0 a 1 blank 2
1 1
2 2
a ~
0
Sample Output
Case 1: 4
Case 2: 3
Counting the trees(B)
Time Limit:2S Memory Limit:65536K
Description
As we known, if we have the pre-order and post-order sequence of a binary tree, we may not draw the binary tree exactly. So the problem is: how many binary trees satisfy the given pre-order and post-order sequence?
Input
Input consists of multiple test cases.
In the first line of the each case, there is a positive integer n (1<=n<=10000), it denotes the number of the nodes in the binary tree. In the following two lines, each line has n positive integers, describing the pre-order and post-order sequence of the binary tree. Each node in the binary tree is labeled from 1 to n.
The last case is followed by a line containing a zero.
Output
For each input case, there is a positive integer s in corresponding line. It denotes the number of binary trees has the same pre-order and post-order sequence as the given one.
Sample Input
2
1 2
2 1
0
Sample Output
Case 1: 2
[此贴子已经被作者于2006-10-11 12:00:25编辑过]
