noip普及组复赛模拟试题15附答案资料

1、 【基础】班委确定 【试题描述】 经过紧张而激烈的选拔考试， 编程班终于浮出水面， 一共有 k位同学幸运的入选， 这 k位同 学个个可都是精英， 才华横溢， 思维敏捷。 让谁做班长？让谁做学习委员？让谁做团委书记 呢？这可让班主任老师伤透了脑筋。 个个都优秀，个个都能干，实在是没有办法了。抓 阄吧！这个抓阄可不是普通的抓阄， 老师让这 k 位同学围成一圈从一号位置开始顺时针报数 报到 m 这个人就出圈(啊？猴子选大王啊！把我们当猴子啦？Of course not )，出圈后就反 向逆时针从下一个开始报数，报到n 再出圈，然后再反向顺时针报到 m 出圈 ,反向逆时针报 到 n 出圈圈里的人越来越

2、少，当还剩下 5 个人的时候那么这 5 个人就是编程班的班委。 Star 很想当班委，为了能够当上班委，他想请你帮忙确定哪些位置是班委的位置。 【输入描述】一行：三个整数 k,m 和 n 【输出描述】 一行： 5 个数，分别为 5 个班委位置的号码(号码从大到小排列)。两个号码 之间用一个空格隔开，最后一个号码没有空格 【输入样例】 10 3 2 【输出样例】 10 9 8 6 4 【解题提示】 样例说明： 出圈顺序为： 3 1 5 2 7 剩下 4 6 8 9 10 数据规模： 10% 的数据 k,n,m = 15 40% 的数据 k,n,m = 200 60%的数据 k,n,m = 500

3、 90%的数据 k,n,m = 1000 100%的数据 k=1000 n,m 5 do begin t:=0; if f=true then begin h:=1;z:=m end else begin h:=-1;z:=n end; while tz do begin w:=w+h; if w=0 then w:=k+w; w:=w mod k; if w=0 then w:=k; t:=t+aw; end; aw:=0; f:=not f; dec(s); end; t:=1; for i:=1 to k do if ai0 then begin bt:=i; inc(t);end; f

4、or i:=5 downto 2 do write(bi, ); write(b1); end. 输入 20 5 3 输出 18 12 9 3 1 输入 40 9 5 输出 31 25 16 2 1 宝石手镯 Kolstad/Cox, 2006 贝茜在珠宝店闲逛时，买到了一个中意的手镯。很自然地，她想从她收集的 N(1 = N = 3,402) 块宝石中选出最好的那些镶在手镯上。对于第 i 块宝石，它 的重量为 W_i(1 = W_i = 400) ，并且贝茜知道它在镶上手镯后能为自己增加的 魅力值 D_i(1 = D_i = 100) 。由于贝茜只能忍受重量不超过 M(1 = M = 12,

5、880) 的手镯，她可能无法把所有喜欢的宝石都镶上。 于是贝茜找到了你，告诉了你她所有宝石的属性以及她能忍受的重量，希望 你能帮她计算一下，按照最合理的方案镶嵌宝石的话，她的魅力值最多能增加多 少。 程序名 : charm 输入格式 : * 第 1 行: 2 个用空格隔开的整数： N 和 M * 第 2.N+1 行: 第 i+1 行为 2 个用空格隔开的整数： W_i、D_i ，分别为第 i 块宝石 的重量与能为贝茜增加的魅力值 输入样例 (charm.in): 4 6 1 4 2 6 3 12 2 7 输入说明 : 贝茜收集了 4 块宝石，她能忍受重量最大为 6 的手镯。 输出格式 : *

6、第 1 行 : 输出 1 个整数，表示按照镶嵌要求，贝茜最多能增加的魅力值 输出样例 (charm.out): 23 输出说明 : 贝茜把除了第二块宝石的其余所有宝石都镶上手镯，这样她能增加 4+12+7=23 的魅力值，并且所有宝石的重量为 1+2+3 b then exit(a) else exit(b); end; begin assign(input,charm.in);reset(input); assign(output,charm.out);rewrite(output); readln(n,m); for i:=1 to n do readln(vi,wi); for i:=1

7、 to n do for j:=m downto vi do fj:=max(fj,fj-vi+wi); writeln(fm); close(output); end. 输入 6 9 1 5 2 8 3 10 2 7 4 6 5 9 输出 30 输入 11 200 1 120 3 80 2 75 4 66 3 90 6 100 7 95 8 65 10 105 6 88 9 92 输出 976 熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。小沐沐先让奶牛研究了最长上升子序 列，再让他们研究了最长公共子序列，现在又让他们要研究最长公共上升子序列了。 小沐沐说，对于两个串 A， B ，如果它们都

8、包含一段位置不一定连续的数字，且数字是严格 递增的， 那么称这一段数字是两个串的公共上升子串， 而所有的公共上升子串中最长的就是 最长公共上升子串了。 奶牛半懂不懂， 小沐沐要你来告诉奶牛什么是最长公共上升子串。 不过， 只要告诉奶牛它的 长度就可以了。 输入格式 Input Format 第一行 N ，表示 A， B 的长度。 第二行，串 A 。 第三行，串 B 。 输出格式 Output Format 输出长度。 样例输入 Sample Input 4 2 2 1 3 2 1 2 3 样例输出 Sample Output 2 注释 Hint 1=Nbj)and(fi-1,jmax) the

9、n max:=fi-1,j; if aibj then fi,j:=fi-1,j; if ai=bj then begin fi,j:=max+1; end; end; end; ans:=0; for i:=1 to n do if ansfn,i then ans:=fn,i; writeln(ans); end; begin init; main; terminate; end. 输入 10 2 3 3 1 4 5 7 5 8 6 2 1 3 4 3 5 6 5 3 7 输出 5 输入 30 4 4 5 8 8 9 10 14 18 14 20 16 13 9 8 22 24 22 23

10、 23 23 19 30 15 15 28 27 28 28 29 3 4 4 4 5 6 6 6 8 8 9 10 14 18 20 20 16 23 23 25 27 28 28 19 11 13 15 15 17 30 输出 11 【解题思路分类讨论： 1.当 aibj 时， fi,j=fi-1,j (因为 aibj ，所以说就等价于在 1i-1 找一个 等于 ak=bj ，如果 ai-1=bj ，那么就是从 fi-1,j 转移而来；如果 ai-1bj ，那么 就是在 1i-2 中去找一个，对于那些不相等的，是没有贡献的， 可以直接从上一个相等的转 移而来，这样就少了第 1 维的枚举，从

11、 O(N4) 一下降为了 O(N3) 。 2.当 ai=bj 时， fi,j=max(fi-1,k)+1 。 这样我们着眼于从状态转移上下功夫， 降了一维。 这道题很显然是很难减少状态数的， 状态 数就定下来是 O(N2) 了，要想继续优化，必须从状态的转移上想办法。 再说更优的 O(N2) 的算法： 在 aibj 时，我们已经将状态转移的复杂度降为了 O(1), 已经无法再优化了。 于是我们就只有优化 ai=bj 时的转移，如何优化？ 我们要一个 max(fi-1,k)(bj=aibk) 。所以我们要求这个 max ，那么就要看能否 不用 O(N)的扫描，而是看能否用 O(1)的代价找到这个

12、 max ，或者是用 O(logN) 的复杂度转 移都是能够承受的了。那么怎么求 max? 我们发现要求的是 i-1 层，这一层是全部求出来了的，对于我们这次对第 i 层求解，每 次都要扫描重复的，这就有冗余关系，为了减少冗余，我们可以把 max(fi-1,k) 保存下来， 因为 j 是递增的，所以每次的 k 也就增加一个，我们只需判断这个新增加的 k 与 max 的大 小。也就是说，在求解 fi,j 的过程中，我们就可以把 fi-1,k 中最大的存下来， 为每次 ai=bj 的转移作准备。 于是，这道题就从状态转移上由 O(N2) 变为了 O(1) ，这个是很优的了。 应该已经达到 了时间复

13、杂度的下界了。 贪心 dp 过河游戏 问题描述 有一个大晴天， Oliver 与同学们一共 N 人出游，他们走到一条河的东岸边， 想要过河到西岸。 而东岸边有一条小船。船太小了，一次只能乘坐两人。每个人都有一个渡河时间T，船划到 对岸的时间等于船上渡河时间较长的人所用时间。 现在已知 N 个人的渡河时间 T，Oliver 想 要你告诉他，他们最少要花费多少时间，才能使所有人都过河。 注意，只有船在东岸(西岸)的人才能坐上船划到对岸。 输入格式 输入文件第一行为人数 N，以下有 N 行，每行一个数。 第 i+1 行的数为第 i 个人的渡河时间。 输出格式 输出文件仅包含一个数，表示所有人都渡过河

14、的最少渡河时间。 样例输入 4 6 7 10 15 样例输出 42 样例解释 初始：东岸 1 ，2，3，4 ，西岸 第一次：东岸 3，4，西岸 1，2 时间 7 第二次：东岸 1 ， 3，4 ，西岸 2 时间 6 第三次：东岸 1 ，西岸 2 ，3，4 ，时间 15 第四次：东岸 1，2，西岸 3，4 时间 7 第五次：东岸 ，西岸 1 ，2，3，4 时间 7 所以总时间为 7+6+15+7+7=42 ，没有比这个更优的方案。 数据范围 对于 40% 的数据满足 N8。 对于 100% 的数据满足 N 100000 。 【解题思路】 这个题我想了很久， 我一直以为是个贪心题， 却没有注意到状态

15、的选择并不是 单一的。结果自己推了好久，在那模拟n=3.8 的情况，还推了个公式， 结果错了，因为我把值等于下标推得，但是实际情况显然不是那样的，也正因为值的不同， 所以不能用单纯的贪心来做。我们不难发现对于每一个人，我们都是有两种选择。 如果是还剩最后两个人，那么就可以是先把 1,2 运过去，然后 1 回来，再把那两个送过 去，然后 2 回来接 1, 最后 1,2 再过去。 如果是还剩最后一个人，那么就是用 1 回来接他，然后一起过去。 所以说： fn=min(fi-1+ai+a1,fi-2+a1+2*a2); program river; uses math; var a,f:array1

16、.100000 of longint; n:longint; procedure init; begin assign(input,river.in); reset(input); assign(output,river.out); rewrite(output); end; procedure terminate; begin close(input); close(output); halt; end; procedure qsort(s,t:longint); var i,j,m,x:longint; begin m:=(s+t) shr 1; x:=am; am:=as; as:=x;

17、 i:=s; j:=t; x:=ai; repeat while (ij) and (xaj) do dec(j); if ij then begin ai:=aj; inc(i); end; while (iai) do inc(i); if ij then begin aj:=ai; dec(j); end; until i=j; ai:=x; inc(i); dec(j); if it then qsort(i,t); if sj then qsort(s,j); end; procedure main; var i,j,x:longint; begin readln(n); for i:=1 to n do readln(ai); qsort(1,n); f