当前位置: 代码迷 >> 综合 >> 1207. 遥控车 (Standard IO)
  详细解决方案

1207. 遥控车 (Standard IO)

热度:4   发布时间:2023-10-09 12:43:51.0

Description

平平带着韵韵来到了游乐园,看到了n辆漂亮的遥控车,每辆车上都有一个唯一的名字name[i]。韵韵早就迫不及待地想玩名字是s的遥控车。可是韵韵毕竟还小,她想象的名字可能是一辆车名字的前缀(也就是说能确定一个i,使s是name[i]的前缀),这时她就能玩第i辆车;或者是一个无中生有的名字,即s不是任何一辆车名字的前缀,这时候她什么也不能玩。
你需要完成下面的任务:
1.韵韵想了m个她想要的名字,请告诉她能玩多少次。
2.由于管理员粗心的操作,导致每辆车的摆放位置都可能出现微小的差错,原来第i辆车现在的位置可能是i-1、i、i+1中的任意一个(第1辆车的位置不可能是0,第n辆车的位置不可能是n+1)。请你计算出共有多少种可能的排列。
注:数据保证当s是name[i]的前缀时,i是唯一确定的。一辆车可以玩多次。
题解:
  第一问:二分匹配
  第二问:斐波那契数列f(n)位
代码:
var
  i,n,m,ans,k:longint;
  s:string;
  a:array[0..20001] of string;
  x,y,z:array[1..20000] of longint;
procedure sort(i,j:longint);
var
  l,r:longint;
  m:string;
begin
  l:=i;
  r:=j;
  m:=a[(i+j) shr 1];
  repeat
    while a[i]<m do inc(i);
    while a[j]>m do dec(j);
    if i<=j then
      begin
        a[0]:=a[i];
        a[i]:=a[j];
        a[j]:=a[0];
        inc(i);
        dec(j);
      end;
  until i>j;
  if i<r then sort(i,r);
  if l<j then sort(l,j);
end;
function search(l,r:longint):boolean;
var
  temp:boolean;
  mid,t:longint;
begin
  search:=false;
  repeat
    mid:=(l+r)div 2;
    if copy(a[mid],1,length(s))=s then
      begin
        search:=true;
        t:=1;
        while copy(a[mid+t],1,length(s))=s do
          begin inc(ans);inc(t);end;
        t:=1;
        while copy(a[mid-t],1,length(s))=s do begin inc(ans);inc(t);end;
        break;
      end
    else
      begin
        if l+1=r then
          if copy(a[mid+1],1,length(s))=s then
            inc(r)
          else break;
        if a[mid]>s then r:=mid
          else l:=mid
      end;
  until l=r;
end;
procedure main;
var
  i:longint;
begin
  for i:=1 to k do
    begin
      x[i]:=x[i]+y[i];
      x[i+1]:=x[i+1]+x[i] div 10;
      x[i]:=x[i] mod 10;
    end;
  if x[k+1]<>0 then inc(k);
end;
begin
  readln(n,m);
  for i:=1 to n do
    readln(a[i]);
  sort(1,n);a[0]:='';
  for i:=1 to m do
    begin
      readln(s);
      if search(1,n) then inc(ans);
    end;
  writeln(ans);
  k:=1;
  x[1]:=1;z[1]:=1;
  for i:=1 to n-1 do
    begin
      y:=z;z:=x;
      main;
    end;
  for i:=k downto 1 do
    write(x[i]);
end.
  相关解决方案