(NOIP2009)复赛模拟试题（一）

题目来源：金陵中学2005-2006年第二学期信息学奥林匹克竞赛训练题

金华一中信息学奥林匹克联赛（NOIP2009）复赛模拟试题（一）

一、题目概览 中文题目名称 英文题目名称 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 比较方式 二、运行内存限制 运行内存上限 32MB 32MB 512MB 512MB 八数码 puzzle puzzle.in puzzle.out 3秒 10 10 全文比较 清扫仓库 clean clean.in clean.out 1秒 10 10 全文比较 数列 sequence sequence.in 1秒 10 10 全文比较 试题安排 arrange arrange.in 1秒 10 10 全文比较 sequence.out arrange.out

第1题 八数码

- 问题描述

大家都熟悉得不能再熟悉的八数码问题：给定一个初始状态 1 2 3 4 5 6 7 8 0

每次可以把0和与它相邻的数字交换，问最少需要多少步，可以转换到目标状态。 - 输入数据

三行三个整数，分别表示了目标状态。

- 输出数据

假如无法从初始状态到目标状态，输出一行\不含引号)，否则输出最少需要的步数。

- 样例输入 1 2 3 4 5 6 0 7 8

- 样例输出 2

第1页 共3页

题目来源：金陵中学2005-2006年第二学期信息学奥林匹克竞赛训练题

第2题 清扫仓库

- 问题描述

李老师的仓库已经有很多年没有清扫了，所以这次的计划是用河水来冲。仓库是一个N*M的矩形，且每个格子里都堆满了尘土。相邻的格子之间都有门，要想让水冲进去，就必须打开这些门。这可不是一件容易的事情。因为有些格子里土堆得很高，因此打开门就很费劲。推开一扇从A格子到B格子的门，需要的力度值为B房间里土堆的高度。写一个程序计算至少需要花费多少力气，才能使所有的格子都进水。

- 输入数据

第一行为N和M(N, M <= 40)，代表仓库的大小。 以后N行，每行N个整数（每个数不超过100），分别表示每个格子里土堆的厚度。

- 输出数据

你得到的结果。所有的格子必须都进水。水是从左上角的格子进去的。

- 样例输入 3 4

3 5 2 1 7 3 4 8 1 6 5 7

- 样例输出 26

第3题 数列

- 问题描述

一个简单的数列问题：给定一个长度为n的数列，求这样的三个元素ai, aj, ak的个数，满足ai < aj > ak，且i < j < k。

- 输入数据

第一行是一个整数n(n <= 50000)。

第二行n个整数ai(0 <= ai <= 32767)。

- 输出数据

一个数，满足ai < aj > ak (i < j < k)的个数。 - 样例输入 5

1 2 3 4 1 - 样例输出 6

第2页 共3页

题目来源：金陵中学2005-2006年第二学期信息学奥林匹克竞赛训练题

第4题 试题安排

- 问题描述

给省队选拔赛命题的时候，李老师手下有N个命题人，要命N种不同类型的试题，其中每人命一题。因为每个命题人对不同题型的掌握程度不同，所以他们编出的试题难度也有不同（这用一个难度数值来表示）。为了尽可能地刁难大家，李老师决定出一张N个题的试卷，而且所有题的难度值总和最大。

- 输入数据

第一行为N(N <= 100)，代表命题人的个数。 以后N行，每行N个整数（每个数不超过100），第i行j列的数表示第i个人出的第j种题目的难度大小。

- 输出数据

一行，表示试卷难度的最大值。

- 样例输入 3

50 50 1 10 100 10 100 10 10

- 样例输出 201

第3页 共3页

本文来源：https://www.bwwdw.com/article/lvzp.html