发布时间 : 星期六 文章2016年4月10日第七届csp认证试题更新完毕开始阅读cdf288c0b90d6c85ed3ac6d0
共 P 行，每行一个字符串，表示经过正规化操作后的路径，顺序与输入对应。 样例输入
7
/d2/d3 /d2/d4/f1 ../d4/f1 /d1/./f1 /d1///f1 /d1/ ///
/d1/../../d2
样例输出
/d2/d4/f1 /d2/d4/f1 /d1/f1 /d1/f1 /d1 / /d2
评测用例规模与约定 1 ≤ P ≤ 10。
文件和目录的名字只包含大小写字母、数字和小数点 .、减号 - 以及下划线 _。
不会有文件或目录的名字是 . 或 .. ，它们具有题目描述中给出的特殊含义。
输入的所有路径每个长度不超过 1000 个字符。
输入的当前目录保证是一个经过正规化操作后的路径。
对于前 30% 的测试用例，需要正规化的路径的组成部分不包含 . 和 .. 。
对于前 60% 的测试用例，需要正规化的路径都是绝对路径。
问题描述
试题编号： 试题名称： 时间限制： 内存限制： 问题描述：
4 游戏 1.0s 256.0MB 问题描述
小明在玩一个电脑游戏，游戏在一个n×m的方格图上进行，小明控制的角色开始的时候站在第一行第一列，目标是前往第n行第m列。
方格图上有一些方格是始终安全的，有一些在一段时间是危险的，如果小明控制的角色到达一个方格的时候方格是危险的，则小明输掉了游戏，如果小明的角色到达了第n行第m列，则小明过关。第一行第一列和第n行第m列永远都是安全的。
每个单位时间，小明的角色必须向上下左右四个方向相邻的方格中的一个移动一格。
经过很多次尝试，小明掌握了方格图的安全和危险的规律：每一个方格出现危险的时间一定是连续的。并且，小明还掌握了每个方格在哪段时间是危险的。
现在，小明想知道，自己最快经过几个时间单位可以达到第n行第m列过关。 输入格式
输入的第一行包含三个整数n, m, t，用一个空格分隔，表示方格图的行数n、列数m，以及方格图中有危险的方格数量。
接下来t行，每行4个整数r, c, a, b，表示第r行第c列的方格在第a个时刻到第b个时刻之间是危险的，包括a和b。游戏开始时的时刻为0。输入数据保证r和c不同时为1，而且当r为n时c不为m。一个方格只有一段时间是危险的（或者说不会出现两行拥有相同的r和c）。 输出格式
输出一个整数，表示小明最快经过几个时间单位可以过关。输入数据保证小明一定可以过关。 样例输入
3 3 3 2 1 1 1 1 3 2 10 2 2 2 10
样例输出
6
样例说明
第2行第1列时刻1是危险的，因此第一步必须走到第1行第2列。 第二步可以走到第1行第1列，第三步走到第2行第1列，后面经过第3行第1列、第3行第2列到达第3行第3列。 评测用例规模与约定
前30%的评测用例满足：0 < n, m ≤ 10，0 ≤ t < 99。
所有评测用例满足：0 < n, m ≤ 100，0 ≤ t < 9999，1 ≤ r ≤ n，1 ≤ c ≤ m，0 ≤ a ≤ b ≤ 100。
问题描述
试题编号： 试题名称： 时间限制： 内存限制：
5 网络连接 5.0s 256.0MB
问题描述
某校新建的大楼中有n台设备，学校需要利用这些设备搭建一个网络。我们用1到n的整数给这些设备编号。
这些设备之间一共可以建立m条连线，建立每条连线会消耗一定的费用。连接建立后两台设备就可以相互通信了。两台设备可以借助其他设备进行通信，即通信关系可传递：如果设备A和设备B都能与设备C相互通信，那么设备A和设备B也能相互通信。
由于大楼的拓扑结构所限，可以建立连线的两台设备，一定满足其编号之差的绝对值不超过p。
这n台设备中的一部分属于用户设备。学校要求在最终的网络中，用户设备必须两两能够相互通信，其他设备则可以根据需要选择连线或不连线。
现在问要达到学校的要求最少要消耗多少的费用。 输入格式
输入的第一行包含一个正整数T，表示数据的组数，保证T=5。接下来依次描述每组数据。
每组数据的第一行包含3个正整数n, m, p，表示设备的总数，可以建立的连线数量和拓扑结构的参数。
第二行包含一个长度为n的01字符串，依次表示这n台设备是否为用户设备；为1表示是，为0表示不是。相邻字符之间无空格隔开，保证不会出现除了0和1之外的字符。保证至少有2个设备是用户设备。 接下来m行，每行包含3个非负整数u, v, w，表示设备u和设备v
6
可以消耗w的费用建立连线。其中0 < u < v ≤ n，v – u ≤ p，w ≤ 10。 除第二行外，所有的数之间用一个空格隔开。
保证两台设备之间最多只有一条可以建立的连线，保证至少存在一种方案能够满足学校的要求。 输出格式
对于每组数据，输出一行一个整数，表示能达到要求所需的最少费用。 样例输入
问题描述：
1
20 11 6
10000100001100000000 1 6 300 1 3 100
3 6 100 4 10 100 4 6 100 6 10 400 10 15 100 11 15 100 10 11 500 12 15 100 15 20 100
样例输出
700
样例说明
用户设备分别是1、6、11、12。最优的方案需要选择以下连线：设备1和3，费用100；设备3和6，费用100；设备4和6，费用100；设备4和10，费用100；设备10和15，费用100；设备11和15，费用100；设备12和15，费用100。共计700。 子任务
每个测试点的每组数据分别都满足以下限制（其中c表示用户设备总数）：
编号 1 2 3 4 5 6 7 8 9 10
n =500 =500 =500 =500 =500 =500 =500 =500 =500 =500
p =6 =6 =6 =6 =6 =2 =2 =3 =6 =6
c =n =2 =4 =6 =10 无限制 无限制 无限制 无限制 无限制