124 lines
4.4 KiB
Plaintext
124 lines
4.4 KiB
Plaintext
NOI94 试题
|
||
|
||
第一天 试题一 字符排列
|
||
|
||
试题
|
||
|
||
键盘输入一个仅由小写字母组成的字符串，输出以该串中任取M 个字母的所有排列及排
|
||
列总数。
|
||
输入数据均不需判错。
|
||
|
||
|
||
第一天 试题二 高精度实数减法
|
||
|
||
试题
|
||
|
||
编程实现两个高精度实数减法，两数分别由键盘输入，均不超过240位。
|
||
输入数据均不需判错。
|
||
|
||
|
||
第一天 第三题 实数数列
|
||
|
||
试题
|
||
|
||
一个实数数列共有N项，已知
|
||
ａi＝（ａi-1－ａi+1）／2＋d，（1＜i＜N）（N＜60）
|
||
键盘输入N，d，ａ1，ａn，m，输出ａm。
|
||
输入数据均不需判错。
|
||
|
||
|
||
第一天 试题四 删数问题
|
||
|
||
试题
|
||
|
||
键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序将组
|
||
成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。
|
||
输出应包括所去掉的数字的位置和组成的新的正整数。（N不超过240位）
|
||
输入数据均不需判错。
|
||
|
||
|
||
第一天 试题五 方阵集合
|
||
|
||
试题
|
||
|
||
一个N×N的方阵由数字0、1、2组成。定义由该方阵中若干元素组成的集合P，满足：
|
||
①P中元素的值要么全部为1，要么全部为2；
|
||
②假设P全由值为1的元素组成，若方阵中任一元素Y，其值也为1，并且Y与P中的某一元
|
||
素存在一条全由值为1的元素组成的四连通路径，则Y必定也属于P；
|
||
同样，假设P全由值为2的元素组成，若方阵中任一元素Y，其值也为2，并且Y与P中的某
|
||
一元素存在一条全由值为2的元素组成的四连通路径，则Y必定也属于P；
|
||
③对于任一元素X，若属于P，则其在原方阵中上下左右四个方向上的相邻元素的值只能
|
||
为1或2，或者超出方阵的边界，但不可能为0。
|
||
编程输出原始方阵中这样的集合总数和每个集合所含元素的个数。
|
||
原始方阵由文本文件输入，文件第一行是一个数字N，表示方阵的大小，其下N行为该方
|
||
阵，同一行中各数字以空格分隔。
|
||
N＜60（文件名由键盘输入）
|
||
输入数据均不需判错。
|
||
|
||
|
||
第二天 试题 零件与部件
|
||
|
||
试题
|
||
|
||
一个部件是由若干单位方格组成的连续的平面图形，其单位方格的个数称为该部件的面
|
||
积。例如下图所示是三个部件，面积分别为6、13和7。
|
||
┏━━━━━━━━━━━━━━━┓
|
||
┃ ┌┬┐ ┌┬┬┬┐ ┌┐ ┃
|
||
┃ ├┼┘ ├┼┼┴┘ ├┼┐ ┃
|
||
┃┌┼┤ ├┼┤┌┐ └┼┼┐ ┃
|
||
┃└┼┤ ├┼┼┼┤ └┼┼┐┃
|
||
┃ └┘ └┴┴┴┘ └┴┘┃
|
||
┗━━━━━━━━━━━━━━━┛
|
||
而一个零件是一个面积不超过给定值P（0＜P＜9）的部件。
|
||
假设已有M（0＜M＜10）种零件，要用M种零件拼接成N（0＜N＜10）个部件，拼接时不
|
||
得有重叠，每个零件可以任意旋转和翻转，每种零件所用个数不限，也可以不用。编程对给
|
||
定形状的N个部件，以及输入的M和P，求解一种定义这M种零件形状的方案，使得拼接所有 N
|
||
个部件，所用的零件总数为最少。
|
||
例如，有3个部件，形状分别如下图所示：
|
||
若M＝3，P＝5，此时一组最佳解和拼接各部件的示意图分别如下所示：（三种零件分别
|
||
以ABC区分）
|
||
┏━━━━━━━━━━━━━━┓
|
||
┃ ┌┬┐ ┌┬┐ ┌┐ ┃
|
||
┃┌┼┼┘ ├┼┤ ├┼┐ ┃
|
||
┃└┼┤ ├┼┤ └┼┼┐ ┃
|
||
┃ ├┤ └┴┘ └┼┼┐┃
|
||
┃ └┘ └┴┘┃
|
||
┗━━━━━━━━━━━━━━┛
|
||
┏━━━━━━━━┓
|
||
┃Ａ ＢＢ Ｃ ┃
|
||
┃Ａ Ｂ ＣＣ ┃
|
||
┃ Ｂ ＣＣ┃
|
||
┗━━━━━━━━┛
|
||
所有零件总数为6。
|
||
┏━━━━━━━━━━━┓
|
||
┃ ＡＡ ＢＢ Ｃ ┃
|
||
┃ＢＢ ＢＡ ＣＣ ┃
|
||
┃ Ｂ ＢＡ ＣＣ ┃
|
||
┃ Ｂ ＡＡ┃
|
||
┗━━━━━━━━━━━┛
|
||
若M＝3，P＝3，此时一组最佳解和拼接各部件的示意图分别如下图所示：
|
||
┏━━━━━━┓
|
||
┃Ａ Ｂ Ｃ┃
|
||
┃ Ｂ ＣＣ┃
|
||
┗━━━━━━┛
|
||
所用零件总数为8。
|
||
┏━━━━━━━━━━━┓
|
||
┃ ＣＡ ＣＣ Ｃ ┃
|
||
┃ＣＣ ＣＣ ＣＣ ┃
|
||
┃ Ｂ ＣＣ ＡＣ ┃
|
||
┃ Ｂ ＣＣ┃
|
||
┗━━━━━━━━━━━┛
|
||
|
||
输入输出要求：
|
||
部件形状由一个文本文件给出，该文件第一行是一个数字N，表示要求拼接的部件总数。
|
||
第二行是一个数字S1（0＜Si＜9，i＝1…N）， 表示能放下第一个部件的最小方阵的大小，
|
||
每一个部件都紧贴着最小方阵的左上角存放。其下S1行是一个S1×S1的仅由0和1组成的数字
|
||
方阵，用来表示第一个部件，该方阵中每个数字对应一个小方格，值为1 表示对应方格属于
|
||
该部件。下一行又是一个数字S2，表示能放下第二个部件的最小方阵的大小，依次类推。文
|
||
件输入不会有错。
|
||
M和P由键盘输入
|
||
输出应包括M种零件的形状和拼接成每个部件主方案， 同题例均以字符形式表示即可。
|
||
输出不应包括所用的零件总数。只需求出一个最佳解。
|
||
整个程序对输入数据不判错。
|
||
注意：在测试时将有严格的时间限制。
|