58问答库 > NOIP2010普及组复赛（Pascal语言）第三、第四题解题报告及源代码？

NOIP2010普及组复赛（Pascal语言）第三、第四题解题报告及源代码？

2024-11-22 20:22:32

推荐回答（2个）

回答（1）：

第三题两个导弹，求拦截导弹的最小和半径（半径的平方和）
难度：★★★★☆
时间：具体是一小时还是两小时记不清了
考试时的思路：贪心，求到两个圆心的最大值，然后如果该点到A的距离小于到B 的距离，则半径为该点到A的距离，另一个半径用同样的方法求
结果：20分
错误点：这样求出的半径会使有些点拦截不到
正确思路：排序+穷举
求所有点到两个圆心的距离，按到A圆的距离排序，按升序，则前i个给A，后面的给B
例如：到A的距离：1 2 3 4 5
到B 的距离：2 5 4 3 1
如果i=3，前3个让A拦截，r=3，后两个让B拦截，r：=3
如果i=4，前4个让A拦截，r=4，后一个让B拦截，r：=1
按照这个思路，需要排序之后穷举i:=1 to n do，然后将i+1 to n 中取最大值，归B拦截，这样的话时间复杂度为：O(N)2，超时；反过来思考：从后向前进行递推，
N到n的最大值为n 设为F[n]
N到n-1 的最大值为
n和n-1 之间的最大值为 max（f[n],b[n-1]）
N到n-2 的最大值为 max（f[n-1],b[n-2]）
这样时间复杂度接近 O(n)，就可以过了
结果：满分
代码：
program ex01;
const
inf='missile.in';
ouf='missile.out';
varx1,x2,y1,y2,i,j,k,tot,n,l,r,max1:longint;
x,y:array[1..100000] of longint;
a,b,f,d:array[1..100000] of longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;
procedure quicksort(l,r:longint);//到（x1,y1）点的距离排序
var
i,j,m,p:longint;
begin
i:=l;j:=r;
m:=a[(i+j) div 2];
repeat
while a[i]while a[j]>m do dec(j);
if i<=j then
begin
p:=a[i];a[i]:=a[j];a[j]:=p;
p:=b[i];b[i]:=b[j];b[j]:=p;
inc(i);dec(j);
end;
until i>j;
if l if i end;
begin
assign(input,inf);
reset(input);
assign(output,ouf);
rewrite(output);
readln(x1,y1,x2,y2);
readln(n);
for i:=1 to n do
readln(x[i],y[i]);
for i:=1 to n do
begin
a[i]:=sqr(x[i]-x1)+sqr(y[i]-y1);
b[i]:=sqr(x[i]-x2)+sqr(y[i]-y2);//求出到两个圆心的距离
end;
l:=1;r:=n
quicksort(l,r);//快排，不解释
for i:=n downto 1 do
begin
d[i]:=f[i+1]+a[i];//A和B的半径和
f[i]:=max(b[i],f[i+1]);//找后i个距B的最大值
end;
max1:=maxlongint;
for i:=1 to n do
if d[i] writeln(max1);
close(input);close(output); end.

第四题人机大战，在获胜的前提下求出最大的默契值
难度：★★★☆☆
时间：10分钟左右，最后十分钟，一个骗分的程序
思路：当时按照样例，想的是找所有数中的最大数，然后人取一个，电脑取一个，类似于模拟，，不过是错误的
最后没时间了，writeln（‘0’）
分数：0分
正确思路：贪心
1）找所有数中次大的，因为你选定默契值最大的武将之一后，最大值就被电脑“咔嚓”掉了。于是我们只可能取到次大值，而次大值中最大的就一定最优了。
2）这个值一定能取到，因为最大值被人机破坏，而人又取到的次大值，所以我们一定会赢（电脑是人设计滴~~！！）
代码：
program ex01;
const
inf='sanguo.in';
ouf='sanguo.out';
var
a:array[1..500,1..500] of longint;
n,i,j,k,tot,temp,max:longint;
begin
assign(input,inf);reset(input);
assign(output,ouf);rewrite(output);
fillchar(a,sizeof(a),0);
readln(n);
for i:=1 to n do
for j:=i+1 to n do
begin
read(a[i,j]);
a[j,i]:=a[i,j];//做成表格
end;
max:=-maxlongint;
k:=-maxlongint;
temp:=-maxlongint;//最终所求的数
for i:=1 to n do begin
max:=-maxlongint;//最大值
k:=-maxlongint;//次大值
for j:=1 to n do
if a[i,j]>max then
begin
k:=max;//记录次大值
max:=a[i,j];
end
else if a[i,j]>k then k:=a[i,j]
if k>temp then temp:=k;//与前一行的次大值进行比较
end;
writeln('1');
writeln(temp);
close(input);
close(output);
end.
最终评价本套题交了3遍
第一次：22个测试点（10 ，10，2，0 ）(思路错误)
第二次：30个测试点（10，10，10）
第三次：全过

回答（2）：

type
pos=record
d1,d2:qword;
end;
var
a:array[1..100000]of pos;
x1,x2,y1,y2,x,y:integer;
n,i:longint;
ans,max:qword;
function f(k:longint):longint;
var
i:longint;
begin
f:=k;
for i:=k+1 to n do
if a[i].d2>=a[f].d2 then f:=i;
end;
procedure qsort(l,r:longint);
var
i,j,m:longint;
t:pos;
begin
i:=l;j:=r;
m:=a[(i+j) div 2].d1;
repeat
while a[i].d1 while a[j].d1>m do dec(j);
if i<=j then
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
inc(i);dec(j);
end;
until i>j;
if i if lend;
begin
assign(input,'missile.in');reset(input);
assign(output,'missile.out');rewrite(output);
readln(x1,y1,x2,y2);
readln(n);
for i:=1 to n do
begin
readln(x,y);
a[i].d1:=sqr(x-x1)+sqr(y-y1);
a[i].d2:=sqr(x-x2)+sqr(y-y2);
end;
qsort(1,n);
max:=f(1);//求出离b最远的序号
ans:=a[max].d2;//离b最远的距离
for i:=1 to n do
begin
if max=i then max:=f(i+1);
if ans>a[max].d2+a[i].d1 then ans:=a[max].d2+a[i].d1;
end;
writeln(ans);
close(input);close(output);
end.
var
a:array[1..500,1..500]of longint;
n,i,j:integer;
max,max2,ans:longint;
procedure init;
begin
fillchar(a,sizeof(a),0);
readln(n);
for i:=1 to n do
begin
for j:=1 to n do
if i read(a[i,j]) else
if i>j then
a[i,j]:=a[j,i];
end;
ans:=0;
end;
procedure main;
begin
for i:=1 to n do
begin
if a[i,1]>a[i,2] then
begin
max:=a[i,1];
max2:=a[i,2];
end else
begin
max:=a[i,2];
max2:=a[i,1];
end;
for j:=3 to n do
begin
if max begin
max2:=max;
max:=a[i,j];
end else if max2 max2:=a[i,j];
end;
if max2>ans then ans:=max2;
end;
writeln(1);
writeln(ans);
end;
begin
assign(input,'sanguo.in');reset(input);
assign(output,'sanguo.out');rewrite(output);
init;
main;
close(input);close(output);
end.

最新问答

从成都火车东站到武候区金履四路怎么走?

青岛本地人请进！！

黄中小区站到成都武侯区一环路南三段53号怎么坐公交

钢笔一般多少钱

集体所有制企业的性质

罗马2全面战争如何存档

成绩特别拉我是女孩子高一读的私立学校到底要不要转学去职中还是继续混日子。

腾讯大王卡归属地天津我去河北能用腾讯的app么

成都火车北站到武侯区少陵路公交

成都东站到武侯区万兴路520号怎么坐地铁？