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

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.


相关文章:
noi2011获奖名单
CCF NOI2011获奖名单选手名单按照成绩由高到低排列 姓名 冯迭乔 倪泽堃 范浩强 陈立杰 艾雨青 贾志鹏 梁俊邦 王钦石 顾昱洲 李超 杨一帆 王呈瑞 李旭鹏 徐捷 鲁...
NOIP选手及指导老师须知(NOI-Linux)2016
NOIP选手及指导老师须知(NOI-Linux)2016_学科竞赛_高中教育_教育专区。NOIP2016 选手及指导老师须知(linux) 一、NOIP2016 提高组考试时间为 11 月 19 日、20 日...
2016信息学竞赛 NOI 2016获奖名单_图文
2016信息学竞赛 NOI 2016获奖名单_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档2016信息学竞赛 NOI 2016获奖名单_学科竞赛_高中教育_教育专区。...
信息学竞赛中的数学知识小结
参考资料: NOI 国家集训队论文 《组合数学》 《算法导论》 《算法竞赛——入门经典 训练指南》 《新编实用算法分析与程序设计》 (本文目的主要是自己的知识梳理,...
noip与noi的区别及作用
noip与noi的区别及作用_军事/政治_人文社科_专业资料。noip与noi的区别及作用 Noi 全称是“全国青少年信息学奥林匹克竞赛” Noip 全称是“全国青少年信息学奥林匹克...
NOI 初赛理论知识复习资料
NOI 初赛理论知识复习资料计算机的诞生与发展, 计算机的诞生与发展,及其特点计算机基本常识 一、计算机的概念: 计算机是一种能迅速而高效的自动完成信息处理的电子设备...
全国信息学奥赛NOI培训教程(Pascal 2016)
全国信息学奥赛 NOI 培训教程 全国信息学奥赛 NOI 培训教程 (Pascal 2016) 目录计算机基础知识 ---6 第一章 计算机基础常识 第二章 操作系统简介 第三章 计算机...
关于NOI系列赛编程语言使用限制的规定
关于NOI系列赛编程语言使用限制的规定_学科竞赛_高中教育_教育专区。关于 NOI 系列赛编程语言使用限制的规定本规定适用于 NOI 系列的各项全国性竞赛。NOI 其它规章、...
CCF NOI2012获奖名单
CCF NOI2012 获奖名单姓名 省份 性别 学校 一等奖(34 名) 顾昱洲 范浩强 贾志鹏 王康宁 陈立杰 余翔 杨志灿 向鹏达 王悦铭 罗雨屏 乔明达 朱新瑞 胡渊鸣 刘定峰...
2015noi小学组初赛试题
2015noi小学组初赛试题_学科竞赛_小学教育_教育专区。第二十一届全国青少年信息学奥林匹克联赛初赛普及组 Pascal 语言试题 一、单项选择题(共 20 题,每题 1.5 分...
更多相关标签:
noi官网 | noip | noi题库 | noi2016 | 傅书宁 | ioi | wjmzbmr | noise |