noip普及组复赛模拟试题17(附答案)

图书馆馆长正犯愁呢，原来，有一堆的书要他整理，每本书都有一个书号（<=32767),现在他有一本书，这本书的书号为K（<=32767),现在他要找出一本书号比这本书大的书和书号比这本小的书(但都要最接近图书馆馆长已有的书号），将找到的这两本书的书号加起来，并算出加起来以后的数是否为素数

Input

第一行二个数为N,K，表示几本书以及手中书的书号（<=32767) 第二行开始有N个整数，表示这些书的书号 Output

第一行一个数，表示两本书书号加起来的和 第二行一个字符，表示和是否为素数，若是则输出\否则输出\（引号不打出） Sample Input 6 5

6 4 5 3 1 20 Sample Output 10 F

program ex1148; var n,k,i,x,s:integer;

a:array[0..32767] of integer; f:boolean; begin

readln(n,k);

fillchar(a,sizeof(a),0); for i:=1 to n do begin read(x); a[x]:=1; end; s:=0;

for i:=k+1 to 32767 do

if a[i]<>0 then begin s:=s+i;break; end; for i:=k-1 downto 1 do

if a[i]<>0 then begin s:=s+i;break; end; f:=true;

for i:=2 to trunc(sqrt(s)) do

if s mod i=0 then begin f:=false;break;end; writeln(s);

if f=true then write('Y') else write('F'); end.

输入 12 7

8 12 18 7 11 3 20 15 14 26 21 16 输出 11 Y

输入 21 10

4 7 12 10 18 29 15 6 17 3 11 20 21 24 14 2 22 26 13 19 9 输出 20 F

父母准备带你到新疆阿克苏旅行，你很高兴的开始准备旅行。现在你有M元钱，可以采购N种物品，每种物品最多可以购买Ai件（也可以不购买），每购买一件会花费Ci元，并能产生Vi的价值。请算出你能买的物品的最大价值和。 【输入】第一行，两个整数M，N用空格隔开。 后面N行，每行三个整数用空格隔开Ai、Ci、Vi 【输出】一个整数，能买的物品的最大价值和 【输入输出样例】

【输入输出样例说明】

购买第二种物品1件，第三中物品2件。 var

a: array[1..100, 1..3] of longint; m, n: longint; i, j, k, ans: longint;

f: array[0..10000] of longint;

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

if a > b then exit(a)

else exit(b); end;

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

if a < b then exit(a) else exit(b); end; begin

Assign(input, 'prepare.in'); Assign(output, 'prepare.out'); reset(input); rewrite(output); readln(m, n); for i := 1 to n do

readln(a[i, 1], a[i, 2], a[i, 3]); for i := 1 to n do

if a[i, 1] * a[i, 2] > m then for j := a[i, 2] to m do

f[j] := max(f[j], a[i, 3] + f[j - a[i, 2]])

else begin k := 1;

while k < a[i, 1] do begin

for j := m downto k * a[i, 2] do

f[j] := max(f[j], k * a[i, 3] + f[j - k * a[i, 2]]); a[i, 1] := a[i, 1] - k; k := k shl 1; end;

for j := m downto a[i, 1] * a[i, 2] do

f[j] := max(f[j], a[i, 1] * a[i, 3] + f[j - a[i, 1] * a[i, 2]]); end;

writeln(f[m]); Close(input); Close(output); end. 输入 100 5 1 30 6 2 20 5 3 40 7 4 35 4

5 50 8 输出 19 输入 300 6

1 80 10 2 120 15 3 150 12 4 100 16 5 110 9

6 90 14 输出 48

【问题描述】

给定一个数列{an}，这个数列满足ai≠aj(i≠j)，现在要求你把这个数列从小到大排序，每次允许你交换其中任意一对数，请问最少需要几次交换？

【输入文件】

第一行，正整数n (n<=100,000)。 以下若干行，一共n个数，用空格分隔开，表示数列{an},任意-231

【输出文件】

只有一行，包含一个数，表示最少的交换次数。

【样例输入】 8

8 23 4 16 77 -5 53 100

【样例输出】 5

将序列排序

找出所有的循环，即错误位置调换的循环 如 2 4 1 3 循环为 2->4->3->1->2 Ans=sigma 循环长度-1 参考程序： var

a,b:array[0..1000000]of longint; n,i,j,tot,t,ans:longint;

use:array[0..1000000]of boolean;

procedure qsort(l,r:longint); var

i,j,x,t:longint; begin

i:=l; j:=r; x:=a[random(r-l+1)+l]; repeat

while a[i]x do dec(j); if i<=j then begin

t:=a[i]; a[i]:=a[j]; a[j]:=t; t:=b[i]; b[i]:=b[j]; b[j]:=t; inc(i); dec(j); end; until i>j;

if i

begin

assign(input,'seqsort.in'); reset(input); readln(n);

for i:=1 to n do begin

read(a[i]); b[i]:=i; end;

close(input); qsort(1,n); for i:=1 to n do a[i]:=i;

for i:=1 to n do

if not use[i] then begin t:=i; tot:=0;

while not use[t] do begin

use[t]:=true; inc(tot); t:=b[t]; end;

ans:=ans+tot-1; end;

assign(output,'seqsort.out'); rewrite(output); writeln(ans); close(output); end.

输入 15

18 25 -30 76 125 67 45 -72 186 100 29 14 88 77 127 输出 13 输入 24

25 18 30 60 200 -104 -32 90 88 64 187 45 36 62 78 94 13 33 24 -56 82 140 189 71 输出 18

【问题描述】

Matrix67要在下个月交给老师n篇论文，论文的内容可以从m个课题中选择。由于课题数有限，Matrix67不得不重复选择一些课题。完成不同课题的论文所花的时间不同。具体地说，对于某个课题i，若Matrix67计划一共写x篇论文，则完成该课题的论文总共需要花费Ai*x^Bi个单位时间（系数Ai和指数Bi均为正整数）。给定与每一个课题相对应的Ai和Bi的值，请帮助Matrix67计算出如何选择论文的课题使得他可以花费最少的时间完成这n篇论文。 【输入文件】

第一行有两个用空格隔开的正整数n和m，分别代表需要完成的论文数和可供选择的课题数。

以下m行每行有两个用空格隔开的正整数。其中，第i行的两个数分别代表与第i个课题相对应的时间系数Ai和指数Bi。 【输出文件】

输出完成n篇论文所需要耗费的最少时间。

【样例输入】 10 3 2 1 1 2 2 1

【样例输出】 19

【样例说明】

4篇论文选择课题一，5篇论文选择课题三，剩下一篇论文选择课题二，总耗时为2*4^1+1*1^2+2*5^1=8+1+10=19。可以证明，不存在更优的方案使耗时小于19。

【数据规模与约定】

对于30%的数据，n<=10,m<=5；

对于100%的数据，n<=200，m<=20，Ai<=100，Bi<=5。 var a,b,i,j,k,n,m:integer;

c:array[1..20,1..200] of int64; {预处理数组} f:array[0..200] of int64; begin

assign(input,'mat.in'); assign(output,'mat.out'); reset(input); rewrite(output); readln(n,m);

for k:=1 to m do begin

readln(a,b);

for i:=1 to n do begin c[k,i]:=a;

for j:=1 to b do c[k,i]:=c[k,i]*i; end; end; f[0]:=0;

for i:=1 to n do

f[i]:=100000000000000000; for k:=1 to m do

for i:=n-1 downto 0 do for j:=1 to n-i do

if f[i]+c[k,j]

输入20 5 2 1 1 2 2 1 2 1

1 2 输出 38 输入 16 7 2 3 3 1 3 2 2 1 2 3 3 2

1 3 输出 31

本文来源：https://www.bwwdw.com/article/kl77.html