首页 > 代码库 > BZOJ1562: [NOI2009]变换序列

BZOJ1562: [NOI2009]变换序列

2024-07-17 11:50:24   215人阅读

1562: [NOI2009]变换序列

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 1148  Solved: 599
[Submit][Status]

Description

Input

Output

Sample Input

5
1 1 2 2 1

Sample Output

1 2 4 0 3

HINT

30%的数据中N≤50；
60%的数据中N≤500；
100%的数据中N≤10000。

Source

题解：

不愧是NOI的题目，果然是好题。

具体题解建BYVOID的博客：https://www.byvoid.com/blog/noi-2009-transform/ 

讲的非常清楚，个人认为第二种解法是容易想到的，这其中有很多细节需要注意：

1.在寻找最小字典序的时候，加入一个当前查询点，使得在寻找增广路的时候如果x<=cur 那么返回false

   这是我在思考的时候没有想到的，就是如何能让后面的点在更新解的时候不妨碍到前面已经更新过的点

   这是一个非常好的思路，十分巧妙

2.我在刚开始想的时候想到每个点一定有两个匹配点吗？答案是不一定的

   于是我在程序中进行了进一步的验证，但在后面的解题中我并没有再考虑a[i]=-1 or b[i]=-1的情况，同样得到了正确的答案

   应该是cur的限制卡掉了这些-1

代码：

 

 1 const maxn=10000+100;maxm=20000+100; 2 type node=record 3      go,next:longint; 4      end; 5 var e:array[0..maxm] of node; 6     head,a,b,px,py,c:array[0..maxn] of longint; 7     v:array[0..maxn] of boolean; 8     cur,i,n,tot,ans,tmp:longint; 9     procedure swap(var x,y:longint);10      var t:longint;11          begin12          t:=x;x:=y;y:=t;13          end;14 15 procedure insert(x,y:longint);16  begin17  inc(tot);18  e[tot].go:=y;e[tot].next:=head[x];head[x]:=tot;19  end;20 function find(x:longint):boolean;21  var i,y:longint;22  begin23  if x<=cur then exit(false);24  i:=head[x];25  while i<>0 do26   begin27   y:=e[i].go;28   if not(v[y]) then29    begin30    v[y]:=true;31    if (py[y]=-1) or (find(py[y])) then32     begin33     py[y]:=x;34     px[x]:=y;35     exit(true);36     end;37    end;38   i:=e[i].next;39   end;40  exit(false);41  end;42 procedure init;43  begin44  readln(n);45  for i:=0 to n-1 do46    begin47    read(c[i]);48    a[i]:=(i+c[i]) mod n;49    if n-abs(a[i]-i)<c[i] then a[i]:=-1;50    b[i]:=(i+n-c[i]) mod n;51    if abs(b[i]-i)<c[i] then b[i]:=-1;52    if a[i]>b[i] then swap(a[i],b[i]);53    if a[i]<>-1 then insert(i,a[i]);54    if b[i]<>-1 then insert(i,b[i]);55    writeln(a[i],‘ ‘,b[i]);56    end;57  end;58 procedure main;59  begin60  for i:=0 to n-1 do py[i]:=-1;61  cur:=-1;62  for i:=0 to n-1 do63   begin64   fillchar(v,sizeof(v),false);65   if find(i) then inc(ans);66   end;67  if ans<>n then begin writeln(‘No Answer‘);exit;end;68  fillchar(v,sizeof(v),false);69  for i:=0 to n-1 do70   begin71   if px[i]<>a[i] then72     begin73     cur:=i;74     fillchar(v,sizeof(v),false);75     tmp:=py[a[i]];76     py[a[i]]:=i;77     py[b[i]]:=-1;78     v[a[i]]:=true;79     if find(tmp) then80       begin81        px[i]:=a[i]82       end83     else84       begin85        py[a[i]]:=tmp;86        py[b[i]]:=i;87       end;88     end;89   end;90  write(px[0]);for i:=1 to n-1 do write(‘ ‘,px[i]);91  end;92 begin93  assign(input,‘input.txt‘);assign(output,‘output.txt‘);94  reset(input);rewrite(output);95  init;96  main;97  close(input);close(output);98 end.
View Code

 


联系
我们