00923旅行复赛模拟2.docx
- 文档编号:9967799
- 上传时间:2023-05-22
- 格式:DOCX
- 页数:13
- 大小:924.86KB
00923旅行复赛模拟2.docx
《00923旅行复赛模拟2.docx》由会员分享,可在线阅读,更多相关《00923旅行复赛模拟2.docx(13页珍藏版)》请在冰点文库上搜索。
00923旅行复赛模拟2
解法:
先解决前50%
方法1:
利用曼哈顿距离分别求出每个点到其他点的横和纵距离和,他们的总和就是前50%的解。
代码:
fori:
=0ton-1do
forj:
=i+1ton-1do
sum:
=sum+int64(m-q(y[i]))*int64(m-q(y[j]))*int64(j-i)*int64
(2);
fori:
=0tom-1do
forj:
=i+1tom-1do
sum:
=sum+int64(n-q(x[i]))*int64(n-q(x[j]))*int64(j-i)*int64
(2);
方法2:
利用坐标。
代码:
varn,m,i,j,kk,t:
longint;
c:
char;
ko,kl:
extended;
a,b:
array[0..1001]oflongint;
fk:
array[0..1000001,1..2]oflongint;
f:
array[0..1001,0..1001]ofint64;
ff,f1:
array[0..1001]ofint64;
begin
readln(n,m);
fori:
=1tondobegin
forj:
=1tomdobegin
read(c);
ifc='.'thenbegin{记录坐标}
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);
fori:
=1tondobegin{求出第i行到其他行的总距离,第i行为0}
kk:
=0;
forj:
=i+1tondobegin
f[i,j]:
=abs(i-j)*a[j];
f[j,i]:
=abs(i-j)*a[i];
kk:
=kk+f[i,j];
end;
forj:
=1toi-1dokk:
=kk+f[i,j];
ff[i]:
=kk;
end;
fillchar(f,sizeof(f),0);
fori:
=1tomdobegin{求出第i列到其他列的总距离,第i列为0}
kk:
=0;
forj:
=i+1tomdobegin
f[i,j]:
=abs(i-j)*b[j];
f[j,i]:
=abs(i-j)*b[i];
kk:
=kk+f[i,j];
end;
forj:
=1toi-1dokk:
=kk+f[i,j];
f1[i]:
=kk;
end;
kl:
=0;ko:
=0;
fori:
=1totdobegin{利用坐标求出这个点到其他点的距离和}
kl:
=kl+ff[fk[i,1]]+f1[fk[i,2]];
ko:
=ko+(i-1);{单向边}
end;
writeln(kl/(ko*2+t):
0:
4);{ko*2+t:
双向边+点的个数}
end.
方法3:
利用矩形。
代码:
varx,y,n,m,t,ans:
int64;
i,j:
longint;
a:
array[0..2000]ofansistring;
begin
readln(n,m);
t:
=n+m-2;ans:
=0;
fori:
=1totdobegin{枚举距离}
x:
=1;y:
=i+1;{枚举坐标}
while(x<=n)dobegin
if(y<=m)and(y>0)thenbegin
if(x>1)and(y>1)theninc(ans,(n-x+1)*(m-y+1)*4*i)
{(x+1,y+1)的右下角有(n-x+1)*(m-y+1)个点,然后分别以这些点
为矩形的右下角点,利用对角线并且每个矩形有两条,长度为i,
再加上双向,为4*i}
elseif(x>1)and(y=1)theninc(ans,(n-x+1)*(m-y+1)*2*i)
{这个是类似(x,y)与(x-i,y)的连线,有(n-x+1)*(m-y+1)}
elseif(x=1)and(y>1)theninc(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;{有n*m为边的一端,又有n*m为边的另一端,所以有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=2x=1,y=3
T=2x=2,y=2
T=2x=3,y=1
T=2x=1,y=4
T=2x=2,y=3
T=2x=3,y=2
T=2x=4,y=1
求得和为38
过了前50%后,要解决后面的障碍。
由上面解释可知,因题目不会全封锁,所以只需原距离+2,但问题是如何的知那些点对需要处理。
如:
X
上面只有1个,下面2个,设above=1,below=2
那么点对有2个,总值+4
以左边的为参考列
当在相邻列的位置上有X时且在其上面时
在X下面的点就一定要拐路走。
以右边的为参考列
当在相邻列的位置上有X时且在其下面时
在X下面的点就不需要拐路走。
上面的不用管否则会重复。
然后按上面的方法,分别枚举行和列,先进行本行和列,再进行相邻行和列的X的比较就可以了。
程序:
constnn=1010;
varn,m,i,j,below,above:
longint;
sum:
int64;
ans:
real;
ch:
array[0..nn,0..nn]ofchar;
x,y:
array[0..nn]oflongint;
functionq(a:
longint):
longint;
begin
ifa>=0thenexit
(1)elseexit(0)
end;
begin
readln(n,m);
fori:
=0ton-1dobegin
forj:
=0tom-1doread(ch[i,j]);
readln
end;
fori:
=0ton-1dobegin
y[i]:
=-1;
forj:
=0tom-1doifch[i,j]='X'thenbegin
y[i]:
=j;break
end
end;
forj:
=0tom-1dobegin
x[j]:
=-1;
fori:
=0ton-1doifch[i,j]='X'thenbegin
x[j]:
=i;break
end
end;
fori:
=0ton-1do
forj:
=i+1ton-1do
sum:
=sum+int64(m-q(y[i]))*int64(m-q(y[j]))*int64(j-i)*int64
(2);
fori:
=0tom-1do
forj:
=i+1tom-1do
sum:
=sum+int64(n-q(x[i]))*int64(n-q(x[j]))*int64(j-i)*int64
(2);
fori:
=0tom-1dobegin
ifx[i]=-1thencontinue;
below:
=n-1-x[i];above:
=x[i];
sum:
=sum+int64(below)*int64(above)*int64(4);
forj:
=i+1tom-1dobegin
if(x[j]=-1)or(x[j]>x[j-1])thenbreak;
above:
=x[j];
sum:
=sum+int64(below)*int64(above)*int64(4);
end;
above:
=x[i];
forj:
=i-1downto0dobegin
if(x[j]=-1)or(x[j]>x[j+1])thenbreak;
above:
=x[j];
sum:
=sum+int64(below)*int64(above)*int64(4);
end;
end;
fori:
=0ton-1dobegin
ify[i]=-1thencontinue;
below:
=y[i];above:
=m-1-y[i];
sum:
=sum+int64(below)*int64(above)*int64(4);
forj:
=i+1ton-1dobegin
if(y[j]=-1)or(y[j] above: =m-1-y[j]; sum: =sum+int64(below)*int64(above)*int64(4); end; above: =m-1-y[i]; forj: =i-1downto0dobegin if(y[j]=-1)or(y[j] above: =m-1-y[j]; sum: =sum+int64(below)*int64(above)*int64(4); end; end; ans: =0; fori: =0ton-1doans: =ans+m-q(y[i]);{所有的“。 ”,不含“X”} ans: =ans*ans; ans: =sum/ans; writeln(ans: 0: 4); end.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 00923 旅行 复赛 模拟