首页 > 代码库 > NOI2011 阿狸的打字机
NOI2011 阿狸的打字机
[Noi2011]阿狸的打字机
Time Limit: 10 Sec Memory Limit: 256 MB[Submit][Status][Discuss]
Description
阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有28个按键，分别印有26个小写英文字母和‘B‘、‘P‘两个字母。
经阿狸研究发现，这个打字机是这样工作的：
l 输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。
l 按一下印有‘B‘的按键，打字机凹槽中最后一个字母会消失。
l 按一下印有‘P‘的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。
例如，阿狸输入aPaPBbP，纸上被打印的字符如下：
a
aa
ab
我们把纸上打印出来的字符串从1开始顺序编号，一直到n。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数(x,y)（其中1≤x,y≤n），打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。
阿狸发现了这个功能以后很兴奋，他想写个程序完成同样的功能，你能帮助他么？
Input
输入的第一行包含一个字符串，按阿狸的输入顺序给出所有阿狸输入的字符。
第二行包含一个整数m，表示询问个数。
接下来m行描述所有由小键盘输入的询问。其中第i行包含两个整数x, y，表示第i个询问为(x, y)。
Output
输出m行，其中第i行包含一个整数，表示第i个询问的答案。
Sample Input
aPaPBbP
3
1 2
1 3
2 3
3
1 2
1 3
2 3
Sample Output
2
1
0
1
0
HINT
1<=N<=10^5
1<=M<=10^5
输入总长<=10^5
题目相当于问在fail树中，字符串x最后一个节点的子树内 有多少属于 字符串y的节点
暴力法：对于字符串y的每个节点，沿fail指针一直往上走，若能走到字符串x的最后一个节点，ans++
据说能得70分
AC做法：离线
1、边输入字符串边建立AC自动机，如果是‘B’，now就跳到trie中父节点
2、抽离fail树构图
3、dfs 遍历fail树，得到每个点的入栈时间和出栈时间（即子树的dfs序范围）
4、如果询问x，y，则在字符串y的最后一个字母 上 挂上 x的最后一个字母
这样遍历到y的时候，就可以处理与 某字符串 在y中出现多少次的所有询问
5、在AC自动机上再跑一遍字符串，
如果是小写字母，当前dfs序位置+1，到往下走；
‘B’，当前dfs序位置-1，到父节点
‘P’，统计答案，做法：枚举这个y的每一个x，对于这一对x、y，答案就是x的入栈时间——出栈时间有多少个1
统计一段区间1的个数，支持单点修改操作：树状数组
#include<queue>#include<cstdio>#include<cstring>#define N 100101using namespace std;int tot,trie[N][26],f[N];int fa[N];int fail_front[N],fail_nxt[N],fail_to[N],cnt;int tree_front[N],tree_nxt[N],tree_to[N];char s[N];int len,now,sum_p;int p[N];int c[N];int ans[N],in[N],out[N];queue<int>q;void add_tree(int u,int v,int k){ tree_to[++tot]=v; tree_nxt[tot]=tree_front[u]; tree_front[u]=tot; ans[tot]=k;}void fail_add(int u,int v){ fail_to[++tot]=v; fail_nxt[tot]=fail_front[u]; fail_front[u]=tot;}int lowbit(int x){ return x&(-x);}void add(int x,int w){ for(int i=x;i<=cnt;i+=lowbit(i)) c[i]+=w;}int query(int x){ int ans=0; for(int i=x;i;i-=lowbit(i)) ans+=c[i]; return ans;}void dfs(int x){ in[x]=++cnt; for(int i=fail_front[x];i;i=fail_nxt[i]) dfs(fail_to[i]); out[x]=cnt;}void getfail(){ for(int i=0;i<26;i++) trie[0][i]=1; q.push(1); int j; while(!q.empty()) { now=q.front(); q.pop(); for(int i=0;i<26;i++) { if(!trie[now][i]) { trie[now][i]=trie[f[now]][i]; continue; } q.push(trie[now][i]); j=f[now]; f[trie[now][i]]=trie[j][i]; fail_add(trie[j][i],trie[now][i]); } }}int main(){ scanf("%s",s); len=strlen(s); now=1; tot=1; for(int i=0;i<len;i++) { if(s[i]>=‘a‘) { trie[now][s[i]-‘a‘]=++tot; fa[tot]=now; now=trie[now][s[i]-‘a‘]; } else if(s[i]==‘B‘) now=fa[now]; else p[++sum_p]=now; } tot=0; getfail(); dfs(1); tot=0; int m,x,y; scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); add_tree(p[y],p[x],i); } now=1; for(int i=0;i<len;i++) { if(s[i]==‘P‘) { for(int i=tree_front[now];i;i=tree_nxt[i]) ans[i]=query(out[tree_to[i]])-query(in[tree_to[i]]-1); } else if(s[i]==‘B‘) { add(in[now],-1); now=fa[now]; } else { add(in[trie[now][s[i]-‘a‘]],1); now=trie[now][s[i]-‘a‘]; } } for(int i=1;i<=m;i++) printf("%d\n",ans[i]);}
NOI2011 阿狸的打字机
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。