2014noip复赛模拟练习20(答案)

Bessie那惨无人道的二年级老师搞了一个有 N (1 <= N <= 100) 个正整数 I (1 <= I <= 10^60) 的表叫Bessie去判断“奇偶性”（这个词语意思向二年级的学生解释，就是“这个 数是单数，还是双数啊？”）。Bessie被那个表的长度深深地震精到了，竟然跟栋栋的泛做表 格一洋多道题！！！毕竟她才刚刚学会数数啊。

写一个程序读入N个整数，如果是双数，那麼在独立的一行内输出\，如果是单数则类似 地输出\

输入格式 Input Format第一行: 一个单独的整数: N

* 第2到第N+1行: 第j+1行有第j个需要判断奇偶性的整数。 输出格式：N行EVEN或ODD

var s:array [1..100] of ansistring; i,l,n:longint; begin

readln(n);

for i:=1 to n do readln(s[i]); for i:=1 to n do begin

l:=length(s[i]);

if (ord(s[i][l])-48) mod 2=0 then writeln('even') else writeln('odd'); end; end. 输入5 98789

12345678903456 98976565

999988888777777666664355451 10233333333333333333011120 输出 ODD EVEN ODD ODD EVEN 输入 8

1111111111111111111111 2222222222222222222222 30000000000000000000000099

1222222222222222222222222222222

999999999999999999999999999999999999999999999 55555555555555555555555555555555555555555555555

77777777777777777777777777777777777777777777777777777

888888888888888888888888888888888888888888888888888888888888888888888 输出 ODD

EVEN ODD EVEN ODD ODD ODD EVEN

津津的零花钱一直都是自己管理。每个月的月初妈妈给津津300元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。

为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上20％还给津津。因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于100元或恰好100元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。

例如11月初津津手中还有83元，妈妈给了津津300元。津津预计11月的花销是180元，那么她就会在妈妈那里存200元，自己留下183元。到了11月月末，津津手中会剩下3元钱。

津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。

现在请你根据2004年1月到12月每个月津津的预算，判断会不会出现这种情况。如果不会，计算到2004年年末，妈妈将津津平常存的钱加上20％还给津津之后，津津手中会有多少钱。

输入格式 Input Format输入文件save.in包括12行数据，每行包含一个小于350的非负整数，分别表示1月到12月津津的预算。

输出格式 Output Format输出文件save.out包括一行，这一行只包含一个整数。如果储蓄计划实施过程中出现某个月钱不够用的情况，输出-X，X表示出现这种情况的第一个月；否则输出到2004年年末津津手中会有多少钱。

var a:array [1..12] of longint; i,s,num,n:longint; begin

for i:=1 to 12 do begin

readln(a[i]); s:=n+300-a[i]; if s<0 then begin

writeln('-',i); halt; end;

num:=num+(s div 100)*10; n:=s mod 100; end;

num:=num*12+n;

writeln(num); end.

输入288 110 310 188 168 161 32 332 89 298 201

60 输出 -3 输入 288 339 342 2 39 245 99 269 92 167 198

61 输出 -2 输入288 225 151 95 279 203 65 300 266 232 199 60

输出 1477 输入288 213 246 237 240

105 265 113 274 188 190

63 输出 1398

给你一个长度为n的数字串，数字串里会包含1-m这些数字。如果连续的一段数字子串包含了1-m这些数字，则称这个数字字串为NUM串。你的任务是求出长度最短的NUM串是什么，只需要输出这个长度即可。 1<=n，m<=200000

输入格式 Input Format第一行给定n和m。 第二行n个数，表示数字串，数字间用空格隔开。 输出格式 Output Format

如果存在NUM串则输出最短NUM串长度，否则输出“NO”。

var a,b:array[1..200000] of longint; n,m,i,k,gs,zgs,p,q,min:longint; begin

readln(n,m); gs:=0; zgs:=0; p:=1;

min:=maxlongint; fillchar(b,sizeof(b),0); for i:=1 to n do begin

read(a[i]); inc(b[a[i]]);

if b[a[i]]=1 then inc(gs); inc(zgs);

while ((a[p]=a[i])and(p1) do begin

dec(zgs); dec(b[a[p]]); inc(p); end;

if (gs=m)and(zgs

if min<>maxlongint then writeln(min) else writeln('NO'); end.

输入5 3

1 2 2 3 1 输出 3 输入 12 7

2 3 4 5 6 4 7 8 9 6 8 7 输出 8

输入 10 4

9 9 8 7 8 9 7 8 7 9 输出 NO 输入 30 23

8 18 38 9 17 36 78 44 12 19 16 3 13 15 20 21 7 8 9 12 11 16 55 5 15 17 4 3 13 22 输出 NO 输入 15 9

3 4 5 6 8 7 6 6 9 10 12 13 14 15 16 输出 11

superwyh的学校要举行拔河比赛，为了在赛前锻炼大家，老师决定把班里所有人分为两拨，进行拔河因为为锻炼所以为了避免其中一方的实力过强老师决定以体重来划分队伍，尽

量保持两个队伍的体重差最少，因为老师对结果没兴趣，所以只告诉老师最小的体重差是多少就行了。这个受苦受累的任务就交给superwyh了，因为这两天superwyh的后背间谍sjh

闹肚子了，所以只好superwyh亲自去调查每个人的体重，但是仅仅知道体重依然难以确定到底如何分配队伍，请各位oier帮助superwyh出出主意。 输入格式

第一行为人数(1<=n<=100)，从第二行开始是每个人的体重(0<=m<=100)。 输出格式 最小体重差。 样例输入 4 10 23 41 12 样例输出 4

var i,j,k,m,n:longint;

a,f:array[0..1001] of longint; begin

readln(n); k:=0;

for i:=1 to n do begin

read(a[i]); k:=k+a[i];

end; for i:=1 to n do for j:=k div 2 downto a[i] do

if f[j]

end. 输入 8

35 68 20 14 57 48 42 54输出 2 输入 15

8 18 28 33 43 53 67 68 76 80 23 55 45 16 26输出 1 输入 30

5 85 65 66 45 35 25 15 95 75 11 21 91 81 71 61 51 41 21 31 17 27 37 69 67 77 57 47 29 89 输出 1

把1-8这8个数放入下图8个格中,要求相邻的格(横,竖,对角线)上填的数不连续.

┌─┐ │①│

┌─┼─┼─┐ │②│③│④│ ├─┼─┼─┤ │⑤│⑥│⑦│ └─┼─┼─┘ │⑧│ └─┘

【参考程序】

const lin:array[1..8] of set of 1..8 = ([3,2,4],[1,6,3,5],[5,7,1,2,4,6],[1,6,3,7], [3,8,2,6],[2,4,3,5,7,8],[3,8,4,6],[5,7,6]); var a:array[1..8] of integer;

total,i:integer; had:set of 1..8;

function ok(dep,i:integer):boolean; {判断是否能在第dep格放数字i} var j:integer; begin

ok:=true;

for j:=1 to 8 do {相邻且连续则不行} if (j in lin[dep]) and (abs(i-a[j])=1) then ok:=false; if i in had then ok:=false; {已用过的也不行} end;

procedure output; {输出一种方案} var j:integer; begin inc(total); write(total,':'); for j:=1 to 8 do write(a[j]:2);writeln; end;

procedure find(dep:byte); var i:byte; begin for i:=1 to 8 do begin {每一格可能放1-8这8个数字中的一个} if ok(dep,i) then begin a[dep]:=i; {把i放入格中} had:=had+[i]; {设置已放过标志} if (dep=8) then output

else find(dep+1); a[dep]:=10; {回溯,恢复原状态} had:=had-[i]; end; end; end;

begin

fillchar(a,sizeof(a),10); total:=0; had:=[]; find(1);

writeln('End.'); end.

输出 1:2 5 8 6 3 1 4 7 2:2 6 8 5 4 1 3 7 3:7 3 1 4 5 8 6 2 4:7 4 1 3 6 8 5 2 END.

斯诺克又称英式台球，是一种流行的台球运动。在球桌上，台面四角以及两长边中心位置各有一个球洞，使用的球分别为1个白球，15个红球和6个彩球（黄、绿、棕、蓝、粉红、黑）共22个球。击球顺序为一个红球、一个彩球直到红球全部落袋，然后以黄、绿、棕、蓝、粉红、黑的顺序逐个击球，最后以得分高者为胜。斯诺克的魅力还在于可以打防守球，可以制造一些障碍球使对方无法击打目标球而被扣分。正是因为这样，斯诺克是一项充满神奇的运动。现在考虑这样一种新斯诺克，设母球（母球即是白球，用于击打其他球）的标号为M，台面上有N个红球排成一排，每一个红球都有一个标号，他们的标号代表了他们的分数。现在用母球击打这些红球，一杆击打，如果母球接触到红球，就称为“K到红球”。我们假设，一次可以击打任意多相邻连续的红球，也可以只击打一个球。并且红球既不会落袋，也不会相互发生碰撞，而只是停留在原处。每次击打时候，要想“K到红球”，至少要击打一个红球，如果想一次击打多个红球，那么击打的红球必须是依次连续排列的。如果一次“K到红球”所有红球的标号之和的平均数大于母球的标号M，就获得了一个“连击”。 现在请你计算总共能有多少种“连击”方案。

注意：如果当前有标号为1、2、3 的三种红球，母球标号为0，有如下6种获得“连击”方案：（1）、（2）、（3）、（1，2）、（2，3）、（1，2，3） 【输入文件】

输入文件sheeta.in共有两行，第一行是N，M (N<=100000，M<=10000) ，N表示台面

上一共有N个红球，M表示母球的标号。

第二行是N个正整数，依次表示台面上N个红球的标号，所有标号均不超过10000。 【输出文件】

输出文件sheeta.out只有一个数，为“连击”的方案总数。 【输入样例】 4 3 3 7 2 4 【输出样例】 7

分析：前i个数累加得到前i个数的最大前缀和a[i] 根据题意对区间 [j+1,i] 的连续和

写成 a[i]-a[j] 根据题意 即求 满足 (a[i]-a[j])/(i-j)>m 的方案数; 将分母乘到右边 a[i]-a[j]>i*m-j*m 再变形 的到 a[i]-i*m>a[j]-j*m 令 b[i]=a[i]-i*m;

所以是求 满足 i>j 并且 b[i]>b[j]的对数 对于一个单调不增的b 序列即是求b 序列的逆序对 用归并排序的方式 时间复杂度为nlogn

注意：1归并排序要包括b[0] 因为 a[i]-a[0] 表示从起点到i 的连续和 2 不用特殊考虑只有一个元素，因为i>j 所以当j=i-1时 a[i]-a[i-1]就表示第i号元素 代码：

program sheeta; var

a,b,c:array[0..100001]of int64; //根据数据开大点

n,m:longint; total:int64; procedure init; begin

assign(input,'sheeta.in'); assign(output,'sheeta.out'); reset(input); rewrite(output); end;

procedure terminate; begin

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

procedure msort(l,r:longint); //归并排序 var

i,j,mid,k:longint; begin

if (l=r) then exit;

mid:=(l+r) shr 1; //先让子序列有序 msort(l,mid); msort(mid+1,r);

for i:=l to r do //记录临时信息

c[i]:=b[i];

i:=l; j:=mid+1; //左右子序列的起点

for k:=l to r do //根据子序列构造单调不增的序列 begin

if (i<=mid) and ((c[i]>=c[j]) or (j>r)) then //左元素大于右元素 或者 右元素已完全输出 begin b[k]:=c[i]; inc(i); end else begin b[k]:=c[j];

inc(total,mid-i+1); //统计核心 当前右元素与所有未输出的左元素构成逆序对 inc(j); end; end; end;

procedure main; var

i,j,x:longint; begin

fillchar(a,sizeof(a),0);

total:=0; readln(n,m); a[0]:=0;b[0]:=0; for i:=1 to n do begin read(x);

a[i]:=a[i-1]+x; //累加前缀和 b[i]:=a[i]-i*m; //根据变形求b 序列 end;

msort(0,n); //左端点包括0 writeln(total); //输出方案 end; begin init; main; terminate; end.

输入 15 8

2 3 5 6 7 9 3 11 12 8 10 18 28 19 17 输出 73 输入 25 14

3 6 15 4 8 24 88 78 99 56 14 21 11 90 80 68 55 32 19 39 69 32 44 51 48 输出 305 输入 40 24

3 1 10 20 4 16 7 9 99 89 19 9 6 16 86 56 66 27 17 30 40 11 21 15 35 55 5 8 18 88 78 68 58 13 33 23 93 98 99 39 输出 724

total:=0; readln(n,m); a[0]:=0;b[0]:=0; for i:=1 to n do begin read(x);

a[i]:=a[i-1]+x; //累加前缀和 b[i]:=a[i]-i*m; //根据变形求b 序列 end;

msort(0,n); //左端点包括0 writeln(total); //输出方案 end; begin init; main; terminate; end.

输入 15 8

2 3 5 6 7 9 3 11 12 8 10 18 28 19 17 输出 73 输入 25 14

3 6 15 4 8 24 88 78 99 56 14 21 11 90 80 68 55 32 19 39 69 32 44 51 48 输出 305 输入 40 24

3 1 10 20 4 16 7 9 99 89 19 9 6 16 86 56 66 27 17 30 40 11 21 15 35 55 5 8 18 88 78 68 58 13 33 23 93 98 99 39 输出 724

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