PDF《CodePlus2017 11 月赛》

11 月赛 汀博尔(timber) 汀博尔(timber) 【题目描述】 有n棵树,初始时每棵树的高度为 Hi,第i棵树每月都会长高 Ai.现在有个木料 长度总量为 S 的订单,客户要求每块木料的长度不能小于 L,而且木料必须是整棵树 (即不能为树的一部分) .现在问你最少需要等多少个月才能满足订单. 【输入格式】 从文件 timber.in 中读入数据. 第一行

3 个用空格隔开的非负整数 n, S, L,表示树的数量、订单总量和单块木料长 度限制. 第二行 n 个用空格隔开的非负整数,依次为 H1, H2,Hn. 第三行 n 个用空格隔开的非负整数,依次为 A1, A2,An. 【输出格式】 输出到文件 timber.out 中. 输出一行一个整数表示答案. 【样例

1 输入】

3 74

51 2

5 2

2 7

9 【样例

1 输出】

7 【Hints】 对于样例,在六个月后,各棵树的高度分别为 14, 47, 56,此时无法完成订单. 在七个月后,各棵树的高度分别为 16, 54, 65,此时可以砍下第

2 和第

3 棵树完成订 单了. CodePlus2017

11 月赛 汀博尔(timber) 【子任务】 测试点编号 n 特殊约定

1 n =

1 1 ≤ S ≤ Hi ≤

10000 2

1 ≤ S, L, Hi, Ai ≤

10000 3

1 ≤ n ≤

1000 4

5 6

1 ≤ S, L, Hi, Ai ≤

109 7

8 9

1 ≤ n ≤

20000 10

11 1 ≤ S, L ≤

1018 ,

1 ≤ Hi, Ai ≤

109 12

13 1 ≤ n ≤

200000 L =

1 14 S ≤ L

15 1 ≤ S, L ≤

1018 ,

1 ≤ Hi, Ai ≤

109 16

17 18

19 20 CodePlus2017

11 月赛 找爸爸(dnaseq) 找爸爸(dnaseq) 【题目描述】 小A最近一直在找自己的爸爸,用什么办法呢,就是 DNA 比对. 小A有一套自己的 DNA 序列比较方法,其最终目标是最大化两个 DNA 序列的相 似程度,具体步骤如下: 1. 给出两个 DNA 序列,第一个长度为 n,第二个长度为 m. 2. 在两个序列的任意位置插入任意多的空格,使得两个字符串长度相同 3. 逐位进行匹配, ・ 如・果・两・个・序・列・相・同・位・置・上・的・字・符・都・不・是・空・格,假设第一个是 x, 第二个是 y,那么他们的相似程度由 d(x, y) 定义.对于两个序列中任意一段极长 的长度为 k 的连续空格,我们定义这段空格的相似程度为 g(k) = ?A ? B(k ? 1). 那么最终两个序列的相似程度就是所有的 d(x, y) 加上所有的极长空格段的相似程 度之和. 现在小 A 通过某种奥妙重重的方式得到了小 B 的DNA 序列中的一段,他想请你 帮他算一下小 A 的DNA 序列和小 B 的DNA 序列的最大相似程度. 【输入格式】 从文件 dnaseq.in 中读入数据. 输入第

1 行一个字符串,表示小 A 的DNA 序列. 输入第

2 行一个字符串,表示小 B 的DNA 序列. 接下来

4 行,每行

4 个整数,用空格隔开,表示 d 数组,具体顺序如下所示. d(A,A) d(A,T) d(A,G) d(A,C) d(T,A) d(T,T) d(T,G) d(T,C) d(G,A) d(G,T) d(G,G) d(G,C) d(C,A) d(C,T) d(C,G) d(C,C) 最后一行两个用空格隔开的正整数 A, B,意义如题中所述. 【输出格式】 输出到文件 dnaseq.out 中. 输出共一行,表示两个序列的最大相似程度. 【样例

1 输入】 ATGG ATCC CodePlus2017

11 月赛 找爸爸(dnaseq)

5 -4 -4 -4 -4

5 -4 -4 -4 -4

5 -4 -4 -4 -4

5 2

1 【样例

1 输出】

4 【样例解释】 首先,将序列补成如下形式("-'' 代表空格) ATGG-- AT--CC 然后所有 d(x, y) 的和为 d(A, A) + d(T, T) =

10 所有极长连续空格段的相似程度之和为 g(2) + g(2) = ?6 总和为 4,可以验证,这是相似程度最大的情况. 【子任务】 对于所有测试点,有0,