信息学选试题

1、第7页 共7页省选试题题目名称生日礼物骰子的学问围豆豆目录giftdicebean可执行文件名giftdicebean输入文件名gift.indice.inbean.in输出文件名gift.outdice.outbean.out每个测试点时限1秒1秒1秒测试点数目101010每个测试点分值101010是否有部分分无无无题目类型传统传统传统附加文件无无无提交源程序须加后缀对于Pascal语言gift.pasdice.pasbean.pas对于C 语言gift.cdice.cbean.c对于C+ 语言gift.cppdice.cppbean.cpp注意：最终测试时，所有编译命令均不打开任何优化开关

2、生日礼物【问题描述】小西有一条很长的彩带，彩带上挂着各式各样的彩珠。已知彩珠有N个，分为K种。简单的说，可以将彩带考虑为x轴，每一个彩珠有一个对应的坐标(即位置)。某些坐标上可以没有彩珠，但多个彩珠也可以出现在同一个位置上。小布生日快到了，于是小西打算剪一段彩带送给小布。为了让礼物彩带足够漂亮，小西希望这一段彩带中能包含所有种类的彩珠。同时，为了方便，小西希望这段彩带尽可能短，你能帮助小西计算这个最短的长度么？彩带的长度即为彩带开始位置到结束位置的位置差。【输入文件】输入文件gift.in，第一行包含两个整数N, K，分别表示彩珠的总数以及种类数。接下来K行，每行第一个数为Ti，表示第i种彩珠

3、的数目。接下来按升序给出Ti个非负整数，为这Ti个彩珠分别出现的位置。【输出文件】输出文件gift.out应包含一行，为最短彩带长度。【样例输入】6 31 52 1 73 1 3 8【样例输出】3【样例说明】有多种方案可选，其中比较短的是15和58。后者长度为3最短。【数据规模】对于50%的数据， N10000；对于80%的数据， N800000；对于100%的数据，1N1000000，1K60，0TiB。 咋一看来，小鱼儿觉得如果AB且BC则AC。可事实恰好相反，存在字符串A, B, C使得AB, BC, CA。小鱼儿被这种戏的一个反常现象所吸引，通过查阅资料，他了解到这种现象被称为“非传递

4、性悖论”，在许多非完全信息游戏（比如军棋）中，经常会有这样的例子。可是它到底是如何产生的呢？小鱼儿决定设计一种游戏，从中可以容易的找到非传递的例子，以便更清楚的认识“非传递性”。当然，这样的游戏越简单道理越深刻，于是小鱼儿想起了最简单的掷骰子游戏这个游戏是这样的，假设有n个骰子D1Dn，每个骰子有m个面。每个面上标有一个1nm的正整数，并且所有骰子的所有nm个面上的数字各不相同。满足这条编号要求，并且每个面被随到的概率相等的，这样的n个骰子称为一组“好骰子”。游戏开始时，两个玩家分别选两个骰子Di和Dj，各掷一次来比较掷出来那一面的数值，数大的获胜。小鱼儿请你帮忙设计一组“好骰子”，使得对任意

5、一个骰子Di，它总能战胜Dai。此处战胜是指选择前者的玩家获胜的概率超过1/2；a1an为输入的1n的正整数。【输入文件】输入文件dice.in第一行为两个整数n, m。第二行有n个整数，为a1，a2, , an。【输出文件】输出文件dice.out包含n行，每行m个1nm的正整数，各不相同，以空格分开。如果有多解，输出任意一组解；如果无解，输出一个整数0。【样例输入输出】示例1示例2示例3示例4样例输入3 32 3 13 42 1 23 42 3 14 44 1 2 3样例输出1 6 83 5 72 4 901 3 10 112 7 8 94 5 6 121 11 8 1412 15 2 5

6、3 6 16 94 10 13 7【样例说明】示例1：D1和D2比，D2和D3比，D3和D1比，前者获胜的几率均为5/9；示例2：D1战胜D2，D2战胜D1 。矛盾！无解；示例3：D1和D2比，D2和D3比，D3和D1比，前者获胜概率分别为9/16, 9/16, 10/16；示例4：D1和D2比，D2和D3比，D3和D4比，D4和D1比，前者获胜的几率均为9/16。【数据规模】30%的数据满足n, m10100%的数据满足3n, m200围豆豆【问题描述】是不是平时在手机里玩吃豆豆游戏玩腻了呢？最近MOKIA手机上推出了一种新的围豆豆游戏，大家一起来试一试吧。游戏的规则非常简单，在一个NM的矩

7、阵方格内分布着D颗豆子，每颗豆有不同的分值Vi。游戏者可以选择任意一个方格作为起始格，每次移动可以随意的走到相邻的四个格子，直到最终又回到起始格。最终游戏者的得分为所有被路径围住的豆豆的分值总和减去游戏者移动的步数。矩阵中某些格子内设有障碍物，任何时刻游戏者不能进入包含障碍物或豆子的格子。游戏者可能的最低得分为0，即什么都不做。注意路径包围的概念，即某一颗豆在路径所形成的多边形（可能是含自交的复杂多边形）的内部。下面有两个例子：豆豆豆围住了中心的豆并没有围住中心的豆第一个例子中，豆在路径围成的矩形内部，所以豆被围住了。第二个例子中，虽然路径经过了豆的周围的8个格子，但是路径形成的多边形内部并不包含豆，所以没有围住豆子。布布最近迷上了这款游戏，但是怎么玩都拿不了高分。聪明的你决定写一个程序来帮助他顺利通关。【输入文件】输入文件bean.in第一行两个整数N和M，为矩阵的边长。第二行一个整数D，为豆子的总个数。第三行包含D个整数V1到VD，分别为每颗豆子的分值。接着N行有一个NM的字符矩阵来描述游戏矩阵状态，0表示空格，#表示障碍物。而数字1到9分别表示对应编号的豆子。【输出文件】输出文件bean.out仅包含