冲刺NOIP2011模拟试题(十二)

《冲刺NOIP2011模拟试题(十二)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、冲刺NOIP2011模拟试题（十二）题目题目名称阅览室影像之结构化特征诸侯安置源文件reading.pas/c/cppgraph.pas/c/cppempire.pas/c/cpp输入文件reading.ingraph.inempire.in输出文件reading.outgraph.outempire.out时空限制1S/128Mb1S/128Mb1S/128Mb1．阅览室【问题描述】    一个阅览室每天都要接待大批读者。阅览室开门时间是O，关门时间是T。每位读者的到达时间都不一样，并且想要阅读的刊物不超过5本。每位读者心里对自己想看的刊物都有一个排位，到达之后他会先去找自己最想看的刊

2、物，如果找不到则去找其次想看的刊物。如果找不到任何他想看的刊物，他会开始等待，直到有一本以上的他想看的刊物被人放回原处。当然，他会先去拿其中自己最想看的刊物。当他看完某一本刊物后，就把它放回原处，接着去找自己没看过的最想看的刊物。如此下去，直到看完所有他想看的刊物为止。矛盾出现在两个人同时想要拿同一本刊物的时候。阅览室为了避免读者之间出现争执，作了一个规定，读者每次在开始等待时先去服务台做一次登记。如果两个人都同时想要一本刊物，那么先登记的读者将得到这本刊物。如果两个人同时登记，那么先到达阅览室的读者将得到刊物。没得到的人就只能去找其他的刊物看。阅览室关门时，所有读者都将被强迫离开阅览室

3、，不再允许继续阅读。    现在阅览室想做一个统计调查，你被要求写一个程序来模拟这个过程计算出所有刊物被阅读的总次数。当某个读者开始阅读某本刊物时，该刊物的被阅读次数就加1，无论这本刊物最后有没有被读完。【输入说明】    输入包括了多个测试数据。每个测试数据开头是两个整数T和n(1≤n≤100)，分别表示图书馆关门时间和读者总数。接下来按照读者的到达时间先后依次给出了每位读者的具体描述。每个读者描述开头是一个整数t(0≤t

4、其中第2i-1个整数表示刊物的编号s(0≤s<1000)，第2i个整数表示该读者读完这本刊物所需的时间。【输出说明】    对于每个测试数据，在单独一行里输出所有刊物被阅读的总次数。【样例输入】10 412 1 4 2 531 2 473 2 2 1 3 3 291 4 2【样例输出】52．影像之结构化特征【问题描述】    在影像比对中，有一种方法是利用影像中的边缘(edge)资讯，计算每个边缘资讯中具有代表性的结构化特征，以作为比对两张影像是否相似的判断标准。Water-filling方法是从每个边缘图的一个端点开始，绕着相连的边缘点走并依序编号。若走到某一步时，遇到一个以上不同的连

5、接点，则分成不同路径同时继续走，直到没有任何连接点为止。如果一个点和另一个点为上下左右相邻，就称为连接。例如，在图1的影像中包含三个边缘图，每个边缘图由一些互相连接的边缘点构成。图中以黑色的方块代表边缘点，白色的方块代表背景。在Water-filling方法中，首先，从第一列(row)开始，由左至右，由上至下，先找到第一个黑点并编号为1。接着，找1的下一个尚未编号的连接点并编号为2。依此方法继续往下一个点前进依次编号。在编号6的点之后有两个尚未编号的连接点，此时，则分为两条路线，并同时编号为7继续往下走。当走到没有任何的相连点时，则结束现有边缘图的编号，并继续对影像中的其它边缘图编号。走

6、完图1所有边缘图后所得到的编号如图2所示。所以，走完这三个边缘图所需要的步数分别为12、7及3；所以，12、7及3可以作为代表此张影像的结构化特征。请注意：位于斜对角上的两点不能算做连接，如：    请写一个程序计算每个影像中，以Water-filling方法走完其中所有的边缘图后，将每个边缘图需走的步数依走访的顺序列出。【输入说明】    输入文件包含一个正方形的影像。每组影像以图的宽度n开头(l≤n≤1000)。接下来的n行代表影像的内容：0表示背景的白点，1表示黑色的边缘点。【输出说明】    对每一个输入的影像，以Water-filling方法走完所有的边缘图后，先印出此张影像中

7、共有几个边缘图。接着，将每个边缘图需走的步数按升序列出。【样例输入】100000000000001111000000000100000011111000001011010000100101100011110010010001001001000001100100000000【样例输出】337123．诸侯安置【问题描述】    很久以前，有一个强大的帝国，它的国土呈正方形状（转45度看），如图2-2所示。  这个国家有若干诸侯。由于这些