Noip练习题.pdf

《Noip练习题.pdf》由会员分享，可在线阅读，更多相关《Noip练习题.pdf（72页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、问题名称文件名输入输出时限分值序列sequence.exesequence.insequence.out2s100连分数faction.exefaction.infaction.outIs100词链link.exelink.inlink,outIs100Geodetic 集合geo.exegeo.ingeo.outIs100模拟一序歹 ij(sequence.exe)问题描述有一个非递减的整数序列S i，S2,S 3,，Sn+1(S i=S i+i)o定义序列m i，m 2,，mn 为 S 的“M 序列”,其中 m j=(Si+Si+i)/2。例如,S=(l,3,3,5),则 m=(2,3,4

2、)。现在给你序列m,要你求有多少个S序列的“M序列”是序列m。输入(sequence.in)第一行一个整数n,下接n行，每行一个整数通输 出(sequence,out)一个整数，表示有多少个S序列的“M序列”是序列m样例样例说明：存在如下四个数列S满足要求:2,2,8,10；1,3,7,11；0,4,6,12；-1,5,5 13 sequence.insequence.out32594数据范围5 0%的数据 n =1 0 0 0,m j =2 0 0 0 01 0 0%的数据 2 =n =1 0 0 0 0 0,m i =1 09连分数(faction.exe)问题描述C i n d y 新学

3、了无理数，老师教她了 一种用有理数逼进无理数的方法：找到这个无理数相应的无限循环连分数。例如，x/5-l _ 1我们可以通过分别取出连分数中的一层、两层、三层、，而忽略其他部分，这样就可以得到一个有理数序列，我们称之为该连分数的渐近分数序列。黄金分割数避二1 的渐近分数是1/1,1/2,2/3,3/5,5/8,8/1 3。2C i n d y 对其中的连分数形式尤为感兴趣，为了简化，她准备研究的连分数都是如下形式的：-:-1P1+-Pn+-j-Pl+Pi+,她用一个简单的记号表示这种连分数：P，P?，P3,P“。例如黄金分割数的连分数简记为 i对于每一个这样的连分数，都有其相应的渐近分数序列：

4、a/b i，a2/b2,o现在C i n d y的研究中出现了一个连分数 PP2，P3,P”，她希望你能帮她求出它的渐近分数序列的第m项。请用二元组(a m，b m)的形式给出答案，并且对于答案的中的两个数，只需要输出它们模9 9 7 3的余数即可。输入(faction.in)第一行为一个整数n,m,分别表示连分数的循环节长度和需要求的渐近分数的项数。下接n行每行一个整数p“描述连分数。输出(faction.out)空格分隔的两个整数a m、b m。样例f a c t i o n.i nf a c t i o n.o u t1618 13数据范围60%的数据，m=105100%的数据，n=10

5、,m=109词 链(link.exe)问题描述给定一个仅包含小写字母的英文单词表，其中每个单词最多包含50个字母。如果一张由一个词或多个词组成的表中，每个单词(除了最后一个)都是排在它后面的单词的前缀，则称此表为一个词链。例如下面的单词组成了 一个词链:ii n ti n t e g e r而下面的单词不组成词链：i n t e g e rintern请在给定的单词表中取出一些词，组成最长的词链。最长的词链就是包含单词数最多的词链。数据保证给定的单词表中，单词互不相同，并且单词按字典顺序排列。输入(link.in)第一行一个整数n,表示单词表中单词数下 接 n 行每行一个单词。输出(link,

6、out)一个整数，表示最长词链长度。样例link.inlink.out5iintintegerinterninternet4数据范围50%的数据，n=1000100%的数据，n=10000Geodetic 集合(geo.exe)问题描述图 G 是一个无向连通图，没有自环，并且两点之间至多只有一条边。我们定义顶点v,u最短路径就是从v 到 u 经过边最少的路径。所有包含在v-u的最短路径上的顶点被称为V-U的 Geodetic顶点，这些顶点的集合记作I(v,u)。我们称集合I(v,u)为一个Geodetic集合。例如下图中，1(2,5)=2,3,4,5),1(1,5)=1,3,5,1(2,4)=

7、2,4。1给定一个图G和若干点对v,u,请你分别求出I(v,u)o输入(geo.in)第行两个整数n,m,分别表示图G的顶点数和边数(顶点编号1-n)下接m行，每行两个整数a,b表示顶点a和b之间有一条无向边。第m+2行有一个整数k,表示给定的点对数。下接k行，每行两个整数v,u。输出(geo.out)共k行，每行对应输入文件中每一个点对v,u,按顶点编号升序输出I(v,u)。同一行的每个数之间用空格分隔。样例geo.ingeo.out561 21 3232435453255 12423 451 3 524数据范围1 0 0%的数据，n =40各题简要分析：sequence 序列：令 S 序列

8、的第一项为k,那么后面几项就可以写成关于k 的多项式:Sl=kS2=2*ml-kS3=2*m2-2*m 1 +k然后根据S 序列的非递减性质，有 S1=S2=S3=.所以有k=2*ml-k2*ml-k=2*m2-2*m 1 +k可以得到n 个关于k 的不等式，而且都是有规律的，可以在O(n)的时间内解出形如a=k=b的结果。由于k 的值和S 序列是一一对应的，所 以 k 的取值的个数(b-a)就是满足要求的S 序列的个数。faction连分数：本题是原创的，重点考察递推和用矩阵乘法优化递推。由递推式：x,1-=-k=(m-1)mod n+1pk+ym-i可得xn,=；y,n=P*y,-i+x，

9、n直接按照这个递推式计算，复杂度O(m),预计得分60%。上面的递推式对应的矩阵运算是：f o 1)(七“，九)=(七”.|，%,1)*p 所以有f o（x,y,“）=（o,i）*c*n._k=n 1 户pj其中c 是(m mod n)部分的余式矩阵的乘积。由于计算矩阵暴时间复杂度为O(logm),所以总的算法复杂度是O(n+logm),预计得分100%。Link词链：本题用动态规划是容易的，设f 表示前i个单词可以构成包含第i个单词的最长词链。F(i)=m a x l,F +1,当 w o r d.是 w o r d i 的前缀)A n s=m a x F(i)这样算法的复杂度是0(/),预

10、计得分50%。其实本题有很简单的贪心算法。用一个栈存储当前的以第i个单词结尾的最长词链，第i+1个单词加在栈的结尾(通过出栈保持栈所存储的是一个词链)。例如：i 栈：ii n t 栈：i i n ti n t e g e r 栈：i i n t i m e r g e ri n t e r n 栈：i i n t i n t e r n (i n t e r g e r 出栈)i n t e r n e t 栈：i i n t i n t e r n i n t e r n e t可以证明，在第i个单词插入后，当前在栈中的词链就是包含第i个单词的最长词链。这样由于每个单词进栈出栈分别一次，所以

11、算法的复杂度是O(n)贪心算法预计得分1 0 0%Geodetic 集合：本题是由p k u上一道试题改编的，考察图的有关知识。算法就是从每个点出发进行B F S扩展，按得到的BFS序列进行递推。设m i n i,j 为从i到j的最短路长度设f i,j 表示从i到j点的最短路覆盖的节点集合，f i,j =f i,k U j k=l.n a n d (m i n i,k +l=m i n i,j )a n d (k,j)存在对于输入的每个v,u对，输出f v,u 中的所有点就可以了。模拟二题目名称奖金编码工作求和程序名称Reward,pas/exeEncode.pas/exeWork.pas/e

12、xeSum.pas/exe输入文件Reward.inEncode.inWork,inSum.in输出文件Reward.outEncode.outWork,outSum.out测试点个数5101010时间限制1秒1秒1秒1秒奖 金(Reward.pas/exe)【题目描述】由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出，Yali Company总经理Mr.Z心情好，决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。于是Mr.Z下令召开m 方会谈。每位参加会谈的代表提出了自己的意见：“我认为员工a 的奖金应该比b 高！”Mr.Z决定要找出一-种奖金方案，满

13、足各位代表的意见，且同时使得总奖金数最少。每位员工奖金最少为100元。【输入】第一行两个整数n,m,表示员工总数和代表数；以下m 行 每 行 2 个整数a,b,表示某个代表认为第a 号员工奖金应该比第b 号员工高。【输出】若无法找到合法方案，则 输出“PoorXed”；否则输出一个数表示最少总奖金。【样例输入】2 11 2【样例输出】201【数据范围】80%的数据满足 n=1000,m=2000；100%的数据满足 n=10()00,m=20000o编 码(Encode.pas/exe)【问题描述】DEX国刚刚截获了 KCAJ国与AWAW国之间的S.Messaged D 国 S302情报机构情

14、报员 0072手里正拿着写有K 国与A 国之间Message的文件。“什么？!居然被加密了！”忍不住说道，“K C A J,你会出路的！”幸运的是K 国与A 国此次通讯时间远远超过了 007所估计的3 0 s,因此007又截获了大量的Message。通过对这些Message的研究，007发现了其中的秘密：每一条S.Message原本由8 个 32-bit的正整数N1.N8组成，本来这8 个整数可以由计算机直接破解得出相应的文字。但对于每条信息，K 国与A 国另外使用了不同的密钥M 来再次加密。所 谓“密钥”其实也是一个32-bit的整数，在传递讯息的时候，是将NIXorM、N2XorM、N8X

15、orM、N9 Xor M 这 9 个整数传给对方(其中N 9为 N1N8这 8 个整数的和 Mod 2A32)。有了上面的发现，007马上意识到他可以破解出Message 了！这实在是一个简单的工作，007决定让你也就是他的助手来完成此工作。【输入】输入文件按顺序输入9 个整数N1.N9。每个整数用16进制表示。【输出】输出仅一个数，即密钥M。同样用16进制表示。【样例输入】3 4 4 7 7 b a 2 2e【样例输出】6【数据范围】40%的数据满足M=500；100%的数据满足M _ ）,那么他该如何挑选任务来做呢？你的任务就是求出HG的最少工作时间（即总共有多少时间HG在做任务）。【输入

16、】第一行一个整数n 表示任务数。以下 n 行,每行三个整数 Ti,Ai,Bi。（n=1000,0=Ai,Bi=l）【输出】输出仅一个数，即最少工作时间。【样例输入】315 0 2550 0 9045 15 70【样例输出】50【数据范围】Ti=l,0=Ai,Bi=1200；30%的数据满足n=5；60%的数据满足n=500；100%的数据满足nl,n0；50%的数据满足n=50；100%的数据满足n+m 根据问题建立图论模型，并应用图论知识解题 对邻接表的掌握 对拓扑排序算法的掌握 简单递推简要解答：首先构图，若存在条件“a 的钱比b 多”则从b 引一条有向指向a；然后拓扑排序，若无法完成排序

17、则表示问题无解(存在圈)；若可以得到完整的拓扑序列，则按序列顺序进行递推：设 fi表示第i 个人能拿的最少奖金数；首先所有fi=100(题目中给定的最小值)；然后按照拓扑顺序考察每个点i，若 存 在 有 向 边 则 表 示 fi必须比切 大，因此我们令fi=Max fij，电+1 即可:递推完成之后所有小 的值也就确定了，而答案就等于fl+.+fn,编 码(Encode)出题意图：递推题几乎也是分区联赛的必考题，本题考察选手运用递推思想解题的能力。简要解答：本题目的是求出M,换言之只要确定M 转换成二进制后每一位是0 还 是 1 即可。首先我们把32-bit整数二进制位从低位到高位编号为第1位

18、到第32位；设输入的 9 个整数为 K P A1=N1 XorM,A2=N2 Xor M.A9=N9 XorM；Ai,j=O或 1,表示Ai转化为2 进制后第j 位上的数字；之后类似做竖式加法，设 表 示 计 算 N1-N8的第i 位到第32位的和，且 第 1位到第 i-1位做加法进位到第i 位后余下j,这种情况下8 个数的和是不是可能等于N9。FI,J=O或 1,0 表示不可能，1表示可能。那么如何递推呢？显然我们需要枚举M 的第i 位数字是0 还 是 1：1、M 的第i 位数字是0：则 N1.N9第 i 位上的数字分别为Al,iXorO,A2,i X o rO,A9,i X o rO,我们

19、用来表示;则 根 据 竖 式 加 法 规 则,必 然 有 +B8+J)Mod2=B 9,否则M 第 i 位数字不可能为0；若满足条件，令 X=(Bl+.+B8+J)Div2,则 X 为进位到第i+1位时余下的数,此时取 FI,J=Max FI,J,FI+1,X 2、M 的第i 位数字是1：则 N1.N9第 i 位上的数字分别为Al,iXor 1,A2,i Xor 1,，A9,i Xor 1,我们用 表示；则必然有(Bl+B+.+B网+J)M od2=B9,否则M 第 i 位不能为1；若满足条件,令Y=(B1+B8+J)D iv2,则 Y 为进位到第i+1位时余下的数,此时取 FI,J=Max

20、FI,J,FI+1,Y 边界条件即F33,x=l；在求FI,J时顺便记录FI,J=1时 M 的第i 位 是。还 是 1,则只要求出F1,O=1后，便可根据记录推出M 的具体数值。工 作（Work）出题意图：考察选手对动态规划的掌握简要解答：此题是一道较简单的动态规划问题；设 Fi表示从开始时刻工作到第i 时 刻 初（或者说是第i-l时刻末），当前空闲，目前最少工作时间是多少。若 Fi=无穷大则表示此种情况不可能；设 S表示工作开始的时刻（即最早的一个工作的到达时间），则 FS=O；很容易写出动态规划方程：Fi=Min Fi-Tj+Tj 且 Aj=i-Tj=0,y=2；那么原题即求0 +1+.+

21、(/!1)容易证明：-(y-i)-(y-i)则0勇+1卫+.+(-1产=i-(w-1)一(m-1)A-(w-l)x,-u-)+.+(3-(-1产)_!_(山 _ 0-f-(W -1)根据上式直接高精度计算即可。模拟三一、任务分配图书馆按顺序排列有N 本书需要维护，每本书的总页数不相同。现有M 位员工。可以给每个员工分配连续的一段书籍，让他进行维护。现在的问题是，怎么样分配，工作任务最重（需要维护的页数最多）的人维护的页数尽量少。输入：第一行两个数，N、M o 接下来N 行，每行一个整数，表示一本书的页数。输出：任务最重的人最少需要维护的页数。样例：book.in5332415book.out5

22、数据范围：N=105,M=No 一本书的页数最多1 0 时间限制为1s。二、求逆序对给定一个序列al,a2 a n,如果存在i aj,那么我们称之为逆序对，求逆序对的数目输入：第一行为n,表示序列长度，接下来的n 行，第 i+1行表示序列中的第i 个数。输出：所有逆序对总数.样例：deseq.in43232deseq.out3数据范围:N=10 Ai=105o 时间限制为Is。三、最优乘车某人从起点去目的地开会，期间需要转乘公共汽车，他比较讨厌专车，因此，要求你设计它如何乘车，使得在转车次数最少的情况下，花费最小。已知起点在公交车站1,终点在公交车站N。输入：第一行为二个数n,m,分别表示该城

23、市中的公共汽车站点个数和线路的条数。接下来的一个n*n维矩阵D,分别描述了这个城市n 个站点的交通网络。数 字 0表示没有连通，非 0 数字表示两个站点之间的直达距离。每条道路都是双向的，也就是数据保证D产小评接下来的m 行，每行由若干不超过n 的整数组成，描述了一条公共汽车的行车线路。每条公交车线路都是往返行驶。输出：第一行为最少转车次数第二行为最少乘车代价（乘车距离最短）。样例：bus.in320 1 31 0 13 1 01 233 1bus.out1 2数据范围:N=1000o M=100o时间限制为5s0四、营救铁塔尼号遇险了！他发出了求救信号。距离最近的哥伦比亚号收到了讯息，时间就

24、是生命，必须尽快赶到那里。通过侦测，哥伦比亚号获取了一张海洋图。这张图将海洋部分化成n*n个比较小的单位，其中用1标明的是陆地，用 0 标明是海洋。船只能从一个格子，移到相邻的四个格子。为了尽快赶到出事地点，哥伦比亚号最少需要走多远的距离。输入：第一行为n,下面是一个n*n的 0,1矩阵，表示海洋地图最后一行为四个小于n 的整数，分别表示哥伦比亚号和铁塔尼号的位置。输出：哥伦比亚号到铁塔尼号的最短距离，答案精确到整数。样例：save.in30011011001133save.out4数据范围：N=1000o时间限制为Iso模拟四本套试题所有题目的空间限制都为512MB。1,2,4 题时间限制都

25、为1s,3 题时间限制为2s第一题：moneyDog同学喜欢去购物，但是他不想花很多钱，所以他总是挑那些打折的东西来买，现在给出他买的所有东西的一个购物清单，以及每个物品打几折，问他这次购物一共花了多少钱？输入文件(money.in)第一行一个 n(lv=n=100)表示dog 一共买了多少个东西。后面紧接n 行，每行描述购买的一种物品：每行 2 个整数 ai,bi(l=ai=10000,l=bi=10)输出文件(money.out)一行，一个实数为dog一共花了多少钱，答案保留2 位小数样例Input：210000 10Output：10000.10第二题：sqrt给出一个正整数n(ln=2

26、A31-l),求 当 x,y 都为正整数，方程sqrt(n)=sqrt(x)-sqrt(y)的解中，X的最大值是多少？输入 文 件(sqrt.in)一行，一个正整数n输出文件(sqrt.out)一行，一个满足条件的最大的x 的解。样例:i n p u t4o u t p u t9第三题：work当前有n （n j=fi-lJlj-l J or 如果当前第i 个事件点是事件开始点fi-lj+k 如果当前第i 个事件点是事件结束点k 是能够完成事件点所代表的事件的工人标号最后输出f2*n0number:主要考察构造首先是要构造出整个序列。这里使用2 个指针就可以完成。指针i,j分向指在当前序列中的

27、某个位置，初始指向1每次判断2*i+l与 4*j+5的大小关系，取小的那个放在当前序列的最后一个，并将其所代表的指针向后推移位直到构造完毕。然后进行删除操作。这个问题在以前的某年的noip试题中出现过，这里不做过多赘述。模拟五1诸侯安置【问题描述】很久以前，有一个强大的帝国，它的国土成正方形状，如 图22所 示。源程序名empire.?(pas,c,cpp)可执行文件名empire.exe输入文件名empire.in输出文件名empire.out这个国家有若干诸侯。由于这些诸侯都曾立下赫赫战功，国王准备给他们每人一块封地(正方形中的一格)。但 是，这些诸侯又非常好战，当两个诸侯位于同一行或同一

28、列时，他们就会开战。如 下 图23为n=3时的国土，阴影部分表示诸侯所处的位置。前两幅图中的诸侯可以互相攻击，第三幅则不可以。国王自然不愿意看到他的诸侯们互相开战，致使国家动荡不安。因此，他希望通过合理的安排诸侯所处的位置，使他们两两之间都不能攻击。现 在，给 出 正 方 形 的 边 长n,以及需要封地的诸侯数量k,要求你求出所有可能的安置方 案 数。(nWlOO,kW2n2-2n+l)由于方案数可能很多，你只需要输出方案数除以504的余数即可。【输 入】仅一行，两 个 整 数n和k,中间用一空格隔开。【输 出】一个整数，表 示 方 案 数 除 以504的余数。【样 例】empire.in e

29、mpire.out22 4【样 例 说 明】2取火柴游戏【问题描述】输 入k及k个整数n l,n 2,，n k,表示有k堆火柴棒，第i堆火柴棒的根数为n i；源程序名m a t c h.?(pa s,:,c pp)可执行文件名m a t c h.e xe输入文件名m a t c h.in输出文件名m a t c h.o u t接着便是你和计算机取火柴棒的对弈游戏。取的规则如下：每次可以从一堆中取走若干根火柴，也可以一堆全部取走，但不允许跨堆取，也不允许不取。谁取走最后一根火柴为胜利者。例如：k=2,m=n 2=2,A代表你，P代表计算机，若决定A先取:A：(2,2)-*(1,2)P：(1,2)

30、7 1,1)A：(1,1)一(1,0)P：(1,0)-(0,0)如果决定A后取：P：(2,2)7 2,0)A：(2,0)-0,0)从一堆中取一根 从另一堆中取一根 P胜利 A胜利又如 k=3,n l=l,n2=2,n 3=3,A 决定后取:P：(1,2,3)-(0,2,3)A：(0,2,3)f(0,2,2)A已将游戏归结为(2,2)的情况，不管P如何取A都必胜。编一个程序，在给出初始状态之后，判断是先取必胜还是先取必败，如果是先取必胜,请输出第一次该如何取。如果是先取必败，则输出“lo s e”。【样 例1】m a t c h.in33 6 9【样例2】m a t c h.o u t4 3 表

31、示第一次从第3堆取4个出来，必胜3 6 5 第一次取后的状态m a t c h.in41 5 2 2 1 9 1 0m a t c h.o u tlo s e 先取必败3地毯填补问题源程序名可执行文件名输入文件名输出文件名blank.?(pas,c,cpp)blank.exeblank.inblank.out【问题描述】相传在一个古老的阿拉伯国家里，有一座宫殿。宫殿里有个四四方方的格子迷宫，国王选择驸马的方法非常特殊，也非常简单：公主就站在其中一个方格子上，只要谁能用地毯将除公主站立的地方外的所有地方盖上，美丽漂亮聪慧的公主就是他的人了。公主这一个方格不能用地毯盖住，毯子的形状有所规定，只能有

32、四种选择（如图4 T）：(1)(2)(3)(4)并且每一方格只能用一层地毯，迷宫的大小为（2,2 的方形。当然，也不能让公主无限制的在那儿等，对吧？由于你使用的是计算机，所以实现时间为1s。【输入】输入文件共2 行。第一行：k,即给定被填补迷宫的大小为2k（0 d2,.,w,dn,所有的数不超过100。第三行 i?个数，a,.i，a,.2 ,a,n,a2.i，a2,2，a2,n,an,i，an,2.,an,n,所有的数都不超过10。af,如果i=j,则知=0。【输出】仅一行，输出所有可能获得冠军的球队，按其编号升序输出，中间用空格分隔。【样 例 1】kleague.in320 1 1020 2

33、 2 2 0 2 2 2 0【样例2】kleague.in34 0 2 2 0 40 1 1 1 0 1 1 1 0【样例3】kleague.in40 3 3 1 1 3 3 00 0 0 2 0 0 1 0 0 1 0 0 2 0 0 0kleague.out123kleague.out1 2kleague.out245小木棍源程序名可执行文件名输入文件名输出文件名stick.?(pas,c,cpp)stick.exestick.instick.out【问题描述】乔治有些同样长的小木棍，他把这些木棍随意砍成儿段，直到每段的长都不超过50。现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开

34、始时有多少根木棍和它们的长度。给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。【输入】输入文件共有二行。第一行为一个单独的整数N 表示看过以后的小木柜的总数，其 中 N W 60,第二行为N个用空个隔开的正整数，表示N 跟小木根的长度。【输出】输出文件仅一行，表示要求的原始木棍的最小可能长度。【样例】stick.in95 2 1 5 2 1 5 2 1stick.out66 平板涂色【问题描述】源程序名p a int.?(p a s,c,cp p)可执行文件名p a int.ex e输入文件名p a int.in输出文件名p a int.outCE数码公司开发 了 一 种 名 为 自

35、动涂色机(APM)的产品。它能用预定的颜色给一块由不同尺寸且互不覆盖的矩形构成的平板涂色。X 0 1 2 3 4 5 60B lue(A)Red(B)R ed(D)B lueB lue(E)(c)R ed(G)B lue(F)23456为了涂色，APM需要使用一组刷子。每个刷子涂一种不同的颜色C。APM拿起一把有颜色C的刷子，并 给 所 有 颜 色 为C且符合下面限制的矩形涂色：为了避免颜料渗漏使颜色混合，一个矩形只能在所有紧靠它I：方的矩形涂色后，才能涂色。例 如 图 中 矩 形F必 须 在C和D涂色后才能涂色。注 意，每一个矩形必须立刻涂满，不能只涂一部分。写 一 个 程 序 求 一 个

36、使APM拿起刷子次数最少的涂色方案。注 意，如果一把刷子被拿起超过一次，则每一次都必须记入总数中。【输 入】文 件p a int.in第 行 为 矩 形 的 个 数N。下 面 有N行描述了 N个矩形。每 个 矩 形 有5个整数描述，左上 角 的y坐 标 和x坐 标，右 下 角 的y坐 标 和x坐 标，以及预定颜色。颜 色 号 为1到20的整数。平板的左上角坐标总是(0,0)。坐 标 的 范 围 是0.9 9。N小 于1 6 o【输 出】输 出 至 文 件p a int.out,文件中记录拿起刷子的最少次数。【样 例】p a int.in p a int.out730022 10 2 1 6 2

37、2042 1124421 436 14064 134662模拟试题说明1诸侯安置【算法分析】重新描述一下问题,其实就是在一个边长为2 n-l的正菱形(如上图2-2为n=3的情形)匕摆放k个棋子，使得任意两个棋子都不在同行、同一列。试问：这样的摆法共有多少种?看到这道题目，我们就会立即想起一道经典的老题目：n皇后问题。这道题目与n皇后问题非常相似。但有两个不同点：一是n皇后问题可以斜着攻击对方棋子，而本题不能；二是n皇后问题是在n,n的正方形棋盘上面放置k个皇后，而本题却是在一个正菱形上摆放。我们试着先将n皇后变为不可斜攻的，再作思考，如果不能够斜着攻击，n皇后的公式是：(C(k,n)2*k!。

38、但是本题不是一个正方形，所以这个公式对本题好像没有任何帮助。看来只能够从另外一个角度思考问题了。首先想到在2nT列中任意取出k列进行具体分析，这样一来问题就转化成：有一个长为k的数列(无重复元素)，每一个数在一个不定的区间当中，第i个数一定在区间M b 之间，求这样的数列有多少种?如果就是这个问题，那么比较难解决，但若把这个数列放在本题中，就比较简单。因为题目中任意两个区间都是一种包含关系。可以先把区间按照长度排 下序，就可以看出来，再用乘法原理进行求解即可。但是，n最多可到1 00,k最多可到5 0,穷举要进行C(5 0,1 00)种方案！显 然 无 法 在 规 定 的 _ _ _ _时间内

39、出解!那么怎么办呢?再继续分析一下问题发现，里面有重叠子问题。匚 匚 工如果一个列作为最后一列，且这一列以及前面所有列共放置p个诸侯，设有q种情况，那么这一列后面的所有列共放置p+1个棋子的方案数都要用 L_到q，从而引用乘法原理。而且在穷举过程中，这一个工作做了许多遍，所以干脆用递推。递推前，先把图形转化为类似图2-5的形式(即列排序)。设f i,j 表示以第i列为最后一列，放置j个棋子的总方案数，得出公式：川，刃=加 一Z，JT*(i7+l)A=1不过还要注意，当k 2 2 n-l时，问题无解。2 取火柴游戏【算法分析】从问题的描述分析，可以将问题中的k堆火柴棒抽象为k个非负整数，而每取一

40、次火柴棒可抽象为使其中的一个自然数变小，当所有的数都变为o时，游戏结束，最后一次取火柴棒的人为胜方。当k较小，且k堆火柴棒也都较小时，可使用递推的方法来处理这个问题，具体做法是从终了状态(全零)反推出初始状态的值是先取必胜还是先取必败，因为某一状态的值可以从它的所有的取一次后的下一状态得到，如果某状态的所有的下一状态都为先取必败，则这一状态为先取必胜，否则为先取必败。但 当k和n i都很大时，上述方法很难行得通，为了解决这个问题，首先引进关于n个非负整数的奇偶状态的定义：如果把n个非负整数都化成二进制数，然后对n个二进制数按位相加(不进行进位)，若每一位相加的结果都为偶数,则称这n 个非负整数

41、的状态为偶状态，否则称之为奇状态。可以证明：任何一个偶状态在某一个数变小后一定成为奇状态，而对任何一个奇状态，必定可以通过将某一个数的值变小，使得改变后的状态成为偶状态。前一种情况是显然的，因为一个数变小以后其对应的二进制数至少有一位发生改变。这一位的改变就破坏了原来的偶状态。后一种情况可以通过构造的方法来证明，首先对任何一个奇状态，从高位向低位寻找到第一位按位加之和为奇数的二进制位，设这一位为第k 位，则 n 个数的对应的二进制数中至少存在一个数，其第k 位 为 1,将这个二进制数的第k位变成0,则所有二进制数的第k 位上的数字之和就变成了偶数。然后再对这个数的比k 位低的所有位作如下调整：

42、如果所有二进制数在该位按位加之和为偶数，则不改变该位的值，否则改变该数在该位的值，若原来的值为0,则改为1,若原来的值为1,则改为0,这样就构造出了一个偶状态，并且被改变的那个数一定变小了，因为这个数被改变的所有二进制位中的最高位从1变成了 0 o如 n=3时，三堆火柴棒的数量分别为3,6,9,则 3=(0 0 1 1)2,6=(0 1 1 0)2,9=(1 0 0 1)2;最高位之和为1,其中9对应的二进制数的最高位为1,将其变为0,次高位之和也是1,9对应的二进制数的次高位为0,根据证明过程将其变为1,最后二位数字之和均为偶数，无需作任何改变，这样 9=(1 0 0 1)2 被变成了(0

43、1 0 1)2=5,显然，3=(0 0 1 1)2,6=(0 1 1 0)2,5=(0 1 0 1)2是一个偶状态。有了前面的分析，一种贪心算法就出来了。程序中用n个包含1 6 个元素的数组(线性表)来存放对每个非负整数对应的二进制数，如 b i,0 存放第i 个数的最低位，n 个数的状态取决于它们对应的二进制数的各位数字之和的奇偶性，而各位数字之和的奇偶性只需用0和 1 来表示，0表示偶，1 表示奇。最后的状态(全0)为偶状态，所以开始状态为偶状态时，先取必败，因为先取后局面变成了奇状态，后取方一定可将字取成偶状态，直至取光为止。反之则先取必胜。【后记】大家都知道国际象棋特级大师卡斯帕罗夫与

44、I B M 公司研制的“深蓝”超级计算机进行国际象棋人机大战的事吧！有了以上算法后，我们也可以编写出这样一个游戏程序。让程序代表计算机与人做取火柴棒游戏，由人或计算机先取，要求你编的程序能够尽可能使计算机获胜。3地毯填补问题【知识准备】分治思想和递归程序设计。【算法分析】拿到这个问题后，便有一种递归重复的感觉。首先对最简单的情况(即k=D 进行分析:公主只会在4个方格中的一个：左上角：则使用3 号毯子补，毯子拐角坐标位于(2,2)；下面就简称为毯子坐标左下角：则使用2 号毯子补，毯子拐角坐标位于(1,2)；右上角：则使用i 号毯子补，毯子拐角坐标位于(2,1)；右下角：则使用4号毯子补，毯子拐

45、角坐标位于(1,1)；其实这样不能说明什么问题,但是继续讨论就会有收获,即讨论k=2 的情况(如图4-1)：#O#OO#我们假设公主所在的位置用实心圆表示，即上图中的（1,4）,那么我们就可以把1号毯子放在（2,3）处，这样就将（1,3）至（2,4）的k=l见方全部覆盖（#表示地毯）。接下来就是3个k=l的见方继续填满，这样问题就归结为k=l的情况了，但是有一点不同的是：没有“公主”了，每一个k=l的小见方都会留下一个空白（即上图中的空心圆），那么空白就有：1*3=3个，组合后便又是一个地毯形状。好了，现在有感觉了吧，我们用分治法来解决它！对于任意k l的宫殿，均可以将其化分为4个k/2大小的

46、宫殿，先看一下公主站的位置是属于哪块，因为根据公主所在的位置，我们可以确定中间位置所放的毯子类型，再递归处理公主所站的那一块，直到出现边界条件k=l的情况，然后在公主边上铺上一块合适的地毯，递归结束。由于要递归到每一-格，复杂度就是面积，就是O（22*k*k）。4 K-联赛【算法分析】看一个队是否有希望夺冠，首先，这个队此后的比赛自然是赢越多越好，所以先让这个队把以后的比赛都赢下来，算出这个队最高能拿多少分。下面关键就看是否有可能让其他队的积分都低于刚才计算出的最高分。建立一个网络，所有的球队作为图中的节点，每两个队之间的比赛也作为图中的节点。从网络的源各连一条边到“比赛的节点”，容量为两队间

47、还剩的比赛场数。从“每个队的节点”都连一条边到网络的汇，容量为这个队当前的积分与最高分之差。如果一个“比赛的节点”代表的是A与B之间的比赛，那么从这个节点连两条边分别到“A队的节点”和“B队的节点”，容量为无穷大。如果这个网络的最大流等于所有还未进行的比赛的场次之和，那么需要我们判断的那个队抗有可能夺得冠军。本题要我们找出所有可能夺冠的队，那么只需枚举所有的球队，判断它们是否有可能夺冠即可。5小木棍【问题分析】搜索的顺序是枚举原始木棍的长度，从小到大或从大到小均可。但注意从大到小枚举的时候，可以剪枝，如果长度为k L的原始木棍尝试失败的话，长度为L的就不必尝试了，因为必然也是失败的。得到了原始

48、木棍的长度后，一个一个的去枚举拼它的方案。注意，枚举要按字典序，举个例子说，就是不允许出现第一个木棍是由第2、5、6个小木棍拼成，而第二个木棍是由第1、3、4个小木棍拼成（2、5,6的字典序大于1、3、4）枚举的过程中，有一个比较强的剪枝：如果放入一个长度为len的小木棍后，正好拼成了一个原始长度的木棍，但是拼后面的木棍失败，那么就没有必要再枚举比len短的木棍了。因为一段整空间被一个刚好长度的木棍去填总是不亏的。（为方便起见，可以事先将小木棍降序排列）6平板涂色【问题分析】指数型动态规划。由于N 小 于 1 6,故可以以一个N-bit的二进制数A 作为状态，其中每个二进制位表示一个格子的涂色

49、情况，二进制位0 表示该格子未被涂色，二进制1表示该格子已被涂色。用 FA表示要得到状态A,最少需要改变多少次颜色。对于每个状态A,通过枚举涂色方案来推新的状态。模拟六1 单向双轨道【问题描述】源程序名track.?(pas,c,cpp)可执行文件名track.exe输入文件名track.in输出文件名track,out如 图 所 示1,某 火 车 站 有B,C两个调度站，左边入口 A处 有n辆火车等待进站(从左到 右 以a、b、c、d编 号)，右边是出口 D,规定在这一段，火 车 从A进 入 经 过B、C只能从左向右单向开，并 且B、C调度站不限定所能停建的车辆数。入 n11口A-B-C-D

50、从 文 件 输 入n及n个小写字母的一个排列，该排列表示火车在出口 D处形成的从左到右的火车编号序列。输出为一系列操作过程，每 一 行 形 如“h L R”的字母序列，其 中h为火车编号，L为h车 原 先 所 在 位 置(位置都以A、B、C、D表示)，R为新位置。或者输出N O 表示不能完成这样的调度。【输 入】一 个 数n(lnm),费用需s 分(sf)。在每天结束时，餐厅必须决定多少块用过的餐巾送到快洗部，多少块送慢洗部。在每天开始时，餐厅必须决定是否购买新餐巾及多少，使洗好的和新购的餐巾之和满足当天的需求量 R i,并使N天总的费用最小。【输入】输入文件共3 行，第 I 行为总天数；第