第 1 题 : 游戏 (game), 运行时限 2s, 内存上限 512M,100 分问题描述一次小 G 和小 H 在玩寻宝游戏, 有 n 个房间排成一列, 编号为 1,2,,n, 相邻房间之间都有 1 道门其中一部分门上有锁 ( 因此需要对应的钥匙才能开门 ), 其余的门都能直接打开现在小

Size: px

Start display at page:

Download "第 1 题 : 游戏 (game), 运行时限 2s, 内存上限 512M,100 分问题描述一次小 G 和小 H 在玩寻宝游戏, 有 n 个房间排成一列, 编号为 1,2,,n, 相邻房间之间都有 1 道门其中一部分门上有锁 ( 因此需要对应的钥匙才能开门 ), 其余的门都能直接打开现在小"

棓湛
5 years ago
Views:

1 NOI2018 湖南省组队选拔赛第二试试题一. 题目概况题目名称游戏排列道路目录 game perm road 可执行文件名 game perm road 输入文件名 game.in perm.in road.in 输出文件名 game.out perm.out road.out 每个测试点时限 1 秒 1 秒 1 秒测试点数目每个测试点分值结果比较方式字符串比较, 多行单字符串比较整数比较, 单行单个数字比较整数比较, 单行单个数字比较题目类型传统传统传统内存上限 512M 256M 512M 二. 提交源程序需加后缀对于 C++ 语言 game.cpp perm.cpp road.cpp 对于 C 语言 game.c perm.c road.c 对于 Pascal 语言 game.pas perm.pas road.pas 三. 编译命令对于 C++ 语言 g++ -o game game.cpp lm O2 g++ -o perm perm.cpp -lm g++ -o road road.cpp -lm 对于 C 语言 gcc o game game.c lm O2 gcc -o perm perm.cpp -lm gcc -o road road.cpp -lm 对于 Pascal 语言 fpc game.pas O2 fpc perm.pas fpc road.pas 注意事项 : (1) 选手必须在自己的工作目录下操作, 严禁在其他目录下工作目录结构请遵从 NOI 规范, 即需要在工作目录下再为每个题目建相应子目录, 子目录名为对应题目的英文名 (2) 选手最后提交的源程序 (.pas 或.c 或.cpp) 必须在自己的工作目录里对应子目录下, 对于缺少文件者, 不予测试, 该题计零分 (3) 子目录名源程序文件名和输入输出文件名必须使用英文小写 (4) 特别提醒 : 评测在 NOI Linux 下进行

2 第 1 题 : 游戏 (game), 运行时限 2s, 内存上限 512M,100 分问题描述一次小 G 和小 H 在玩寻宝游戏, 有 n 个房间排成一列, 编号为 1,2,,n, 相邻房间之间都有 1 道门其中一部分门上有锁 ( 因此需要对应的钥匙才能开门 ), 其余的门都能直接打开现在小 G 告诉了小 H 每把锁的钥匙在哪个房间里 ( 每把锁有且只有一把钥匙 ), 并作出 p 次指示 : 第 i 次让小 H 从第 S i 个房间出发, 去第 T i 个房间寻宝但是小 G 有时会故意在指令里放入死路, 而小 H 也不想浪费多余的体力去尝试, 于是想事先调查清楚每次的指令是否存在一条通路你是否能为小 H 作出解答呢? 程序文件名源程序文件名为 game. cpp/c/pas 输入格式输入文件名为 game. in 第一行三个整数 n, m, p, 代表共有 n 个房间,m 道门上了锁, 以及 p 个询问接下来 m 行每行有两个整数 x, y, 代表第 x 到第 x + 1 个房间的门上有把锁, 并且这把锁的钥匙被放在了第 y 个房间里输入保证 x 不重复接下来 p 行其中第 i 行是两个整数 S i, T i, 代表一次询问输出格式输出文件名为 game. out 输出 m 行, 每行一个大写的 "" 或 "NO" 分别代表能或不能到达 ( 输出不包含引号 ) 输入输出样例 1 game.in game.out NO NO 样例解释 1 第一个询问 S = 2 T = 5 的一条可行路线是 :

3 输入输出样例 2 ( 此组样例满足特性 :y x 恒成立 ) game.in game.out NO 4 2 NO 样例解释 2 第一个询问 2 和 1 房间之间没有锁所以为一条通路数据范围测试点编号 n m 其他特性无 3 y x 恒成立无 6 7 y x 恒成立无 10 对于所有数据, 保证 1 n, p 10 6,0 m < n,1 x, y, S i, T i < n, 保证 x 不重复由于本题输入文件较大, 建议在程序中使用读入优化编译命令对于 c++ 语言 : g++ -o game game.cpp lm O2 对于 c 语言 : gcc -o game game.c lm O2 对于 pascal 语言 : fpc game.pas O2 提示 : 本题将开启 O2 优化指令

4 第 2 题 : 排列 (perm), 运行时限 1s, 内存上限 256M,100 分问题描述给定 n 个整数 a 1, a 2,, a n,0 a i n, 以及 n 个整数 w 1, w 2,, w n 称 a 1, a 2,, a n 的一个排列 a p[1], a p[2],, a p[n] 为 a 1, a 2,, a n 的一个合法排列, 当且仅当该排列满足 : 对于任意的 k 和任意的 j, 如果 j<=k, 那么 a p[j] 不等于 p[k] ( 换句话说就是 : 对于任意的 k 和任意的 j, 如果 p[k] 等于 a p[j], 那么 k<j ) 定义这个合法排列的权值为 w p[1] + 2w p[2] + + nw p[n] 你需要求出在所有合法排列中的最大权值如果不存在合法排列, 输出 -1 样例解释中给出了合法排列和非法排列的实例程序文件名源程序文件名为 perm.cpp/c/pas 输入格式输入文件名为 perm.in 第一行一个整数 n 接下来一行 n 个整数, 表示 a 1, a 2,,a n 接下来一行 n 个整数, 表示 w 1,w 2,,w n 输出格式输出文件名为 perm.out 输出一个整数表示答案输入输出样例 1 perm.in perm.out 32 样例解释 1 对于 a 1=0,a 2=1,a 3=1, 其排列有 a 1=0,a 2=1,a 3=1, 是合法排列, 排列的权值是 1*5+2*7+3*3=28; a 2=1,a 1=0,a 3=1, 是非法排列, 因为 a p[1] 等于 p[2]; a 1=0,a 3=1,a 2=1, 是合法排列, 排列的权值是 1*5+2*3+3*7=32; a 3=1,a 1=0,a 2=1, 是非法排列, 因为 a p[1] 等于 p[2]; a 2=1,a 3=1,a 1=0, 是非法排列, 因为 a p[1] 等于 p[3]; a 3=1,a 2=1,a 1=0, 是非法排列, 因为 a p[1] 等于 p[3] 因此该题输出最大权值 32

5 输入输出样例 2 perm.in perm.out -1 样例解释 2 对于 a 1=2,a 2=3,a 3=1, 其排列有 : a 1=2,a 2=3,a 3=1, 是非法排列, 因为 a p[1] 等于 p[2]; a 2=3,a 1=2,a 3=1, 是非法排列, 因为 a p[1] 等于 p[3]; a 1=2,a 3=1,a 2=3, 是非法排列, 因为 a p[1] 等于 p[3]; a 3=1,a 1=2,a 2=3, 是非法排列, 因为 a p[2] 等于 p[3]; a 2=3,a 3=1,a 1=2, 是非法排列, 因为 a p[2] 等于 p[3]; a 3=1,a 2=3,a 1=2, 是非法排列, 因为 a p[1] 等于 p[3] 因此该题没有合法排列输入输出样例 3 perm.in perm.out 809 数据范围对于前 20% 的数据,1 n 10 对于前 40% 的数据,1 n 15 对于前 60% 的数据,1 n 1000 对于前 80% 的数据,1 n 对于 100% 的数据,1 n ,0 a i n,1 w i 10 9, 所有 w i 的和不超过编译命令对于 c++ 语言 : g++ -o perm perm.cpp lm 对于 c 语言 : gcc -o perm perm.c lm 对于 pascal 语言 : fpc perm.pas

6 第 3 题 : 道路 (road), 运行时限 1s, 内存上限 512M,100 分问题描述 W 国的交通呈一棵树的形状 W 国一共有 n 1 个城市和 n 个乡村, 其中城市从 1 到 n 1 编号, 乡村从 1 到 n 编号, 且 1 号城市是首都道路都是单向的, 本题中我们只考虑从乡村通往首都的道路网络对于每一个城市, 恰有一条公路和一条铁路通向这座城市对于城市 i, 通向该城市的道路 ( 公路或铁路 ) 的起点, 要么是一个乡村, 要么是一个编号比 i 大的城市没有道路通向任何乡村除了首都以外, 从任何城市或乡村出发只有一条道路 ; 首都没有往外的道路从任何乡村出发, 沿着唯一往外的道路走, 总可以到达首都 W 国的国王小 W 获得了一笔资金, 他决定用这笔资金来改善交通由于资金有限, 小 W 只能翻修 n 1 条道路小 W 决定对每个城市翻修恰好一条通向它的道路, 即从公路和铁路中选择一条并进行翻修小 W 希望从乡村通向城市可以尽可能地便利, 于是根据人口调查的数据, 小 W 对每个乡村制定了三个参数, 编号为 i 的乡村的三个参数是 a i,b i 和 c i 假设从编号为 i 的乡村走到首都一共需要经过 x 条未翻修的公路与 y 条未翻修的铁路, 那么该乡村的不便利值为 c i (a i + x) (b i + y) 在给定的翻修方案下, 每个乡村的不便利值相加的和为该翻修方案的不便利值翻修 n 1 条道路有很多方案, 其中不便利值最小的方案称为最优翻修方案, 小 W 自然希望找到最优翻修方案, 请你帮助他求出这个最优翻修方案的不便利值程序文件名源程序文件名为 road.cpp/c/pas 输入格式输入文件名为 road.in 第一行为正整数 n 接下来 n 1 行, 每行描述一个城市其中第 i 行包含两个数 s i, t i s i 表示通向第 i 座城市的公路的起点,t i 表示通向第 i 座城市的铁路的起点如果 s i > 0, 那么存在一条从第 s i 座城市通往第 i 座城市的公路, 否则存在一条从第 s i 个乡村通往第 i 座城市的公路 ;t i 类似地, 如果 t i > 0, 那么存在一条从第 t i 座城市通往第 i 座城市的铁路, 否则存在一条从第 t i 个乡村通往第 i 座城市的铁路接下来 n 行, 每行描述一个乡村其中第 i 行包含三个数 a i, b i, c i, 其意义如题面所示输出格式输出文件名为 road.out 输出一行一个整数, 表示最优翻修方案的不便利值输入输出样例 1

7 road.in road.out 样例解释 1 如图所示, 我们分别用蓝色黄色节点表示城市乡村 ; 用绿色红色箭头分别表示公路铁路 ; 用加粗箭头表示翻修的道路一种不便利值等于 54 的方法是 : 翻修通往城市 2 和城市 5 的铁路, 以及通往其他城市的公路用和表示公路和铁路, 用和表示翻修的公路和铁路, 那么 : 编号为 1 的乡村到达首都的路线为 : 1 3 1, 经过 0 条未翻修公路和 1 条未翻修铁路, 代价为 3 (1 + 0) (2 + 1) = 9; 编号为 2 的乡村到达首都的路线为 : 2 3 1, 经过 0 条未翻修公路和 2 条未翻修铁路, 代价为 2 (1 + 0) (3 + 2) = 10; 编号为 3 的乡村到达首都的路线为 : , 经过 1 条未翻修公路和 0 条未翻修铁路, 代价为 3 (2 + 1) (1 + 0) = 9; 编号为 4 的乡村到达首都的路线为 : , 经过 1 条未翻修公路和 1 条未翻修铁路, 代价为 1 (2 + 1) (3 + 1) = 12; 编号为 5 的乡村到达首都的路线为 : , 经过 1 条未翻修公路和 0 条未翻修铁路, 代价为 2 (3 + 1) (1 + 0) = 8; 编号为 6 的乡村到达首都的路线为 : , 经过 0 条未翻修公路和 0 条未

8 翻修铁路, 代价为 1 (3 + 0) (2 + 0) = 6; 总的不便利值为 = 54 可以证明这是本数据的最优解输入输出样例 2 road.in road.out 548 样例解释 2 在这个样例中, 显然应该翻修所有公路输入输出样例 3 road.in road.out

9 数据范围一共 20 组数据, 编号为 1 20 对于编号 4 的数据,n 20; 对于编号为 5 8 的数据,a i, b i, c i 5,n 50; 对于编号为 9 12 的数据,n 2000; 对于所有的数据,n 20000,1 a i, b i 60,1 c i 10 9,s i, t i 是 [ n, 1] (i, n 1] 内的整数, 任意乡村可以通过不超过 40 条道路到达首都编译命令对于 c++ 语言 : g++ -o road road.cpp lm 对于 c 语言 : gcc -o road road.c lm 对于 pascal 语言 : fpc road.pas

第 1 题 : 寻宝游戏 (hunt), 运行时限 1s, 内存上限 12M,100 分问题描述某大学每年都会有一次 Mystery Hunt 的活动, 玩家需要根据设置的线索解谜, 找到宝藏的位置, 前一年获胜的队伍可以获得这一年出题的机会作为新生的你, 对这个活动非常感兴趣你每天都要从西

第 1 题 : 寻宝游戏 (hunt), 运行时限 1s, 内存上限 12M,100 分问题描述某大学每年都会有一次 Mystery Hunt 的活动, 玩家需要根据设置的线索解谜, 找到宝藏的位置, 前一年获胜的队伍可以获得这一年出题的机会作为新生的你, 对这个活动非常感兴趣你每天都要从西 NOI2018 湖南省组队选拔赛第一试试题一. 题目概况题目名称寻宝游戏转盘毒瘤目录 hunt circle duliu 可执行文件名 hunt circle duliu 输入文件名 hunt.in circle.in duliu.in 输出文件名 hunt.out circle.out duliu.out 每个测试点时限 1 秒 2 秒 1 秒测试点数目 10 10 20 每个测试点分值