英才it群囧花提升练习题1动态规划

《英才it群囧花提升练习题1动态规划》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、英才IT群冏花提升练习题1动态规划共四题满分400分（请选手务必仔细阅读本页内容）完成时限3小时（180min）一.题目概况中文题目名称字串距离血缘关系尼克的任务书的复制英文题目与子目录名blastfamilylignjabook可执行文件名blast.exefamily.exelignja.exebook.exe输入文件名blastt.infamily.inHgnja.inbook.in输出文件名blast.outfamily.outlignja.outbook.out每个测试点时限1秒1秒1秒1秒测

2、试点数目1061010每个测试点分值1010(2)/20(4)1010附加样例文件有有有有结果比较方式全文比较（过滤行末空格及文末回车）题目类型传统传统传统传统二.提交源程序文件名对于pascal语言blast.pasfamily.paslignja.pasbook.pas对于C语言blast.cfamily.clignja.cbook.c对于C++语言blast.cppfamilyxpplignja.cppbook.cpp三.编译命令（不包含任何优化开关）对于pascal语言fpcblast.pasf

3、pcfamily.pasfpclignja.pas^pcbook.pas对于C语言gcc-oblastblast.c-lmgcc-ofamilyfamily.c-lmgcc-olignjalignja.c-lmgcc-obookbook.c-lm对于C++语言g++-oblastblast.cpp-lmg++-ofamilyfamily.cpp-lmg++-olignjalignja.cpp-lmg++-obookbook.cpp・lm四.运行内存甲制内存上限64M64M64M64M内存上限~64M64

4、M64M64M五.注意事项：1、文件名（程序名和输入输出文件名）必须使用英文小写。2、C/C++中函数mainO的返冋值类型必须是int,程序正常结束时的返冋值必须是Oo3、全国统一评测时采用的机器配置为：CPUP43.0GHz,内存1G,上述时限以此配置为准。各省在自测时可根据具体配置调整时限。4、木套练习题难度系数0.5较难，最低要求200分。不统一提供标准题解，若需要请自行私聊管理员或度娘一下。5、组题：哥不是猥琐男，本套试题最终解释权归哥不是猥琐男所有。1•字串距离(blast・pas/c/cp

5、p)【问题描述】设有字符串X,我们称在X的头尾及屮间插入任意多个空格后构成的新字符串为X的扩展串,如字符串X为”abcbcd”，则字符串“abcbUcd”，“□adbcbcd口”和“abcbDcd□”都是X的扩展串，这里“□”代表空格字符。如果A1是字符串A的扩展串，B1是字符串B的扩展串，A1与B1具有相同的长度，那么我扪定义字符串A1与B1的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的ASCII码的差的绝对值，而空格字符与其他任意字符Z间的距离为已知的定值K,空格字符与空格字

6、符的距离为0。在字符串A、B的所有扩展串中，必定存在两个等长的扩展串Al、B1,使得A1与B1之间的距离达到最小，我们将这一距离定义为字符串A、B的距离。请你写一个程序，求出字符串A、B的距离。【输入】输入文件名为blastin,第一行为字符串A,第二行为字符串B。A、B均由小写字母组成且长度均不超过200()。第三行为一个整数K(IWKWIOO),表示空格与其他字符的距离。【输出】输出文件名为blast.out,仅一行包含一个整数，表示所求得字符串A、B的距离。【输入输出样例】blast.inblas

7、t.outcmc10snmn2【数据范围】对于100%的数据有1WKW100。2.血缘关系(family.pas/c/cpp)【问题描述】我们正在研究妖怪家族的血缘关系。每个妖怪都有相同数量的基因，但是不同的妖怪的基因可能是不同的。我们希望知道任意给定的两个妖怪Z间究竟有多少相同的基因。由于基因数量相当庞大，直接检测是行不通的。但是，我们知道妖怪家族的家谱，所以我们可以根据家谱来估算两个妖怪之I'可相同基因的数量。妖怪之间的基因继承关系相当简单：如果妖怪C是妖怪A和B的孩子，则C的任意一个基因只能是继承

8、A或B的基因，继承A或B的概率各占50%o所有基因可认为是相互独立的，每个基因的继承关系不受别的基因影响。现在，我们来定义两个妖怪X和Y的基因相似程度。例如，有一个家族，这个家族中有两个亳无关系(没有相同基因)的妖怪A和B,及它们的孩子C和D。那么C和D相似程度是多少呢？因为C和D的基因都來自A和B,从概率来说，各占50%o所以，依概率计算C和D平均有50%的相同基因，C和D的基因相似程度为50%。需要注意的是，如果A和B之间存在相同基因的