BZOJ1562: [NOI2009]变换序列

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          begin
12          t:=x;x:=y;y:=t;
13          end;
14 
15 procedure insert(x,y:longint);
16  begin
17  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  begin
23  if x<=cur then exit(false);
24  i:=head[x];
25  while i<>0 do
26   begin
27   y:=e[i].go;
28   if not(v[y]) then
29    begin
30    v[y]:=true;
31    if (py[y]=-1) or (find(py[y])) then
32     begin
33     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  begin
44  readln(n);
45  for i:=0 to n-1 do
46    begin
47    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  begin
60  for i:=0 to n-1 do py[i]:=-1;
61  cur:=-1;
62  for i:=0 to n-1 do
63   begin
64   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 do
70   begin
71   if px[i]<>a[i] then
72     begin
73     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) then
80       begin
81        px[i]:=a[i]
82       end
83     else
84       begin
85        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 begin
93  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