NOI 2011阿狸的打字机 题解.doc

NOI 2011阿狸的打字机 题解【题目描述】阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有28个按键，分别印有26个小写英文字母和B、P两个字母。 经阿狸研究发现，这个打字机是这样工作的：l 输入小写字母，打字机的一个凹槽中会加入这个字母(按P前凹槽中至少有一个字母)。l 按一下印有B的按键，打字机凹槽中最后一个字母会消失。l 按一下印有P的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失（保证凹槽中至少有一个字母）。例如，阿狸输入aPaPBbP，纸上被打印的字符如下： a aa ab 我们把纸上打印出来的字符串从1开始顺序编号，一直到n。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数(x,y)（其中1x,yn），打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。 阿狸发现了这个功能以后很兴奋，他想写个程序完成同样的功能，你能帮助他么？【思路分析】据说kmp算法可以得40分，直接用ac自动机可以得70分，AC自动机加上树状数组优化可以得100分。具体算法：首先构造Tire，根据构造规则B：将指针变为父节点；P：处理现在的节点；小写字母：访问相应的子节点。建立好Tire后，顺便构造Fail Tree。那么询问(i,j)就是i在fail树中的节点的子节点与j到树根的树链上的节点的交集的元素个数。这样可以用dfs序加树状数组优化。至于为如何用树状数组优化，如何构造ac自动机，那就你去法学习了。【源代码】【type.cpp】#include #include using namespace std;struct node int son26,fail,father,key; bool e;node ns100005;int nns=1, n = 0, m, ln = 0, sto100001, /记录某个字符串对应的节点 l100005, /dfs/bfs序列 ask1000013, st100005, next100005, /存储ask s100005, h100005, ls100005, le100005, /存储failtree low100005; /树状数组 char S100005;/Class_lowbitvoid low_inc(int w, int x) for (; w0; w -= w & (-w) sum += loww; return sum;/Class_AC_Automachineint getfail(int x) if (x=1) return 0; int w, key = nsx.key; w = nsnsx.father.fail; while (w!=0) & (nsw.sonkey=0) w = nsw.fail; if (w = 0) return 1; else return nsw.sonkey;void buildAC()/Build AC Automachine(done) int s = 0,e = 0,x; l0 = 1; for (; s=e; s+) x = ls; nsx.fail = getfail(x); for (int i=0; i1; i-) hi = snsi.fail; snsi.fail = i; dfs(1);/Class_Mainvoid init() /Build Tire & Read ask list(done) /Deal with String scanf(%s, S); int len = strlen(S), w = 1, t; for (int i=0; ilen; i+) if (Si = B) w = nsw.father; else if (Si = P) sto+n = w; nsw.e = true; else t = Si - 97; if (nsw.sont = 0) nsw.sont = +nns; nsnns.father = w; nsnns.key = t; w = nns; else w = nsw.sont; buildAC(); BuildFailTree(); / Deal With Asks scanf(%d, &m); for (int i=1; i=m; i+) scanf(%d%d, &aski0, &aski1); aski0 = stoaski0; aski1 = stoaski1; nexti = staski1; staski1 = i; void run() int len = strlen(S), w = 1; for (int i=0; ilen; i+) if (Si = B) low_inc(lsw, -1); w = nsw.father; else if (Si = P) for (int j=stw; j!=0; j=nextj) askj2 = low_sum(leaskj0) - low_sum(lsaskj0-1); else w = nsw.sonSi-97; low_inc(lsw, 1); int main() freopen(type.in,r,stdin); freopen(type.out,w,stdout); init(); run(); for (int i=1; i=m; i+) printf(%dn, aski2); return 0;【type.pas】type node=record son:array1.26of longint; fail,father,key:longint; e:boolean; end;var ns:array1.100005of node; nns:longint=1; len:longint; n,m,ln,i:longint; sto:array0.100005of longint; l:array0.100005of longint; ask:array0.100001,0.2of longint; st:array0.100005of longint; next:array0.100005of longint; for ansking s,h,ls,le:array0.100005of longint; low:array0.100005of longint; /? ss:array0.100005of char;procedure low_inc(w,x:longint);begin while w0 do begin inc(sum,loww); dec(w,w and (-w); end; exit(sum);end;function getfail(x:longint):longint;var w:longint; key:integer;begin if x=1 then exit(0); key:=nsx.key; w:=nsnsx.father.fail; while (w0)and(nsw.sonkey=0) do w:=nsw.fail; if w=0 then exit(1) else exit(nsw.sonkey);end;procedure build_ac;var s,e,i,x:longint;begin s:=0; e:=0; x:=0; l0:=1; while s=e do begin x:=ls; nsx.fail:=getfail(x); for i:=1 to 26 do if nsx.soni0 then begin inc(e); le:=nsx.soni; end; inc(s); end;end;procedure dfs(x:longint);var w:longint;begin inc(ln); lln:=x; lsx:=ln; w:=sx; while w0 do begin dfs(w); w:=hw; end; lex:=ln;end;procedure build_fail;var i:longint;begin for i:=nns downto 2 do begin hi:=snsi.fail; snsi.fail:=i; end; dfs(1);end;procedure init;var ch:char; w,t,i:longint;begin w:=1; while not eoln do begin inc(len); read(ch); sslen:=ch; case ch of B:w:=nsw.father; P:begin inc(n); ston:=w; nsw.e:=true; end; a.z:begin t:=ord(sslen)-96; if nsw.sont=0 then begin inc(nns); nsw.sont:=nns; nsnns.father:=w; nsnns.key:=t; w:=nns; end else w:=nsw.sont; end; end; end; build_ac; build_fail; readln(m); for i:=1 to m do begin readln(aski0,aski1); aski0:=stoaski0; aski1:=stoaski1; nexti:=staski1; staski1:=i; end;end;procedure run;var w,i,j:longint;begin w:=1; for i:=1 to len do begin if ssi=B then begin low_inc(lsw,-1); w:=nsw.father; end else if ssi=P then begin j:=stw; while j0 do begin askj,2:=low_sum(leaskj0)-low_sum(lsaskj0-1);j:=nextj; end; end