编程之美2013全国挑战赛------资格赛

[复制链接]

foodszhu

该用户从未签到

30 主题	127 好友	2万积分

技术宅认证程序员

重度中二患者

积分: 28325

发表于 2013-4-6 10:46:05 | 显示全部楼层 |阅读模式

╱人◕‿‿◕人╲定下契约

您需要登录才可以下载或查看，没有账号？╱人◕‿‿◕人╲订下契约（注册新用户）

本帖最后由 foodszhu 于 2013-4-7 12:16 编辑

转自http://programming2013.cstnet.cn/qualification/

依旧是3道题。。。过一道题的小数据就可以参加初赛。。。不过看样子吾辈虽然能过资格赛。。但是估计到初赛就一道题都做不出来了。。召唤做题@Mr_Alex @Whisper1166 @langyxxl @汝欠咱的一生
--------------------------------------------------------------------------------------------------------------------------------------------------------------
题目 1传话游戏
时间限制: 1000ms 内存限制: 256MB
描述
Alice和Bob还有其他几位好朋友在一起玩传话游戏。这个游戏是这样进行的：首先，所有游戏者按顺序站成一排，Alice站第一位，Bob站最后一位。然后，Alice想一句话悄悄告诉第二位游戏者，第二位游戏者又悄悄地告诉第三位，第三位又告诉第四位……以此类推，直到倒数第二位告诉Bob。两位游戏者在传话中，不能让其他人听到，也不能使用肢体动作来解释。最后，Bob把他所听到的话告诉大家，Alice也把她原本所想的话告诉大家。
由于传话过程中可能出现一些偏差，游戏者越多，Bob最后听到的话就与Alice所想的越不同。Bob听到的话往往会变成一些很搞笑的东西，所以大家玩得乐此不疲。经过几轮游戏后，Alice注意到在两人传话中，有些词汇往往会错误地变成其他特定的词汇。Alice已经收集到了这样的一个词汇转化的列表，她想知道她的话传到Bob时会变成什么样子，请你写个程序来帮助她。
输入
输入包括多组数据。第一行是整数 T，表示有多少组测试数据。每组数据第一行包括两个整数 N 和 M，分别表示游戏者的数量和单词转化列表长度。随后有 M 行，每行包含两个用空格隔开的单词 a 和 b，表示单词 a 在传话中一定会变成 b。输入数据保证没有重复的 a。最后一行包含若干个用单个空格隔开的单词，表示Alice所想的句子，句子总长不超过100个字符。所有单词都只包含小写字母，并且长度不超过20，同一个单词的不同时态被认为是不同的单词。你可以假定不在列表中的单词永远不会变化。
输出
对于每组测试数据，单独输出一行“Case #c: s”。其中，c 为测试数据编号，s 为Bob所听到的句子。s 的格式与输入数据中Alice所想的句子格式相同。
数据范围
1 ≤ T ≤ 100

小数据：2 ≤ N ≤ 10, 0 ≤ M ≤ 10
大数据：2 ≤ N ≤ 100, 0 ≤ M ≤ 100
样例输入24 3
ship sheep
sinking thinking
thinking sinking
the ship is sinking
10 5
tidy tiny
tiger liar
tired tire
tire bear
liar bear
a tidy tiger is tired
样例输出
Case #1: the sheep is thinking
Case #2: a tiny bear is bear
本人目前唯一做出来的题。。。较水。。。属于只要学过C基本都能做型。。。。大数据给的数据规模也不大。。。称得上是保送的题

题目 2 长方形

时间限制: 1000ms 内存限制: 256MB
描述
在 N × M 的网格上，放 K 枚石子，每个石子都只能放在网格的交叉点上。问在最优的摆放方式下，最多能找到多少四边平行于坐标轴的长方形，它的四个角上都恰好放着一枚石子。
输入
输入文件包含多组测试数据。
第一行，给出一个整数T，为数据组数。接下来依次给出每组测试数据。
每组数据为三个用空格隔开的整数 N，M，K。
输出
对于每组测试数据，输出一行"Case #X: Y"，其中X表示测试数据编号，Y表示最多能找到的符合条件的长方形数量。所有数据按读入顺序从1开始编号。
数据范围
1 ≤ T ≤ 100
0 ≤ K ≤ N * M
小数据：0 < N, M ≤ 30
大数据：0 < N, M ≤ 30000

样例输入
3
3 3 8
4 5 13
7 14 86
样例输出
Case #1: 5
Case #2: 18
Case #3: 1398
有点眉目的题。。。不过有限制需要仔细想想。。。
[fold=小提示]对于一个N x M 的方格，其中长方形的数量是NM(N-1)(M-1)/4个[/fold]

恩，这题也算水过了。。。暴力穷举。。。

题目 3 树上的三角形
时间限制: 2000ms 内存限制: 256MB
描述
有一棵树，树上有只毛毛虫。它在这棵树上生活了很久，对它的构造了如指掌。所以它在树上从来都是走最短路，不会绕路。它还还特别喜欢三角形，所以当它在树上爬来爬去的时候总会在想，如果把刚才爬过的那几根树枝/树干锯下来，能不能从中选三根出来拼成一个三角形呢？
输入
输入数据的第一行包含一个整数 T，表示数据组数。
接下来有 T 组数据，每组数据中：
第一行包含一个整数 N，表示树上节点的个数（从 1 到 N 标号）。
接下来的 N-1 行包含三个整数 a, b, len，表示有一根长度为 len 的树枝/树干在节点 a 和节点 b 之间。
接下来一行包含一个整数 M，表示询问数。
接下来M行每行两个整数 S, T，表示毛毛虫从 S 爬行到了 T，询问这段路程中的树枝/树干是否能拼成三角形。
输出
对于每组数据，先输出一行"Case #X:",其中X为数据组数编号，从 1 开始。
接下来对于每个询问输出一行，包含"Yes"或“No”，表示是否可以拼成三角形。
数据范围
1 ≤ T ≤ 5
小数据：1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 1 ≤ len ≤ 10000
大数据：1 ≤ N ≤ 100000, 1 ≤ M ≤ 100000, 1 ≤ len ≤ 1000000000
样例输入
2
5
1 2 5
1 3 20
2 4 30
4 5 15
2
3 4
3 5
5
1 4 32
2 3 100
3 5 45
4 5 60
21 41 3
样例输出
Case #1:No
Yes
Case #2:No
Yes
怎么说呢，这种题看着就不想做的样子。。。。

小数据的话。。看起来最短路+模拟应该就能解决。。。大数据。。。。不想说话
实验证明的确是这样。。。先最短路保存路径，然后排序路径长度，每相邻3个不能组成的话就不行
RF原来是不能用qsort。。。。枉我改了一晚上。。。。愣是不知道错哪。。。。最后一个冒泡解决了。。。。
---------------------------------------------------------------------------------------------------------------------------------------

恩。。大家可以在这里好好讨论一下哦。。。。如果还是高校在校生的可以自己注册一个号来玩，如果不是的可以贴代码。。。我去交。。。。当然讨论为主。。。。

评分

参与人数 2	宅币 +50	贡献 +1	收起理由
Mr_Alex	+ 25	+ 1	o(￣▽￣)ブ发糖
_Nozomi	+ 25		我一会儿来看看…………

查看全部评分

等死星人

合作站点账号登陆

编程之美2013全国挑战赛------资格赛

╱人◕‿‿◕人╲定下契约

评分

浏览过的版块