noip普及组复赛模拟试题15（附答案）

【基础】班委确定 【试题描述】

经过紧张而激烈的选拔考试，编程班终于浮出水面，一共有k位同学幸运的入选，这k位同学个个可都是精英，才华横溢，思维敏捷。让谁做班长？让谁做学习委员？让谁做团委书记呢……？这可让班主任老师伤透了脑筋。个个都优秀，个个都能干，实在是没有办法了。抓阄吧！这个抓阄可不是普通的抓阄，老师让这k位同学围成一圈从一号位置开始顺时针报数报到m这个人就出圈（啊？猴子选大王啊！把我们当猴子啦？Of course not），出圈后就反向逆时针从下一个开始报数，报到n再出圈，然后再反向顺时针报到m出圈,反向逆时针报到n出圈……圈里的人越来越少，当还剩下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 90%的数据 k,n,m <= 1000

100%的数据 k<=1000 n,m <= 100000 【试题来源】 常州长训班测试 var k,i,h,s,w:integer;t,z,m,n:int64; f:boolean; a:array[1..1000] of 0..1; b:array[1..5] of integer;

begin readln(k,m,n); fillchar(a,sizeof(a),1); f:=true; s:=k; w:=0; while s>5 do begin t:=0;

if f=true then begin h:=1;z:=m end else begin h:=-1;z:=n end; while t

w:=w+h; if w<=0 then w:=k+w; w:=w mod k; if w=0 then w:=k; t:=t+a[w]; end; a[w]:=0; f:=not f; dec(s); end;

t:=1;

for i:=1 to k do

if a[i]<>0 then begin b[t]:=i; inc(t);end; for i:=5 downto 2 do write(b[i],' '); write(b[1]); 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,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的手镯。

输出格式:

* 第1行: 输出1个整数，表示按照镶嵌要求，贝茜最多能增加的魅力值

输出样例 (charm.out): 23

输出说明:

贝茜把除了第二块宝石的其余所有宝石都镶上手镯，这样她能增加

4+12+7=23的魅力值，并且所有宝石的重量为1+2+3 <= 6，同样符合要求。 题解：这题太水了，随便dp一下就AC了，最朴素的背包， code：

var

f:array[0..12880]of longint; v,w:array[1..3402]of longint; i,j,n,m:longint;

function max(a,b:longint):longint; begin

if a>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(v[i],w[i]); for i:=1 to n do

for j:=m downto v[i] do f[j]:=max(f[j],f[j-v[i]]+w[i]); writeln(f[m]); 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，如果它们都包含一段位置不一定连续的数字，且数字是严格递增的，那么称这一段数字是两个串的公共上升子串，而所有的公共上升子串中最长的就是最长公共上升子串了。

奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子串。不过，只要告诉奶牛它的长度就可以了。

输入格式 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<=N<=3000，

program tyvj1071;

var f:array[0..3000,0..3000] of longint; a,b:array[1..3000] of longint; ans,n,max:longint;

procedure init; begin

assign(input,'p1071.in'); reset(input);

assign(output,'p1071.out'); rewrite(output); end;

procedure terminate; begin

close(input); close(output); halt; end;

procedure main; var i,j,k,t:longint; begin

readln(n);

for i:=1 to n do read(a[i]); for i:=1 to n do read(b[i]); for i:=1 to n do begin max:=0;

for j:=1 to n do begin

if (a[i]>b[j])and(f[i-1,j]>max) then max:=f[i-1,j]; if a[i]<>b[j] then f[i,j]:=f[i-1,j]; if a[i]=b[j] then begin f[i,j]:=max+1; end; end; end; ans:=0;

for i:=1 to n do

if ans

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 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

【解题思路分类讨论：