USACO三月份试题

1、USACO三月份试题简体中文版本*Byxzh华丽的分割线*青铜组问题华丽的分割线*11到14*华丽的分割线*问题11：极品飞车贝西正在为一场即将到来的大奖赛准备她的赛车。她希望购买一些部件来提高这辆赛车的性能。他的赛车质量为M(1<=M<=1,000)，加速度为(1<=F<=1,000,000)。在赛车的配件店有N(1<=N<=20)个零件，编号分别为1到N。只要他愿意，贝西可以买任意多个或者任意少个零件。第P_i个零件增加加速度F_i(1<=F_i<=1,000,000)，同时重量为M_i(1<=M_i<=1,000)。根据牛顿第二

2、定律，F=MA，F为加速度，M为质量，A为速度。为了使她的赛车最大限度的发挥它的加速度的同时减少重量，她应该安装哪些组件？假设一辆赛车，他的初始加速度为1500，初始重量为100，有四种零件可以选择：iF_iM_i1 250252 15093 1205如果只添加零件2，他的速度将是(1500+150)/(100+9)=1650/109=15.13761下面是一个表格，表现了添加或不添加不同的零件后赛车的速度。一个表格，表现了添加或/、添加/、同的零件后赛车的速度。(0表示未添加，1表示已添加)部件总和总和1234FMF/M0000150010015.00000001170010815.7407

3、0010162010515.42860011182011316.10620100165010915.13760101185011715.81200110177011415.52630111197012216.1475<-最高的F/M1000175012514.00001001195013314.66171010187013014.38461011207013815.00001100190013414.17911101210014214.78871110202013914.53241111222014715.1020最终，最佳的方案是选择2，3和4号部件问题名称:boost输入格式：第一行

4、：三个整数：F,M和N从第二行到第N+1行：第I+1行有两个整数：F_i和M_i样例输入：（文件boost.in）:1500100425025150912052008输出格式第一到P行：P个贝西应该给他的赛车增加的额外部件的编号，每个一行。如果一个也不要增加，输出NONE（不带引号）。输出顺序应该是递增，因此，如果零部件的最优解集为（2,4,6,7），那么输出应为2,4,6,7，而不是例如4,2,7,6之类的。样例输出：（文件boost.out）：23*华丽的分割线*问题12：传说中的十六进制转换贝西在给杰西上课。她在讲一些关于二进制的有趣的事实。一般来说计算机所有数字存储为0和1。杰西对于这

5、些有一些不清楚，于是贝西给他做了以下的练习：编写一个程序，把一个一个无符号的十六进制数转换成八进制（基数为8）的形式。十六进制数最多只能有100000个数字，包含数字和大写字母从A至F。注意！十六进制数是一种特殊的表示数字的方式（基数为16）。0-9的数字仍符合0-9，然后A（大写A!）代表10,B代表11,等等（到F为止）。例如，十六进制数A10B对应的十进制是10*16人31*16人20*1611*1=41227。相应的八进制（基数为8）是120413,即1*8A52*8A40*8A34*8A23*1*=41227。提示：有一个更简单的方法从十六进制转换为八进制数比起从十六进制转换到十进制

6、再到八进制。你可以试一试二进制（基数为2）。问题名称：hex输入格式：第一行：一个十六进制数。前面没有多余的0（即A1，而不是00A1）。0本身是一个有效的输入。样例输入：（文件hex.in）：123ABC输出格式：第一行：一个前面没有多余零的八进制值。如果输入为0，输出也应为0。样例输出(文件hex.out)：4435274*华丽的分割线*问题13MasterMind杰西正在了解在“贝西的膝盖”节目比赛。“他们在玩游戏吗？”她问。“噢，是的，”贝茜一本正经地点头。“这是一个经典的游戏。”MasterMind是一个典型的多人游戏。一个玩家是Codemaker，她挑选一个四位数字的秘密数S(10

7、00<=S<=9999)。另一个玩家是Codebreaker'。他将猜测这四个数字可能是什么。直到他找到了正确的答案。每个Codebreaker猜测G_i(1000<=G_i<=9999)时，Codemaker将提供一些提示，包括两个整数。第一个整数C_i(0<=C_i<=4)指定了多少猜测的数字是正确的，而且他们在秘密号码中正确的位置第一个整数W_i(0<=W_i<=4-C_i)指定了多少猜测的数字是正确的，但是不属于C_i，因为他们在秘密号码中错误的位置。Code maker例如，假设Codemaker的秘密号码是2351。如果密码破

8、译者猜测1350将提供反馈21，因为3和5是在正确的位置的数目，然而1在错误的位置。又例如，如果秘密号码是11223（在位数为五的版本）和猜测是12322，则反馈将是22。下面是一个示例游戏，秘密号码是2351：猜测的值|正确的数字正确的位置|正确的数字错误的位置315712135021612002238130235140对于这个任务，您将得到N（1<=N<=100）与在游戏中他们的猜测和反馈。要求输出最小的四位数字，可以是一个候选的Codemaker的秘密代码（即，它满足所有条件）。如果没有这样的数字，输出NONE（不带引号）。输入格式：第1行：一个整数：N第二行到第N+1行：一

9、个猜测的值以及Codemaker的反馈。表现为空格分隔的整数：G_i，C_i和W_i。样例输入（文件mmind.in）：315712135021612002238130输出格式：*第1行：单个的整数，是最小的四位数的可能的秘密代码。如果没有这样的数字，输出一行包（秘密整数的范围：1000.9999）含单词NONE（没有引号）。样例输出（文件mmind.out）：2351*华丽的分割线*14最长公共子串贝西的朋友杰西想进入编程竞赛。贝西，她知道这么多。她说：“这是一个典型的公共子串问题，早在很久以前就有了。看看个典型的公共子串问题，早在很久以前就有了。看看你是否能解决这个问题。“也许你能做到！“

10、这个任务是什么？“她问道。您将得到两个整数以及S1和S2这两个序列。S1的长度为L1(1<=L1<=180)，而S2的长度为L1(1<=L1<=180)。你的工作是打印出最长公共子串的长度。S1和S2只含有普通的数字。有序序列S1的元素分别为S1_1，S1_2，.，S1_L1(-100<=S1_i<=100);S2的元素分别为S2_1，S2_2，.，S2_L1(-100<=S2_i<=100)。一个字串是指数字连续没有中断的序列。比如说1231的字串有空序列，“1”，“12“123”，“1234”，“2”，“23”，“231”，“3”和“31”问题名称：Sub输入格式：第一行：两个用空格分隔的整数：L1和L2第二行到第L1+1行：每一行中包含一个整数：S1_i第L1+2行到第L1+L2+1行：每一行中包含一个整数：