NOT A BLOG | sqybi

URAL 1158 — Censored!

Posted on 三月 19th, 2008.

一个晚上,在Nxun和MaShuo的帮助下,终于AC了URAL的1158…

这道题是一个自动机上的DP,算是挺经典的了.

首先按照那些forbidden words建立自动机,并在适当的位置标注该位置是某个单词的结尾.
然后,f[i, j]表示当前在自动机上走第i步,走到了Trie树的第j号结点.则f[i, j] -> f[i+1, pre]; f[i+1, k]; 0.
其中,pre代表在自动机上不断找pre找到的那个结点…不太好表述,就是说在下面没有孩子结点的时候不是向上走么…然后就是最后走到的那个结点…
f[i+1, k]是正常情况,就是k是j的孩子结点,然后就f[i+1, k] <- f[i+1, k] + f[i, j].
0是说,对于上面的那个f[i+1, k],若k是一个单词的结束,那么肯定不能到k啊…所以f[i+1, k] <- 0.

发现自动机上的DP还挺难表述…

不过要注意一点的是,比如i结点是j结点的pre,那么如果i是一个单词的结束被打上标记,j也要被打上标记(就是我在程序里用//important!注释标注的那一句).刚开始的WA就是这个原因.

这道题的提交结果:
WA on Test 2; WA on Test 13; AC.
第一次的WA很无语…BFS和跑自动机写到了一起…转移方程不对…还好挺好改.

 

{
URAL 1158; Censored!
- sqybi’s code
- 自动机+DP
}
//for my winsty
{$APPTYPE CONSOLE}
program ural1158_sqybi;
  const
    nn = 50;
    mm = 50;
    pp = 10;
    rr = 10;

  type
    trieNode = record
      son: array[1..nn]of longint;
      pre: longint;
      f: boolean;
    end;
    arr = array[0..100]of longint;

  var
    n, m, p, i, j, k, trieNum, now, qs, qe: longint;
    ch: char;
    res: arr;
    a: array[1..nn]of char;
    s: array[1..pp, 0..mm]of longint;
    q: array[1..mm*pp]of longint;
    d: array[0..mm, 1..mm*pp]of arr;    
    trie: array[0..mm*pp]of trieNode;

  procedure plus(a, b: arr; var c: arr);
    var
      i: longint;
    begin
      fillchar(c, sizeof(c), 0);
      c[0] := a[0];
      if b[0] > c[0] then
        c[0] := b[0];
      for i:=1 to c[0] do begin
        c[i] := c[i] + a[i] + b[i];
        c[i+1] := c[i] div rr;
        c[i] := c[i] mod rr;
      end;
      if c[c[0]+1] <> 0 then
        inc(c[0]);
      while (c[0] > 1) and (c[c[0]] = 0) do
        dec(c[0]);
    end;
  begin
    assign(input, ‘in.txt’);
    assign(output, ‘out.txt’);
    reset(input);
    rewrite(output);

    readln(n, m, p);
    for i:=1 to n do read(a[i]);
    readln;
    for i:=1 to p do begin
      while not seekEoLn do begin
        read(ch);
        for j:=1 to n do
          if ch = a[j] then begin
            inc(s[i, 0]);
            s[i, s[i, 0]] := j;
            break;
          end;
      end;
      readln;
    end;

    //create Trie
    trieNum := 1;
    for i:=1 to n do
      trie[0].son[i] := 1;
    trie[0].f := false;
    trie[1].f := false;
    for i:=1 to p do begin
      now := 1;
      for j:=1 to s[i, 0] do begin
        if trie[now].son[s[i, j]] = 0 then begin
          inc(trieNum);
          trie[trieNum].f := false;
          trie[now].son[s[i, j]] := trieNum;
        end;
        now := trie[now].son[s[i, j]];
      end;
      trie[now].f := true;
    end;

    //BFS
    qs := 1;
    qe := 1;
    q[1] := 1;
    trie[1].pre := 0;
    while qs <= qe do begin
      for i:=1 to n do
        if trie[q[qs]].son[i] <> 0 then begin
          inc(qe);
          q[qe] := trie[q[qs]].son[i];
          now := trie[q[qs]].pre;
          while trie[now].son[i] = 0 do
            now := trie[now].pre;
          now := trie[now].son[i];
          trie[q[qe]].f := trie[q[qe]].f or trie[now].f; //important!
          trie[q[qe]].pre := now;
        end;
      inc(qs);
    end;

    //DP
    fillchar(d, sizeof(d), 0);
    for i:=0 to m do
      for j:=1 to trieNum do
        d[i, j][0] := 1;
    d[0, 1][1] := 1;
    for i:=0 to m-1 do
      for j:=1 to trieNum do
        for k:=1 to n do
          if trie[j].son[k] <> 0 then begin
            if not trie[trie[j].son[k]].f then
              plus(d[i+1, trie[j].son[k]], d[i, j], d[i+1, trie[j].son[k]]);
          end
          else begin
            now := trie[j].pre;
            while trie[now].son[k] = 0 do
              now := trie[now].pre;
            now := trie[now].son[k];
            if not trie[now].f then
              plus(d[i+1, now], d[i, j], d[i+1, now]);
          end;

    //get result
    fillchar(res, sizeof(res), 0);
    res[0] := 1;
    for i:=1 to trieNum do
      plus(res, d[m, i], res);

    //output
    for i:=res[0] downto 1 do
      write(res[i]);

    close(input);
    close(output);
  end.

阅读(281 次)

Make a Comment

Make A Comment: ( 2 so far )

2 Responses to “URAL 1158 — Censored!”

Comments RSS Feed

Where's The Comment Form?