试题解析1_试题及解析一

试题解析1由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“试题及解析一”。

试题解析

题1：

方法1：枚举第2站上车人数b，然后模拟递推。

方法2：找数学规律

为了找规律，我们建立一个表。

站号123456

开车时人数num[]aa2a2a+b 3a+2b 4a+4b

上车人数in[]aba+b a+2b 2a+3b 3a+5b

下车人数out[]0bba+ba+2b2a+3b

规律出来了，设第k(k>=3)站时

上车人数为：f[k-2]a+f[k-1]b

(f[k]={1,1,2,3,5,8,13,21..}为fibonacci数列)

设：第n-1站开车时人数为m,第x站开车时的人数p。

即：

m=(f[n-3]+1)a +(f[n-2]-1)b(2)

p=(f[x-2]+1)a +(f[x-1]-1)b(3)

从(2)解得b,代入(3)计算知

题2：贪心法

极易犯的错误：按整数对应的字符串大到小连接。

反例： 12 121 应该组成12121而非12112

正确贪心标准：如果a后接b比b后接a大，就说“a>b”。直接输出排序结果。

题3

（1）解状态是一个K元组(v1,v2,v3..vk),不妨设：v1

递归搜索就可以了。

注意确定V1，V2…VK的上界！（若假定N=3）

V1=1，V2：可以从2、3……，其上界为N+1（若假定N=3，则上界P2=4,因为若V2=5，则4无法获得）

V3：上界为N*P2+1（若假定N=3，则上界P3=13）

（2）本题的难点是如何计算最大连续值（以下成为Q值）。

一个容易想到的方法是枚举所有的取法，求出可以取到的最大值，再求Q值，简单，但是效率不高。

另解：动态规划

设：F[I，J，K]：表示考虑到第I种币值，使用J张，凑成面值为K的数目的可能（布尔值）。

则：

F[I，J，K]={ F[I-1，J，K] ORF[I-1，J-1，K-Di] ORF[I-1，J-2，K-2*Di] OR F[I-1，J-3，K-3*Di] OR…… }：

复杂度：O（IJKJ）