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

把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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库2014noip复赛模拟练习20(答案)(2)在线全文阅读。