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种零件的形状和拼接成每个部件主方案， 同题例均以字符形式表示即可。 输出不应包括所用的零件总数。只需求出一个最佳解。 　　整个程序对输入数据不判错。 　　注意：在测试时将有严格的时间限制。