宁波市第29届中小学生程序设计竞赛复赛试题（初中组）解题报告(1)

dist[i]:=10000; end;

for i:=1 to n do begin //将机器进行连边 cnt1:=0; j:=head[i];

while j<>0 do begin v:=value[j]; inc(cnt1); jq[cnt1]:=v; j:=next[j]; end;

for j:=1 to cnt1-1 do

for i1:=j+1 to cnt1 do begin g[jq[j],jq[i1]]:=1; g[jq[i1],jq[j]]:=1; end; end;

while hd<=tl do begin //最短路spfa算法，基本类似宽搜 u:=q[hd]; inc(hd); vist[u]:=0;

for v:=1 to m do

if (g[u][v]=1)and(dist[v]>dist[u]+1) then begin dist[v]:=dist[u]+1; if vist[v]=0 then begin vist[v]:=1; inc(tl); q[tl]:=v; end; end; end;

ans:=10000; for i:=1 to m do

if (ist[i]=1)and(dist[i]

if n=1 then writeln(1) else if ans<10000 then writeln(ans+1) else writeln(-1); end.

第四题 马球比赛

首先不难想到最简单的做法，枚举组队马匹的数量c1，计算c1能够整除的数的个数c2，

我们的答案就是最大的c1*c2 （根据题意有c2>1)。

这样的算法时间复杂度是多少呢？N<=200 000，a(i)<=2 000 000, 那么时间复杂度就是O（n*a(i))，若用上述算法，将会超时，因此要想出优化算法。

分析题目后，组队马匹数c1的枚举是必要的，那么接下来我们必须在O(1)的时间内统计出有多少数能够被c1整除，如何做到O（1）呢？只有一个办法，在枚举c1之前，将答案预处理出来，比如我们用一个数组c来保存，其中c[x]表示以x为组队马匹数时，有多少个数能够整除x。

但是c数组该怎么计算呢？枚举x吗？显然不能， 这样就与上面的做法没什么差别了，换个思路，我们可以对于每个a(i) 求出它的所有因子x，对于每个x，都执行c[x]:=c[x]+1的操作，就可以将c(x)计算出来了。

为了保证在计算a(i)的因子是能够不超时，我们在事先先打一个质数表，然后利用质数表，将a(i)进行质因数分解，再利用a(i)的质因数，算出a(i)的所有因子。由于a(i)<=2 000 000，所以它的因子个数不会超过500，不会超时。

计算完c数组后，题目就很容易解决了，枚举组队马匹数c1，求一个最大的c1*c[c1] （c[c1]>1），即为所求答案。

代码如下：

var

n,cnt,cnt1,i,j,ans:longint;

a:array [1..200000] of longint; c:array [1..2000000] of longint; b:array [1..2000] of boolean; d,e,f:array [1..2000] of longint;

procedure find(k,count:integer); // 根据质因数搜索求出a[i]的每一个约数 var i:integer; begin

if k>cnt1 then begin inc(c[count]); exit; end;

for i:=1 to f[k] do begin find(k+1,count); count:=count*e[k]; end;

find(k+1,count); end;

begin

readln(n);

for i:=1 to n do read(a[i]);

fillchar(b,sizeof(b),true); b[1]:=false;

for i:=2 to trunc(sqrt(2000)+0.00001) do //筛质数表 if b[i] then for j:=2 to 2000 div i do b[i*j]:=false;

cnt:=0;

for i:=2 to 2000 do //将质数都存到一个d数组里，方便使用 if b[i] then begin inc(cnt); d[cnt]:=i; end;

fillchar(c,sizeof(c),0);

for i:=1 to n do begin cnt1:=0;

for j:=1 to cnt do //将每一个a[i]分解质因数 if a[i] mod d[j]=0 then begin inc(cnt1); e[cnt1]:=d[j]; f[cnt1]:=0;

while a[i] mod d[j]=0 do begin a[i]:=a[i] div d[j]; inc(f[cnt1]); end; end;

if a[i]>1 then begin inc(cnt1); e[cnt1]:=a[i]; f[cnt1]:=1; end;

find(1,1); end;

ans:=2;

for i:=1 to 2000000 do //比较得出最大的答案 if (c[i]>1)and(ans

end.