noip普及组复赛模拟试题15(附答案).docVIP

【基础】班委确定 【试题描述】 经过紧张而激烈的选拔考试，编程班终于浮出水面，一共有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 s5 do 牋燽egin 牋牋爐:=0; 牋牋爄f f=true then begin h:=1;z:=m end 牋牋牋牋牋牋牋爀lse begin h:=-1;z:=n end; 牋牋爓hile 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+a[w]; 牋牋牋end; 牋牋牋a[w]:=0; 牋牋牋f:=not f; 牋牋牋dec(s); 牋爀nd; 牋爐:=1; 牋爁or i:=1 to k do 牋牋爄f a[i]0 then begin b[t]:=i; inc(t);end; 牋爁or i:=5 downto 2 do牋write(b[i], ); 牋爓rite(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 61 42 63 122 7输入说明:??? 贝茜收集了4块宝石，她能忍受重量最大为6的手镯。输出格式:* 第1行: 输出1个整数，表示按照镶嵌要求，贝茜最多能增加的魅力值输出样例 (charm.out):23输出说明:??? 贝茜把除了第二块宝石的其余所有宝石都镶上手镯，这样她能增加4+12+7=23的魅力值，并且所有宝石的重量为1+2+3 = 6，同样符合要求。 题解：这题太水了，随便dp一下就AC了，最朴素的背包， code： var??? f:a