解法:先解决前50%
方法1:利用曼哈顿距离分别求出每个点到其他点的横和纵距离和,他们的总和就是前50%的解。
**:for i:=0 to n-1 do
for j:=i+1 to n-1 do
sum:=sum+int64(m-q(y[i]))int64(m-q(y[j]))int64(j-i)*int64(2);
for i:=0 to m-1 do
for j:=i+1 to m-1 do
sum:=sum+int64(n-q(x[i]))int64(n-q(x[j]))int64(j-i)*int64(2);
方法2:利用坐标。
**:var n,m,i,j,kk,t:longint;
c:char;
ko,kl:extended;
a,b:array[0..1001]of longint;
fk:array[0..1000001,1..2]of longint;
f:array[0..1001,0..1001]of int64;
ff,f1:array[0..1001]of int64;
beginreadln(n,m);
for i:=1 to n do begin
for j:=1 to m do begin
read(c);
if c='.then begin
inc(a[i]);inc(b[j]);
inc(t);
fk[t,1]:=i; fk[t,2]:=j;
end;end;
readln;
end;fillchar(f,sizeof(f),0);
fillchar(ff,sizeof(ff),0);
for i:=1 to n do begin
kk:=0;
for j:=i+1 to n do begin
f[i,j]:=abs(i-j)*a[j];
f[j,i]:=abs(i-j)*a[i];
kk:=kk+f[i,j];
end;for j:=1 to i-1 do kk:=kk+f[i,j];
ff[i]:=kk;
end;fillchar(f,sizeof(f),0);
for i:=1 to m do begin
kk:=0;
for j:=i+1 to m do begin
f[i,j]:=abs(i-j)*b[j];
f[j,i]:=abs(i-j)*b[i];
kk:=kk+f[i,j];
end;for j:=1 to i-1 do kk:=kk+f[i,j];
f1[i]:=kk;
end;kl:=0; ko:=0;
for i:=1 to t do begin
kl:=kl+ff[fk[i,1]]+f1[fk[i,2]];
ko:=ko+(i-1);
end;writeln(kl/(ko*2+t):0:4);
end.方法3:利用矩形。
**:var x,y,n,m,t,ans:int64;
i,j:longint;
a:array[0..2000] of ansistring;
beginreadln(n,m);
t:=n+m-2; ans:=0;
for i:=1 to t do begin
x:=1; y:=i+1;
while (x<=n) do begin
if (y<=m) and (y>0) then begin
if (x>1) and (y>1) then inc(ans,(n-x+1)*(m-y+1)*4*i)
x+1,y+1)的右下角有(n-x+1)*(m-y+1)个点,然后分别以这些点。
为矩形的右下角点,利用对角线并且每个矩形有两条,长度为i,再加上双向,为4*i}
else if (x>1) and (y=1) then inc(ans,(n-x+1)*(m-y+1)*2*i)
这个是类似(x,y)与(x-i,y)的连线,有(n-x+1)*(m-y+1)}
else if (x=1) and (y>1) then inc(ans,(n-x+1)*(m-y+1)*2*i);
也是类似(x,y)与(x,y-i)的连线,有(n-x+1)*(m-y+1)}
之所以是(x=1)或(y=1),是因为是边也不可能是矩形的右下角点,同时又能做到完全覆盖}
end;inc(x); dec(y);
end;end;
t:=n*m*n*m;
writeln(ans/t:0:4);
end.举个例子:
以n=2,m=2为例:
总和为8模拟n=2,m=3时:
t=1: x=1,y=2:
t=1: x=2,y=1
t=2 x=1,y=3
t=2 x=2,y=2
t=2 x=3,y=1
t=2 x=1,y=4
t=2 x=2,y=3
t=2 x=3,y=2
t=2 x=4,y=1
求得和为 38
过了前50%后,要解决后面的障碍。
由上面解释可知,因题目不会全封锁,所以只需原距离+2,但问题是如何的知那些点对需要处理。
如:x上面只有1个,下面2个,设above=1, below=2
那么点对有2个,总值+4
以左边的为参考列。
当在相邻列的位置上有x时且在其上面时。
在x下面的点就一定要拐路走。
以右边的为参考列。
当在相邻列的位置上有x时且在其下面时。
在x下面的点就不需要拐路走。上面的不用管否则会重复。
然后按上面的方法,分别枚举行和列,先进行本行和列,再进行相邻行和列的x的比较就可以了。
程序:const nn=1010;
var n,m,i,j,below,above:longint;
sum:int64;
ans:real;
ch:array[0..nn,0..nn] of char;
x,y:array[0..nn] of longint;
function q(a:longint):longint;
beginif a>=0 then exit(1) else exit(0)
end;begin
readln(n,m);
for i:=0 to n-1 do begin
for j:=0 to m-1 do read(ch[i,j]);
readln
end;for i:=0 to n-1 do begin
y[i]:=1;
for j:=0 to m-1 do if ch[i,j]='x' then begin
y[i]:=j; break
endend;
for j:=0 to m-1 do begin
x[j]:=1;
for i:=0 to n-1 do if ch[i,j]='x' then begin
x[j]:=i; break
endend;
for i:=0 to n-1 do
for j:=i+1 to n-1 do
sum:=sum+int64(m-q(y[i]))int64(m-q(y[j]))int64(j-i)*int64(2);
for i:=0 to m-1 do
for j:=i+1 to m-1 do
sum:=sum+int64(n-q(x[i]))int64(n-q(x[j]))int64(j-i)*int64(2);
for i:=0 to m-1 do begin
if x[i]=-1 then continue;
below:=n-1-x[i]; above:=x[i];
sum:=sum+int64(below)*int64(above)*int64(4);
for j:=i+1 to m-1 do begin
if (x[j]=-1) or (x[j]>x[j-1]) then break;
above:=x[j];
sum:=sum+int64(below)*int64(above)*int64(4);
end;above:=x[i];
for j:=i-1 downto 0 do begin
if (x[j]=-1) or (x[j]>x[j+1]) then break;
above:=x[j];
NOIP2019复赛模拟练习卷 一
1.序列 问题描述 有一个整数序列,它的每个数各不相同,我们不知道它的长度 即序列中的整数个数 是多少,但我们知道,在某些区间中至少有多少个整数,用区间 li,ri,ci 来描述,表示这个整数序列中至少有ci个数来自区间 li,ri 给定若干个这样的区间,问这个整数序列的长度最少能为多少?输入 第1...
高中物理竞赛复赛模拟卷
江苏省梁丰高级中学物理竞赛模拟试题。1.试证明 物体的相对论能量e与相对论动量p的量值之间有如下关系 2.在用质子轰击固定锂靶的核反应中,1 计算放出 粒子的反应能。2 如果质子能量为1兆电子伏特,问在垂直质子束的方向观测到 粒子的能量有多大?有关原子核的质量如下 1.007825 4.002603...
物理竞赛复赛模拟训练卷
题1 如图1所示,轻滑轮两边分别悬挂相同的托盘和砝码。系统处于静止状态时右边砝码挂在盘底上方l处,然后右边砝码由于细线断裂而自由落下,已知每个托的。质量和砝码的质量都是m,绳子与滑轮无摩擦且重量不计。求 1 当右边砝码撞击盘底前一瞬间系统的总动能 2 碰撞前后系统的总动量。分析与解答 首先应明确,系...