NOI95试题 第一天 第一题 查阅单词 试题 一个文本文件仅含有英文字母和分隔符，分隔符包括空格、逗号、句号和换行符。除此 之外，该文件不含其它符号。一个单词的由一个或多个分隔符分隔的连续字母序列，例如： 下面是一个包含５个单词的文件 ┏━━━━━━━━━━━━━━━━┓ ┃＿Student＿＿must＿＿＿have↓ ┃ ┃↓ ┃ ┃↓ ┃ ┃a＿book ┃ ┗━━━━━━━━━━━━━━━━┛ 其中符号“＿”为空格符；“↓”为换行符；“”为句号。 文本文件中的第一个句子是从文件头到第一个句号间的字符序列（含句号）， 除第一个句 子之外的所有句子都是由两个句号间的所有字符组成的序列（含后面的句号）。 编一程序，由键盘输入一个符合上述约定的文本文件名和一个单词， 计算该单词在该 文件中出现的次数，并输出包含该单词的所有句子（按句子在文件中的先后次序，依次输 出）。 注意： ①文件中每个单词长度不超过２０个字母。 ②判断单词是否相同时不区分大小写。例如ＡＢＣ、Ａｂｃ、 ＡＢｃ、ａＢＣ、ａｂｃ…都是同一个单词。 输入数据： 由键盘输入待查文本文件名和待查单词。 输出数据： 输入文件为output.txt 该文件第一行为该单词在文件中出现的次数。 从每二行开始是依先后次序输出的包含该单词的句子。 在输出句子时请注意： ①每个句子无论多长只占一行； ②原句中每一个换行符用一个空格符代替。 输入输出范例： 输入文件内容： ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓ ┃ __Every computer will have MsDos, Borland C Microsoft ┃ ┃ Quick Basic. And Turbo Pascal. For the translati ons ┃ ┃ the teamleaders will be provided with Microsoft Office ┃ ┃ with MS Word and WordPerfect Information on directories┃ ┃ and last instructions will be sent to you in the last ┃ ┃ newsletter and distributed on the day before the first ┃ ┃ contest day._Each student will have the opportunity ┃ ┃ for some practice. On the equipment. ┃ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ 输出文件内容： ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓ ┃2 ┃ ┃__Every computer will have MsDos, Borland C Microsoft ┃ ┃Quick Basic. ┃ ┃_Each student will have the oppertunity for some practice.┃ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ 第一天 第二题 石子合并 试题 在一个园形操场的四周摆放N堆石子（N≤100），现要将石子有次序地合并成一堆。规定 每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。 编一程序，由文件读入堆数N及每堆的石子数（≤２０）， ①选择一种合并石子的方案，使得做N-1次合并，得分的总和最小； ②选择一种合并石子的方案，使得做N-1次合并，得分的总和最大。 例如，图1所示的４堆石子，每堆石子数（从最上面的一堆数起，顺时针数）依 次为4 5 9 4。则３次合并得分总和最小的方案为图2，得分总和最大的方案为图3。 4 4 8 * * 4 5 4 5 -> * 5 -> * 13 -> * 22 9 9 9 9 * 图1 图2 总得分＝８＋１３＋２２＝４３ 4 4 4 * 4 5 -> 4 * -> 18 * -> 22 * 9 14 * * 图3 总得分＝１４＋１８＋２２＝５４ 输入数据： 文件名由键盘输入，该文件内容为： 第一行为石子堆数N； 第二行为每堆的石子数，每两个数之间用一个空格符分隔。 输出数据： 输出文件名为output.txt 从第1至第N行为得分最小的合并方案。第N＋1行是空行。从第N＋2行到第2N＋1行是得 分最大合并方案。 每种合并方案用N行表示，其中第i行（1≤i≤N）表示第i 次合并前各堆的石子数（依 顺时针次序输出，哪一堆先输出均可）。 要求将待合并的两堆石子数以相应的负数表示， 以便标识。 输入输出范例： ┏━━━━━━━┓ ┏━━━━━━━━━┓ ┃输入文件内容：┃ ┃输出文件内容： ┃ ┠───────┨ ┠─────────┨ ┃４ ┃ ┃－４ ５ ９ －４ ┃ ┃４ ５ ９ ４ ┃ ┃－８－５ ９ ┃ ┗━━━━━━━┛ ┃－１３ －９ ┃ ┃２２ ┃ ┃ ┃ ┃４ －５ －９ ４ ┃ ┃４ －１４ －４ ┃ ┃－４－１８ ┃ ┃２２ ┃ ┗━━━━━━━━━┛ (图6.2-4) 第一天 第三题 最短编号序列 试题 表A和表B各含K(k≤２０)个元素，元素编号从１到k。两个表中的每个元素都是由０、 １组成的字符串。(不是空格)字符串的长度≤２０。例如下面的两个表， 每个都含３个元 素（k＝３）。 表a 表b ┏━━━━┯━━━━━┓ ┏━━━━┯━━━┓ ┃元素编号│ 字符串 ┃ ┃元素编号│字符串┃ ┠────┼─────┨ ┠────┼───┨ ┃ 1 │1 ┃ ┃ 1 │111 ┃ ┃ 2 │10111 ┃ ┃ 2 │10 ┃ ┃ 3 │10 ┃ ┃ 3 │0 ┃ ┗━━━━┷━━━━━┛ ┗━━━━┷━━━┛ 对于表A和表B，存在一个元素编号的序列２１１３，分别用表A中的字符串和表B 中的字符 串去置换相应的元素编号，可得相同的字符串序列１０１１１１１１０，见下表： ┏━━━━━━━━━┯━━━━━┯━━━┯━━━┯━━┓ ┃元素编号序列 │ 2 │ 1 │ 1 │ 3 ┃ ┠─────────┼─────┼───┼───┼──┨ ┃用表A的字符串替换 │10111 │ 1 │ 1 │10 ┃ ┠─────────┼─────┼───┼───┼──┨ ┃用表B的字符串替换 │ 10 │111 │111 │ 0 ┃ ┗━━━━━━━━━┷━━━━━┷━━━┷━━━┷━━┛ 对表A和表B，具有上述性质的元素编号序列称之为S（AB）。对于上例S（AB）＝２１１３。 编写程序：从文件中读入表A和表B的各个元素， 寻找一个长度最短的具有上述性质的 元素编号序列S（AB）。 注意：如果对于表A和表B不存在S（AB），即找不到相同元素编号序列对应有相同的长 度≤１００的由０、１组成的字符串序列，这时应输出“No Answer”（无解）。 输入数据： 输入文件名由键盘输入，该文件 第１行为K的值； 第２行至第K＋１行为表A的内容（依次是元素编号从１到K的相应 ０、１字符串）； 第K＋2行至第2K＋１行为表B的内容（依次是元素编号从１至K的相应０、１字符串） 输出数据： 输出文件名为OUTPUT.TXT，该文件只有一行。或是S（AB）的值，或是“No Answer ”（无 解时）。s（AB）是元素编号序列，输出时每个编号占一行。 输入输出范例： ┏━━━━━━━┓ ┏━━━━━━━┓ ┃输入文件内容：┃ ┃输出文件内容：┃ ┠───────┨ ┠───────┨ ┃３ ┃ ┃２ ┃ ┃１ ┃ ┃１ ┃ ┃１０１１１ ┃ ┃１ ┃ ┃１０ ┃ ┃３ ┃ ┃１１１ ┃ ┗━━━━━━━┛ ┃１０ ┃ ┃０ ┃ ┗━━━━━━━┛ 第一天第四题 “互邻”数码序列（已删除） 　　N位由0和1组成的字符串A、B可分别表示为 　　A＝ａNａN-1…ａi…ａ2ａ1 　　B＝ｂNｂN-1…ｂi…ｂ2ｂ1 其中, ａi＝0或1, ｂi＝0或1 1≤i≤N, N≤15 如果存在某一位j(j∈1…N), 在该位上两串不同, 即ａj≠ｂj, 而其余N-1位上的两串相同, 即ａi＝ｂi(i∈1…N，i≠j), 则称A、B两串“互邻”。 　　比如，在N＝4时, A＝1100, B＝1000, A、B 两串“互邻”, 而 C＝1100, D＝1010, C、D两 串不“互邻”。 编程要求： 寻找一个含有2N个上述01串的序列, 该序列满足以下要求: ① 组成该序列的每一个01串都与其它串不同; ② 第k个串与第k-1个串有“互邻”关系，2≤k≤2N; ③ 该序列首项由输入指定. 例如 N=2, 指定首项为01, 则一个满足上述要求的序列为 01 11 10 00 　　输入数据 ┏━━━━━━┓ ┏━━━━━┓ 文件名由键盘输入 ┃EXAMPLE4.TXT┃ ┃MODEL4.TXT┃ 该文件共有两行 ┠──────┨ ┠─────┨ 第一行为 N ┃2 ┃ ┃2 ┃ 第二行为指定的序列首项 ┃01 ┃ ┃01 ┃ ┃ ┃ ┃11 ┃ 　　输出数据 ┗━━━━━━┛ ┃10 ┃ 输出文件为 OUTPUT.TXT ┃00 ┃ 第一行为 N ┃ ┃ 第二行至第2N+1行依次输出序列的每一个串. ┗━━━━━┛ 　　输入输出举例 参考输入文件: EXAMPLE4.TXT 参考输出文件: MODEL4.TXT 第一天第五题 极值问题 试题 m、n为整数，且满足下列两个条件： ①m、n∈１，２，…，K，（１≤K≤ 10^9） ②(n^2－mn－m^2)^2=1 编一程序，由键盘输入K，求一组满足上述两个条件的m、n，并且使m^2＋n^2的值最大。 例如，若K＝１９９５，则m＝９８７，n＝１５９７，则m、n满足条件，且可使m^2＋n^2的值最大。 输入数据： 键盘输入K。 输出数据： 输出有两行： 第一行为m的值； 第二行为n的值。 第二天试题 下棋 一个Ｎ×Ｍ的棋盘上每格均涂有黑色或白色，黑色代表建筑物，白色代表街道。例如 下图是个６×８的棋盘。Ｎ为行数，Ｍ为列数。棋盘上只有建筑物和街道， 不存在广场， 即任意一个２×２的区域不会全是白格。 １２３４５６７８ １□□□□□■□■ ２■■□■□□□□ ３□□□■□■□■ ４□■■■□■□□ ５□■□□□■■■ ６□□□■□□□□ （图６．５－１） 现有Ｒ枚棋子（代表Ｒ个行人）分别放在棋盘的Ｒ个白格上， 它们各自有一个目的格 （也是白格，目的格有可能相同），希望它们能尽快地全部到达目的格，行动规则如下： ①所有棋子同时行动一次称为一步，行动包括走入相邻白格或原地不动； ②同一时刻任何一白格内最多只有一枚棋子； ③棋子行动时可以“跟随”，但不允许“碰撞”。 以下情况称为“跟随”，①、②分别代表第１、２号棋子 ┏━┳━┳━┓ 移动 ┏━┳━┳━┓ ┃①┃②┃ ┃───→┃ ┃①┃②┃ ┗━┻━┻━┛ 一步后 ┗━┻━┻━┛ ┏━┓ ┏━┓ ┃①┃ ┃ ┃ ┏━╋━┫───→┏━╋━┫ 或者 ┃ ┃②┃ ┃②┃①┃ ┗━┻━┛ ┗━┻━┛ （图６．５－２） 以下情况称为“碰撞” ┏━┳━┓ ┏━┳━┓ ┃①┃②┃───→┃②┃①┃ ┗━┻━┛ ┗━┻━┛ （图６．５－３） ④棋子在到达目的格后即可从棋盘上拿走，此格在下一步才允许走入别的棋子； ⑤所有棋子均到达目的格所用步数称为收盘步数Ｓｔｅｐ。 要求： ①求Ｒ＝１时收盘步数最优解； ②求Ｒ＝２时收盘步数最优解。较优解酌情给分； ③Ｒ〉２时求较优解。 注意： 以上均要求能判无解（即按前述规则无法使全部棋子到达目的格）； ２≤Ｍ≤１６； ２≤Ｎ≤１６； １≤Ｒ≤６； 解的收盘步数均≤６０步。 输入数据： 第１行是Ｍ,Ｎ（列数在前，行数在后）； 第２行至第Ｎ＋１行是Ｎ×Ｍ的０、１矩阵，矩阵元素间有一空格。元素０表示白格， １表示黑格； 第Ｎ＋２行是Ｒ； 第Ｎ＋３行至第Ｎ＋２＋Ｒ行分别是第１～Ｒ号棋子的 起点横坐标＿起点纵坐标＿终点横坐标＿终点纵坐标 输入文件不会有错 注意棋子有编号，编号不可颠倒。 输出数据： 若无解，输出文件为－１； 若有解，第一行输出收盘步数Ｓｔｅｐ， 第二行至第Ｓｔｅｐ＋１行依次输出第一步 至第Ｓｔｅｐ步后所有棋子位置，每行格式为 １号棋子横坐标＿１号纵坐标＿２号横坐标＿……＿Ｒ号纵坐标 坐标参见（图６．５－１）。特别地，当某个棋子从棋盘上拿去后，其坐标输出为０ ０， 以便标识。 评分： 输入输出文件名由键盘输入，评测时运行时间分三个档次： ≤５秒， ≤１０秒， ≤２０秒。