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

NOI


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 2016 获奖名单
NOI 2016 获奖名单_学科竞赛_高中教育_教育专区。NOI 2016 获奖名单 CCF NOI 2016 获奖名单金牌 62 名证书编号 CCF-NOI16-001 CCF-NOI16-002 CCF-NOI16-003...
廖贝特作品《圣母之子》El Noi de la Mare;Miguel Llob...
廖贝特作品《圣母之子》El Noi de la Mare;Miguel Llobet;古典吉他谱_艺术_高等教育_教育专区。 文档贡献者 朱小岷3 贡献于2016-01-09 相关文档推荐 暂无相关...
noi2011获奖名单
CCF NOI2011获奖名单选手名单按照成绩由高到低排列 姓名 冯迭乔 倪泽堃 范浩强 陈立杰 艾雨青 贾志鹏 梁俊邦 王钦石 顾昱洲 李超 杨一帆 王呈瑞 李旭鹏 徐捷 鲁...
CCF NOI2012获奖名单
CCF NOI2012 获奖名单姓名 省份 性别 学校 一等奖(34 名) 顾昱洲 范浩强 贾志鹏 王康宁 陈立杰 余翔 杨志灿 向鹏达 王悦铭 罗雨屏 乔明达 朱新瑞 胡渊鸣 刘定峰...
NOIP选手及指导老师须知(NOI-Linux)2016
NOIP选手及指导老师须知(NOI-Linux)2016_学科竞赛_高中教育_教育专区。NOIP2016 选手及指导老师须知(linux) 一、NOIP2016 提高组考试时间为 11 月 19 日、20 日...
NOI初级教程
循环结构程序设计 8、 分支与循环应用加深 9、 字符串与数组 10、枚举算法入门 11、数组应用举例 12、过程与函数的简单使用 第一章 前言 一、有关 NOI 的几个...
Noi知识点总提纲
Noi知识点总提纲_从业资格考试_资格考试/认证_教育专区。0. 算法的时空分析 0.1 时间分析 0.2 空间分析 0.3 时空分配 K K K K 1. 基础算法 1.1 枚举...
NOI答案
NOI答案_工学_高等教育_教育专区。NOI’95 “同创杯”全国青少年信息学(计算机)奥林匹克竞赛 同创杯”全国青少年信息学(计算机)奥林匹克竞赛 分区联赛初赛试题(初中...
2015NOIP选手及指导老师须知(NOI-Linux)
2015NOIP选手及指导老师须知(NOI-Linux)_学科竞赛_高中教育_教育专区。NOIP2015 选手及指导老师须知(linux) 一、NOIP2015 提高组考试时间为 11 月 7 日、8 日...
noip与noi的区别及作用
noip与noi的区别及作用_军事/政治_人文社科_专业资料。noip与noi的区别及作用 Noi 全称是“全国青少年信息学奥林匹克竞赛” Noip 全称是“全国青少年信息学奥林匹克...
更多相关标签: