di3.txt

信息学 (计算机) 奥林匹克训练题 (中级部分) 天津师范大学 李学武 编

 节点为根节点的字符串形式。程序输出无根树的字符串形式时，各个节点的名称无        

 关紧要，所有节点都以Ｐ表示，以后的各种输出也采用这种形式。例如：输入无根        

 树的字符串形式：Ａ（Ｂ（ＣＤ（ＥＦ））），指定根节点为Ｄ，程序应能输出          

 Ｐ（Ｐ（ＰＰ）ＰＰ），Ｐ（ＰＰ（ＰＰ）Ｐ），Ｐ（ＰＰＰ（ＰＰ））中的任意        

 一种即可。                                                                      

    任务二：输入两个串表示的无根树，判断其结构是否一样。注意它与节点名称         

 无关，只考虑结构。                                                              

    任务三：输入无根树的总枝数Ｎ（1<=N<=11），输出所有枝数为Ｎ的互不相同         

 的无根树，并记录总数。以字符串形式输出，例如：N=5 时共有６种不同结构的无        

 根树。                                                                          

    注意：各种树结构的字符串表达形式不唯一。                                     

                                                                                 

 60. 用Ｎ＊Ｎ（１＜＝Ｎ＜＝８）的格点阵代表海，其中＊号代表岛。给你一组编        

 码信息，让你重构一张地图。这组信息是按垂直方向，水平方向岛的情况摘取的。        

 下例中，每行右边的数字按顺序表示该行中“岛组”的大小，如第一行数字为            

 “１２”，表示该行第一“岛组”由一个岛组成，第二“岛组”由两个岛组成，而        

 第四列下面的“２３”则表示本列由两个“岛组”组成，第一个“岛组”由两个岛        

 组成，第二个“岛组”由三个岛组成。                                              

    任务：编程执行以下步骤，直到给定的输入 (ASCII) 文件中的信息组全部读完        

 为止，步骤如下：                                                                

   （１）从输入文件 (ASCII 文件）中读入下一个信息块，并将它显示在屏幕上。        

 每个信息块组成为：                                                              

    格点阵大小 (N)，以后是行的约束条件（Ｎ行的），列的约束条件（Ｎ列的）,        

 每行（或每列）的约束条件是                                                      

    一行数字，数字间有空格，最后用０结束。上面的例子如图所示。                   

   （２）重构这张地图（若有多个解，要逐个构成地图），并显示。                    

   （３）将重构的地图以ＡＳＣＩＩ文件形式输出。每岛以＊后加一个空格表示；        

 空白处用连续的两个空格表示。若同一已知条件可画出多张地图，相互间用空行隔        

 开；若一组已知条件画不出地图，用“ＮＯ  ＭＡＰ（占一行）表示。由不同的信        

 息组求得的解用“ＮＥＸＴ  ＰＲＯＢＬＥＭ”（占一行表示）１＜＝Ｎ＜＝８.         

                                                                                 

 61. 一个餐厅在相继的Ｎ天里，第 i 天需要 Ri 块餐巾(i=1，2，...，N)。餐厅         

 可以从三种途径得到餐巾:                                                         

   (1) 购买新的餐巾，每块需Ｐ分；                                                

   (2) 把用过的餐巾送到快洗部，洗一块需Ｍ天，费用需Ｆ分(Ｆ＜Ｐ)；                

   (3) 把餐巾送到慢洗部，洗一块需Ｎ天(Ｎ＞Ｍ)，费用需Ｓ分(Ｓ＜Ｆ)。              

 在每天结束时，餐厅必须决定将多少块用过的餐巾送到快洗部，多少块送慢洗部，        

 多少块保存起来延期送洗。在每天开始时，餐厅必须决定是否购买新餐巾及购买多        

 少，使洗好的和新购的餐巾之和满足当天的需求量Ri，并使Ｎ天总的费用最小。请        

 编程输入总天数，每天所需的餐巾块数以及每块餐巾的新购费用Ｐ，快，慢洗费用        

 Ｆ，Ｓ，和所需天数Ｍ，Ｎ，输出每天开始时需购新餐巾数，结束时送快，慢洗部        

 和延期送洗的餐巾数。                                                            

                                                                                 

 62. ( 旅行商 ) 一个推销员计划做一次旅行，他必须访问如图所示每个城市。每         

 两个城市的路径旁标有路径。要求从城市Ａ出发，访问每个城市一次，且只访问一        

 次，最后返回城市Ａ，求一条距离最短的路线。                                      

                                                                                 

 63. (tic__tac__toe 游戏) tic__tac__toe 游戏的规则是：从一个空的 (N*N) 的        

 棋盘（例如Ｎ＝３）开始，甲乙二人轮流将棋子放置在棋盘上未被占据的方格中，        

 例如甲第一个放，他把棋子放在中央的方格里， 然后轮到乙放，他把棋子放在第        

 一行中间的方格里。于是又轮到甲放，......如此进行下去。判定胜负的方法是：        

 若某一游戏者有Ｎ枚棋子占据了一横行，或一竖列，或一对角线，则此人获胜；若        

 直至整个棋盘被占满还没有一方获胜，则为平局。                                    

     ┏━┯━┯━┓         ┏━┯━┯━┓         ┏━┯━┯━┓                

     ┃  │  │  ┃         ┃  │  │  ┃         ┃  │Ｏ│  ┃                

     ┠─┼─┼─┨         ┠─┼─┼─┨         ┠─┼─┼─┨                

     ┃  │  │  ┃         ┃  │Ｘ│  ┃         ┃  │Ｘ│  ┃                

     ┠─┼─┼─┨         ┠─┼─┼─┨         ┠─┼─┼─┨                

     ┃  │  │  ┃         ┃  │  │  ┃         ┃  │  │  ┃                

     ┗━┷━┷━┛         ┗━┷━┷━┛         ┗━┷━┷━┛                

                                                                                 

 64.  以字符串形式由键盘输入两个高精度的８进制正整数，串长小于２５５，以         

 第一个数为被除数，第二个数为除数，进行高精度除法运算，并显示按 8 进制表         

 示的商和余数。                                                                  

 ( 参看程序 8 )                                                                                

 

 65. ( NOI'94.1_1 ) 键盘输入一个仅由小写字母组成的字符串，输出以该串中任         

 取Ｍ个字母的所有排列及排列总数。                                                

                                                                                 

 66. ( NOI'94.1_2 ) 编程实现两个高精度实数减法，两数分别由键盘输入，均不         

  超过２４０位。                                                                  

 ( 参看程序 5 )                                                                                

 

 67. ( NOI'94.1_3 ) 一个实数数列共有Ｎ项，已知a(i)=(a(i-1)-a(i+1))/2+d，         

（１〈i〈Ｎ）(N<60) , 键盘输入Ｎ，d，a(1)，a(n)，m，输出 a(m)。                  

                                                                                 

 68. ( NOI'94.1_4 ) 键盘输入一个高精度的正整数Ｎ，去掉其中任意Ｓ个数字后         

 剩下的数字按原左右次序将组成一个新的正整数。编程对给定的Ｎ和Ｓ，寻找一种        

 方案使得剩下的数字组成的新数最小。输出应包括所去掉的数字的位置和组成的新        

 的正整数。（Ｎ不超过２４０位）                                                  

 

 69. 在两个文本文件中各存有一个以西文制表符制成的未填入任何表项的表结构，        

 分别称之为表１和表２，要求编程将表１和表２下述规则合并成表３：                  

     规则：表１在表２之上，表１和表２的左边框对齐，将表１的最低行与表２的        

 最顶行合并。例：在你的Ｃ盘根目录下有两个文件 t0.1 和 t0.2，分别存放上述         

 的表１和表２，经上述规则合并后得到表３，放在文件中。三张表见下图：              

  ┎─┰─┰─┰─┒                                ┎─┰─┰─┰─┒           

  ┃  ┃  ┃  ┃  ┃        ┎┰─┰─┒            ┃  ┃  ┃  ┃  ┃           

  ┠─╂─╂─╂─┨        ┃┃  ┃  ┃            ┠─╂─╂─╂─┨           

  ┃  ┃  ┃  ┃  ┃        ┖┸─┸─┚            ┃  ┃  ┃  ┃  ┃           

  ┖─┸─┸─┸─┚                                ┠┰┸┰┸┰┸─┚           

                                                    ┃┃  ┃  ┃                 

                                                    ┖┸─┸─┚                 

        表１                    表２                     表３                    

    编程要求：                                                                   

   (1) 程序应能自给定的文件中读入两个源表并显示。                                

   (2) 若源表有错，应能指出其错。                                                

   (3) 将表１和表２规则合并成表３，并显示之。                                    

   (4) 所有制表符的ＡＳＣＩＩ码应由选手自己从给出的示例文件中截取。              

 

 70. (圆盘问题) 从左向右依次安放 4 根细柱 A,B,C,D. 在 A 上套有 N (N≤20)        

 个直径相同的圆盘, 从下到上依次用连续的小写字母 a,b,c,...编号, 将这些圆盘        

 经过 B, C 单向地移入 D (即不允许从右向左移动). 圆盘可在 B,C 中暂存. 从键        

 盘输入 N, 及前 N 个小写字母的一个排列, 它表示最后在 D 盘上形成的一个从下        

 到上的圆盘序列. 请用文本文件 ANS2.TXT 输出形成这一排列的操作过程.               

   该文件的每一行为一个形如 "k M L" 的字母序列, 其中 k 为圆盘编号, M 为 k        

 盘原先的柱号, L 为新柱号. 或者直接在屏幕上输出"No",表示不能生成这种排列.        

     例:                                ┃      ┃      ┃      ┃               

     键盘输入:                          ┃      ┃      ┃      ┃               

         3                        d   ━╋━    ┃      ┃      ┃               

         acb                      c   ━╋━    ┃      ┃      ┃               

     则一个正确的输出文件         b   ━╋━    ┃      ┃      ┃               

  可以是:                         a   ━╋━    ┃      ┃      ┃               

      c  A  B                       ━━┻━━━┻━━━┻━━━┻━