当前位置:首页 >> 初中教育 >>

NOI


NOI 2011 阿狸的打字机 题解 【题目描述】 阿狸喜欢收藏各种稀奇古怪的东西,最近他淘到一台老式的打字机。打字机上只有 28 个按 键,分别印有 26 个小写英文字母和'B'、'P'两个字母。 经阿狸研究发现,这个打字机是这样 工作的: ? 输入小写字母,打字机的一个凹槽中会加入这个字母(按 P 前凹槽中至少有一个字母)。 ? 按一下印有&#

39;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_2015获奖名单
CCF NOI2015 获奖名单金牌姓名 吴作凡 金策 袁宇韬 汪文潇 吉如一 张若天 张志俊 李昊 邹逍遥 赵晟宇 王梦迪 姜志豪 王天懿 省份 安徽 浙江 湖南 福建 ...
2015NOIP选手及指导老师须知(NOI-Linux)
2015NOIP选手及指导老师须知(NOI-Linux)_学科竞赛_高中教育_教育专区。NOIP2015 选手及指导老师须知(linux) 一、NOIP2015 提高组考试时间为 11 月 7 日、8 日...
NOI算法大全
NOI】算法大全(已更新) 一、数论算法 1.求两数的最大公约数 function gcd(a,b:integer):integer; begin if b=0 then gcd:=a else gcd:=gcd (b,a ...
NOI及NOIP需要知道的与自己的心得
NOI及NOIP需要知道的与自己的心得_工学_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 NOI及NOIP需要知道的与自己的心得_工学_高等教育_教育专区。1 ...
NOI算法
NOI算法_交规考试_资格考试/认证_教育专区。时间复杂度(渐近时间复杂度的严格定义,NP 问题,时间复杂度的分析方法, 主定理) 排序算法(平方排序算法的应用,Shell 排...
2016信息学竞赛 NOI 2016获奖名单
2016信息学竞赛 NOI 2016获奖名单_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档2016信息学竞赛 NOI 2016获奖名单_学科竞赛_高中教育_教育专区。...
NOI初级教程
循环结构程序设计 8、 分支与循环应用加深 9、 字符串与数组 10、枚举算法入门 11、数组应用举例 12、过程与函数的简单使用 第一章 前言 一、有关 NOI 的几个...
noip与noi的区别及作用
noip与noi的区别及作用_军事/政治_人文社科_专业资料。noip与noi的区别及作用 Noi 全称是“全国青少年信息学奥林匹克竞赛” Noip 全称是“全国青少年信息学奥林匹克...
关于NOI系列赛编程语言使用限制的规定
NOI系列NOI系列隐藏>> 关于NOI 系列赛编程语言使用限制的规定本规定适用于 NOI 系列的各项全国性竞赛。NOI 其它规章、规则中所有与 本规定不符之处, 均以本规定...
NOI 2016 获奖名单
NOI 2016 获奖名单_学科竞赛_高中教育_教育专区。NOI 2016 获奖名单 CCF NOI 2016 获奖名单金牌 62 名证书编号 CCF-NOI16-001 CCF-NOI16-002 CCF-NOI16-003...
更多相关标签:
noi官网 | noip | noi题库 | noi2016 | 傅书宁 | ioi | wjmzbmr | noise |