博文
通配符匹配串(2007-09-07 22:48:00)
摘要：
Wildcard Characters
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Problem description
In computer (software) technology, a wildcard character can be used to substitute for any other character or characters in a string.
The asterisk (*) usually substitutes as a wildcard character for any zero or more characters, and the question mark (?) usually substitutes as a wildcard character for any one character, as in the CP/M, DOS, Microsoft Windows and POSIX (Unix) shells. (In Unix this is referred to as glob expansion.)
For example: a string "wildcard" can be matched by expression "*", "**", "????????", "?ildcar?", "*card", "?ild*d", etc.
Input
The first line of input contains a non-negtive integer t(1 <= t <= 1000), then followed t lines, each contains a single word(composed by alphabet characters, digits or underlines "_", and no longer than 10 characters), the next line contains a non-negtive integer n(1......
字母表示数(2007-09-07 13:08:00)
摘要：
String’s Puzzle
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 11, Accepted users: 11
Problem 10783 : No special judgement
Problem description
Zhu Ming and Small Li find a strange stone tablet, which has some capitals printed on it. Capitals in every string are different with each other, and every capital string is followed by a number. Because of their supernormal intelligence, Zhu Ming and Small Li find the number following the string is numbered in the order of dictionary sequence from little to big (the original number is 0).For example, when the length of capital string is 3, number following the string will be: ABC 0 ABD 1 …… ZYX 15599 To better study this puzzle, please make a program to given a n-length string (1<=n<=26), output the number of the string.
Input
There are several test cases. Each data is made up of two lines. The first line is number n (1<=n<=26) The second line is a ......
角色扮演（湖南省第二界程序设计赛题）(2007-08-28 16:07:00)
摘要：
角色扮演
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 26, Accepted users: 8
Problem 10845 : No special judgement
Problem description
某年轻导演准备拍摄一部名为《温柔石头》的喜剧电影。由于预算紧张导演绞尽脑汁想节省开支。作为剧务的你提醒他：“演员的出场费很高，能不能让他们一人分演多个角色？充分挖掘他们的潜力，也可以节省我们的开支嘛！”导演大呼“有创意”，并顺手把剧本塞给你,“你研究研究剧本，看最少需要几个演员”，说着就准备出门去再拉几个广告赞助商，临走前他又补充了几点要求：
1 男演员只能演男角色，女演员只能演女角色。
2 角色的扮演者确定下来后，在演出的过程中就不能中途更改。
3 如果两个角色会同时在一个场景中出现，则这两个角色必须由两个不同的演员扮演。
导演走后，你翻开剧本看了看，发现了一张场景清单，也就是本题目的输入文件。
Input
输入文件的第一行包含用空格分隔的3个正整数，M, F和S。
其中M代表剧中的男角色数目，取值在[1, 10]之间；
F代表剧中的女角色数目，取值在[1, 10]之间；
S代表剧中的场景数目，取值在[1, 100]之间。
第二行和第三行分别列出了男角色和女角色的名字，每个名字都是一个英文字符串，名字之间有空格分隔。
下面的S行分别描述了每个场景中出现的角色数和角色名（有空格分隔）。
Output
本剧需要的男女演员的最少数目，具体格式如下：
“You need x actors and y actresses” 其中x和y分别代表男、女演员的最少数目
Sample Input
4 3 6
Tarzan Jim John Tom
Lucy Cynthia Jane
3 Jim John Tom
2 Tarzan Lucy
2 Jane Cynthia
2 Jim Jane
2 Tarzan......
岛上的植物(湖南省第二届大学生程序设计大赛)(2007-08-19 10:40:00)
摘要：
岛上的植物
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 31, Accepted users: 26
Problem 10844 : No special judgement
Problem description
测绘人员将卫星拍摄的地面遥感图像转换成了数值方阵。方阵中的每个元素都是正整数，代表某单位面积土地上的植物类型。元素为质数时对应土地上的植物为稀有类型，元素为合数时对应土地上的植物为常见类型。为保护稀有植物，林业局雇佣你编写程序分析上述数值方阵，从中检测出稀有植物区和非稀有植物区。划分区域的原则是：如果数值方阵中的两个元素同为质数或同为合数，而且它们共行相邻或共列相邻，则这两个元素同属一个区域。
Input
输入文件中包含若干待分析的数值方阵。方阵的每一行占据文件的每一行，同一行的方阵元素之间用空格分隔。每个数值方阵的前一行包含且仅包含一个正整数，代表该方阵的行数。文件的结尾行包含且仅包含一个负整数。数值方阵的行数不会超过100，元素的值不会大于100000000。
Output
针对输入文件中的每一个数值方阵分别输出如下信息： 1 该数值方阵的序号（按照其在输入文件中的位置从1计起）。格式是：“Area n:” (n代表方阵序号) 2 稀有植物区域的数目和每个稀有植物区域的面积（按升序排列）。格式是： “M unique vegetation regions: a1 a2 ...” (M为区域数目，a1, a2,...等代表每个区域的面积) 3 非稀有植物区域的数目。格式是：“K non-unique vegetation regions” (K为区域数目) 具体的输出格式请参考示例。
Sample Input
3
2 4 9
17 6 37
29 8 11
4
2 3 12 15
5 7 21 33
4 6 11 17
8 9 13 29
-1
Sample Output
Area 1:
2 unique vegetation regions: 2 ......
何时“苏醒”? (湖南省第二届程序设计大赛)(2007-08-19 10:00:00)
摘要：
何时“苏醒”?
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 61, Accepted users: 41
Problem 10843 : No special judgement
Problem description
人类的大脑是按功能分区的。正常人的大脑分区都是活跃的，分区之间有着广泛的神经连接；而脑病患者的某些大脑分区则是不活跃的，处于“睡眠”状态。最近的研究发现：如果某个“睡眠”分区X与其它至少3个活跃分区保持连接1年时间，则分区X会“苏醒”过来，恢复成活跃状态。 “苏醒”后的分区不会再转入“睡眠”状态。
有位病人的大脑分区都处于“睡眠状态”。经用一种新方法治疗后，其中3个分区同时“苏醒”过来。根据上文的结论，若不再进行治疗则其它分区经过多少年也能全部“苏醒”过来？
Input
输入文件的第1行仅包含1个整数M，取值范围是[3, 26]，它表示病人大脑的分区数。
第2行也只包含1个非负整数N，它表示分区之间的连接数（如果分区A与分区B相连，则分区B也与分区A相连。由于这样的连接是等价的，所以只计数1次）。
第3行包含3个相邻的大写英文字母，分别代表刚刚同时“苏醒”的3个分区。
第4行中包含N个用空格分割的字符串，每个字符串包含2个大写英文字母，分别代表2个相连接的分区。
Output
如果该病人的大脑分区经过若干年后能够全部“苏醒”，请在输出文件中按格式输出一行：
“WAKE UP IN n YEARS” （其中n指分区全部“苏醒”需要的年数）
如果该病人的大脑分区无法全部“苏醒”，请在输出文件中按格式输出一行：
“THIS BRAIN NEVER WAKES UP”
Sample Input
6
11
HAB
AB AC AH BD BC BF CD CF CH DF FH
Sample Output
WAKE UP IN 3 YEARS
Problem Source
湖南省第二届程序设计大赛<......
完全二叉树(湖南省第二界程序设计大赛)(2007-08-19 09:52:00)
摘要：
完全二叉树
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 22, Accepted users: 18
Problem 10846 : No special judgement
Problem description
“树”在计算机科学中是一种非常重要的数据结构。它的应用极为广泛，从计算机图形学中的空间层次剖分到人工智能中的状态搜索都离不开它。二叉树是一种特殊的树，它的每个节点最多只有左、右两个子树，如下图所示。
我们用二元组(n,s)来表示二叉树中的任意节点。其中n代表该节点的值，s代表从根节点到该节点的路径字符串，字符串中只包含’L’和’R’两种字符，分别指“左子树”和“右子树”。上图中值为13的节点用(13,RL)表示，值为2的节点用(2, LLR)表示；根节点用(5,)表示，空路径字符串表示它是根节点。如果每个节点到根节点的路径上都没有缺少节点，而且每个节点只被赋值一次，则称这样的二叉树是“完备描述”的。本题目要求你判断给定二叉树是否是“完备描述”的，如果是，输出其节点值的按层次遍历序列（即先上层后下层、从左至右地遍历）。图1中的二叉树，其节点值的按层次遍历序列为：5, 4, 8, 11, 13, 4, 7, 2, 1。
Input
输入文件中包含多个二叉树的节点序列，每个节点用上述(n,s)形式描述，节点值都是正整数。节点之间以空格分隔，节点内部没有空格。每个二叉树至少包含一个节点，树的结尾处以两个英文括号字符“()”标记，括号之内没有空格。
Output
针对输入文件中的每个二叉树，分别输出其对应的信息。对于完备描述的二叉树，输出其节点值的按层次遍历序列。每个二叉树的遍历序列值占据一行，且值与值之间用空格分隔。对于不完备描述的二叉树，则在新的一行中输出字符串“not complete”。
Sample Input
(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) ......
青蛙过河(DP加状态压缩)(2007-07-30 10:20:00)
摘要：
以前写代码都不写解题报告，从现在开始对于比较难的题都提供解题报告
一方面自己以后好查阅，一方面供网友理解学习交流。
---- 江南孤峰 ----
2007--7--30
下面这题调试了很久，主要是状态压缩出错，最后到网上找到了测试数据，终于
AC了，而且还是最优的代码，冲这点，我觉得发点时间写份详细的报告，值得。
代码真的是调试出来的！！！
/////////////////////////////////////////////////////////////////////
青蛙过河
Problem description
在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子
青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以
把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。
题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定
青蛙要想过河，最少需要踩到的石子数。
Input
输入的第一行是一个整数T,测试数据的组数。对于每一组测试数据，第一行是一个正整数
L（1 <= L <= 10^9），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1 <= S <= T <= 10，1 <= M <= 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。
Output
对于每一组测试数据，输出一行只包括一个整数，表示青蛙过河最少需要踩到的石子数。
Sample Input
1
10
2 3 5<......
典型DP(2007-07-28 20:38:00)
摘要：ct5_2: 跳棋★★
题目描述：
水平方向上有n个格子，格子上写着1到n的数字中的一个，
游戏规则是：走到某一格，上面的数字假如是s，
则可以选择跳到第s个格子或者前进一格，
问你最少要走多少步才能到达最后一格并且返回起点。
如：3 5 3 2 6 5 ，你去的时候可以一步一步到终点(5步)，
也可以一开始就跳到第三格，再一步一步到终点(4步)，
或者先前进一步再跳到第5格再一步一步地走(3步)，
最少是3步到达。然后要再返回的时候，最少步数的走法是，
左移两步再跳到第二格再左移一步(4步)，共7步。
输入：
多组测试数据，第一行是一个整数n(1<=n<=1e5)，
第二行是n个整数，表示对应的格子上写着的数。
当n输入为0的时候结束。
输出：
输出最少所需要的到达终点再返回原点的总步数
样例输入：
6
3 5 3 2 6 5
0
样例输出：
7
//////// 写了下面的东西，干脆就帖出来了
ct5_2 解题DP方法
例如数据：
6
3 5 3 2 6 5
设两个数组： data[] = 3 5 3 2 6 5
另设一个用于DP Dp[],Dp[n]表示从n位置到达终点需要走的最少的步数
首先，从终点 n=6 开始，终点到终点需要 0 步,所以设Dp[6]=0
然后n--,即 n=5，n=5到达终点需要 1 步，设Dp[5]=1
到此Dp[]数组初始化完毕 n--,此时 n=4
因为 data[4] <= 4 因此这里不能往终点方向跳
只能向前一步,Dp[4] = Dp[5]+1 = 2
同里Dp[3] = Dp[4]+1 = 3
Dp[2]，因为data[2] = 5 > 2 所以可以跳到第五个位置，这里需要决策，从
两种方法里选一种，如果往前一步，则到达终点最少需要 Dp[3]+1 = 4 步
而跳到第五个位置，则需要 Dp[5]+1= 2,显然选择 Dp[2] = Dp[5]+1 = 2
同理Dp[1]=Dp[2]+1 = 3;
因此从起始点到终点最少需要 Dp[1] = 3 步
从终点回到起点是一样的方法。
data[] = 3 5 3 2......
滑雪（DP）(2007-07-10 18:18:00)
摘要：滑雪★★★★
Description
Michael喜欢滑雪但这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。
Input
多组测试数据。输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
Output
输出最长区域的长度。
Sample Input
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
Sample Output
25
解题报告：
对于 4*4 矩阵:
a1 a2 a3 a4
b1 b2 b3 b4
c1 c2 c3 c4
d1 d2 d3 d4
假如我们从某个点开始滑，可以向它周围的四个点中的某个高度小于该点的
点滑过去，对于某个点，如果从它周围的四个点开始滑的最优值已经求出，
则该点的最优值就是在四个点中所有高度比它小的点最优值最大的那个加一
我们可以设两个数组，一个用于保存原来的高度，另外一个用于记录从该点
开始滑的最优值
比如，假设高度值矩阵如下：
1 2 5 3
14 2 5 6
14 2 56 3
1 7 8 9
最优值矩阵初始化如下：
0 0 0 0