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

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

2、ar很想当班委，为了能够当上班委，他想请你帮忙确定哪些位置是班委的位置。【输入描述】一行：三个整数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 = 1540% 的数据 k,n,m = 20060% 的数据 k,n,m = 50090% 的数据 k,n,m = 1000100%的数据 k=1000 n,m 5 dobegint:=0;if f=t

3、rue the n begi n h:=1;z:=m endelse begi n h:=-1;z:=n end;while tz dobeginw:=w+h; if w=0 the n w:=k+w;w:=w mod k;if w=0 the n w:=k;t:=t+aw;en d;aw:=0;f:=not f;dec(s);en d;t:=1;for i:=1 to k doif ai0 then begin bt:=i; inc(t);end;for i:=5 downto 2 do write(bi,);write(b1);en d.输入20 5 3输出18 12 9 3 1输入40

4、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,880)的手镯，她可能无法把所有喜欢的宝石都镶上。于是贝茜找到了你，告诉了你她所有宝石的属性以及她能忍受的重量，希望你能帮她计算一下，按照最合理的方案镶嵌宝石的话，她的魅力值最多能增加多

5、少。程序名：charm输入格式：*第1行:2个用空格隔开的整数：N和M*第2.N+1行：第i+1行为2个用空格隔开的整数：W_i、D_i，分别为第i块宝石的重量与能为贝茜增加的魅力值输入样例(charm.i n):4 61 42 63 122 7输入说明：贝茜收集了 4块宝石，她能忍受重量最大为6的手镯。输出格式：*第1行：输出1个整数，表示按照镶嵌要求，贝茜最多能增加的魅力值输出样例(charm.out):23输出说明：贝茜把除了第二块宝石的其余所有宝石都镶上手镯，这样她能增加4+12+7=23的魅力值，并且所有宝石的重量为1+2+3 b the n exit(a) else exit(b)

6、;en d;beginassig n(i nput,charm.i n);reset(i nput);assig n(o utput,charm.out);rewrite(output);readl n(n, m);for i:=1 to n do readln(-vi,wi);for i:=1 to n dofor j:=m dow nto vi dofj:=max(fj,fj-vi+wi);writel n(fm);close(output);en d.输入6 91 52 83 102 74 65 9输出30输入11 2001 1203 802 754 663 906 1007 958 6

7、510 1056 889 92输出976熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们要研究最长公共上升子序列了。小沐沐说，对于两个串A，B,如果它们都包含一段位置不一定连续的数字，且数字是严格递增的，那么称这一段数字是两个串的公共上升子串，而所有的公共上升子串中最长的就是最长公共上升子串了。奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子串。不过，只要告诉奶牛它的长度就可以了。输入格式In put Format第一行N，表示A， B的长度。第二行，串A。第三行，串B。输出格式 Output Format输出长

8、度。样例输入Sample In put42 2 1 32 1 2 3样例输出 Sample Output2注释Hint1=Nbj)a nd(fi-1,jmax) then max:=fi-1,j;if aibj then fi,j:=fi-1,j;if ai=bj the n beg infi,j:=max+1;en d;en d;en d;an s:=0;for i:=1 to n doif an sf n,i the n an s:=f n,i;writel n(a ns);en d;beginin it;main;termi nate;en d.输入102 3 31 45 75 862

9、1 34 35 65 37输出5输入304 4 58 89 10 1418142016 13 98 22 24 2223232319 30 15 15282728 28 293 4 44 56 66 88 9101418 20 20 16232325 27 28 28 19 1113151517 30输出11【解题思路分类讨论：1. 当 aibj时，fi,j=fi-1,j(因为 aibj，所以说就等价于在 1i-1 找一个等于ak=bj，如果ai-1=bj，那么就是从fi-1,j转移而来；如果 ai-1bj，那么 就是在1i-2中去找一个，对于那些不相等的，是没有贡献的，可以直接从上一个相等的

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

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

12、，他们走到一条河的东岸边，想要过河到西岸。 而东岸边有一条小船。船太小了，一次只能乘坐两人。每个人都有一个渡河时间T,船划到对岸的时间等于船上渡河时间较长的人所用时间。现在已知N个人的渡河时间T，Oliver想要你告诉他，他们最少要花费多少时间，才能使所有人都过河。注意，只有船在东岸(西岸)的人才能坐上船划到对岸。输入格式 输入文件第一行为人数N,以下有N行，每行一个数。第i+1行的数为第i个人的渡河时间。输出格式 输出文件仅包含一个数，表示所有人都渡过河的最少渡河时间。样例输入4671015样例输出42样例解释初始：东岸1，2，3，4，西岸第一次：东岸 3，4，西岸 1，2 时间 7第二次：

13、东岸 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。【解题思路】 这个题我想了很久， 我一直以为是个贪心题， 却没有注意到状态的选择并不是 单一的。结果自己推了好久，在那模拟n=3.8 的情况，还推了个公式，结果错了，因为我把值等于下标推得，但是实际情况显然不是那样的，也正因为值的不同， 所以不能用单纯的贪心来做。我们

14、不难发现对于每一个人，我们都是有两种选择。如果是还剩最后两个人，那么就可以是先把 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.100000 of longint;n:longint;procedure init;beginassign(input,river.in); reset(input);assign(output,river.o

15、ut); rewrite(output);end;procedure terminate;beginclose(input); close(output);halt;end;procedure qsort(s,t:longint);var i,j,m,x:longint;beginm:=(s+t) shr 1;x:=am; am:=as; as:=x;i:=s; j:=t; x:=ai;repeatwhile (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;beginreadln(n);for i:=1 to n do readln(ai);qsort(1,n)