当前位置:首页 >> 工学 >>

NOI 2011阿狸的打字机 题解


NOI 2011 阿狸的打字机 题解 【题目描述】 阿狸喜欢收藏各种稀奇古怪的东西,最近他淘到一台老式的打字机。打字机上只有 28 个按 键,分别印有 26 个小写英文字母和'B'、'P'两个字母。 经阿狸研究发现,这个打字机是这样 工作的: ? 输入小写字母,打字机的一个凹槽中会加入这个字母(按 P 前凹槽中至少有一个字母)。 ? 按一下印有'B'的按键,打字机凹槽中最后一个字母会消失。 ? 按一下印有'P'的按键,打字机会在纸上打印出凹槽中现有的所有字母并换行,但凹槽中 的字母不会消失(保证凹槽中至少有一个字母) 。 例如,阿狸输入 aPaPBbP,纸上被打印的字符如下: a aa ab 我们把纸上打印出来的字符串 从 1 开始顺序编号,一直到 n。打字机有一个非常有趣的功能,在打字机中暗藏一个带数字 的小键盘,在小键盘上输入两个数(x,y)(其中 1≤x,y≤n) ,打字机会显示第 x 个打印的字符 串在第 y 个打印的字符串中出现了多少次。 阿狸发现了这个功能以后很兴奋,他想写个程 序完成同样的功能,你能帮助他么? 【思路分析】 据说 kmp 算法可以得 40 分,直接用 ac 自动机可以得 70 分,AC 自动机加上树状数组 优化可以得 100 分。 具体算法: 首先构造 Tire,根据构造规则 B:将指针变为父节点; P:处理现在的节点; 小写字母:访问相应的子节点。 建立好 Tire 后,顺便构造 Fail Tree。 那么询问(i,j)就是 i 在 fail 树中的节点的子节点与 j 到树根的树链上的节点的交集的元素 个数。这样可以用 dfs 序加树状数组优化。 至于为如何用树状数组优化,如何构造 ac 自动机,那就你去法学习了。 【源代码】 【type.cpp】 #include <cstdio> #include <cstring> using namespace std; struct node { int son[26],fail,father,key; bool e; }; node ns[100005]; int nns=1, n = 0, m, ln = 0, sto[100001], //记录某个字符串对应的节点 l[100005], //dfs/bfs 序列 ask[100001][3], st[100005], next[100005], //存储 ask s[100005], h[100005], ls[100005], le[100005], //存储 failtree low[100005]; //树状数组

char S[100005]; //Class_lowbit void low_inc(int w, int x) { for (; w<=ln; w += w & (-w)) low[w] += x; } int low_sum(int w) { int sum = 0; for (; w>0; w -= w & (-w)) sum += low[w]; return sum; } //Class_AC_Automachine int getfail(int x) { if (x==1) return 0; int w, key = ns[x].key; w = ns[ns[x].father].fail; while ((w!=0) && (ns[w].son[key]==0)) w = ns[w].fail; if (w == 0) return 1; else return ns[w].son[key]; } void buildAC()//Build AC Automachine(done) { int s = 0,e = 0,x; l[0] = 1; for (; s<=e; s++) { x = l[s]; ns[x].fail = getfail(x); for (int i=0; i<26; i++) if (ns[x].son[i] != 0) l[++e] = ns[x].son[i]; } } //Class_FailTree void dfs(int x) { l[++ln] = x;

ls[x] = ln; for (int w=s[x]; w!=0; w=h[w]) dfs(w); le[x] = ln; } void BuildFailTree() { for (int i=nns; i>1; i--) { h[i] = s[ns[i].fail]; s[ns[i].fail] = i; } dfs(1); } //Class_Main void init() //Build Tire & Read ask list(done) { //Deal with String scanf("%s", S); int len = strlen(S), w = 1, t; for (int i=0; i<len; i++) if (S[i] == 'B') w = ns[w].father; else if (S[i] == 'P') { sto[++n] = w; ns[w].e = true; } else { t = S[i] - 97; if (ns[w].son[t] == 0) { ns[w].son[t] = ++nns; ns[nns].father = w; ns[nns].key = t; w = nns; } else w = ns[w].son[t]; } buildAC(); BuildFailTree();

// Deal With Asks scanf("%d", &m); for (int i=1; i<=m; i++) { scanf("%d%d", &ask[i][0], &ask[i][1]); ask[i][0] = sto[ask[i][0]]; ask[i][1] = sto[ask[i][1]]; next[i] = st[ask[i][1]]; st[ask[i][1]] = i; } } void run() { int len = strlen(S), w = 1; for (int i=0; i<len; i++) if (S[i] == 'B') { low_inc(ls[w], -1); w = ns[w].father; } else if (S[i] == 'P') for (int j=st[w]; j!=0; j=next[j]) ask[j][2] = low_sum(le[ask[j][0]]) - low_sum(ls[ask[j][0]]-1); else { w = ns[w].son[S[i]-97]; low_inc(ls[w], 1); } } int main() { freopen("type.in","r",stdin); freopen("type.out","w",stdout); init(); run(); for (int i=1; i<=m; i++) printf("%d\n", ask[i][2]); return 0; }

【type.pas】 type node=record son:array[1..26]of longint; fail,father,key:longint; e:boolean; end; var ns:array[1..100005]of node; nns:longint=1; len:longint; n,m,ln,i:longint; sto:array[0..100005]of longint; l:array[0..100005]of longint; ask:array[0..100001,0..2]of longint; {} st:array[0..100005]of longint; next:array[0..100005]of longint; {for ansking} s,h,ls,le:array[0..100005]of longint; low:array[0..100005]of longint; //???? ss:array[0..100005]of char; procedure low_inc(w,x:longint); begin while w<=ln do begin inc(low[w],x); inc(w,w and (-w)); end; end; function low_sum(w:longint):longint; var sum:longint=0; begin while w>0 do begin inc(sum,low[w]); 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:=ns[x].key;

w:=ns[ns[x].father].fail; while (w<>0)and(ns[w].son[key]=0) do w:=ns[w].fail; if w=0 then exit(1) else exit(ns[w].son[key]); end; procedure build_ac; var s,e,i,x:longint; begin s:=0; e:=0; x:=0; l[0]:=1; while s<=e do begin x:=l[s]; ns[x].fail:=getfail(x); for i:=1 to 26 do if ns[x].son[i]<>0 then begin inc(e); l[e]:=ns[x].son[i]; end; inc(s); end; end; procedure dfs(x:longint); var w:longint; begin inc(ln); l[ln]:=x; ls[x]:=ln; w:=s[x]; while w<>0 do begin dfs(w); w:=h[w]; end; le[x]:=ln; end; procedure build_fail; var i:longint; begin for i:=nns downto 2 do begin h[i]:=s[ns[i].fail]; s[ns[i].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); ss[len]:=ch; case ch of 'B':w:=ns[w].father; 'P':begin inc(n); sto[n]:=w; ns[w].e:=true; end; 'a'..'z':begin t:=ord(ss[len])-96; if ns[w].son[t]=0 then begin inc(nns); ns[w].son[t]:=nns; ns[nns].father:=w; ns[nns].key:=t; w:=nns; end else w:=ns[w].son[t]; end; end; end; build_ac; build_fail; readln(m); for i:=1 to m do begin readln(ask[i][0],ask[i][1]); ask[i][0]:=sto[ask[i][0]]; ask[i][1]:=sto[ask[i][1]]; next[i]:=st[ask[i][1]]; st[ask[i][1]]:=i; end; end; procedure run; var w,i,j:longint; begin w:=1; for i:=1 to len do begin if ss[i]='B' then begin low_inc(ls[w],-1); w:=ns[w].father; end else if ss[i]='P' then

begin j:=st[w]; while j<>0 do begin ask[j,2]:=low_sum(le[ask[j][0]])-low_sum(ls[ask[j][0]]-1); j:=next[j]; end; end else begin w:=ns[w].son[ord(ss[i])-96]; low_inc(ls[w],1); end; end; end; begin assign(input,'type.in'); assign(output,'type.out'); reset(input); rewrite(output); init; run; for i:=1 to m do writeln(ask[i][2]); close(input); close(output); end.


相关文章:
NOI 2011阿狸的打字机 题解.doc
NOI 2011阿狸的打字机 题解_工学_高等教育_教育专区。NOI 2011 阿狸的打字机 题解 【题目描述】 阿狸喜欢收藏各种稀奇古怪的东西,最近他淘到一台老式的打字机...
NOI_2011阿狸的打字机_题解.doc
NOI_2011阿狸的打字机_题解_初中教育_教育专区。NOI 2011 阿狸的打字机 题解 【题目描述】 阿狸喜欢收藏各种稀奇古怪的东西,最近他淘到一台老式的打字机。打字...
NOI2011day1.pdf
NOI2011day1_IT/计算机_专业资料。NOI 2011 第一试题目 第二十八届全国信息...阿狸的打字机 type type type.in type.out 1秒 256M 10 10 否 传统型 ...
字符串问题.ppt
字符串问题 - 字符串 HFLS-WJMZBMR AC自动机->Fail树 ? 十分有用的数据结构。 [Noi2011]阿狸的打字机 ? http://www.lydsy.com/JudgeOnline/
NOI2011基本知识题库.pdf
NOI2011基本知识题库 - NOI2011 基础知识题库 ?竞赛环境和竞赛规则 1. NOI 机试使用的操作系统是:Linux 2. Linux 中为文件改名使用的命令是:mv 3. 在 L...
noi2011团队赛试题.doc
第二十八届全国信息学奥林匹克竞赛 CCF NOI 2011 团体对抗赛竞赛时间:2011 :00竞赛时间:2011 年 8 月 11 日上午 8:00-12:00 题目名称 英文名称 输入 输出...
NOI2011 Day2试题.doc
NOI2011 Day2试题_IT/计算机_专业资料。RT 道路修建【问题描述】
noi2011第2题.doc
noi2011第2题 - 2.统计单词数 (stat.cpp/c/pas) 【问
NOI2011笔试题基础知识题库.pdf
NOI2011笔试题基础知识题库_IT认证_资格考试/认证_教育专区。NOI2011笔试题目一览无余! NOI2011 基础知识题库 ?竞赛环境和竞赛规则 1. NOI 机试使用的操作系统...
noi2011获奖名单_图文.doc
解铮 王翔宇 施天宁 王求元 华逸青 孙禹达 孔令航 金汶功 张未雨 高宇 莫...noi2011第2题 2页 免费 noi2011第1题 2页 免费 [NOI2011阿狸的打字机]=....
noi2011获奖名单.xls
解铮 山东 340 男 山东师范大学附属中学 高二 赵宗昌 王翔宇 山东 339 男 ...noi2011第2题 2页 免费 noi2011第1题 2页 免费 [NOI2011阿狸的打字机]=....
(NOI)2011第十七届全国青少年信息学奥林匹克联赛初赛试....doc
(NOI)2011第十七届全国青少年信息学奥林匹克联赛初赛试题及答案_学科竞赛_
NOI2011Day2兔兔与蛋蛋游戏.doc
NOI2011Day2 兔兔与蛋蛋游戏 [分析]:这是一道二分图匹配的问题,先说说我的...然后看 了题解,发现自己其实已经离 AC 思路很近了,只要把原始思路的本质发掘...
CCF关于NOI2011名额分配方案的公告(6号).doc
CCF 关于 NOI2011 名额分配方案的公告 CCF[2011]第 6 号 CCF NOI 各省组织单位: 中国计算机学会决定对 NOI2011 名额分配方案进行改革,NOI2011 年各省 可得名额...
更多相关标签: