《noip搜索模拟试题》由会员分享，可在线阅读，更多相关《noip搜索模拟试题（6页珍藏版）》请在金锄头文库上搜索。
1、 青岛二中青岛二中 2010 年联赛年联赛集训集训 搜索专练搜索专练 考试时间考试时间: 2010 年年 9 月月 16 日日 18:00 PM 21:00 PM 共共 3 小时小时 命题人命题人:任青任青 Www.1992y.Com 题目名称 数独 流星雨 大海的回忆 突然好想你 提交文件 Sudoku Meteor Memory Missu 输入文件 Sudoku.in Meteor.in Memory.in Missu.in 输出文件 Sudoku.out Meteor.out Memory.out Missu.out 题目类型 传统 传统 传统 传统 时间限制 0.2s 1s 1s 3
2、s 内存限制 128MB 128MB 16MB 256MB 分值 100 100 100 100 是否有部分分 无 无 无 无 提交源文件后缀名说明 对于 C+语言 Sudoku.cpp Meteor.cpp Memory.cpp Missu.cpp 对于 C 语言 Sudoku.c Meteor.c Memory.c Missu.c 对于 Pascal 语言 Sudoku.pas Meteor.pas Memory.pas Missu.pas 注意：如无特殊说明，最终评测时所有编译命令均不打开任何优化开关。注意：如无特殊说明，最终评测时所有编译命令均不打开任何优化开关。 如无特殊说明，最终评
3、测时比较方式均采用逐字节比较。输出的每一行均以如无特殊说明，最终评测时比较方式均采用逐字节比较。输出的每一行均以 换行符结束。换行符结束。 对于对于 C+选手，允许使用选手，允许使用 STL，但测评时不开启，但测评时不开启 O2 优化，有超时的风险。优化，有超时的风险。 数独数独 题目描述题目描述 说到搜索，就不得不提到数独，这是一道多么经典的搜索题目啊。 如果你不知道数独是什么，那就听小 Q 来介绍一下吧，数独是一个填数游戏：将 1-9 填入一个 9*9 的方阵中，使得每行、每列、9 个 3*3 的子方阵内都没有重复的数。 给定初始方阵，小 Q 想请你将它填满。给定的初始方阵保证有且仅有一个
4、解。 输入格式输入格式 一个 9*9 的方阵，每个数是 0-9 的数码。0 表示未填的数。 输出格式输出格式 一个 9*9 的方阵，数之间用一个空格隔开。 样例输入样例输入 0 0 3 0 2 0 6 0 0 9 0 0 3 0 5 0 0 1 0 0 1 8 0 6 4 0 0 0 0 8 1 0 2 9 0 0 7 0 0 0 0 0 0 0 8 0 0 6 7 0 8 2 0 0 0 0 2 6 0 9 5 0 0 8 0 0 2 0 3 0 0 9 0 0 5 0 1 0 3 0 0 样例输出样例输出 4 8 3 9 2 1 6 5 7 9 6 7 3 4 5 8 2 1 2 5 1
5、8 7 6 4 9 3 5 4 8 1 3 2 9 7 6 7 2 9 5 6 4 1 3 8 1 3 6 7 9 8 2 4 5 3 7 2 6 8 9 5 1 4 8 1 4 2 5 3 7 6 9 6 9 5 4 1 7 3 8 2 数据规模及约定数据规模及约定 保证存在唯一可行解 流星雨流星雨 题目描述题目描述 夜深了，小 Q 独自坐在校园里，仰望着天空，等待着流星雨的到来。我们假设二中校 园是一个无穷大的矩阵，小 Q 所在地点为(0,0)。因为某种原因，一些流星会在某一时刻砸落 到地面上，并毁坏它降落的地点及相邻的上下左右四个格，被毁坏的点就不能再通行了。虽 然流星雨很美，但生命诚可
6、贵，所以小 Q 希望移动到一个永远不会被流星砸到的点来欣赏 流星雨。已知，每秒钟，小 Q 可以移动到相邻的一个没有被毁坏的格子，请你求出，小 Q 移动到一个永远不会被毁坏的点，也就是安全的点，最短需要多少时间。 输入格式输入格式 第一行共一个整数 M，表示共有 M 颗流星会砸落到地面上。 接下来 M 行，每行三个整数 Xi,Yi,Ti，表示在第 Ti 秒流星会毁坏 (Xi,Yi)及相邻的四个点。 输出格式输出格式 第一行，一个整数，表示小 Q 最短需要多少时间才能到达一个永远不会被流星毁坏的 地点。如果无法到达，输出-1。 样例输入样例输入 4 0 0 2 2 1 2 1 1 2 0 3 5
7、样例输出样例输出 5 数据规模及约定 对于 20%的数据,M3，耗费 2； 体力耗费第 2 小的方案:1-3，耗费 3； 样例输入样例输入 2 3 4 3 1 2 1 1 2 3 2 3 1 2 3 2 样例输出样例输出 2 9 样例说明样例说明 2 体力耗费第 1 小的方案:1-(权重为 1 的道路)-2-(权重为 1 的道路)-3，耗费 2； 体力耗费第 2 小的方案:1-(权重为 1 的道路)-2-(权重为 2 的道路)-3，耗费 3； 体力耗费第 3 小的方案:1-(权重为 3 的道路)-2-(权重为 1 的道路)-3，耗费 4； 数据规模及约定数据规模及约定 对于 10%的数据，K=1,N=10,每个点的出度最多为 6. 对于另外 10%的数据，K=2,N=500,且每个点在一个方案中最多会被访问一次. 对于另外 20%的数据，N=100,K=100 对于 100%的数据，N=1000,M=10000,K=1000,1=c=1000，保证标程能通过= =+，数据会 有区分性，不全部接近规模上限。
