英才IT群囧花提升练习题1动态规划.doc

英才IT群囧花提升练习题1 动态规划 共四题 满分400分 （请选手务必仔细阅读本页内容） 完成时限3小时（180min） 题目概况 中文题目名称 字串距离 血缘关系 尼克的任务 书的复制 英文题目与子目录名 blast family lignja book 可执行文件名 blast.exe family.exe lignja.exe book.exe 输入文件名 blast t.in family.in lignja.in book.in 输出文件名 blast.out family.out lignja.out book.out 每个测试点时限 1秒 1秒 1秒 1秒 测试点数目 10 6 10 10 每个测试点分值 10 10(2)/20(4) 10 10 附加样例文件 有 有 有 有 结果比较方式 全文比较（过滤行末空格及文末回车） 题目类型 传统 传统 传统 传统 二．提交源程序文件名 对于pascal 语言 blast.pas family.pas lignja.pas book.pas 对于 C 语言 blast.c family.c lignja.c book.c 对于 C++语言 blast.cpp family.cpp lignja.cpp book.cpp 三．编译命令（不包含任何优化开关） 对于pascal 语言 fpc blast.pas fpc family.pas fpc lignja .pas fpc book .pas 对于 C 语言 gcc –o blast blast.c -lm gcc –o family family.c –lm gcc –o lignja lignja .c –lm gcc –o book book .c -lm 对于 C++语言 g++ -o blast blast.cpp –lm g++ -o family family.cpp –lm g++ -o lignja lignja .cpp –lm g++ -o book book .cpp -lm 四．运行内存限制 内存上限 64M 64M 64M 64M 五. 注意事项： 1、文件名（程序名和输入输出文件名）必须使用英文小写。 2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。 3、全国统一评测时采用的机器配置为：CPU P4 3.0GHz，内存 1G，上述时限以此配置为准。各省在自测时可根据具体配置调整时限。 4、本套练习题难度系数0.5较难，最低要求200分。不统一提供标准题解，若需要请自行私聊管理员或度娘一下。 5、组题：哥不是猥琐男，本套试题最终解释权归哥不是猥琐男所有。 1.字串距离 （blast.pas/c/cpp） 【问题描述】 设有字符串X，我们称在X的头尾及中间插入任意多个空格后构成的新字符串为X的扩展串，如字符串X为”abcbcd”，则字符串“abcb□cd”，“□a□bcbcd□”和“abcb□cd□”都是X的扩展串，这里“□”代表空格字符。 如果A1是字符串A的扩展串，B1是字符串B的扩展串，A1与B1具有相同的长度，那么我扪定义字符串A1与B1的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的ASCII码的差的绝对值，而空格字符与其他任意字符之间的距离为已知的定值K，空格字符与空格字符的距离为0。在字符串A、B的所有扩展串中，必定存在两个等长的扩展串A1、B1，使得A1与B1之间的距离达到最小，我们将这一距离定义为字符串A、B的距离。 请你写一个程序，求出字符串A、B的距离。 【输入】 输入文件名为blast.in，第一行为字符串A，第二行为字符串B。A、B均由小写字母组成且长度均不超过2000。第三行为一个整数K（1≤K≤100），表示空格与其他字符的距离。 【输出】 输出文件名为blast.out，仅一行包含一个整数，表示所求得字符串A、B的距离。 【输入输出样例】 blast.in blast.out cmc snmn 2 10 【数据范围】 对于100%的数据有1≤K≤100。 2.血缘关系 （family.pas/c/cpp） 【问题描述】 我们正在研究妖怪家族的血缘关系。每个妖怪都有相同数量的基因，但是不同的妖怪的基因可能是不同的。我们希望知道任意给定的两个妖怪之间究竟有多少相同的基因。由于基因数量相当庞大，直接检测是行不通的。但是，我们知道妖怪家族的家谱，所以我们可以根据家谱来估算两个妖怪之间相同基因的数量。 妖怪之间的基因继承关系相当简单：如果妖怪C是妖怪A和B的孩子，则C的任意一个基因只能是继承A或B的基因