您所在位置：主题：[讨论]第八次编程比赛题目
林木
[专家分：130] 发布于 2005-12-24 07:56:00
严重道歉,各位,我来晚了.比赛时间延长150分钟.
/////////////////////////////////////////////////////////////////////////////////
[color=FF0000]注意:不得不再提醒大家一下,你们的排名不仅将同你的正确率有关,另一个重要因素是效率,所以请在保证正确的情况下,尽量提高你的时空效率.[/color]
/////////////////////////////////////////////////////////////////////////////////
1.注释提取器
[题目描述]
给出一个程序源代码
要求输出其注释部分内容.即/* 与 */中的内容
[输入样例]
#include <stdio.h>/* Hello world*/
int main(){
printf("example.");/* 世界,你好. */
return 0;
}
[输出样例]:
Hello world 世界,你好.
提示:包括空格.
2.单词查找树(TRIE)
[题目描述]
在进行文法分析的时候，通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度，通常都要画出与单词列表所对应的单词查找树，其特点如下：
根节点不包含字母，除根节点外每一个节点都仅包含一个大写英文字母；
从根节点到某一节点，路径上经过的字母依次连起来所构成的字母序列，称为该节点对应的单词。单词列表中的每个词，都是该单词查找树某个节点所对应的单词；
在满足上述条件下，该单词查找树的节点数最少。
例：
对一个确定的单词列表，请统计对应的单词查找树的节点数（包括根节点）
[输入样例]
注:为一个单词列表，每一行仅包含一个单词和一个换行/回车符。每个单词仅由大写的英文字符组成，长度不超过63个字符。文件总长度不超过32K，至少有一行数据.
A
AN
ASP
AS
ASC
ASCII
BAS
BASIC
[输出样例]
注:该文件中仅包含一个整数和一个换行/回车符。该整数为单词列表对应的单词查找树的节点数。
13
4.墙上的灯
[题目描述]：
Arthur King的城堡有一个圆形的大厅。大厅的墙壁上有N盏灯，分别按顺序从1到N编号。每盏灯都可以每打开或关上。在每一秒钟，如果第I+1盏灯是亮的，那么第I盏灯在下一秒会变化它的状态；特别的，如果第1盏灯是亮的，那么第N盏灯在下一秒会变化它的状态。
Arthur King给你某一时刻所有灯的状态，希望你能求出它们在M秒之后的状态。你正好想加入圆桌骑士的行列，赶快抓住这个机会，向Arthur King证明你的实力吧。
[输入描述]：
输入文件有N+1行。第一行有两个数N,M。此后N行，每行是一个数，不是0就是1。第I+1行的数描述初始时第I盏灯的状态。如果这个数为0，表示第I盏灯是灭的；如果这个数为1，表示第I盏灯是亮的。
20<N<500,2<M<200000
[输出描述]：
输出文件有N行，每行一个数，不是0就是1。第I行的数描述M秒后第I盏灯的状态。如果这个数为0，表示第I盏灯是灭的；如果这个数为1，表示第I盏灯是亮的。
[输入范例]：
3 1
0
0
1
[输出范例]：
0
1
1
4.强强的烦恼
[题目描述]:
新的赛季即将来临，强强将派出自己的球队---强强队 去参加这来之不易的比赛，由于这场比赛非常重要，强强 不光要考虑队员的体力和技术 还必须考虑到整个球队队员的亲密程度，如果球队中出现一些亲密度较差的队员那么一定会影响这个比赛的成绩，这个问题使强强很伤脑筋，因为他训练的队员太多了，无法完全掌握所有队员之间的亲密度~~。再这样下去强强精神就要崩溃了，看来我们还是要想个办法帮帮他。
你设计了一个程序，由程序存入各个球员之间的信息，用来方便强强查询。
输入数据：第一行3个数N，M，K 表示有N个队员M个关系以及K次询问(1<N<=2000,1<=M<=500000,1<=K<=500000)
接下来M+K行 ，前M行给出A，B(A<>B A B分别表示不同的两个队员的球衣编号A<=2000 B<=2000)两队员的关系（F表示亲密度较高 E表示亲密度较低） 后K行为强强的询问
值得注意的是：如果A与B亲密度比较低 B与C亲密度也比较低 那么A与C的亲密度就算为比较高咯
如果A与B亲密度比较高 B与C亲密度也比较高 那么A与C的亲密度就算为比较高咯
[输入样例]:
5 4 4
1 2 F
2 3 F
1 4 E
4 5 E
1 5
1 3
2 4
2 5
[输出样例]注：输出K行 如果询问的对象亲密度比较高则输出 高 如果亲密度比较低则输出 低 如果不清楚询问对象的关系那么就输出 不知道
例：
高
高
不知道
高
/////////////////////////////////////////////////////////////////////////////////
[color=FF0000]注意:不得不再提醒大家一下,你们的排名不仅将同你的正确率有关,另一个重要因素是效率,所以请在保证正确的情况下,尽量提高你的时空效率.[/color]
/////////////////////////////////////////////////////////////////////////////////
1.注释提取器
[题目描述]
给出一个程序源代码
要求输出其注释部分内容.即/* 与 */中的内容
[输入样例]
#include <stdio.h>/* Hello world*/
int main(){
printf("example.");/* 世界,你好. */
return 0;
}
[输出样例]:
Hello world 世界,你好.
提示:包括空格.
2.单词查找树(TRIE)
[题目描述]
在进行文法分析的时候，通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度，通常都要画出与单词列表所对应的单词查找树，其特点如下：
根节点不包含字母，除根节点外每一个节点都仅包含一个大写英文字母；
从根节点到某一节点，路径上经过的字母依次连起来所构成的字母序列，称为该节点对应的单词。单词列表中的每个词，都是该单词查找树某个节点所对应的单词；
在满足上述条件下，该单词查找树的节点数最少。
例：
对一个确定的单词列表，请统计对应的单词查找树的节点数（包括根节点）
[输入样例]
注:为一个单词列表，每一行仅包含一个单词和一个换行/回车符。每个单词仅由大写的英文字符组成，长度不超过63个字符。文件总长度不超过32K，至少有一行数据.
A
AN
ASP
AS
ASC
ASCII
BAS
BASIC
[输出样例]
注:该文件中仅包含一个整数和一个换行/回车符。该整数为单词列表对应的单词查找树的节点数。
13
4.墙上的灯
[题目描述]：
Arthur King的城堡有一个圆形的大厅。大厅的墙壁上有N盏灯，分别按顺序从1到N编号。每盏灯都可以每打开或关上。在每一秒钟，如果第I+1盏灯是亮的，那么第I盏灯在下一秒会变化它的状态；特别的，如果第1盏灯是亮的，那么第N盏灯在下一秒会变化它的状态。
Arthur King给你某一时刻所有灯的状态，希望你能求出它们在M秒之后的状态。你正好想加入圆桌骑士的行列，赶快抓住这个机会，向Arthur King证明你的实力吧。
[输入描述]：
输入文件有N+1行。第一行有两个数N,M。此后N行，每行是一个数，不是0就是1。第I+1行的数描述初始时第I盏灯的状态。如果这个数为0，表示第I盏灯是灭的；如果这个数为1，表示第I盏灯是亮的。
20<N<500,2<M<200000
[输出描述]：
输出文件有N行，每行一个数，不是0就是1。第I行的数描述M秒后第I盏灯的状态。如果这个数为0，表示第I盏灯是灭的；如果这个数为1，表示第I盏灯是亮的。
[输入范例]：
3 1
0
0
1
[输出范例]：
0
1
1
4.强强的烦恼
[题目描述]:
新的赛季即将来临，强强将派出自己的球队---强强队 去参加这来之不易的比赛，由于这场比赛非常重要，强强 不光要考虑队员的体力和技术 还必须考虑到整个球队队员的亲密程度，如果球队中出现一些亲密度较差的队员那么一定会影响这个比赛的成绩，这个问题使强强很伤脑筋，因为他训练的队员太多了，无法完全掌握所有队员之间的亲密度~~。再这样下去强强精神就要崩溃了，看来我们还是要想个办法帮帮他。
你设计了一个程序，由程序存入各个球员之间的信息，用来方便强强查询。
输入数据：第一行3个数N，M，K 表示有N个队员M个关系以及K次询问(1<N<=2000,1<=M<=500000,1<=K<=500000)
接下来M+K行 ，前M行给出A，B(A<>B A B分别表示不同的两个队员的球衣编号A<=2000 B<=2000)两队员的关系（F表示亲密度较高 E表示亲密度较低） 后K行为强强的询问
值得注意的是：如果A与B亲密度比较低 B与C亲密度也比较低 那么A与C的亲密度就算为比较高咯
如果A与B亲密度比较高 B与C亲密度也比较高 那么A与C的亲密度就算为比较高咯
[输入样例]:
5 4 4
1 2 F
2 3 F
1 4 E
4 5 E
1 5
1 3
2 4
2 5
[输出样例]注：输出K行 如果询问的对象亲密度比较高则输出 高 如果亲密度比较低则输出 低 如果不清楚询问对象的关系那么就输出 不知道
例：
高
高
不知道
高
