jzoj 2570. 【NOIP2011模拟9.17】数字生成游戏

发布于 2019-03-29  4 次阅读


题目描述

小明完成了这样一个数字生成游戏,对于一个不包含0的数字s来说,有以下3种生成新的数的规则:
1.将s的任意两位对换生成新的数字,例如143可以生成341,413,134;
2.将s的任意一位删除生成新的数字,例如143可以生成14,13,43
3.在s的相邻两位之间s[i],s[i + 1]之间插入一个数字x,x需要满足s[i]

输入

输入文件gen.in的第一行包含1个正整数,为初始数字s。
第2行包含一个正整数m,为询问个数。
接下来m行,每行一个整数t(t不包含0),表示询问从s开始不断生成数字到t最少要进行多少次操作。任两个询问独立,即上一个询问生成过的数到下一个询问都不存在,只剩下初始数字s。

输出

输出文件gen.out包括m行,每行一个正整数,对每个询问输出最少操作数,如果无论也变换不成,则输出-1。

思路

bfs求出所有可能做到的数,将次数记录下来,读入时直接输出
(看起来容易做起来难系列)

var
  t,f:array[0..100000] of longint;
  i,j,k,s,n,m,o:longint;
procedure bfs;
var
  tail,head,l,len,x,xx:longint;
  st:string;
  ch:char;
begin
  f[o]:=1;
  head:=0; tail:=1;
  t[1]:=o;
  str(o,st);
  xx:=length(st);
  while head<=tail do
    begin
      inc(head);
      for i:=1 to 3 do
        begin
          if i=1 then
            begin
              str(t[head],st);
              len:=length(st);
              for j:=1 to len do
                for k:=1 to len do
                  if j<>k then
                    begin
                      ch:=st[j];
                      st[j]:=st[k];
                      st[k]:=ch;
                      val(st,x);
                      if f[x]=0 then
                        begin
                          f[x]:=f[t[head]]+1;
                          inc(tail);
                          t[tail]:=x;
                        end;
                      str(t[head],st);
                    end;
            end;
          if i=2 then
            begin
              str(t[head],st);
              len:=length(st);
              for j:=1 to len do
                begin
                  delete(st,j,1);
                  val(st,x);
                  if f[x]=0 then
                    begin
                      f[x]:=f[t[head]]+1;
                      inc(tail);
                      t[tail]:=x;
                    end;
                  str(t[head],st);
                end;
            end;
          if i=3 then
            begin
              str(t[head],st);
              len:=length(st);
              if len>=xx then continue;
              for j:=1 to len-1 do
                begin
                  for k:=ord(st[j])-48+1 to ord(st[j+1])-48-1 do
                    begin
                      ch:=chr(k+48);
                      insert(ch,st,j+1);
                      val(st,x);
                      if f[x]=0 then
                        begin
                          f[x]:=f[t[head]]+1;
                          inc(tail);
                          t[tail]:=x;
                        end;
                      str(t[head],st);
                    end;
                end;
            end;
        end;
    end;
end;
begin
  readln(o);
  readln(n);
  bfs;
  for i:=1 to n do
    begin
      readln(m);
      if f[m]-1<>0 then writeln(f[m]-1)
      else if o=m then writeln(0)
        else writeln(-1);
    end;
end.
]]>