Section 1.4 Arithmetic Progressions

2023-09-27 12:07:58

寒假的第一天，终于有空再写题目了，专心备战了。本想拿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[0..62600*2] of boolean;
    list:array[0..62600] of longint;
    a0,b0:array[0..10000] of longint;
    m,n,i,j,a,b,count,ans_count,temp:longint;
    flag,code:boolean;
procedure start;
var i,j:longint;
begin
  count:=0;
  for i:=0 to m do
    for j:=0 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-1)*b>m*m*2 then exit;
  flag:=true;
  for i:=1 to n-1 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:=1 to count-1 do
    for j:=i+1 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<>0 then
    begin
      for i:=1 to ans_count-1 do
        for j:=i+1 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:=1 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[0..62600*2] 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:=0 to m do
    for j:=0 to m do
      se[i*i+j*j]:=true;
  fillchar(cha,sizeof(cha),false);
  for i:=0 to m do
    for j:=0 to m do
      for k:=0 to i do
        for l:=0 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:=2*m*m;
  code:=false;
  start;
  for b:=1 to trunc(max/(n-1)) do
    if cha[b]=true then
    begin
      for a:=0 to 2*m*m do
        begin
          if a+(n-1)*b>max then break;
          if se[a]=true then
            begin
              i:=1;flag:=true;
              while i<=n-1 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

Section 1.4 Arithmetic Progressions

码农公寓

相关文章