寒假的第一天，终于有空再写题目了，专心备战了。本想拿usaco上的题目练手热身，结果被磕住了T T。
其实这是一道穷举题，一开始我在穷举a，b，但是怎么优化就是过不了Test 8，后来参照NOCOW上的解题弄了se和list两个数组，也算是终于通过了，这时候已经是Submission #7了。（啊，有两次是因为没开文件，一次是因为没打‘NONE’）
总之，祝寒假的OI学习顺利吧~All or Nothing, Now or Never!
program ariprog2;
var se:array[..*] of boolean;
list:array[..] of longint;
a0,b0:array[..] of longint;
m,n,i,j,a,b,count,ans_count,temp:longint;
flag,code:boolean;
procedure start;
var i,j:longint;
begin
count:=;
for i:= to m do
for j:= to m do
begin
if se[i*i+j*j]=false then
begin
se[i*i+j*j]:=true;
inc(count);
list[count]:=i*i+j*j;
end;
end;
end;
procedure pd(a,b:longint);
var i:integer;
flag:boolean;
begin
if a+(n-)*b>m*m* then exit;
flag:=true;
for i:= to n- do
if se[a+i*b]=false then
begin
flag:=false;
break;
end;
if flag then
begin
inc(ans_count);
a0[ans_count]:=a;
b0[ans_count]:=b;
end;
end; begin
assign(input,'ariprog.in');reset(input);
assign(output,'ariprog.out');rewrite(output);
readln(n);
readln(m);
start;
for i:= to count- do
for j:=i+ to count do
begin
a:=list[i];
if list[j]<a then a:=list[j];
b:=abs(list[j]-list[i]);
pd(a,b);
end;
if ans_count<> then
begin
for i:= to ans_count- do
for j:=i+ to ans_count do
begin
if (b0[i]>b0[j]) or ((b0[i]=b0[j])and(a0[i]>a0[j])) then
begin
temp:=b0[i];b0[i]:=b0[j];b0[j]:=temp;
temp:=a0[i];a0[i]:=a0[j];a0[j]:=temp;
end;
end;
for i:= to ans_count do
writeln(a0[i],' ',b0[i]);
end
else
writeln('NONE');
close(input);close(output);
end.
ariprog2
Executing...
Test 1: TEST OK [0.000 secs, 720 KB]
Test 2: TEST OK [0.000 secs, 720 KB]
Test 3: TEST OK [0.000 secs, 720 KB]
Test 4: TEST OK [0.000 secs, 720 KB]
Test 5: TEST OK [0.022 secs, 720 KB]
Test 6: TEST OK [0.151 secs, 720 KB]
Test 7: TEST OK [1.717 secs, 720 KB]
Test 8: TEST OK [3.823 secs, 720 KB]
Test 9: TEST OK [3.834 secs, 720 KB]
All tests OK.
话说，过了的那个程序可以再优化的。
题目讲输出范围小于10000我就直接上O(N^2)排序了，用快排可以再省一点时间吧。
顺便把那个怎么也过不掉Test 8的程序也发上来好了，不能让自己白打这么久！！
program ariprog;
var se,cha:array[..*] of boolean;
m,n,i,j,k,l,a,b,max,num_se:longint;
flag,code:boolean; procedure start;
var i,j:integer;
begin
fillchar(se,sizeof(se),false);
for i:= to m do
for j:= to m do
se[i*i+j*j]:=true;
fillchar(cha,sizeof(cha),false);
for i:= to m do
for j:= to m do
for k:= to i do
for l:= to j do
cha[i*i+j*j-k*k-l*l]:=true;
end; begin
assign(input,'ariprog.in');reset(input);
assign(output,'ariprog.out');rewrite(output);
readln(n);
readln(m);
max:=*m*m;
code:=false;
start;
for b:= to trunc(max/(n-)) do
if cha[b]=true then
begin
for a:= to *m*m do
begin
if a+(n-)*b>max then break;
if se[a]=true then
begin
i:=;flag:=true;
while i<=n- do
begin
if se[a+i*b]=false then
begin
flag:=false;
break;
end;
inc(i);
end;
if flag then
begin
code:=true;
writeln(a,' ',b);
end;
end;
end;
end;
if not code then writeln('NONE');
close(input);close(output);
end.
ariprog