POI XII Stage I Bankomat (ban) 题解

只要依次求出每个动作的可能密码, 再在其中求出在所有动作的可行密码都出现的密码.

为了方便描述, 先作一些声明和定义:

• 一共有n个动作. 依题意, $n \le 1000$.
• 第i个动作的长度是t_i, 所有动作的总长度和为m. 依题意, $m \le 1000000$.
• 密码的字母表大小为k, 长度为s. 这里k = 10, s = 4.
• 密码片段是指长度不超过s的合法字符序列. 一个密码片段的位置是指这个密码片段在这个动作中的最早可能结束位置.

设A是一个密码片段, b是一个合法字符, 那么Ab的位置就是A的位置后(包括A的位置)b首次出现的位置.

于是, 我们只要求出所有的密码片段的位置, 就知道了哪些密码片段出现过.

最直接的方法

求出所有位置后(包括当前位置)每个字母首次出现的位置, 然后枚举所有密码, 验证是否出现. 时间复杂度: O(mk + nk^{s + 1}), 本题中最大运算量为20000000.

基于桶的方法

预处理和维护下面两个变量:

• next_same_i: 位置i后第一个和这个位置上字母相同的位置.
• first_c: 当前位置后(包括当前位置)字母c首次出现的位置.

再在每个位置上用一个桶存储在当前位置上的最早出现的密码片段.

顺序扫描所有的桶. 这样每个密码片段最多被扫描到一次. 额外的代价至多为动作的长度.

由于扫描是顺序的, 每向后移动一位, 可以在O(1)时间内更新first, 于是预处理和维护next_same和first的总时间为动作的长度.

于是本方法的时间复杂度为$O(n\frac{k^{s+1}-1}{k-1}+m)$, 本题中最大运算量为2111000.

参考代码

program poi2005stage1ban;
 
//writen by yangzhe1990
 
const
   maxt  = 10000;	//一个movement的最大长度
   maxs  = 10000;	//可能的密码个数
   digit = 10;		//字母表大小
 
var
   count_app : array [maxs..maxs*2 - 1] of longint;	//计数每个密码片段的出现次数
   head      : array [1..maxt] of longint;		//链表: 记录这个位置上出现的第一个密码片段
   next      : array [1..maxs*2 - 1] of longint;	//链表: 记录同一个位置上的下一个密码片段
   movement  : array [1..maxt] of longint;
   next_same : array [1..maxt] of longint;		//下一个和自己相同的字母的出现位置
   first     : array [0..digit - 1] of longint;		//当前位置后每个字母的最早出现位置
   n, k      : longint;
   i, t      : longint;
   j, s, ns  : longint;
   c         : char;
 
begin
   readln(n);
 
   filldword(count_app, maxs, 0);
   for k := 1 to n do begin
      read(t); read(c);
      for i := 1 to t do begin
         read(c);
         movement[i] := ord(c) - 48;
      end;
 
      fillchar(first, sizeof(first), 0);
      for i := t downto 1 do begin
         next_same[i] := first[movement[i]];
         first[movement[i]] := i;
      end;
 
      filldword(head, t, 0);
      for j := digit - 1 downto 0 do
         if first[j] <> 0 then begin
            next[j] := head[first[j]];
            head[first[j]] := 10 + j;
         end;
      for i := 1 to t do begin
         s := head[i];
         while s <> 0 do begin
            head[i] := next[s];
 
            if s < maxs then begin
               ns := (s + 1) * digit;
               for j := digit - 1 downto 0 do begin
                  dec(ns);
                  if first[j] <> 0 then begin
                     next[ns] := head[first[j]];
                     head[first[j]] := ns;
                  end;
               end;
            end
            else
               inc(count_app[s]);
 
            s := head[i];
         end;
 
         first[movement[i]] := next_same[i];
      end;
   end;
 
   s := 0;
   for j := maxs*2 - 1 downto maxs do
      if count_app[j] = n then
         inc(s);
   writeln(s);
end.